Programmable storage

19 June 2018

​

Noah Watkins

Thesis defense

Three common application I/O stack architectures

2

App

​

POSIX file storage

POSIX*

Middleware**

* POSIX-ish, **HDF5, PLFS, MPI-IO

1

Redundancy and specialization costs

3

Paxos is like the simplest thing ever…

System stabilization is expen$$ive

“It takes 10 years before a new storage system is trusted.”

-- Gary Grider (LANL)�The man, the myth, the legend

4

Eyeballs act as a proxy for reliability!

Share code-hardened sub-systems!

Outline and contributions

5

Data interfaces

Programmable storage design paradigm

2

Outline and contributions

6

Data interfaces

Programmable storage design paradigm

Transactional data

Structured data

Durability

Outline and contributions

7

Data interfaces

Programmable storage design paradigm

New way to build storage interfaces!

• Don’t re-implement an entire system
• Recombining existing sub-systems

Transactional data

Structured data

Durability

Outline and contributions

8

Transactional data

Structured data

Durability

Data interfaces

Programmable storage design paradigm

Widely applicable, but challenges!

• Design space and unpredictable costs
• Problems → research opportunities

2

Outline and contributions

9

Data interfaces

Programmable storage design paradigm

Will this�ever work?

Tying it all together

• Declaratively specifying interfaces
• Apply DB opt. to composable subsystems

2

Programmability: avoid duplication and specialization

10

App

​

POSIX file storage

POSIX*

Middleware**

* POSIX-ish, **HDF5, PLFS, MPI-IO

1

Programmable storage

11

n+k

App

App

App

App

Programmable storage system

(share common sub-systems)

File

Object

Block

App

​

POSIX file storage

POSIX*

Middleware**

* POSIX-ish, **HDF5, PLFS, MPI-IO

1

App

App

App

A

B

C

Programmable storage

​

Storage system that facilitates the reuse and extension of existing storage abstractions provided by the underlying software stack, to enable to the creation of new services via composition.

Programmable storage compared to…

Software-defined storage (SDS)

• Buzzword for provisioning
• Original SDS work
• [Thereska, ‘13], IOFlow
• [Stefanovici, ‘16], sRoute
• Recombining services
• [Dorier, ‘17], CoSS/Mochi
• [Gracia-Tinedo, ‘17], Crystal

Active storage

• Use remote hardware computation resources
• Original work with disks
• [Riedel, ‘98] Active storage
• [Keeton, ‘98], Intelligent disks
• Object-based storage
• [Du, ‘05], Intelligent OSDs
• [Xie, ‘11], T10 integration
• Recent work with SSDs
• [Seshadri, ‘14], Willow
• [Jo, ‘16], YourSQL
• [Do, ‘13], SmartSSDs

​

12

Motivation, use cases, and lessons learned

Similar motivation, HPC specific, entire systems from scratch

Programmable storage exposes internal subsystems

13

file, object, block

New interfaces through composition and customization

Storage system

Programmability survey in Ceph (data interfaces)

14

Programmability in Ceph (reusable data interfaces)

15

Method Examples

• Locking and concurrency control
• Logging
• Metadata management
• Remote compute

Developers willing to break layers and use non-standard APIs

Outline and contributions

16

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Driving example: CORFU distributed shared-log

17

