diff options
Diffstat (limited to '')
-rw-r--r-- | doc/dev/seastore.rst | 323 |
1 files changed, 323 insertions, 0 deletions
diff --git a/doc/dev/seastore.rst b/doc/dev/seastore.rst new file mode 100644 index 000000000..eb89d8219 --- /dev/null +++ b/doc/dev/seastore.rst @@ -0,0 +1,323 @@ +========== + SeaStore +========== + +Goals and Basics +================ + +* Target NVMe devices. Not primarily concerned with pmem or HDD. +* make use of SPDK for user-space driven IO +* Use Seastar futures programming model to facilitate + run-to-completion and a sharded memory/processing model +* Allow zero- (or minimal) data copying on read and write paths when + combined with a seastar-based messenger using DPDK + +Motivation and background +------------------------- + +All flash devices are internally structured in terms of segments that +can be written efficiently but must be erased in their entirety. The +NVMe device generally has limited knowledge about what data in a +segment is still "live" (hasn't been logically discarded), making the +inevitable garbage collection within the device inefficient. We can +design an on-disk layout that is friendly to GC at lower layers and +drive garbage collection at higher layers. + +In principle a fine-grained discard could communicate our intent to +the device, but in practice discard is poorly implemented in the +device and intervening software layers. + +The basic idea is that all data will be stream out sequentially to +large segments on the device. In the SSD hardware, segments are +likely to be on the order of 100's of MB to tens of GB. + +SeaStore's logical segments would ideally be perfectly aligned with +the hardware segments. In practice, it may be challenging to +determine geometry and to sufficiently hint to the device that LBAs +being written should be aligned to the underlying hardware. In the +worst case, we can structure our logical segments to correspond to +e.g. 5x the physical segment size so that we have about ~20% of our +data misaligned. + +When we reach some utilization threshold, we mix cleaning work in with +the ongoing write workload in order to evacuate live data from +previously written segments. Once they are completely free we can +discard the entire segment so that it can be erased and reclaimed by +the device. + +The key is to mix a small bit of cleaning work with every write +transaction to avoid spikes and variance in write latency. + +Data layout basics +------------------ + +One or more cores/shards will be reading and writing to the device at +once. Each shard will have its own independent data it is operating +on and stream to its own open segments. Devices that support streams +can be hinted accordingly so that data from different shards is not +mixed on the underlying media. + +Persistent Memory +----------------- + +As the initial sequential design above matures, we'll introduce +persistent memory support for metadata and caching structures. + +Design +====== + +The design is based heavily on both f2fs and btrfs. Each reactor +manages its own root. Prior to reusing a segment, we rewrite any live +blocks to an open segment. + +Because we are only writing sequentially to open segments, we must +“clean” one byte of an existing segment for every byte written at +steady state. Generally, we’ll need to reserve some portion of the +usable capacity in order to ensure that write amplification remains +acceptably low (20% for 2x? -- TODO: find prior work). As a design +choice, we want to avoid a background gc scheme as it tends to +complicate estimating operation cost and tends to introduce +non-deterministic latency behavior. Thus, we want a set of structures +that permits us to relocate blocks from existing segments inline with +ongoing client IO. + +To that end, at a high level, we’ll maintain 2 basic metadata trees. +First, we need a tree mapping ghobject_t->onode_t (onode_by_hobject). +Second, we need a way to find live blocks within a segment and a way +to decouple internal references from physical locations (lba_tree). + +Each onode contains xattrs directly as well as the top of the omap and +extent trees (optimization: we ought to be able to fit small enough +objects into the onode). + +Segment Layout +-------------- + +The backing storage is abstracted into a set of segments. Each +segment can be in one of 3 states: empty, open, closed. The byte +contents of a segment are a sequence of records. A record is prefixed +by a header (including length and checksums) and contains a sequence +of deltas and/or blocks. Each delta describes a logical mutation for +some block. Each included block is an aligned extent addressable by +<segment_id_t, segment_offset_t>. A transaction can be implemented by +constructing a record combining deltas and updated blocks and writing +it to an open segment. + +Note that segments will generally be large (something like >=256MB), +so there will not typically be very many of them. + +record: [ header | delta | delta... | block | block ... ] +segment: [ record ... ] + +See src/crimson/os/seastore/journal.h for Journal implementation +See src/crimson/os/seastore/seastore_types.h for most seastore structures. + +Each shard will keep open N segments for writes + +- HDD: N is probably 1 on one shard +- NVME/SSD: N is probably 2/shard, one for "journal" and one for + finished data records as their lifetimes are different. + +I think the exact number to keep open and how to partition writes +among them will be a tuning question -- gc/layout should be flexible. +Where practical, the goal is probably to partition blocks by expected +lifetime so that a segment either has long lived or short lived +blocks. + +The backing physical layer is exposed via a segment based interface. +See src/crimson/os/seastore/segment_manager.h + +Journal and Atomicity +--------------------- + +One open segment is designated to be the journal. A transaction is +represented by an atomically written record. A record will contain +blocks written as part of the transaction as well as deltas which +are logical mutations to existing physical extents. Transaction deltas +are always written to the journal. If the transaction is associated +with blocks written to other segments, final record with the deltas +should be written only once the other blocks are persisted. Crash +recovery is done by finding the segment containing the beginning of +the current journal, loading the root node, replaying the deltas, and +loading blocks into the cache as needed. + +See src/crimson/os/seastore/journal.h + +Block Cache +----------- + +Every block is in one of two states: + +- clean: may be in cache or not, reads may cause cache residence or + not +- dirty: the current version of the record requires overlaying deltas + from the journal. Must be fully present in the cache. + +Periodically, we need to trim the journal (else, we’d have to replay +journal deltas from the beginning of time). To do this, we need to +create a checkpoint by rewriting the root blocks and all currently +dirty blocks. Note, we can do journal checkpoints relatively +infrequently, and they needn’t block the write stream. + +Note, deltas may not be byte range modifications. Consider a btree +node structured with keys to the left and values to the right (common +trick for improving point query/key scan performance). Inserting a +key/value into that node at the min would involve moving a bunch of +bytes, which would be expensive (or verbose) to express purely as a +sequence of byte operations. As such, each delta indicates the type +as well as the location of the corresponding extent. Each block +type can therefore implement CachedExtent::apply_delta as appopriate. + +See src/os/crimson/seastore/cached_extent.h. +See src/os/crimson/seastore/cache.h. + +GC +--- + +Prior to reusing a segment, we must relocate all live blocks. Because +we only write sequentially to empty segments, for every byte we write +to currently open segments, we need to clean a byte of an existing +closed segment. As a design choice, we’d like to avoid background +work as it complicates estimating operation cost and has a tendency to +create non-deterministic latency spikes. Thus, under normal operation +each seastore reactor will be inserting enough work to clean a segment +at the same rate as incoming operations. + +In order to make this cheap for sparse segments, we need a way to +positively identify dead blocks. Thus, for every block written, an +entry will be added to the lba tree with a pointer to the previous lba +in the segment. Any transaction that moves a block or modifies the +reference set of an existing one will include deltas/blocks required +to update the lba tree to update or remove the previous block +allocation. The gc state thus simply needs to maintain an iterator +(of a sort) into the lba tree segment linked list for segment +currently being cleaned and a pointer to the next record to be +examined -- records not present in the allocation tree may still +contain roots (like allocation tree blocks) and so the record metadata +must be checked for a flag indicating root blocks. + +For each transaction, we evaluate a heuristic function of the +currently available space and currently live space in order to +determine whether we need to do cleaning work (could be simply a range +of live/used space ratios). + +TODO: there is not yet a GC implementation + +Logical Layout +============== + +Using the above block and delta semantics, we build two root level trees: +- onode tree: maps hobject_t to onode_t +- lba_tree: maps lba_t to lba_range_t + +Each of the above structures is comprised of blocks with mutations +encoded in deltas. Each node of the above trees maps onto a block. +Each block is either physically addressed (root blocks and the +lba_tree nodes) or is logically addressed (everything else). +Physically addressed blocks are located by a paddr_t: <segment_id_t, +segment_off_t> tuple and are marked as physically addressed in the +record. Logical blocks are addressed by laddr_t and require a lookup in +the lba_tree to address. + +Because the cache/transaction machinery lives below the level of the +lba tree, we can represent atomic mutations of the lba tree and other +structures by simply including both in a transaction. + +LBAManager/BtreeLBAManager +-------------------------- + +Implementations of the LBAManager interface are responsible for managing +the logical->physical mapping -- see crimson/os/seastore/lba_manager.h. + +The BtreeLBAManager implements this interface directly on top of +Journal and SegmentManager using a wandering btree approach. + +Because SegmentManager does not let us predict the location of a +committed record (a property of both SMR and Zone devices), references +to blocks created within the same transaction will necessarily be +*relative* addresses. The BtreeLBAManager maintains an invariant by +which the in-memory copy of any block will contain only absolute +addresses when !is_pending() -- on_commit and complete_load fill in +absolute addresses based on the actual block addr and on_delta_write +does so based on the just committed record. When is_pending(), if +is_initial_pending references in memory are block_relative (because +they will be written to the original block location) and +record_relative otherwise (value will be written to delta). + +TransactionManager +------------------ + +The TransactionManager is responsible for presenting a unified +interface on top of the Journal, SegmentManager, Cache, and +LBAManager. Users can allocate and mutate extents based on logical +addresses with segment cleaning handled in the background. + +See crimson/os/seastore/transaction_manager.h + +Next Steps +========== + +Journal +------- + +- Support for scanning a segment to find physically addressed blocks +- Add support for trimming the journal and releasing segments. + +Cache +----- + +- Support for rewriting dirty blocks + + - Need to add support to CachedExtent for finding/updating + dependent blocks + - Need to add support for adding dirty block writout to + try_construct_record + +LBAManager +---------- + +- Add support for pinning +- Add segment -> laddr for use in GC +- Support for locating remaining used blocks in segments + +GC +--- + +- Initial implementation +- Support in BtreeLBAManager for tracking used blocks in segments +- Heuristic for identifying segments to clean + +Other +------ + +- Add support for periodically generating a journal checkpoint. +- Onode tree +- Extent tree +- Remaining ObjectStore integration + +ObjectStore considerations +========================== + +Splits, merges, and sharding +---------------------------- + +One of the current ObjectStore requirements is to be able to split a +collection (PG) in O(1) time. Starting in mimic, we also need to be +able to merge two collections into one (i.e., exactly the reverse of a +split). + +However, the PGs that we split into would hash to different shards of +the OSD in the current sharding scheme. One can imagine replacing +that sharding scheme with a temporary mapping directing the smaller +child PG to the right shard since we generally then migrate that PG to +another OSD anyway, but this wouldn't help us in the merge case where +the constituent pieces may start out on different shards and +ultimately need to be handled in the same collection (and be operated +on via single transactions). + +This suggests that we likely need a way for data written via one shard +to "switch ownership" and later be read and managed by a different +shard. + + + |