Module lsm_tree 

End-Key Indexing for File Extents

Fxfs indexes file extents by their end offset because it avoids expensive reverse iteration (Prev()) during lookups in the LSM tree.

If we indexed by start offset, a Seek(>= X) would return the extent starting after X, requiring a Prev() to find the extent actually containing X.

By indexing by end offset, a Seek(>= X + 1) returns the first extent ending after X. Since extents do not overlap, this is the only extent that could possibly contain X, eliminating the need for backtracking.

Re-exports

pub use merge::Query;

pub use persistent_layer::LayerHeader as PersistentLayerHeader;

pub use persistent_layer::LayerHeaderV39 as PersistentLayerHeaderV39;

pub use persistent_layer::LayerInfo as PersistentLayerInfo;

pub use persistent_layer::LayerInfoV39 as PersistentLayerInfoV39;

Modules

cache

merge

persistent_layer

skip_list_layer

types

Structs

CompactionCounters

Metrics related to LSM tree churn, layer depths, and compaction performance.

LSMTree

LSMTree manages a tree of layers to provide a key/value store. Each layer contains deltas on the preceding layer. The top layer is an in-memory mutable layer. Layers can be compacted to form a new combined layer.

LayerSet

A LayerSet provides a snapshot of the layers at a particular point in time, and allows you to get an iterator. Iterators borrow the layers so something needs to hold reference count.

LockedLayer

This is an RAII wrapper for a layer which holds a lock on the layer (via the Layer::lock method).

TreeCounters

Global counters and metrics for an LSM tree’s lifetime.

Enums

Operation

Constants

LOG2_HISTOGRAM_BUCKETS

Traits

Yielder

A yielder can be used during compactions which are low priority.

Functions

compact_with_iterator

Writes the items yielded by the iterator into the supplied object.

layers_from_handles

Type Aliases

MutationCallback