Balakrishnan et al., “CORFU: A Shared Log Design for Flash Clusters”, NSDI, `12

log striping

How can we implement CORFU with programmability?

Driving example: CORFU distributed shared-log

• Implementation concerns
• Partitioning, distribution
• Metadata management
• I/O interfaces

18

• How to evaluate strategies?
• Don’t want 9 implementations!
• Metrics (throughput, latency)
• Reduce the search space

ℕ:𝕄

Design space: ZLog design on Ceph

19

Are these combinations worth exploring?

Append throughput for 128 byte log entries

20

Design space: ZLog design on Ceph

21

Append performance for a variety of entry sizes

22

Append size (bytes)

Design space: ZLog design on Ceph

23

What about extended attributes (xattr)

• Extended attributes are fast
• Cached in-memory
• Efficient [small] writes

24

• Created a design for small metadata
• Compressed bitmaps!
• Expected benefit over heavy-weight interfaces

• The results are inconclusive
• Ceph is gaslighting us!
• And we are relative experts

What am I missing?

Are my other decisions incorrect?

Interest in ZLog from MegaCorp^®

25

Acceptance of programmable storage paradigm

• Salesforce was using Apache BookKeeper
• Distributed logging solution
• Separate everything
• Hardware storage cluster
• Software ecosystem
• External services (Zookeeper)
• Maintenance and expertise

26

“... we are considering large scale deployments of Ceph ...“

“... Zlog seems more attractive as its on the same technology stack.”

Many use cases; tail latency is universally important

27

Tail latency in Ceph isn’t good, but interfaces matter!

28

Design space: ZLog design on Ceph

29

Navigating the design space is an obstacle

• The CORFU storage abstraction is conceptually simple
• Far more complex abstractions!
• Searching and pruning the design space are essential
• Need to build actual prototypes
• Implementation issues always emerge
• What about reads, scans, etc… ?
• How do we know we aren’t missing something?
• Deep understanding of Ceph, and still have doubts?

30

Outline and contributions

31

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

32

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

How to grow a database: scale-up approach

33

• This isn’t a talk about database architectures
• Many, many, approaches to scalability
• See (MPP, Hybrid-MPP, etc…)

Skyhook: exploit storage resources

34

​

Database Node

CPU

RAM

​

Database storage

Network /

Bus

Q

Skyhook project

• Elastic database system
• Lead: Jeff LeFevre
• Active CROSS incubator

Single-node architecture

Programmable storage

Skyhook: aligns data with storage interfaces

35

Ceph OSD

RAM

CPU

Storage+Index

Ceph OSD

RAM

CPU

Storage+Index

Ceph OSD

RAM

CPU

Storage+Index

Ceph OSD

RAM

CPU

Storage+Index

Ceph OSD

RAM

CPU

Storage+Index

Ceph OSD

RAM

CPU

Storage+Index

Ceph Cluster

Table

Table

Shards

partitioning

Programmability used in a completely different way than to build a log abstraction

Skyhook experiments with programmable storage

• Real-world dataset
• TPC lineitem table
• 1 billion rows
• 140 GB
• Storage in Ceph objects
• Table divided into ~10,000 14 MB objects
• Optimize for workload (e.g. 4MB)
• Each object contains a dedicated index
• Index stored in omap (RocksDB)
• Storage hardware (thanks CloudLab!)
• Modern 20 core Intel
• 128 GB DRAM, 500 GB SSD
• 10 GB/s Ethernet
• 1 -- 16 Ceph nodes

36

​

Database Node

CPU

RAM

​

Programmable storage

​

​

Network

(Database-specific data interface)

Q

Q

Q

Q

Benchmark queries evaluated

Qa: Range query with 10% selectivity:

​

SELECT * FROM lineitem WHERE extendedprice > 71000.0

​

Qb: Point query (unique row) issued with and without index:

​

SELECT extendedprice

FROM lineitem� WHERE orderkey=5 AND linenumber=3

​

Qc: Regex query with 10% selectivity (CPU intensive):

​

SELECT * FROM lineitem WHERE comment iLIKE '%uriously%'

37

+ data loading

Range query performance (10% selectivity)

38

Bulk-load and index generation performance

39

Point query performance (find unique row)

40

Outline and contributions

41

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

42

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

What is durability?

• Overloaded terminology
• You get out what you put into it
• Preserve historically important info
• Always access the very best data now

• We assume storage systems expose durable interfaces
• Unless explicitly otherwise

• Broad class of subsystems
• Redundancy (replication, EC)
• Recovery / failover / availability
• Consistency semantics
• Properties and behaviors of media

43

Driving example: CORFU distributed shared-log

44

Balakrishnan et al., “CORFU: A Shared Log Design for Flash Clusters”, NSDI, `12

