ไธไธชๅ LevelDB ๅฏๅ็ C++20 ๅตๅ ฅๅผ้ฎๅผๅญๅจๅผๆ๏ผ้็จ LSM-Tree ๆถๆ๏ผๆฏๆ WALใSSTableใๅค็บง Compactionใๅฟซ็ ง้็ฆปๅ Bloom Filter ็ญ็นๆงใ
็ๆฌ: 1.23 | ่ฏญ่จ: C++20 | ๆถๆ: LSM-Tree
- ้กน็ฎ็ฎไป
- ๆ ธๅฟ็นๆง
- ๆถๆๆป่ง
- ๆจกๅ่ฏฆ่งฃ
- ๆฐๆฎๆ ผๅผ่ฎพ่ฎก
- ๅๅ ฅ่ทฏๅพ
- ่ฏปๅ่ทฏๅพ
- Compaction ๆบๅถ
- ๆๅปบไธ่ฟ่ก
- ้ ็ฝฎ่ฏดๆ
- ๆๆฏไบฎ็น
DeltaDB ๆฏไธไธช้ซๆง่ฝๅตๅ ฅๅผ้ฎๅผๅญๅจๅผๆ๏ผ้็จ LSM-Tree๏ผLog-Structured Merge Tree๏ผ ๆถๆ่ฎพ่ฎกใ้กน็ฎๆดไฝๅ LevelDB ๅฏๅ๏ผไฝฟ็จ C++20 ๆ ๅๅฎ็ฐ๏ผไปฃ็ ้ตๅพช Google ็ผ็ ่ง่๏ผclang-format ๆ ผๅผๅ๏ผ120 ๅๅฎฝ้ๅถ๏ผ4 ็ฉบๆ ผ็ผฉ่ฟ๏ผใ
DeltaDB ้็จไบ้่ฆๆไน ๅๅญๅจใ้ซๅๅๅๅ ฅ็ๅบๆฏ๏ผๅฆๆฅๅฟๅญๅจใๆถๅบๆฐๆฎใ็ผๅญๅ็ซฏ็ญใไฝไธบๅตๅ ฅๅผๆฐๆฎๅบ๏ผๅฎ็ดๆฅ้พๆฅๅฐๅบ็จ็จๅบไธญ๏ผๆ ้็ฌ็ซ็ๆฐๆฎๅบๆๅกๅจใ
| ็นๆง | ่ฏดๆ |
|---|---|
| LSM-Tree ๆถๆ | 7 ๅฑ็ปๆ๏ผL0-L6๏ผ๏ผMemTable โ SSTable โ ๅค็บง Compaction |
| WAL ๆไน ๅ | 32KB ๅๅฏน้ฝ็้ขๅๆฅๅฟ๏ผCRC32C ๆ ก้ช๏ผๆฏๆๅ็่ฎฐๅฝ |
| ๅฟซ็ ง้็ฆป | ๅบไบ MVCC ็ๅฟซ็ งๆบๅถ๏ผ56 ไฝๅบๅๅทไฟ่ฏไธ่ดๆง่ฏป |
| Bloom Filter | ๅๅฑๅๅธๅธ้่ฟๆปคๅจ๏ผๅคงๅน ๅๅฐๆ ๆ็ฃ็่ฏปๅ |
| ๅ็ผๅ็ผฉ | SSTable Block ๅ ้ฎๅ็ผๅ็ผฉ๏ผๆๆ้ไฝๅญๅจๅ ็จ |
| ๆฐๆฎๅ็ผฉ | ๆฏๆ Snappy ๅ Zstd ๅ็ผฉ๏ผๅ็ผฉ็ไธไฝณๆถ่ชๅจๅ้ |
| LRU ็ผๅญ | 16 ๅ็ LRU ็ผๅญ Block ๆฐๆฎ๏ผ็บฟ็จๅฎๅ จ้ซๅนถๅ |
| ๅๅญๆน้ๅๅ ฅ | WriteBatch ๆฏๆๅๅญ Put/Delete ๆไฝ๏ผWAL ๅๅนถๅ |
| ๅผๆญฅๆฅๅฟ | ๅค็บงๅผๆญฅๆฅๅฟ็ณป็ป๏ผๆฏๆๆๅคงๅฐ่ฝฎ่ฝฌๅไฟกๅทๅค็ |
| ่ทณ่กจ็ดขๅผ | ๆ ้่ฏปๅ่ทณ่กจ๏ผSkipList๏ผไฝไธบ MemTable ๅ็ซฏ |
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ DeltaDB โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโโโโโโ โ
โ โ DB API โ โ WriteBatch โ โ Snapshot โ โ
โ โ Put/Get/Del โ โ Atomic Ops โ โ MVCC Read โ โ
โ โโโโโโโโฌโโโโโโโ โโโโโโโโฌโโโโโโโโ โโโโโโโโโโฌโโโโโโโโโโโ โ
โ โ โ โ โ
โ โโโโโโโโผโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโ โ
โ โ DBImpl ๆ ธๅฟๅฎ็ฐ โ โ
โ โ โโโโโโโโโโโโ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโโโโ โ โ
โ โ โ MemTable โ โ Immutable MT โ โ Background โ โ โ
โ โ โ SkipList โ โ (readonly) โ โ Compaction โ โ โ
โ โ โโโโโโฌโโโโโโ โโโโโโโโฌโโโโโโโโ โโโโโโโโโโฌโโโโโโโโโ โ โ
โ โ โ โ โ โ โ
โ โ โโโโโโผโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโ โ โ
โ โ โ VersionSet ็ๆฌ็ฎก็ โ โ โ
โ โ โ L0 (SST) โ L1 (SST) โ ... โ L6 (SST) โ โ โ
โ โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโผโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ WAL ้ขๅๆฅๅฟ โ โ
โ โ 32KB Block | CRC32C | ๅ็่ฎฐๅฝ | fsync ไฟ้ โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ
โ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Bloom Filterโ โ LRU Cache โ โ SSTable ๆไปถ็ผๅญ โ โ
โ โ ๅๅๅธๆขๆต โ โ 16 ๅ็ โ โ RandomAccessFile โ โ
โ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโ โโโโโโโโโโโโโโโโโโโโโโ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
ๅบ็กๅทฅๅ ท้ๅ๏ผไธบๆดไธช้กน็ฎๆไพๅบๅฑๆฏๆใ
็ปไธ็้่ฏฏๅค็ๆบๅถ๏ผ้็จ็ดงๅ็็ถๆ็ผ็ ๆ ผๅผ๏ผ
- ็ถๆ็ :
OKใNotFoundใCorruptionใNotSupportedใInvalidArgumentใIOError - ็ผ็ ๆ ผๅผ: ไฝฟ็จ 4 ๅญ่ packed ็ถๆ็ + ๅฏๅ้ฟๅบฆๆถๆฏ๏ผๅ ๅญๅ ็จๆๅฐ
- ๅทฅๅๆนๆณ:
Status::OK()ใStatus::NotFound(msg)็ญ้ๆๅทฅๅๆนๆณ
ๆไพๅบๅฎๅฎฝๅบฆๅๅฏๅ้ฟๅบฆๆดๆฐ็ผ่งฃ็ ๏ผ
- ๅบๅฎๅฎฝๅบฆ:
EncodeFixed32/64ใDecodeFixed32/64๏ผๅฐ็ซฏๅบ๏ผ - Varint:
GetVarint32/64ใPutVarint32/64๏ผๅฐๅผไป ๅ 1 ๅญ่๏ผๆๆ่็ๅญๅจ็ฉบ้ด - LevelDB ๅ ผๅฎน: ็ผ่งฃ็ ๆ ผๅผไธ LevelDB ๅฎๅ จๅ ผๅฎน
ๆฝ่ฑกๆฏ่พๆฅๅฃ๏ผๆฏๆ่ชๅฎไนๆๅบ่งๅ๏ผ
BytewiseComparator: ๆๅญ่ๅบๆฏ่พ็้ป่ฎคๅฎ็ฐFindShortestSeparator: ๅฏปๆพไธคไธช้ฎไน้ด็ๆ็ญๅ้็ฌฆ๏ผ็จไบ Block ๅ็ผๅ็ผฉไผๅ๏ผFindShortSuccessor: ๅฏปๆพ้ฎ็ๆ็ญๅ็ปง๏ผ็จไบ SSTable ่ๅดๆซๆไผๅ๏ผ
Bump-Pointer ๅ้ ๅจ๏ผไธไธบๅฐๅฏน่ฑก้ซ้ขๅ้ ๅบๆฏ่ฎพ่ฎก๏ผ
- ๅๅ้ : ๆฏๆฌกๅ้ 4KB ๅ ๅญๅ๏ผๅๅฐ็ณป็ป่ฐ็จ
- ๅฏน้ฝๅ้ : ๆฏๆๅฏน้ฝๅ ๅญๅ้ ๏ผๆปก่ถณ SIMD ็ญๅบๆฏ้ๆฑ
- ้็จๅบๆฏ: MemTable ไธญ็้ฎๅผๅฏนๅ้ ๏ผ้ฟๅ ้ข็น malloc/free
LSM-Tree MemTable ็ๆ ธๅฟๆฐๆฎ็ปๆ๏ผ
- ๆ ้่ฏปๅ: ๅๅญๆ้ๅๅธ๏ผ่ฏปๅ็ซฏๅฎๅ จๆ ้
- ๅๅค้จๅๆญฅ: ๅๅ ฅ็ฑๅค้จ้ไฟๆค๏ผ่ฏปๅนถๅๆ ็ซไบ
- ๆๅคง้ซๅบฆ 12: ๆฆ็ๆงๅฑ็บง็ปๆ๏ผๆ็ดขๆถ้ดๅคๆๅบฆ O(log N)
- ไธๅฏๅ่็น: ่็นไธๆฆๅๅปบไพฟไธๅฏไฟฎๆน๏ผไฟ่ฏ่ฏปๅ็บฟ็จๅฎๅ จ
ๅฆไธ็ๆฌ็่ทณ่กจๅฎ็ฐ๏ผไฝฟ็จ shared_mutex ่ฏปๅ้๏ผ
- ๆฏๆๆๅ ฅ/ๆ็ดข/ๅ ้คๆไฝ
- ๅบไบๆฆ็็ๅฑ็บง็ๆ
- ้ๅ้่ฆๅนถๅๅ ้ค็ๅบๆฏ
DeltaDB ็ๅ ้จ้ฎๆ ผๅผ่ฎพ่ฎกๆฏๆดไธช MVCC ๆบๅถ็ๅบ็ณ๏ผ
โโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโ
โ user_key โ 56-bit sequence โ 8-bit type โ
โ (ๅ้ฟ็จๆท้ฎ) โ (MVCC ๅบๅๅท) โ (ๅผ็ฑปๅ) โ
โโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโ
- InternalKeyComparator: ๅ ๆ user_key ๅๅบ๏ผๅๆ sequence ้ๅบ๏ผไฟ่ฏ็ธๅ key ็ๆๆฐ็ๆฌๆๅจๆๅ๏ผ
- InternalFilterPolicy: ๅ ่ฃ ็จๆท Bloom Filter๏ผ้้ ๅ ้จ้ฎๆ ผๅผ
- LookupKey: ๆฅๆพ้ฎๅฐ่ฃ ๏ผๆนไพฟ MemTable ๅฟซ้ๅฎไฝ
ๅบไบ TinyXML ็ XML ้ ็ฝฎ่งฃๆ๏ผ
- ้ ็ฝฎ้กน: WAL ่ทฏๅพใCompaction ่งฆๅ้ๅผใ็ผๅฒๅบๅคงๅฐใBlock ๅคงๅฐใๅ็ผฉ่ฎพ็ฝฎใ็ผๅญๅคงๅฐใBloom Filter ็ญ
- ReadOptions/WriteOptions: ่ฏปๅๆไฝ็่ฟ่กๆถ้้กน
- Limiter: ๅๅญ่ตๆบๆงๅถๅจ๏ผ็จไบ้ๅถๅนถๅๆไปถๆ่ฟฐ็ฌฆ็ญ
ๅค็บงๅผๆญฅๆฅๅฟ็ณป็ป๏ผ
- ๆฅๅฟ็บงๅซ: DEBUG / INFO / WARN / ERROR
- ๅผๆญฅๅๅ ฅ: ็ฌ็ซ็บฟ็จ็ผๅฒๅๅ ฅ๏ผๅๅฐๅฏนไธป่ทฏๅพ็ๅฝฑๅ
- ๆไปถ่ฝฎ่ฝฌ: ๆๆไปถๅคงๅฐ่ชๅจ่ฝฎ่ฝฌ๏ผ้ป่ฎค 5MB๏ผ
- ไฟกๅทๅค็: ๆณจๅ coredump ไฟกๅทๅค็ๅจ
- ็บฟ็จๅฎๅ จ: ๅค็บฟ็จๅฎๅ จ็็ผๅฒๅๅ ฅ
็ฉบ้ด้ซๆ็ๆฆ็ๅๆฐๆฎ็ปๆ๏ผ
- ๅๅๅธๆๅทง: ไฝฟ็จไธคไธชๅๅธๅฝๆฐๆจกๆๅคไธชๅๅธ๏ผๅๅฐ่ฎก็ฎๅผ้
- ๅฏ้
็ฝฎไฝๆฐ:
NewBloomFilterPolicy(bits_per_key)ๆงๅถ่ฏฏๅค็ - ๅบ็จๅบๆฏ: SSTable ๅฟซ้ๅคๆญ้ฎๆฏๅฆไธๅญๅจ๏ผ้ฟๅ ๆ ๆ็ฃ็ I/O
- ๆไปถๆไฝ:
CreateDirใRenameFileใRemoveFileใWriteStringToFileSync - ๅ็ผฉๅฐ่ฃ : Snappy / Zstd ๅ็ผฉ/่งฃๅ
- ้ๆบๆฐ:
Random๏ผ็บฟๆงๅไฝ PRNG๏ผ - ๅๅธ: Murmur ้ฃๆ ผๅๅธๅฝๆฐ
- ๆถ้ด:
NowMicrosใSleepForMicroseconds - ๅๆญฅๅ่ฏญ:
CondVarๆกไปถๅ้ๅฐ่ฃ
็บฟ็จๅฎๅ จ็ๅไพๅ ่ฃ ๅจ๏ผ้ฟๅ ้ๆๅฏน่ฑก้ๆฏ้กบๅบ้ฎ้ขใ
ๆๅฏๅจ็ๅๅทฅไฝ็บฟ็จๆฑ ๏ผ้ฆๆฌก Schedule() ๆถๅฏๅจ็บฟ็จ๏ผ็จไบๅๅฐ Compaction ไปปๅกใ
Write-Ahead Log ๆฏไฟ่ฏๆฐๆฎๆไน ๅ็ๆ ธๅฟๆบๅถใ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ 32KB Block โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Record Header (7 bytes) โ โ
โ โ โโโโโโโโโโโโฌโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโ โ โ
โ โ โ 4B CRC32Cโ 2B Length โ 1B Type โ โ โ
โ โ โ (ๆ ก้ชๅ) โ (ๆฐๆฎ้ฟๅบฆ) โ (Full/First/Middle/Last)โ โ โ
โ โ โโโโโโโโโโโโดโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโ โ โ
โ โ Record Data โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
- ๅๅคงๅฐ: 32KB ๅบๅฎๅ๏ผไพฟไบ็ฎก็ๅๅฏน้ฝ
- ่ฎฐๅฝ็ฑปๅ:
Full๏ผๅฎๆด่ฎฐๅฝ๏ผใFirst/Middle/Last๏ผ่ทจๅๅ็่ฎฐๅฝ๏ผ - CRC32C ๆ ก้ช: ๆฏๆก่ฎฐๅฝๅ ๅซ CRC32C ๆ ก้ชๅ๏ผๆฃๆตๆฐๆฎๆๅ
- ่ชๅจ่พน็ๅค็: ๅฝ่ฎฐๅฝ่ทจ่ถ 32KB ๅ่พน็ๆถ๏ผ่ชๅจๅ็ไธบ First/Middle/Last ็ฑปๅ
- CRC ้ข่ฎก็ฎ่กจ: ้ข่ฎก็ฎ CRC32C ็ฑปๅ่กจ๏ผๅ ้ๆ ก้ชๅ่ฎก็ฎ
- ่ฟฝๅ ๅๅ ฅ: ้กบๅบ่ฟฝๅ ๏ผๆๅคงๅๅๅ ฅๅๅ
- ๅ็้็ป: ่ชๅจ้็ป First/Middle/Last ๅ็่ฎฐๅฝ
- CRC ๆ ก้ช: ่ฏปๅๆถ้ช่ฏ CRC๏ผๆฃๆตๆๅๆฐๆฎ
- Reporter ๅ่ฐ: ๅ็ฐๆๅๆถ่ฐ็จๅ่ฐๅฝๆฐ้็ฅไธๅฑ
- ๅ็งปๅๆญฅๅค็: ๅค็ๆชๅฎๆ็ fsync ไบง็็่ๆฐๆฎ
- 64KB ็ผๅฒ: ๅ ็ฝฎ 64KB ๅ็ผๅฒ๏ผๅๅฐ็ณป็ป่ฐ็จ
- Append/Flush/Sync/Close: ๅฎๆด็ๅๅ ฅ็ๅฝๅจๆ็ฎก็
- MANIFEST ็นๆฎๅค็: MANIFEST ๆไปถๅๅ ฅๅๅๆญฅ็ถ็ฎๅฝ๏ผ็กฎไฟๅ ๆฐๆฎๆไน ๅ
- ๅทฅๅๆนๆณ:
NewWritableFile๏ผ่ฆ็ๅ๏ผ/NewAppendableFile๏ผ่ฟฝๅ ๅ๏ผ
- ๅช่ฏป้กบๅบ่ฎฟ้ฎ: ็จไบ WAL ๅๆพๅ MANIFEST ่ฏปๅ
- Read/Skip ๆไฝ: ่ฏปๅๅ่ทณ่ฟๆๅฎๅญ่ๆฐ
- ReadFileToString ่พ ๅฉ: ๅฐๆดไธชๆไปถ่ฏปๅ ฅๅญ็ฌฆไธฒ
SSTable๏ผSorted String Table๏ผๆฏๆไน ๅๆฐๆฎ็ๆ ธๅฟๆไปถๆ ผๅผใ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ SST File Layout โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโค
โ [Data Block 0] โ
โ [Data Block 1] โ
โ ... โ
โ [Data Block N] โ
โ [Meta Block (Filter Block)] โ
โ [Meta Index Block] โ
โ [Index Block] โ
โ [Footer (48 bytes fixed)] โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ FilterBH | MetaIndexBH | IndexBH | Padding | Magicโ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ Magic Number: 0xdb4775248b80fb57 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
- BlockHandle: varint ็ผ็ ็ๅ็งป้ + ๅคงๅฐ๏ผ็ดงๅๅญๅจ
- Footer: ๅบๅฎ 48 ๅญ่๏ผๅ
ๅซ้ญๆฐ
0xdb4775248b80fb57็จไบๆไปถๅฎๆดๆงๆ ก้ช - ReadBlock: ่ฏปๅๆถ่ชๅจ CRC ๆ ก้ช + Snappy/Zstd ่งฃๅ
SSTable ็ๅบๆฌๅญๅจๅๅ ๏ผ
- ๅ็ผๅ็ผฉ: Block ๅ ็ธ้ป้ฎๅ ฑไบซๅ็ผ๏ผไป ๅญๅจๅทฎๅผๅ็ผ
- Restart Point: ๆฏ
block_restart_interval๏ผ้ป่ฎค 16๏ผๆก่ฎฐๅฝ่ฎพ็ฝฎไธไธชๅฎๆด้ฎ้ๅฏ็น - ๅๅ่ฟญไปฃ: ๆฏๆ forward/backward ้ๅ
- ไบๅๆ็ดข: ๅบไบ Restart Point ๅฏน้ฎ่ฟ่กไบๅๆ็ดข๏ผๅ ้็นๆฅ
- ๅ็ผๅ็ผฉไผๅ: ่ชๅจๆฃๆต็ธ้ป้ฎ็ๅ ฑๅๅ็ผ๏ผๅๅฐๅไฝๅญๅจ
- ้ๅฏ็น็ฎก็: ๅฎๆๆๅ ฅๅฎๆด้ฎไฝไธบ้ๅฏ็น๏ผๆฏๆๅฟซ้ไบๅๆฅๆพ
- ไธคๅฑ่ฟญไปฃๅจ: Index Block โ Data Block๏ผ้ๆ้ๅๆๆๆฐๆฎ
- Bloom Filter ไผๅ: ็นๆฅๆถๅ ๆฃๆฅ Bloom Filter๏ผๅฟซ้่ทณ่ฟไธๅญๅจ็้ฎ
- InternalGet: ้ๅฏนๅ ้จๆฅ่ฏข็ไผๅ่ทฏๅพ๏ผ็ดๆฅๅฎไฝๅฐ็ฎๆ Block
ๅฎๆด็ SST ๆไปถๆๅปบๆต็จ๏ผ
- ๆๅปบ Data Block๏ผๅซๅ็ผๅ็ผฉ๏ผ
- ๆๅปบ Filter Block๏ผๆฏ 2KB ๆฐๆฎๆฎต็ๆไธไธช Bloom Filter๏ผ
- ๆๅปบ Meta Index Block
- ๆๅปบ Index Block
- ๅๅ ฅ Footer
- ๅ็ผฉ็ญ็ฅ: ๆฏๆ Snappy ๅ Zstd๏ผๅ็ผฉ็ไฝไบ 12.5% ๆถ่ชๅจๅ้ไธบๆชๅ็ผฉ
- Zstd ๅฏ้ ็ฝฎ็บงๅซ: ้่ฟ config.xml ่ฎพ็ฝฎๅ็ผฉ็บงๅซ
- 16 ๅ็่ฎพ่ฎก: ๅๅฐ้็ซไบ๏ผๆฏไธชๅ็็ฌ็ซไบๆฅ้
- ๅๅธ่กจ + ๅๅ้พ่กจ: O(1) ๆฅๆพ + LRU ๆทๆฑฐ
- ็บฟ็จๅฎๅ จ: ๅ็็บง็ป็ฒๅบฆ้
- ๆไปถๅทๆ ๅฐ: ๅฐ file_number ๆ ๅฐๅฐ Table ๅฏน่ฑก
- ่ฟญไปฃๅจๆธ ็ๅ่ฐ: ่ฟญไปฃๅจ้ๆฏๆถ่ชๅจ้ๆพๅ ณ่่ตๆบ
- ๅบๅฑ LRU ็ผๅญ: ๅค็จ้็จ LRU ็ผๅญๅฎ็ฐ
- ๅๆฎต Bloom Filter: ๆฏ 2KB ๆฐๆฎๆฎต็ๆ็ฌ็ซ็ Bloom Filter
- ๆ ผๅผ:
[Filter 0][Filter 1]...[ๅ็งปๆฐ็ป][4B ๅ็งป + 1B log_base] - ้ซๆๆๅปบ/่ฏปๅ: FilterBlockBuilder/FilterBlockReader ๅฎๆด็ๅฝๅจๆ็ฎก็
- K ่ทฏๅฝๅนถ: ๅค่ทฏๆๅบ่ฟญไปฃๅจ็ๅฝๅนถๆๅบ
- ๅๅ้ๅ: ๆฏๆๆนๅๅๆขๆถ็่ชๅจ้ๅฎไฝ
- ๅบ็จๅบๆฏ: ๅคๅฑ็บงใๅคๆไปถ็ๆๅบๆฐๆฎๅๅนถ
- Index โ Data ๅทฅๅ: ้่ฟ Index Block ๅฎไฝ Data Block๏ผๆ้ๅ ่ฝฝ
- ้ๆ้ๅ: ไธๅฑๆ ้ๅ ณๅฟๅบๅฑ Block ่พน็
- pread ็ณป็ป่ฐ็จ: ็บฟ็จๅฎๅ จ็้ๆบ่ฏปๅ๏ผๆ ้็ปดๆคๆไปถๅ็งป
- FD Limiter ้ๆ: ๆงๅถๆๅผ็ๆไปถๆ่ฟฐ็ฌฆๆฐ้
ๆไพ็ฎๆด็็จๆทๆฅๅฃ๏ผ
DB::Open() // ๆๅผ/ๅๅปบๆฐๆฎๅบ
Put(key, value) // ๅๅ
ฅ้ฎๅผๅฏน
Get(key, &value) // ่ฏปๅๅผ
Delete(key) // ๅ ้ค้ฎ
Write(options, batch) // ๅๅญๆน้ๅๅ
ฅ
NewIterator() // ๅๅปบ่ฟญไปฃๅจ
GetSnapshot() // ่ทๅๅฟซ็
ง
ReleaseSnapshot() // ้ๆพๅฟซ็
ง
GetProperty(name) // ่ทๅๅฑๆง
CompactRange(begin, end) // ๆๅจๅ็ผฉ
DestroyDB() // ้ๆฏๆฐๆฎๅบ
RepairDB() // ไฟฎๅคๆฐๆฎๅบDeltaDB ็ๆ ธๅฟๅผๆ๏ผๅ่ฐๆๆๅญ็ณป็ป๏ผ
- ๅๅ ฅ้ๅ: ๆน้ๅ็ปๅๅ ฅ๏ผWrite Grouping๏ผ๏ผๅคไธช WriteBatch ๅๅนถไธบไธๆฌก WAL ๅๅ ฅ
- WAL ๅๅ ฅ: ไฟ่ฏๆไน ๅ๏ผfsync ็กฎไฟๆฐๆฎ่ฝ็
- MemTable ็ฎก็: ๆดป่ท MemTable ๅ Immutable MemTable ็ๅๆข
- ๅๅฐ Compaction: ้่ฟๅ็บฟ็จๆฑ ่ฐๅบฆ๏ผ่งฆๅๆกไปถๅ็ญ็ฅ็ฑ VersionSet ๅณๅฎ
- ๅฟซ็ ง็ฎก็: ็ปดๆคๅฟซ็ ง้พ่กจ๏ผไฟ่ฏไธ่ดๆง่ฏป
- VersionSet ไบคไบ: ็ๆฌ้พ็ๆดๆฐๅๆไน ๅ
- ๆไปถๆธ ็: ๅผๆญฅๆธ ็ไธๅ่ขซไปปไฝ็ๆฌๅผ็จ็ๆง SST ๆไปถ
- ่ทณ่กจๅ็ซฏ: ไฝฟ็จ SkipList ไฝไธบๅบๅฑๆฐๆฎ็ปๆ
- ๅ ้จ้ฎๅญๅจ: ๅญๅจๅธฆๅบๅๅทๅ็ฑปๅไฟกๆฏ็ๅ ้จ้ฎ
- Varint ้ฟๅบฆๅ็ผ: ้ฎๅผๅฏน้็จ varint ้ฟๅบฆๅ็ผๆ ผๅผ
- ๅผ็จ่ฎกๆฐ: ๅฎๅ จ็็ๅฝๅจๆ็ฎก็
- ๆไฝ:
Add()ใGet()ใNewIterator()
- ๅๅญๆไฝ: ไธๆน Put/Delete ๆไฝ่ฆไนๅ จ้จๆๅ๏ผ่ฆไนๅ จ้จๅคฑ่ดฅ
- ๅบๅๅๆ ผๅผ: 12 ๅญ่ๅคด๏ผ8B ๅบๅๅท + 4B ่ฎกๆฐ๏ผ+ varint ๅ็ผๅญ็ฌฆไธฒ
- WriteBatchInternal: ๆไพๅบๅฑๆไฝๆฅๅฃ
- MemTableInserter: ๅฐ Batch ๅๆพ่ณ MemTable
- WAL ๅๅนถๅ: ๅคไธชๅนถๅ Write ๅๅนถไธบไธๆฌก WAL ๅๅ ฅ๏ผๆๅคงๆๅๅๅ
- ๅๅๅพช็ฏ้พ่กจ:
SnapshotList็ฎก็ๆๆๆดป่ทๅฟซ็ ง - ๅบๅๅท: ๆฏไธชๅฟซ็ งๆๆๅๅปบๆถ็ๅบๅๅท๏ผ็จไบ MVCC ๅฏ่งๆงๅคๆญ
- ไธ่ดๆง่ฏป: ๅฟซ็ ง็กฎไฟ่ฏปๅๆไฝๅช็ๅฐๅฟซ็ งๅๅปบไนๅ็ๆฐๆฎ
- ๅ ้จ่ฟญไปฃๅจๅ ่ฃ : ๅฐ่ฃ ๅ ้จ่ฟญไปฃๅจ๏ผๆไพ็จๆท่งๅพ
- ๅฟซ็ ง่ฟๆปค: ๆ นๆฎๅฟซ็ งๅบๅๅท่ฟๆปคไธๅฏ่ง็้ฎ็ๆฌ
- ๅ ้คๆ ่ฎฐๅค็: ่ชๅจ่ทณ่ฟๅทฒๅ ้ค็้ฎ
- ๆนๅ่ฟฝ่ธช: ่ฎฐๅฝ้ๅๆนๅ๏ผๆฏๆๆญฃๅ/ๅๅๅๆข
- ่ฏปๅ้ๆ ท: ่ฎฐๅฝ่ฏปๅๆ ทๆฌ๏ผ็จไบ่ชๅจ่งฆๅ Compaction
ๆ่ฟฐ็ๆฌไน้ด็ๅๅ๏ผ
- ่ฎฐๅฝๅ ๅฎน: ๆฏ่พๅจๅ็งฐใWAL ็ผๅทใไธไธไธชๆไปถ็ผๅทใๆๅๅบๅๅทใCompaction ๆ้ใๆฐๅข/ๅ ้ค็ SST ๆไปถ
- Tag ็ผ็ : ๅบไบ Tag ็ไบ่ฟๅถ็ผ็ ๏ผ็ดงๅ้ซๆ
็ๆฌ็ฎก็็ๆ ธๅฟ็ณป็ป๏ผ
- Version: ๆไธชๆถ้ด็น็ SST ๆไปถๅฟซ็ ง๏ผ่ทจ L0-L6 ๆๆๅฑ๏ผ
- VersionSet: ็ๆฌ้พ๏ผ้่ฟ MANIFEST ๆไปถๆไน ๅ
- Compaction ้ๆฉ: ๅบไบๆไปถๅคงๅฐ๏ผSize-based๏ผๆ Seek ๆฌกๆฐ๏ผSeek-based๏ผ
- Builder ้ซๆๅบ็จ:
Builder็ปๆ้ซๆๅฐๅฐ็ผ่พๅบ็จๅฐๅฝๅ็ๆฌ - MANIFEST ๅๆพ: ๅฏๅจๆถ้ๆพ MANIFEST ๆขๅค็ๆฌ็ถๆ
- Compaction ่ฏๅ: ่ฎก็ฎๆฏไธชๅฑ็ Compaction ๅๆฐ๏ผๅณๅฎไผๅ ็บง
็ปไธ็ๆไปถๅฝๅ่ง่๏ผ
| ๆไปถ็ฑปๅ | ๅฝๅๆ ผๅผ | ่ฏดๆ |
|---|---|---|
| WAL | {dbname}/NNNNNN.wal |
้ขๅๆฅๅฟ |
| SST | {dbname}/NNNNNN.sst |
ๆๅบๅญ็ฌฆไธฒ่กจ |
| Temp | {dbname}/NNNNNN.dbtmp |
ไธดๆถๆไปถ |
| MANIFEST | MANIFEST-NNNNNN |
็ๆฌๅ ๆฐๆฎ |
| CURRENT | CURRENT |
ๆๅๅฝๅ MANIFEST |
| LOCK | LOCK |
ๆฐๆฎๅบ้ๆไปถ |
| LOG | LOG |
่ฟ่กๆฅๅฟ |
- ParseFileName: ่งฃๆๆไปถๅๆฃๆต็ฑปๅ
- SetCurrentFile: ๅๅญๆดๆฐ CURRENT ๆไปถ
โโโโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโ
โ user_key โ sequence (56bit) โ type (8bit) โ
โ (ๅ้ฟ๏ผ็จๆทๅฎไน) โ (MVCC ็ๆฌๅท) โ (ValueType) โ
โโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโ
- ValueType:
kTypeValue(0x0) ่กจ็คบๆๆๅผ๏ผkTypeDeletion(0x1) ่กจ็คบๅ ้คๆ ่ฎฐ - ๆฏ่พ่งๅ: user_key ๅๅบ โ sequence ้ๅบ๏ผ็กฎไฟ็ธๅ key ็ๆๆฐ็ๆฌไผๅ ่ขซๆซๆๅฐ๏ผ
โโโโโโโโโโโโโโโโโโโโโฌโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Header (12 bytes)โ Record Body โ
โ โโโโโโโโโโฌโโโโโโโโโ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โ โ Seq(8B)โCnt(4B)โโโ [tag][varint_len][data]... ้ๅค โ โ
โ โโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ โ
โโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
็จๆท Put/Delete
โ
โผ
โโโโโโโโโโโ
โWriteBatchโ โ ๅคไธช Write ๅๅนถไธบไธไธช Batch
โโโโโโฌโโโโโโ
โ
โผ
โโโโโโโโโโโโ
โ WAL ๅๅ
ฅ โ โ ้กบๅบ่ฟฝๅ ๅฐ WAL๏ผfsync ไฟ้ๆไน
ๅ
โโโโโโฌโโโโโโ
โ
โผ
โโโโโโโโโโโโโ
โ MemTable โ โ ๅๅ
ฅๆดป่ท MemTable๏ผ่ทณ่กจ็ปๆ๏ผ
โโโโโโโฌโโโโโโ
โ
โ MemTable ๆปก (write_buffer_size)
โผ
โโโโโโโโโโโโโโโโ
โ Immutable MT โ โ ๅๆขไธบๅช่ฏป๏ผ่งฆๅๅๅฐ Compaction
โโโโโโโโฌโโโโโโโโ
โ
โผ
โโโโโโโโโโโโโโโโ
โ Flush to L0 โ โ ็ๆ L0 ๅฑ SSTable ๆไปถ
โโโโโโโโโโโโโโโโ
็จๆท Get(key)
โ
โผ
โโโโโโโโโโโโโโโ ๆชๆพๅฐ๏ผ โโโโโโโโโโโโโโโโ
โ MemTable โ โโโโโโโโโโโถ โ Immutable MT โ
โโโโโโโโโโโโโโโ โโโโโโโโฌโโโโโโโโ
โ
ๆชๆพๅฐ๏ผโ
โผ
โโโโโโโโโโโโโโโโโโ
โ L0 SST files โ โ ๅฏ่ฝๆ้ๅ ๏ผ้ไธชๆฃๆฅ
โโโโโโโโโฌโโโโโโโโโ
โ
ๆชๆพๅฐ๏ผโ
โผ
โโโโโโโโโโโโโโโโโโ
โ L1 โ L6 SST โ โ Bloom Filter ๅฟซ้่ทณ่ฟ
โ (Bloom Filter) โ ไธๅญๅจ็ๆไปถ
โโโโโโโโโโโโโโโโโโ
Bloom Filter ไผๅ: ๅจ่ฏปๅ SSTable ไนๅ๏ผๅ ๆฃๆฅๅฏนๅบๆไปถ็ Bloom Filterใๅฆๆ Bloom Filter ่ฟๅ negative๏ผๅ็ดๆฅ่ทณ่ฟ่ฏฅๆไปถ๏ผ้ฟๅ ๆ ๆ็ฃ็ I/Oใ
MemTable (ๆปก)
โ flush
โผ
โโโโโโโโโโโ
โ L0 โ โ ๆไปถๅฏ่ฝๆ้ฎ้ๅ
โ (4 ๆไปถ) โ โ L0_compaction_trigger = 4 ่งฆๅ
โโโโโโฌโโโโโ
โ compaction
โผ
โโโโโโโโโโโ
โ L1 โ โ ๆไปถๆ ้ๅ ๏ผๆๅบๆๅ
โ โ
โโโโโโฌโโโโโ
โ
โผ
โโโโโโโโโโโ
โ L2 โ
โโโโโโฌโโโโโ
โ
...
โ
โผ
โโโโโโโโโโโ
โ L6 โ โ ๆ็ปๅฑ๏ผๅ
ๅซๆๅคๆฐๆฎ
โโโโโโโโโโโ
่งฆๅ็ญ็ฅ:
- Size-based: ๆๅฑๆไปถๆฐ/ๅคงๅฐ่ถ ่ฟ้ๅผๆถ่งฆๅ Compaction
- Seek-based: ๆๆไปถ Seek ๆฌกๆฐ่ฟๅค๏ผ่ฏดๆ Bloom Filter ่ฏฏๅค็้ซ๏ผ๏ผ่งฆๅ Compaction ๆธ ็
Compaction ่ฟ็จ:
- ้ๆฉๅพ Compaction ็่พๅ ฅๆไปถ
- ไธไธไธๅฑๆ้ๅ ็ๆไปถๅๅนถ
- ็ๆๆฐ็ SSTable ๆไปถ
- ๆดๆฐ VersionSet๏ผ่ฎฐๅฝๆฐๅข/ๅ ้ค็ๆไปถ
- ๆไน ๅๅฐ MANIFEST
- ๅผๆญฅๆธ ็ๆงๆไปถ
| ๅบ | ็จ้ |
|---|---|
| crc32c | CRC32C ๆ ก้ชๅ่ฎก็ฎ |
| ZLIB | ๆฐๆฎๅ็ผฉ |
| GTest | ๅๅ ๆต่ฏ |
| TinyXML | XML ้ ็ฝฎ่งฃๆ |
| Snappy | ๅฟซ้ๅ็ผฉ๏ผๅฏ้๏ผ |
| Zstd | ้ซๅ็ผฉๆฏๅ็ผฉ๏ผๅฏ้๏ผ |
# ไธ้ฎๆๅปบ๏ผๆธ
็ + CMake + ็ผ่ฏ๏ผ
./to_build.sh
# ๆๅจๆๅปบ
mkdir -p build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j$(nproc)ๆๅปบไบง็ฉ๏ผ
- ๅฏๆง่กๆไปถ:
build/bin/deltadb - ๅบๆไปถ:
build/lib/ไธ็้ๆๅบ
./build/bin/deltadb # ้ป่ฎคๆฐๆฎๅบ่ทฏๅพ ./output/delta
./build/bin/deltadb --db /path # ๆๅฎๆฐๆฎๅบ่ทฏๅพ| ๅฝไปค | ่ฏดๆ |
|---|---|
put <key> <value> |
ๅๅ ฅ้ฎๅผๅฏน |
get <key> |
ๆฅ่ฏขๅผ |
del <key> |
ๅ ้ค้ฎ |
scan [begin] [end] |
่ๅดๆซๆ |
compact [begin] [end] |
ๆๅจ Compaction |
stats |
ๆฅ็็ป่ฎกไฟกๆฏ |
dbdir |
ๆฅ็ๆฐๆฎๅบ็ฎๅฝ |
help |
ๅธฎๅฉ |
quit |
้ๅบ |
้
็ฝฎๆไปถไฝไบ conf/config.xml๏ผไธป่ฆ้
็ฝฎ้กน๏ผ
<log>
<path>./output/log</path> <!-- ๆฅๅฟ็ฎๅฝ -->
<prefix>delta</prefix> <!-- ๆฅๅฟๆไปถๅๅ็ผ -->
<max_file_size>5242880</max_file_size> <!-- ๅๆไปถๆๅคง 5MB -->
<level>DEBUG</level> <!-- ๆฅๅฟ็บงๅซ -->
<sync_interval>500</sync_interval> <!-- ๅๆญฅ้ด้ 500ms -->
</log><wal>
<path>./output/wal</path> <!-- WAL ็ฎๅฝ -->
<base_name>WAL</base_name> <!-- WAL ๆไปถๅๅ็ผ -->
<max_file_size>10485760</max_file_size> <!-- ๅๆไปถๆๅคง 10MB -->
</wal><db>
<num_levels>7</num_levels> <!-- LSM ๅฑๆฐ -->
<l0_compaction_trigger>4</l0_compaction_trigger> <!-- L0 ่งฆๅ Compaction ๆไปถๆฐ -->
<l0_slowdown_writes_trigger>8</l0_slowdown_writes_trigger> <!-- L0 ๅๅ
ฅๅ้้ๅผ -->
<l0_stop_writes_trigger>12</l0_stop_writes_trigger> <!-- L0 ๅๅ
ฅๅๆญข้ๅผ -->
<write_buffer_size>4194304</write_buffer_size> <!-- MemTable ๅคงๅฐ 4MB -->
<block_size>4096</block_size> <!-- SST Block ๅคงๅฐ 4KB -->
<block_restart_interval>16</block_restart_interval> <!-- Block ้ๅฏ็น้ด้ -->
<max_sst_size>2097152</max_sst_size> <!-- ๆๅคง SST ๆไปถๅคงๅฐ 2MB -->
<zstd_compression_level>1</zstd_compression_level> <!-- Zstd ๅ็ผฉ็บงๅซ -->
<fd_limiter>50</fd_limiter> <!-- ๆไปถๆ่ฟฐ็ฌฆ้ๅถ -->
</db>ๅคไธชๅนถๅๅๅ ฅ่ฏทๆฑ่ขซๅๅนถไธบไธไธช WriteBatch๏ผไธๆฌกๆงๅๅ ฅ WAL ๅ MemTableใ่ฟๆๅคงๅๅฐไบ fsync ็ๆฌกๆฐ๏ผๅฐ้ๆบๅ่ฝฌไธบ้กบๅบ่ฟฝๅ ๏ผๆพ่ๆๅไบๅๅ ฅๅๅ้ใ
MemTable ็ SkipList ้็จๅๅญๆ้ๅๅธๆบๅถ๏ผ่ฏปๅ็ซฏๅฎๅ จๆ ้ใๅๆไฝ็ฑๅค้จไบๆฅ้ไฟๆค๏ผ่ฏปๅไบไธ้ปๅก๏ผๅจ่ฏปๅคๅๅฐ็ๅบๆฏไธๆง่ฝไผๅผใ
Index Block ๆๅ Data Block๏ผ้่ฟ TwoLevelIterator ้ๆ้ๅใไธๅฑๆ ้ๅ ณๅฟ Block ่พน็๏ผๆ้ๅ ่ฝฝ Data Block ๅฐ็ผๅญ๏ผๆๆๅฉ็จๅ ๅญใ
ๆฏ 2KB ๆฐๆฎๆฎต็ๆ็ฌ็ซ็ Bloom Filter๏ผ็นๆฅๆถๅ ๆฃๆฅ Bloom Filterใๅฆๆ็กฎๅฎ้ฎไธๅญๅจ๏ผ็ดๆฅ่ทณ่ฟ่ฏฅ SSTable ๆไปถ๏ผ้ฟๅ ๆ ๆ็็ฃ็ I/Oใๅจ้ซ่ฏฏๅคๅฎนๅฟๅบๆฏไธ๏ผๅฆ 1%๏ผ๏ผๅฏไปฅ่ฟๆปคๆ 99% ็ๆ ๆ่ฏปๅใ
SSTable Block ๅ ็ธ้ป้ฎๅ ฑไบซๅ็ผ๏ผไป ๅญๅจๅทฎๅผๅ็ผใๆฏ 16 ๆก่ฎฐๅฝ่ฎพ็ฝฎไธไธช Restart Point ไฟ่ฏไบๅๆ็ดข็ๆญฃ็กฎๆงใๅฏนไบๆๅบๅๅ ฅ็ๅบๆฏ๏ผๅฆๆถ้ดๅบๅ๏ผ๏ผๅ็ผๅ็ผฉ็ๆ้ซใ
16 ไธช็ฌ็ซ็็ผๅญๅ็๏ผๆฏไธชๅ็ๆ่ชๅทฑ็ไบๆฅ้ใๅๅธ่กจๅ LRU ้พ่กจใ็ธๆฏๅ จๅฑ้็็ผๅญ๏ผๅ็่ฎพ่ฎกๅคงๅน ๅๅฐไบ้็ซไบ๏ผๆๅไบๅนถๅ่ฏปๆง่ฝใ
56 ไฝๅบๅๅท + ๅๅๅพช็ฏ้พ่กจ็ฎก็ๅฟซ็ งใๆฏไธชๅฟซ็ งๆๆๅๅปบๆถ็ๅบๅๅท๏ผ่ฏปๅๆถๅช็ๅฐๅบๅๅทๅฐไบ็ญไบๅฟซ็ งๅบๅๅท็้ฎ็ๆฌใ่ฟไฟ่ฏไบๅจ Compaction ๅๅนถๅ่ฏปๅๅบๆฏไธ็ไธ่ดๆง่ฏปใ
SSTable ๆๅปบๆถๅฐ่ฏ Snappy ๆ Zstd ๅ็ผฉ๏ผๅฆๆๅ็ผฉๅๅคงๅฐ reduction < 12.5%๏ผๅๅ้ๅฐๆชๅ็ผฉๆ ผๅผใ่ฟ้ฟๅ ไบๅจไธๅฏๅ็ผฉๆฐๆฎไธ็ CPU ๆตช่ดนใ
ๅฝ่ฎฐๅฝ่ทจ่ถ 32KB ๅ่พน็ๆถ๏ผ่ชๅจๅ็ไธบ First/Middle/Last ็ฑปๅใ่ฏปๅ็ซฏ่ชๅจ้็ป๏ผ็กฎไฟๆฐๆฎๅฎๆดๆงๅๆถ้ฟๅ ไบๅๆตช่ดนใ
MANIFEST ๆไปถๅๅ ฅๅๅๆญฅ็ถ็ฎๅฝ๏ผfsync + fdatasync๏ผ๏ผ็กฎไฟๅ ๆฐๆฎๅๆดๆไน ๅๅฐๅญๅจ่ฎพๅคใๅณไฝฟๅ็ๅดฉๆบ๏ผไน่ฝ้่ฟ MANIFEST ๅๆพๆขๅค็ๆฌ็ถๆใ
็ฌ็ซ็ๆฅๅฟ็บฟ็จ็ผๅฒๅๅ ฅ่ฏทๆฑ๏ผๆๆไปถๅคงๅฐ่ชๅจ่ฝฎ่ฝฌใไธป่ทฏๅพ็ๆฅๅฟๅๅ ฅไธไผ้ปๅกๆ ธๅฟ่ฏปๅ้ป่พ๏ผๆฅๅฟ็บงๅซไป DEBUG ๅฐ ERROR ็ตๆดปๅฏๆงใ
้่ฟ Limiter ๅๅญ่ฎกๆฐๅจๆงๅถๆๅผ็ๆไปถๆ่ฟฐ็ฌฆๆฐ้ใๅฝ SSTable ๆไปถๆฐ้ๅพๅคๆถ๏ผไธไผ่ถ
ๅบ็ณป็ป้ๅถ๏ผไฟ้ไบๆฐๆฎๅบ็็จณๅฎๆงใ
ๆฌ้กน็ฎไธบๅญฆไน /็ ็ฉถ็จ้็ๅตๅ ฅๅผ LSM-Tree ๅญๅจๅผๆๅฎ็ฐใ