loro_kv_store/lib.rs
1//! # MemKvStore Documentation
2//!
3//! MemKvStore use SSTable as backend. The SSTable (Sorted String Table) is a persistent data structure
4//! used for storing key-value pairs in a sorted manner. This document describes the binary format of
5//! the SSTable.
6//!
7//! ## Overall Structure
8//!
9//! The SSTable consists of the following sections:
10//!
11//! ┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
12//! │ MemKVStore │
13//! │┌ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ┐│
14//! │ Magic Number │ Schema Version │ Block Chunk ... │ Block Chunk Block Meta │ Meta Offset │
15//! ││ u32 │ u8 │ bytes │ │ bytes │ bytes │ u32 ││
16//! │ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ │
17//! └─────────────────────────────────────────────────────────────────────────────────────────────────┘
18//!
19//! 1. Magic Number (4 bytes): A fixed value "LORO" to identify the file format.
20//! 2. Schema Version (1 byte): The version of the MemKVStore schema.
21//! 3. Block Chunks: A series of data blocks containing key-value pairs.
22//! 4. Block Meta: Metadata for all blocks, including block offset, the first key of the block, `is_large` flag, and last key
23//! if not large.
24//! 5. Meta Offset (4 bytes): The offset of the Block Meta section from the beginning of the file.
25//!
26//! ## Block Types
27//!
28//! There are two types of blocks: Normal Blocks and Large Value Blocks.
29//!
30//! ### Normal Block
31//!
32//! Normal blocks store multiple key-value pairs with compressed keys.
33//!
34//! ┌────────────────────────────────────────────────────────────────────────────────────────────┐
35//! │Block │
36//! │┌ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─┌ ─ ─ ─┌ ─ ─ ─ ┬ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ │
37//! │ Key Value Chunk ... │Key Value Chunk offset │ ... │ offset kv len │Block Checksum│ │
38//! ││ bytes │ │ bytes │ u16 │ │ u16 │ u16 │ u32 │
39//! │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ┘ │
40//! └────────────────────────────────────────────────────────────────────────────────────────────┘
41//!
42//! Each Key Value Chunk is encoded as follows:
43//!
44//! ┌─────────────────────────────────────────────────────┐
45//! │ Key Value Chunk │
46//! │┌ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─┬ ─ ─ ─ ┐│
47//! │ common prefix len key suffix len│key suffix│ value ││
48//! ││ u8 │ u16 │ bytes │ bytes ││
49//! │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ┘─ ─ ─ ─┘│
50//! └─────────────────────────────────────────────────────┘
51//!
52//! Because the key of the first chunk is equal to the first key of the block,
53//! the first chunk can be simplified as:
54//! ┌────────────────────┐
55//! │ Key Value Chunk │
56//! │┌ ─ ─ ─ ─ ─┬ ─ ─ ─ ┐│
57//! ││key suffix│ value ││
58//! ││ bytes │ bytes ││
59//! │ ─ ─ ─ ─ ─ ┘─ ─ ─ ─┘│
60//! └────────────────────┘
61//!
62//! Encoding:
63//! 1. Compress key-value pairs data as Key Value Chunk.
64//! 2. Write offsets for each key-value pair.
65//! 3. Write the number of key-value pairs.
66//! 4. By default, **Compress** the entire block using LZ4. If you set `compression_type` to `None`, it will not compress the block.
67//! - For now, there are two compression type: `None` and `LZ4`.
68//! 5. Calculate and append xxhash_32 checksum.
69//!
70//! Decoding:
71//! 1. Verify the xxhash_32 checksum.
72//! 2. By default, **Decompress** the block using LZ4. If you set `compression_type` to `None`, it will not decompress the block.
73//! 3. Read the number of key-value pairs.
74//! 4. Read offsets for each key-value pair.
75//! 5. Parse individual key-value chunks.
76//!
77//! ### Large Value Block
78//!
79//! Large Value Blocks store a single key-value pair with a large value.
80//!
81//! ┌──────────────────────────┐
82//! │Large Block │
83//! │┌ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ │
84//! │ value Block Checksum ││
85//! ││ bytes │ u32 │
86//! │ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘│
87//! └──────────────────────────┘
88//!
89//! Encoding:
90//! 1. Write the value bytes.
91//! 2. Calculate and append xxhash_32 checksum.
92//!
93//! Decoding:
94//! 1. Verify the xxhash_32 checksum.
95//! 2. Read the value bytes.
96//!
97//! We need not encode the length of value, because we can get the whole Block by offset in meta.
98//!
99//! ## Block Meta
100//!
101//! The Block Meta section contains metadata for all blocks in the SSTable.
102//!
103//! ┌────────────────────────────────────────────────────────────┐
104//! │ All Block Meta │
105//! │┌ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─┌ ─ ─ ─┌ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ │
106//! │ block number │ Block Meta │ ... │ Block Meta │ checksum ││
107//! ││ u32 │ bytes │ │ bytes │ u32 │
108//! │ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ┘─ ─ ─ ┘─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ┘│
109//! └────────────────────────────────────────────────────────────┘
110//!
111//! Each Block Meta entry is encoded as follows:
112//!
113//! ┌──────────────────────────────────────────────────────────────────────────────────────────┐
114//! │ Block Meta │
115//! │┌ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─┌ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ┐ │
116//! │ block offset │ first key len first key block type │ last key len last key │
117//! ││ u32 │ u16 │ bytes │ u8 │ u16(option) │bytes(option)│ │
118//! │ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │
119//! └──────────────────────────────────────────────────────────────────────────────────────────┘
120//!
121//! Encoding:
122//! 1. Write the number of blocks.
123//! 2. For each block, write its metadata (offset, first key, block type, and last key if not large).
124//! - block type: the first bit for is_large, the next 7 bits for compression_type.
125//! 3. Calculate and append xxhash_32 checksum.
126//!
127//! Decoding:
128//! 1. Read the number of blocks.
129//! 2. For each block, read its metadata.
130//! 3. Verify the xxhash_32 checksum.
131//!
132//!
133//! Note: In this crate, the empty value is regarded as deleted. **only** [MemStoreIterator] will filter empty value.
134//! Other iterators will still return empty value.
135#![allow(clippy::uninlined_format_args)]
136pub mod block;
137pub mod compress;
138pub mod iter;
139pub mod mem_store;
140pub mod sstable;
141mod utils;
142pub use iter::{KvIterator, MergeIterator};
143pub use mem_store::{MemKvStore, MemStoreIterator};