log striping

Sequencer (P)

Sequencer (B)

1, 2, 3, 4, 5, ….

read

clients

append

Ceph data interfaces

• They are all durable / persistent!
• Test it out: map to DRAM

Persistent media is only part of the bottleneck

45

DRAM

Software is a bottleneck

46

Queuing and scheduling

network

Persistent storage media

Transactional context

client req

This I/O path is taken by all requests… regardless of need!

error conditions

replication

tiering

error conditions

{ client operations }

concurrency control

clone

indexing

error

conditions

CoW

The CORFU sequencer is a high availability service

47

Balakrishnan et al., “CORFU: A Shared Log Design for Flash Clusters”, NSDI, `12

log striping

Sequencer (P)

Sequencer (B)

1, 2, 3, 4, 5, ….

read

clients

append

Ceph already provides availability... recovery!

• But the state is volatile…
• What is recovered?

Data availability applied to sequencer interface

48

Seq @ OSD.0

Configurable

timeouts

Outline and contributions

49

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

50

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Metadata management

• Metadata is everywhere in storage
• It gives the data we store meaning
• Plays a supportive role in everything
• Naming resources
• Feature implementation

51

• Many types of metadata
• POSIX file abstraction
• Cluster-level metadata
• Sub-systems (caching, scrubbing, …)

Metadata management

• Metadata is everywhere in storage
• It gives the data we store meaning
• Plays a supportive role in everything
• Naming resources
• Feature implementation
• Many types of metadata
• POSIX file abstraction
• Cluster-level metadata
• Sub-systems (caching, scrubbing, …)
• New interfaces with programmability
• A programmable interface needs a name
• Instances of interfaces track metadata
• Need similar sets of services

52

App

App

App

Storage system

File

Object

A

B

C

mount/

• file1
• file2

POSIX file resource

Config DB

POSIX namespace management of all interfaces

53

/users/

• jane/
• jerry/
• john/

mount/

/science/

• fake/
• data/
• graphs/

Programmable metadata management (file types)

54

/users/

• jane/
• jerry/
• john/

mount/

/science/

• fake/
• data/
• graphs/

/log-instances/

• log1
• log2
• log3

/log-instances/

• log4/
• stream0
• stream1

inode

inode

Metadata cluster

concurrency control

capabilities

security

cache management

POSIX/File

[Karpovich, ‘94]

Programmable metadata management (file types)

55

mount/

/log-instances/

• log1
• log2
• log3

inode

Metadata cluster

concurrency control

capabilities

security

cache management

ZLog Basic

inode

[Karpovich, ‘94]

Programmable metadata management (coherency)

56

mount/

/log-instances/

• log1
• log2
• log3

inode

Metadata cluster

concurrency control

capabilities

security

cache management

ZLog Basic

inode

ZLog metadata

• Cost model

​

​

Naming / discovery

• Sequencer state (integer)

pos = seq++

The capability-based sequencer is round-robin

57

Compared to centralized architecture…

can benefit bursty workloads

best effort

delay

quota

Findings trade-offs with capability-based sequencer

​

58

Throughput per Policy

Latency per Policy

Outline and contributions

59

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

60

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Programmability looks like a one-time cost

• Navigating the design space
• Difficult and time-consuming

61

• Tricks of the trade
• Trimming down the search space

• But if you put in the hard work…
• …you’ll eventually arrive at a design that works

ZLog performance toss up on 2014 version of Ceph

• Four ZLog implementations
• Ceph release (2014)
• Graph takeaways
• Clear performance losers
• Similar top performers (few %)
• Our claim…
• Select simpler implementation
• Added complexity for no benefit
• What is complexity?
• Lines of code
• Conceptual

62

Performance Comparison of 4 Designs

Appends / Sec

Ceph 2014

Clear ZLog implementation choice in 2016

• Same implementations
• Same hardware / benchmark
• Newer version of Ceph
• Clear performance winner

Takeaway:

• A reasonable choice in 2014 is bad choice in 2016
• Worst part: happy with one not knowing about the other

63

Performance Comparison of 4 Designs

Appends / Sec

Ceph 2014

Ceph 2016

Appends / Sec

That is the state of programmable storage

• Large design space
• High cost of searching this space
• Costs are difficult to predict
• Simple upgrade and change the calculus!
• Much harder than what we have presented
• > 500 tunables/settings in Ceph
• Not counting dependencies
• Runs on a wide-variety of hardware
• No hope of migrating to a new system
• There are no standards!

​

64

Ceph programmability 2010 to 2016

65

Ceph programmability usage since 2016

66

61%

Programmability is critical to the Ceph ecosystem

• Ceph is currently undergoing a major redesign
• Address performance issues
• Next-generation hardware (e.g. persistent memories).

When asked about the fate of object classes given the redesign opportunity:

​

67

Popping up in different places

• OpenStack Swift Storlets
• Swift is a cloud-scale object storage system
• Storlets allow developers to push code into system
• Cloud functions / lambda
• Similar conceptual ideas to programmability
• Priming new generation of developers
• Coming to a storage system near you
• What can we do to deal with the issues?

68

Swift

Storlets

Microsoft

Google

Amazon

Outline and contributions

69

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

70

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Declarative storage

• Design space was a late discovery
• And operational pitfalls (e.g. simple upgrades!)
• Immediately understood it to be a major concern

71

• Automate parts of this process
• Searching the design space
• Generating implementations

• Express interfaces declaratively
• Eliminate need for storage system expertise
• High-level abstractions across services / systems

In-vivo storage system development

• Storage systems are high-availability; they’re “always-on”
• Once systems are made to be more adaptable…
• ...they’ll need to adapt while running

• How will developers interact with the system?
• Interfaces are developed like software
• And inextricably linked to data

• How will the system evolve?
• Conflicting goals and user needs
• Maintain common requirements like SLA
• Observation
• Well-defined points of change
• Hardware and software changes
• Offline optimization techniques

72

Outline and contributions

73

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Outline and contributions

74

Transactional data

Compute resources

Structured data

Graph processing

Durability

Data interfaces

Metadata management

Programmable storage design paradigm

2

Development process

1

3

Will this

ever work?

Recap and conclusions

• Storage systems from scratch
• Expensive and unreliable
• Reproduce common sub-systems
• Programmability surfaces sub-systems for reuse
• Applicable across a wide range of application needs
• Transactional, computation resources
• Structured and graph data models
• Challenges with programmability → new research goals
• Large design space
• Portability challenges
• Introducing the next stage: declarative storage
• Applying techniques from database world to programmable components
• This is where a large portion of real-value comes from
• This is a large research area, and we’ve come very close to connecting it all :)

75

Future work

76

Storage system architecture

• Internal organizations that increase programmability (e.g. request handling)
• Expanding the search of system components
• Queueing and batching

Developer assistance

• Automatically generating cost models
• Automated performance sweeps
• Identify equivalence classes
• Survey patterns across large set of examples found in real-world use cases

Declarative storage

• End-to-end demonstration using CORFU specification and cost models
• Non-volatile memories
• “The CPU is the bottleneck”
• Generating “less” code
• Formalizing the interaction between components
• Allow modeling and verification tools to be applied

Publications

77

Thank you everyone

Committee: Carlos Maltzahn, Scott Brandt, Peter Alvaro, and other amazing collaborators: Neoklis Polyzotis, Jeff LeFevre, Shel Finkelstein, Ike Nassi, Kleoni Ioannidou

Michael Sevilla, Ivo Jimenez, Joe Buck, Dimitris Skourtis, Adam Crume

Pat McCormick, Galen Shipman, John Bent, Gary Grider, Adam Manzanares, Kleoni Ioannidou, Jay Lofstead, Sage Weil, Anna Povzner, Greg Farnum

78