文章目录《现代 Key-Value 数据库原理从 BTree 到 LSM Tree》第五篇现代数据库横向对比第一章 现代数据库整体分类第二章 现代数据库横向总表第三章 LMDB3.1 LMDB的数据结构3.2 LMDB为什么读取快3.3 LMDB的核心优势读取优秀事务简单数据结构稳定非常适合AI数据集3.4 LMDB的限制第四章 LevelDB4.1 LevelDB为什么选择LSM4.2 LevelDB核心组件4.3 LevelDB的缺点第五章 RocksDB5.1 为什么需要RocksDB5.2 Column Family5.3 RocksDB适合什么第六章 BadgerDB6.1 为什么Key和Value分开6.2 Badger适合什么第七章 BoltDB / bbolt7.1 bbolt结构7.2 bbolt与LMDB第八章 SQLite8.1 SQLite底层是什么8.2 SQLite最大的特点8.3 SQLite为什么这么流行8.4 SQLite vs LMDB第九章 Berkeley DB9.1 Berkeley DB适合什么第十章 Redis10.1 Redis不是单一数据结构10.2 Redis为什么快10.3 Redis为什么还能持久化第十一章 WiredTiger11.1 WiredTiger为什么重要11.2 MongoDB为什么需要独立存储引擎第十二章 Pebble12.1 Pebble为什么出现第十三章 TiKV13.1 TiKV整体架构13.2 为什么TiKV使用RocksDB思想第十四章 FoundationDB14.1 FoundationDB最大的特点第十五章 BTree vs LSM TreeBTreeLSM第十六章 写入性能BTreeLSM第十七章 读取性能第十八章 Read Amplification第十九章 Write Amplification第二十章 Space Amplification第二十一章 三种放大之间的关系第二十二章 mmap vs Buffer PoolmmapBuffer Pool22.1 两者区别第二十三章 SSD时代的数据库23.1 SSD改变的是成本而不是原理第二十四章 HDD、SSD、NVMe对比24.1 HDD24.2 NVMe第二十五章 AI数据集应该选什么方案一LMDB方案二LevelDB方案三RocksDB第二十六章 日志系统应该选什么第二十七章 缓存系统应该选什么第二十八章 嵌入式设备应该选什么第二十九章 Go项目应该选什么第三十章 分布式数据库应该选什么第三十一章 Storage Engine与Database的区别第三十二章 数据库的分层第三十三章 为什么没有“最好的数据库”LMDBRocksDBRedisSQLite第三十四章 从访问模式选择数据库场景一读多写少场景二写多读多场景三超低延迟缓存场景四需要SQL场景五分布式KV第三十五章 AI/视觉行业数据库选择第三十六章 一个工业视觉系统应该如何组合第三十七章 BTree与LSM Tree的最终理解BTreeLSM Tree第三十八章 从LMDB到LevelDB再到RocksDB第三十九章 现代数据库真正的核心技术第四十章 数据库学习路线第四十一章 如果要阅读源码应该先看什么第四十二章 最终总结《现代 Key-Value 数据库原理从 BTree 到 LSM Tree》第五篇现代数据库横向对比前面四篇分别从数据库存储基础、BTree、LMDB、LevelDB出发逐渐建立了一个完整的认知体系。现在可以把这些知识放在一起。现代数据库看起来种类非常多LMDB LevelDB RocksDB SQLite Redis BadgerDB bbolt WiredTiger TiKV FoundationDB Pebble但如果从底层存储结构来看它们并没有想象中那么复杂。大量数据库最终都可以归结到几种核心思想BTree LSM Tree Hash SkipList Log Structured Storage Memory Data Structure Distributed KV因此学习数据库真正重要的不是记住几十个数据库的名字而是理解为什么这个数据库选择这种数据结构以及这种选择解决了什么问题。第一章 现代数据库整体分类先建立一个全局视图。Database | ----------------------------------- | | | v v v BTree LSM Tree Memory | | | -------- -------- -------- | | | | | | LMDB SQLite LevelDB RocksDB Redis ... | | | | bbolt WiredTiger | Pebble | TiKV再进一步BTree | -- LMDB -- SQLite -- bbolt -- WiredTiger LSM | -- LevelDB -- RocksDB -- Pebble -- BadgerDB -- TiKV Memory | -- Redis但是需要注意现实数据库往往不是纯粹的一种结构。例如BadgerDB LSM Tree Value LogRedisHash SkipList Rax List Set Sorted SetFoundationDB则更加复杂Distributed Transaction Storage Engine所以“数据库属于什么类型”通常应该理解为它的核心存储架构而不是说整个数据库只包含一种数据结构。第二章 现代数据库横向总表先给出本篇最重要的一张表。数据库核心结构核心特点典型场景LMDBBTreemmap、Copy-On-Write、MVCC、读性能优秀AI数据集、嵌入式LevelDBLSM TreeMemTable、SSTable、Compaction嵌入式KV、日志RocksDBLSM Tree高性能、丰富Compaction和缓存优化高写入、高并发BadgerDBLSM Value LogGo生态、Key/Value分离Go服务WiredTigerBTree等高性能通用存储引擎MongoDBSQLiteBTree单文件、完整SQL桌面、移动、嵌入式Berkeley DBBTree / Hash等经典嵌入式数据库嵌入式系统bboltBTreeGo、单文件、简单Go嵌入式应用Redis内存数据结构极低延迟、丰富数据结构缓存、消息、实时数据TiKVRocksDB等LSM分布式KV、Raft云原生数据库PebbleLSM TreeCockroachDB生态分布式数据库FoundationDB分布式KV强事务、可组合分布式数据库第三章 LMDBLMDBLightning Memory-Mapped Database它是OpenLDAP项目中的核心嵌入式数据库之一。核心设计BTree mmap Copy-On-Write MVCC3.1 LMDB的数据结构可以简单表示Root | ---------- | | Branch Branch | | ---- ---- | | | | Leaf Leaf Leaf Leaf数据库文件data.mdb直接通过mmap()映射到进程地址空间。于是Disk | v Virtual Memory | v Page | v CPU3.2 LMDB为什么读取快传统数据库Disk ↓ Read ↓ Buffer Pool ↓ Copy ↓ ApplicationLMDBDisk ↓ mmap ↓ Virtual Address ↓ Application因此减少了大量系统调用 用户态/内核态切换 数据复制3.3 LMDB的核心优势读取优秀尤其适合大量读取 少量写入事务简单采用MVCC多个Reader可以并发。数据结构稳定BTree查询 O(logN)非常适合AI数据集例如image_001 → JPEG image_002 → JPEG image_003 → JPEG最终dataset.mdb3.4 LMDB的限制最大的特点其实也是最大的限制一个Writer因此如果业务是大量并发写入LMDB通常不是第一选择。第四章 LevelDBLevelDB 是Google设计的嵌入式KV数据库。核心LSM Tree完整写路径Put | ---- WAL | ---- MemTable | v Immutable | v SSTable | v Compaction4.1 LevelDB为什么选择LSM因为它希望解决BTree 大量随机写的问题。LSMRandom Write ↓ Memory ↓ Sequential Write所以写入吞吐通常非常优秀。4.2 LevelDB核心组件MemTable SkipList WAL Immutable MemTable SSTable Bloom Filter Compaction Manifest Snapshot Iterator这些概念实际上已经成为现代LSM数据库的基础。4.3 LevelDB的缺点LSM不是没有代价。主要问题Compaction会导致Write Amplification Read Amplification Space Amplification例如写1GB ↓ 后台Compaction ↓ 可能产生多个GB的数据读写所以LSM把随机写问题转化成了后台整理问题。第五章 RocksDBRocksDB 是基于LevelDB思想发展起来的高性能LSM存储引擎。可以理解成LevelDB | ---------------- | | 性能优化 功能扩展 | | --------------- | RocksDB5.1 为什么需要RocksDBFacebook面对SSD NVMe 多核CPU 高并发 海量数据LevelDB的设计比较简单。RocksDB进一步强化Compaction Cache Concurrency SSD Write Buffer Compression Column Family Bloom Filter5.2 Column FamilyRocksDB一个非常重要的设计Column Family例如Database ├── metadata ├── image ├── feature └── result不同数据可以独立配置 独立Compaction 独立Cache策略这对于大型系统很重要。5.3 RocksDB适合什么例如高写入日志 时序数据 缓存 状态存储 分布式数据库底层存储如果系统写入量非常大RocksDB通常比LMDB更值得考虑。第六章 BadgerDBBadgerDB 是Go生态中的高性能KV数据库。核心思想LSM Tree Value Log6.1 为什么Key和Value分开传统SSTable Key Value Key Value Key Value如果Value非常大10KB 100KB 1MBCompaction就会产生大量数据移动。BadgerLSM Key Key Key Key而ValueValue Log Value Value Value形成Key ↓ Value Pointer ↓ Value Log例如Key: image_001 Value Pointer: offset 100000 size 200KB ↓ Value Log 100000 | v JPEG Data这样可以减少大Value参与LSM Compaction的成本。6.2 Badger适合什么特别适合Go服务 大Value 高写入 嵌入式KV例如Go ↓ Badger ↓ RocksDB风格LSM第七章 BoltDB / bboltGo生态还有一个非常经典的数据库bbolt。它的前身是BoltDB。核心BTree和LMDB思路比较接近。7.1 bbolt结构Database | v BTree | ---------- | | Bucket BucketBucket可以理解成Key Namespace例如users images config7.2 bbolt与LMDB两者都属于BTree但是LMDB重点mmap Copy-On-Write MVCC而bbolt是Go生态中更加简单直接的嵌入式BTree方案。第八章 SQLiteSQLite 是完全不同于LevelDB的数据库。它不仅是KV而是关系型数据库支持SQL Table Index Transaction Join Query8.1 SQLite底层是什么SQLite主要使用B-Tree进行表和索引的组织。例如Database ------------------- | Table | | | | B-Tree | ------------------- ------------------- | Index | | | | B-Tree | -------------------8.2 SQLite最大的特点一个数据库database.db可以直接复制。例如app.db里面用户 配置 历史记录 索引全部存在一个文件。8.3 SQLite为什么这么流行因为它解决的是不需要部署数据库服务器但又需要完整关系型数据库能力。例如Android iOS Windows桌面 嵌入式设备 浏览器 单机软件8.4 SQLite vs LMDB如果数据是Key → Value而且极致简单LMDB非常合适。如果需要SELECT*FROMimageWHEREcamera_id10ANDtimestamp...那么SQLite明显更加合适。第九章 Berkeley DBBerkeley DB 是非常经典的嵌入式数据库。历史非常悠久。它支持多种数据访问方式BTree Hash Queue Recno因此它不是单纯的BTree数据库而是一个多种嵌入式存储结构集合。9.1 Berkeley DB适合什么历史上大量用于嵌入式系统 网络服务 配置数据 缓存 本地数据库其重要意义在于它代表了早期Embedded Database的经典设计路线。第十章 RedisRedis 和LMDB、LevelDB有很大区别。Redis的核心思想数据主要驻留在内存中。10.1 Redis不是单一数据结构Redis内部使用多种数据结构。例如String Hash List Set Sorted Set Stream底层还涉及Hash Table SkipList Rax ZipList / Listpack10.2 Redis为什么快典型路径Client ↓ Redis Server ↓ Memory ↓ Data Structure而不是Client ↓ Disk ↓ BTree ↓ Data因此访问延迟非常低。10.3 Redis为什么还能持久化Redis提供RDB AOF例如Memory | ---- RDB | ---- AOF所以Redis并不是纯内存 数据一定不持久化而是以内存为核心数据层同时提供持久化机制。第十一章 WiredTigerWiredTiger 是MongoDB长期使用的重要存储引擎。MongoDBDocument Database底层MongoDB | WiredTiger | Storage Engine11.1 WiredTiger为什么重要它代表了一种通用高性能存储引擎设计。涉及B-Tree LSM相关能力 Compression Cache Transactions MVCCWiredTiger并不能简单概括为“就是一个BTree数据库”实际实现包含多个存储和事务机制。11.2 MongoDB为什么需要独立存储引擎因为MongoDB上层解决Document Query Aggregation Replication而存储引擎解决Page Index Transaction Disk Cache Concurrency于是MongoDB | v WiredTiger | v Disk这也是数据库分层架构的重要体现。第十二章 PebblePebble 是CockroachDB生态中的LSM存储引擎。它与LevelDB、RocksDB属于同一个思想体系LSM | -- MemTable -- WAL -- SSTable -- Compaction12.1 Pebble为什么出现CockroachDB最初大量借鉴RocksDB。随着自身需求不断发展分布式 事务 Raft Cloud Native需要更加贴合自身系统的存储引擎。于是发展出Pebble第十三章 TiKVTiKV 是分布式KV数据库。它与前面最大的区别LMDB 单机LevelDB 单机RocksDB 单机存储引擎而TiKV 分布式KV13.1 TiKV整体架构可以理解为Client | v TiKV | -------------------- | | Raft RocksDB | | v v Replication Storage多个TiKV节点Node1 Node2 Node3通过Raft保证副本一致性。13.2 为什么TiKV使用RocksDB思想因为RocksDB已经很好地解决单机高性能存储TiKV可以在其基础上增加分布式 Raft 事务 Region Replication形成Distributed Database Local Storage Engine第十四章 FoundationDBFoundationDB 的设计思路又有所不同。它强调Distributed Transactions Ordered Key-Value可以把它理解成Application ↓ FoundationDB API ↓ Distributed Transaction Layer ↓ Storage Servers ↓ Storage Engine14.1 FoundationDB最大的特点不是提供很多SQL语法而是提供一个强一致的、有序Key-Value基础层。在它之上可以构建SQL Document DB Metadata Store Queue Index这是一种Database as a Foundation的思想。第十五章 BTree vs LSM Tree现在回到整个系列最核心的问题。BTreeRoot | -------- | | Branch Branch | | Leaf Leaf数据始终维护在Tree中。LSMMemTable ↓ L0 ↓ L1 ↓ L2 ↓ L3数据先进入Memory再不断Merge第十六章 写入性能BTree典型Write ↓ Locate Page ↓ Modify Page ↓ Write Page可能出现Random IOLSMWrite ↓ MemTable ↓ Sequential WAL ↓ Flush因此大量写入通常更加有优势。第十七章 读取性能BTreeRoot ↓ Branch ↓ Leaf通常只需要O(logN)并且Key Range天然适合范围扫描。LSMMemTable Immutable L0 L1 L2 L3可能需要多个层级 多个SST所以LSM需要Bloom Filter、Block Cache、Index等机制来降低读取成本。第十八章 Read Amplification读放大为了读取一个用户数据系统实际读取了多少额外数据。例如用户需要 1KB数据库可能实际读取 4KB Block这就是Block级读放大。LSM还可能MemTable L0 L1 L2多个层级检查。第十九章 Write Amplification写放大用户写入 1GB数据库实际WAL SSTable Compaction Rewrite最终磁盘可能写3GB 5GB 10GB这就是Write AmplificationLSM数据库尤其需要关注这一指标。第二十章 Space Amplification空间放大用户有效数据 100GB磁盘实际150GB甚至200GB原因可能包括旧版本 Tombstone Compaction尚未完成 冗余Block Index Bloom Filter第二十一章 三种放大之间的关系这是LSM数据库非常重要的概念。Database Performance | ------------------------ | | | v v v Read Ampl. Write Ampl. Space Ampl. | | | 读取 写入 空间 | | | SSTable Compaction Old Data三者往往存在Trade-off。例如Compaction更积极可能Read Amplification ↓ Space Amplification ↓ Write Amplification ↑因此现代LSM数据库实际上一直在寻找读、写、空间三者之间的最佳平衡。第二十二章 mmap vs Buffer Pool这是LMDB与传统数据库非常重要的区别。mmapLMDBdata.mdb | v mmap | v Virtual Memory操作系统负责Page Cache Page Fault Memory MappingBuffer Pool传统数据库Disk ↓ Buffer Pool ↓ Page ↓ Database数据库自己管理Page Cache Eviction Dirty Page22.1 两者区别mmapBuffer Pool管理者OS为主数据库地址空间直接映射数据库控制数据复制通常更少通常存在Page管理控制能力较弱较强实现简单复杂典型LMDBSQLite等数据库体系中常见但是不能简单理解为mmap一定比Buffer Pool快实际性能取决于工作负载 数据大小 访问模式 内存压力 操作系统 存储设备第二十三章 SSD时代的数据库传统观点HDD 随机IO很慢 ↓ LSM非常有优势到了SSDSSD 随机IO变快那么BTree是不是就没用了不是。23.1 SSD改变的是成本而不是原理SSD依然存在Random IO Write Amplification Garbage Collection Erase Block尤其NVMe高IOPS 高并发 低延迟反而使后台Compaction 多线程IO 并发Flush成为新的优化重点。第二十四章 HDD、SSD、NVMe对比可以简单理解存储特点数据库影响HDD随机访问非常昂贵尽量顺序IOSATA SSD随机IO明显提升LSM/BTree均可NVMe SSD高IOPS、低延迟更关注并发和写放大24.1 HDDHDD磁头移动 盘片旋转随机Read A Seek Read B Seek Read C非常慢。所以Sequential IO优势巨大。LSM Tree非常适合这种思路。24.2 NVMeNVMePCIe | SSD Controller | Flash可以同时处理大量IO。于是Compaction可以使用多个线程 多个IO队列第二十五章 AI数据集应该选什么假设1000万图片 每张 100KB ~ 5MB目标训练读取方案一LMDB图片 ↓ LMDB ↓ DataLoader ↓ GPU非常合适。尤其写一次 读很多次方案二LevelDB也可以。但是Compaction对于大Value并不一定理想。方案三RocksDB适合持续更新 数据不断写入 大规模服务但如果只是训练集静态读取LMDB通常更加直接。第二十六章 日志系统应该选什么假设每秒 100万条日志核心要求高吞吐 顺序写 后台整理LSMRocksDB LevelDB会更加自然。第二十七章 缓存系统应该选什么如果目标微秒级访问 大量热点数据 TTL Counter List Set那么Redis更加适合。因为数据 | Memory而不是Disk | BTree第二十八章 嵌入式设备应该选什么假设工业设备 Windows/Linux 单机 配置数据 状态数据可以考虑SQLite LMDB bbolt如果需要SQL 复杂查询 关系选择SQLite如果Key-Value 读多写少 追求极低读取开销可以考虑LMDB第二十九章 Go项目应该选什么如果Go 嵌入式KV可以考虑bbolt BadgerDB Pebble大致BTree | bbolt LSM | Badger Pebble第三十章 分布式数据库应该选什么如果已经进入多机器 多副本 故障恢复 一致性 事务就不应该只考虑LMDB LevelDB RocksDB因为这些本质上主要是Local Storage Engine需要Raft Replication Transaction Distributed Scheduling此时可以考虑TiKV FoundationDB CockroachDB第三十一章 Storage Engine与Database的区别这是非常重要的概念。很多初学者会把RocksDB直接理解成完整数据库系统实际上更准确的是RocksDB ↓ Storage Engine而TiKV ↓ Distributed Database ↓ RocksDB同样MongoDB ↓ Database ↓ WiredTiger ↓ Storage Engine所以可以形成Database | v Storage Engine | v File System | v SSD第三十二章 数据库的分层现代数据库大致可以拆成Application | v Query Layer | v Transaction | v Storage Engine | ---------------------- | | Memory Disk | | Cache/MemTable SST/BTree | | ---------------------- | v File System | v SSD如果是分布式数据库Client | v Distributed Layer | -------------------- | | | Node Node Node | | | Storage Storage Storage第三十三章 为什么没有“最好的数据库”这是数据库选择中最重要的结论。因为数据库性能不是一个单一数字。必须考虑Read Write Latency Throughput Space Consistency Transaction Scale Availability例如LMDBRead ★★★★★ Write ★★★ Distributed ☆RocksDBRead ★★★★ Write ★★★★★ Distributed ☆RedisMemory Read ★★★★★ Memory Write ★★★★★ Disk Storage 取决于持久化策略SQLiteSQL ★★★★★ Embedded ★★★★★ Distributed ☆因此数据库不是越复杂越好而是要匹配访问模式。第三十四章 从访问模式选择数据库这是比记数据库名字更加重要的方法。场景一读多写少Read Write考虑LMDB BTree场景二写多读多Write ≈ Read考虑RocksDB LSM场景三超低延迟缓存Memory考虑Redis场景四需要SQLSQL考虑SQLite PostgreSQL MySQL而不是RocksDB然后自己实现SQL。场景五分布式KVMulti Node考虑TiKV FoundationDB第三十五章 AI/视觉行业数据库选择结合视觉行业可以得到一个比较实用的选择表。数据类型推荐方案原因静态图片数据集LMDB读性能好、简单点云数据集LMDB / RocksDB取决于读写比例Tensor数据集LMDB顺序读取方便推理结果SQLite需要查询和统计实时设备状态Redis低延迟高频日志RocksDB高写入本地配置SQLite / LMDB单机嵌入式大规模分布式KVTiKV分布式一致性Go本地KVbbolt / Badger / PebbleGo生态MongoDB底层WiredTiger文档数据库存储引擎第三十六章 一个工业视觉系统应该如何组合实际项目通常不会整个系统只选择一种数据库。而是Vision System | -------------------------- | | | v v v Redis SQLite LMDB | | | 实时状态 元数据 图片数据 | v Device Cache例如Camera | ---- Image ------ LMDB/NAS | ---- Result ------ SQLite | ---- Status ------ Redis | ---- Log --------- RocksDB这才是实际工程更加常见的架构。第三十七章 BTree与LSM Tree的最终理解可以用一句话概括BTree直接维护最终的数据结构。Write ↓ Tree ↓ DiskLSM Tree先接受写入再通过后台合并维护最终的数据结构。Write ↓ Memory ↓ SST ↓ Merge ↓ Final State因此BTree Write Cost ↑ Read Cost ↓而LSM Write Cost ↓ Read/Compaction Cost ↑当然这是总体趋势不是绝对规律。现代数据库通过Cache Bloom Filter Prefetch Compaction Index Compression Batch Parallelism不断缩小这种差距。第三十八章 从LMDB到LevelDB再到RocksDB整个系列可以串成一条技术发展路线。Database | ---------------- | | v v BTree LSM Tree | | v v LMDB LevelDB | v RocksDB | ---------------------------- | | | v v v TiKV Pebble Badger然后进一步Local Storage Engine | v Distributed Database | -------- | | TiKV FoundationDB第三十九章 现代数据库真正的核心技术如果从源码和工程角度继续深入实际上最终会发现现代数据库真正重要的是下面这些技术。1. BTree 2. LSM Tree 3. WAL 4. MVCC 5. Snapshot 6. Copy-On-Write 7. Cache 8. Bloom Filter 9. Compaction 10. Transaction 11. Lock 12. Iterator 13. Serialization 14. Compression 15. Checksum 16. Recovery 17. Concurrency 18. Replication而LMDB LevelDB RocksDB SQLite TiKV只是这些技术不同组合的结果。第四十章 数据库学习路线如果希望真正达到能够阅读数据库源码推荐按照下面的顺序学习。第一阶段 Array Linked List Hash Tree Heap ↓ 第二阶段 BST AVL Red-Black Tree B Tree BTree ↓ 第三阶段 Disk IO Page Buffer Pool WAL Transaction ↓ 第四阶段 LMDB BTree mmap MVCC Copy-On-Write ↓ 第五阶段 LSM Tree SkipList MemTable SSTable Bloom Filter ↓ 第六阶段 LevelDB ↓ 第七阶段 RocksDB Compaction Cache Column Family SSD Optimization ↓ 第八阶段 Distributed Storage Raft MVCC Replication Sharding ↓ 第九阶段 TiKV FoundationDB CockroachDB第四十一章 如果要阅读源码应该先看什么对于C开发者建议不要一开始直接阅读整个RocksDB。可以按照LevelDB作为入口。因为LevelDB代码量相对较小 设计思想清晰 核心模块集中建议阅读顺序DBImpl ↓ Write ↓ MemTable ↓ SkipList ↓ WAL ↓ VersionSet ↓ SSTable ↓ Block ↓ Iterator ↓ Compaction理解LevelDB之后再看RocksDB会容易很多。第四十二章 最终总结整个系列最终可以浓缩成下面这张图Key-Value Storage | ---------------------------- | | v v BTree LSM | | ---------------- ---------------- | | | | | | LMDB SQLite bbolt LevelDB RocksDB Pebble | | | | mmap SQL SSTable | | Compaction | MVCC | v TiKV而不同数据库实际上是在解决不同的问题LMDB 解决 如何让嵌入式BTree读取非常快 LevelDB 解决 如何把随机写转换成顺序写 RocksDB 解决 如何把LSM做到高吞吐、高并发、适合SSD SQLite 解决 如何在一个文件里提供完整关系型数据库 Redis 解决 如何提供极低延迟的内存数据结构 TiKV 解决 如何把KV存储扩展到分布式环境 FoundationDB 解决 如何构建强事务、可组合的分布式KV基础设施最终应该形成这样一个认知数据库不是一堆API而是一套“数据结构 内存管理 磁盘布局 并发控制 事务 崩溃恢复”的系统工程。BTree解决的是如何组织磁盘上的有序数据LSM Tree解决的是如何降低随机写成本WAL解决的是程序崩溃以后如何恢复MVCC解决的是读写并发时如何看到一致的数据Bloom Filter解决的是如何快速判断数据大概率不存在Compaction解决的是如何把大量SSTable重新整理Cache解决的是如何减少昂贵的磁盘访问Raft解决的是多个机器之间如何保持一致而这些技术组合起来才形成我们今天看到的SQLite LMDB LevelDB RocksDB Redis TiKV FoundationDB MongoDB CockroachDB因此真正掌握现代数据库的关键不是记住“哪个数据库性能最高”而是看到一个业务需求后能够判断数据规模 ↓ 读多还是写多 ↓ Value大小 ↓ 是否需要范围查询 ↓ 是否需要事务 ↓ 是否需要SQL ↓ 是否需要分布式 ↓ 延迟还是吞吐 ↓ HDD / SSD / NVMe ↓ 最终选择合适的Storage Engine这也是从数据结构学习数据库最终走向数据库系统设计的关键一步。 《现代 Key-Value 数据库原理：从 B+Tree 到 LSM Tree》-第五篇：现代数据库横向对比
文章目录《现代 Key-Value 数据库原理从 BTree 到 LSM Tree》第五篇现代数据库横向对比第一章 现代数据库整体分类第二章 现代数据库横向总表第三章 LMDB3.1 LMDB的数据结构3.2 LMDB为什么读取快3.3 LMDB的核心优势读取优秀事务简单数据结构稳定非常适合AI数据集3.4 LMDB的限制第四章 LevelDB4.1 LevelDB为什么选择LSM4.2 LevelDB核心组件4.3 LevelDB的缺点第五章 RocksDB5.1 为什么需要RocksDB5.2 Column Family5.3 RocksDB适合什么第六章 BadgerDB6.1 为什么Key和Value分开6.2 Badger适合什么第七章 BoltDB / bbolt7.1 bbolt结构7.2 bbolt与LMDB第八章 SQLite8.1 SQLite底层是什么8.2 SQLite最大的特点8.3 SQLite为什么这么流行8.4 SQLite vs LMDB第九章 Berkeley DB9.1 Berkeley DB适合什么第十章 Redis10.1 Redis不是单一数据结构10.2 Redis为什么快10.3 Redis为什么还能持久化第十一章 WiredTiger11.1 WiredTiger为什么重要11.2 MongoDB为什么需要独立存储引擎第十二章 Pebble12.1 Pebble为什么出现第十三章 TiKV13.1 TiKV整体架构13.2 为什么TiKV使用RocksDB思想第十四章 FoundationDB14.1 FoundationDB最大的特点第十五章 BTree vs LSM TreeBTreeLSM第十六章 写入性能BTreeLSM第十七章 读取性能第十八章 Read Amplification第十九章 Write Amplification第二十章 Space Amplification第二十一章 三种放大之间的关系第二十二章 mmap vs Buffer PoolmmapBuffer Pool22.1 两者区别第二十三章 SSD时代的数据库23.1 SSD改变的是成本而不是原理第二十四章 HDD、SSD、NVMe对比24.1 HDD24.2 NVMe第二十五章 AI数据集应该选什么方案一LMDB方案二LevelDB方案三RocksDB第二十六章 日志系统应该选什么第二十七章 缓存系统应该选什么第二十八章 嵌入式设备应该选什么第二十九章 Go项目应该选什么第三十章 分布式数据库应该选什么第三十一章 Storage Engine与Database的区别第三十二章 数据库的分层第三十三章 为什么没有“最好的数据库”LMDBRocksDBRedisSQLite第三十四章 从访问模式选择数据库场景一读多写少场景二写多读多场景三超低延迟缓存场景四需要SQL场景五分布式KV第三十五章 AI/视觉行业数据库选择第三十六章 一个工业视觉系统应该如何组合第三十七章 BTree与LSM Tree的最终理解BTreeLSM Tree第三十八章 从LMDB到LevelDB再到RocksDB第三十九章 现代数据库真正的核心技术第四十章 数据库学习路线第四十一章 如果要阅读源码应该先看什么第四十二章 最终总结《现代 Key-Value 数据库原理从 BTree 到 LSM Tree》第五篇现代数据库横向对比前面四篇分别从数据库存储基础、BTree、LMDB、LevelDB出发逐渐建立了一个完整的认知体系。现在可以把这些知识放在一起。现代数据库看起来种类非常多LMDB LevelDB RocksDB SQLite Redis BadgerDB bbolt WiredTiger TiKV FoundationDB Pebble但如果从底层存储结构来看它们并没有想象中那么复杂。大量数据库最终都可以归结到几种核心思想BTree LSM Tree Hash SkipList Log Structured Storage Memory Data Structure Distributed KV因此学习数据库真正重要的不是记住几十个数据库的名字而是理解为什么这个数据库选择这种数据结构以及这种选择解决了什么问题。第一章 现代数据库整体分类先建立一个全局视图。Database | ----------------------------------- | | | v v v BTree LSM Tree Memory | | | -------- -------- -------- | | | | | | LMDB SQLite LevelDB RocksDB Redis ... | | | | bbolt WiredTiger | Pebble | TiKV再进一步BTree | -- LMDB -- SQLite -- bbolt -- WiredTiger LSM | -- LevelDB -- RocksDB -- Pebble -- BadgerDB -- TiKV Memory | -- Redis但是需要注意现实数据库往往不是纯粹的一种结构。例如BadgerDB LSM Tree Value LogRedisHash SkipList Rax List Set Sorted SetFoundationDB则更加复杂Distributed Transaction Storage Engine所以“数据库属于什么类型”通常应该理解为它的核心存储架构而不是说整个数据库只包含一种数据结构。第二章 现代数据库横向总表先给出本篇最重要的一张表。数据库核心结构核心特点典型场景LMDBBTreemmap、Copy-On-Write、MVCC、读性能优秀AI数据集、嵌入式LevelDBLSM TreeMemTable、SSTable、Compaction嵌入式KV、日志RocksDBLSM Tree高性能、丰富Compaction和缓存优化高写入、高并发BadgerDBLSM Value LogGo生态、Key/Value分离Go服务WiredTigerBTree等高性能通用存储引擎MongoDBSQLiteBTree单文件、完整SQL桌面、移动、嵌入式Berkeley DBBTree / Hash等经典嵌入式数据库嵌入式系统bboltBTreeGo、单文件、简单Go嵌入式应用Redis内存数据结构极低延迟、丰富数据结构缓存、消息、实时数据TiKVRocksDB等LSM分布式KV、Raft云原生数据库PebbleLSM TreeCockroachDB生态分布式数据库FoundationDB分布式KV强事务、可组合分布式数据库第三章 LMDBLMDBLightning Memory-Mapped Database它是OpenLDAP项目中的核心嵌入式数据库之一。核心设计BTree mmap Copy-On-Write MVCC3.1 LMDB的数据结构可以简单表示Root | ---------- | | Branch Branch | | ---- ---- | | | | Leaf Leaf Leaf Leaf数据库文件data.mdb直接通过mmap()映射到进程地址空间。于是Disk | v Virtual Memory | v Page | v CPU3.2 LMDB为什么读取快传统数据库Disk ↓ Read ↓ Buffer Pool ↓ Copy ↓ ApplicationLMDBDisk ↓ mmap ↓ Virtual Address ↓ Application因此减少了大量系统调用 用户态/内核态切换 数据复制3.3 LMDB的核心优势读取优秀尤其适合大量读取 少量写入事务简单采用MVCC多个Reader可以并发。数据结构稳定BTree查询 O(logN)非常适合AI数据集例如image_001 → JPEG image_002 → JPEG image_003 → JPEG最终dataset.mdb3.4 LMDB的限制最大的特点其实也是最大的限制一个Writer因此如果业务是大量并发写入LMDB通常不是第一选择。第四章 LevelDBLevelDB 是Google设计的嵌入式KV数据库。核心LSM Tree完整写路径Put | ---- WAL | ---- MemTable | v Immutable | v SSTable | v Compaction4.1 LevelDB为什么选择LSM因为它希望解决BTree 大量随机写的问题。LSMRandom Write ↓ Memory ↓ Sequential Write所以写入吞吐通常非常优秀。4.2 LevelDB核心组件MemTable SkipList WAL Immutable MemTable SSTable Bloom Filter Compaction Manifest Snapshot Iterator这些概念实际上已经成为现代LSM数据库的基础。4.3 LevelDB的缺点LSM不是没有代价。主要问题Compaction会导致Write Amplification Read Amplification Space Amplification例如写1GB ↓ 后台Compaction ↓ 可能产生多个GB的数据读写所以LSM把随机写问题转化成了后台整理问题。第五章 RocksDBRocksDB 是基于LevelDB思想发展起来的高性能LSM存储引擎。可以理解成LevelDB | ---------------- | | 性能优化 功能扩展 | | --------------- | RocksDB5.1 为什么需要RocksDBFacebook面对SSD NVMe 多核CPU 高并发 海量数据LevelDB的设计比较简单。RocksDB进一步强化Compaction Cache Concurrency SSD Write Buffer Compression Column Family Bloom Filter5.2 Column FamilyRocksDB一个非常重要的设计Column Family例如Database ├── metadata ├── image ├── feature └── result不同数据可以独立配置 独立Compaction 独立Cache策略这对于大型系统很重要。5.3 RocksDB适合什么例如高写入日志 时序数据 缓存 状态存储 分布式数据库底层存储如果系统写入量非常大RocksDB通常比LMDB更值得考虑。第六章 BadgerDBBadgerDB 是Go生态中的高性能KV数据库。核心思想LSM Tree Value Log6.1 为什么Key和Value分开传统SSTable Key Value Key Value Key Value如果Value非常大10KB 100KB 1MBCompaction就会产生大量数据移动。BadgerLSM Key Key Key Key而ValueValue Log Value Value Value形成Key ↓ Value Pointer ↓ Value Log例如Key: image_001 Value Pointer: offset 100000 size 200KB ↓ Value Log 100000 | v JPEG Data这样可以减少大Value参与LSM Compaction的成本。6.2 Badger适合什么特别适合Go服务 大Value 高写入 嵌入式KV例如Go ↓ Badger ↓ RocksDB风格LSM第七章 BoltDB / bboltGo生态还有一个非常经典的数据库bbolt。它的前身是BoltDB。核心BTree和LMDB思路比较接近。7.1 bbolt结构Database | v BTree | ---------- | | Bucket BucketBucket可以理解成Key Namespace例如users images config7.2 bbolt与LMDB两者都属于BTree但是LMDB重点mmap Copy-On-Write MVCC而bbolt是Go生态中更加简单直接的嵌入式BTree方案。第八章 SQLiteSQLite 是完全不同于LevelDB的数据库。它不仅是KV而是关系型数据库支持SQL Table Index Transaction Join Query8.1 SQLite底层是什么SQLite主要使用B-Tree进行表和索引的组织。例如Database ------------------- | Table | | | | B-Tree | ------------------- ------------------- | Index | | | | B-Tree | -------------------8.2 SQLite最大的特点一个数据库database.db可以直接复制。例如app.db里面用户 配置 历史记录 索引全部存在一个文件。8.3 SQLite为什么这么流行因为它解决的是不需要部署数据库服务器但又需要完整关系型数据库能力。例如Android iOS Windows桌面 嵌入式设备 浏览器 单机软件8.4 SQLite vs LMDB如果数据是Key → Value而且极致简单LMDB非常合适。如果需要SELECT*FROMimageWHEREcamera_id10ANDtimestamp...那么SQLite明显更加合适。第九章 Berkeley DBBerkeley DB 是非常经典的嵌入式数据库。历史非常悠久。它支持多种数据访问方式BTree Hash Queue Recno因此它不是单纯的BTree数据库而是一个多种嵌入式存储结构集合。9.1 Berkeley DB适合什么历史上大量用于嵌入式系统 网络服务 配置数据 缓存 本地数据库其重要意义在于它代表了早期Embedded Database的经典设计路线。第十章 RedisRedis 和LMDB、LevelDB有很大区别。Redis的核心思想数据主要驻留在内存中。10.1 Redis不是单一数据结构Redis内部使用多种数据结构。例如String Hash List Set Sorted Set Stream底层还涉及Hash Table SkipList Rax ZipList / Listpack10.2 Redis为什么快典型路径Client ↓ Redis Server ↓ Memory ↓ Data Structure而不是Client ↓ Disk ↓ BTree ↓ Data因此访问延迟非常低。10.3 Redis为什么还能持久化Redis提供RDB AOF例如Memory | ---- RDB | ---- AOF所以Redis并不是纯内存 数据一定不持久化而是以内存为核心数据层同时提供持久化机制。第十一章 WiredTigerWiredTiger 是MongoDB长期使用的重要存储引擎。MongoDBDocument Database底层MongoDB | WiredTiger | Storage Engine11.1 WiredTiger为什么重要它代表了一种通用高性能存储引擎设计。涉及B-Tree LSM相关能力 Compression Cache Transactions MVCCWiredTiger并不能简单概括为“就是一个BTree数据库”实际实现包含多个存储和事务机制。11.2 MongoDB为什么需要独立存储引擎因为MongoDB上层解决Document Query Aggregation Replication而存储引擎解决Page Index Transaction Disk Cache Concurrency于是MongoDB | v WiredTiger | v Disk这也是数据库分层架构的重要体现。第十二章 PebblePebble 是CockroachDB生态中的LSM存储引擎。它与LevelDB、RocksDB属于同一个思想体系LSM | -- MemTable -- WAL -- SSTable -- Compaction12.1 Pebble为什么出现CockroachDB最初大量借鉴RocksDB。随着自身需求不断发展分布式 事务 Raft Cloud Native需要更加贴合自身系统的存储引擎。于是发展出Pebble第十三章 TiKVTiKV 是分布式KV数据库。它与前面最大的区别LMDB 单机LevelDB 单机RocksDB 单机存储引擎而TiKV 分布式KV13.1 TiKV整体架构可以理解为Client | v TiKV | -------------------- | | Raft RocksDB | | v v Replication Storage多个TiKV节点Node1 Node2 Node3通过Raft保证副本一致性。13.2 为什么TiKV使用RocksDB思想因为RocksDB已经很好地解决单机高性能存储TiKV可以在其基础上增加分布式 Raft 事务 Region Replication形成Distributed Database Local Storage Engine第十四章 FoundationDBFoundationDB 的设计思路又有所不同。它强调Distributed Transactions Ordered Key-Value可以把它理解成Application ↓ FoundationDB API ↓ Distributed Transaction Layer ↓ Storage Servers ↓ Storage Engine14.1 FoundationDB最大的特点不是提供很多SQL语法而是提供一个强一致的、有序Key-Value基础层。在它之上可以构建SQL Document DB Metadata Store Queue Index这是一种Database as a Foundation的思想。第十五章 BTree vs LSM Tree现在回到整个系列最核心的问题。BTreeRoot | -------- | | Branch Branch | | Leaf Leaf数据始终维护在Tree中。LSMMemTable ↓ L0 ↓ L1 ↓ L2 ↓ L3数据先进入Memory再不断Merge第十六章 写入性能BTree典型Write ↓ Locate Page ↓ Modify Page ↓ Write Page可能出现Random IOLSMWrite ↓ MemTable ↓ Sequential WAL ↓ Flush因此大量写入通常更加有优势。第十七章 读取性能BTreeRoot ↓ Branch ↓ Leaf通常只需要O(logN)并且Key Range天然适合范围扫描。LSMMemTable Immutable L0 L1 L2 L3可能需要多个层级 多个SST所以LSM需要Bloom Filter、Block Cache、Index等机制来降低读取成本。第十八章 Read Amplification读放大为了读取一个用户数据系统实际读取了多少额外数据。例如用户需要 1KB数据库可能实际读取 4KB Block这就是Block级读放大。LSM还可能MemTable L0 L1 L2多个层级检查。第十九章 Write Amplification写放大用户写入 1GB数据库实际WAL SSTable Compaction Rewrite最终磁盘可能写3GB 5GB 10GB这就是Write AmplificationLSM数据库尤其需要关注这一指标。第二十章 Space Amplification空间放大用户有效数据 100GB磁盘实际150GB甚至200GB原因可能包括旧版本 Tombstone Compaction尚未完成 冗余Block Index Bloom Filter第二十一章 三种放大之间的关系这是LSM数据库非常重要的概念。Database Performance | ------------------------ | | | v v v Read Ampl. Write Ampl. Space Ampl. | | | 读取 写入 空间 | | | SSTable Compaction Old Data三者往往存在Trade-off。例如Compaction更积极可能Read Amplification ↓ Space Amplification ↓ Write Amplification ↑因此现代LSM数据库实际上一直在寻找读、写、空间三者之间的最佳平衡。第二十二章 mmap vs Buffer Pool这是LMDB与传统数据库非常重要的区别。mmapLMDBdata.mdb | v mmap | v Virtual Memory操作系统负责Page Cache Page Fault Memory MappingBuffer Pool传统数据库Disk ↓ Buffer Pool ↓ Page ↓ Database数据库自己管理Page Cache Eviction Dirty Page22.1 两者区别mmapBuffer Pool管理者OS为主数据库地址空间直接映射数据库控制数据复制通常更少通常存在Page管理控制能力较弱较强实现简单复杂典型LMDBSQLite等数据库体系中常见但是不能简单理解为mmap一定比Buffer Pool快实际性能取决于工作负载 数据大小 访问模式 内存压力 操作系统 存储设备第二十三章 SSD时代的数据库传统观点HDD 随机IO很慢 ↓ LSM非常有优势到了SSDSSD 随机IO变快那么BTree是不是就没用了不是。23.1 SSD改变的是成本而不是原理SSD依然存在Random IO Write Amplification Garbage Collection Erase Block尤其NVMe高IOPS 高并发 低延迟反而使后台Compaction 多线程IO 并发Flush成为新的优化重点。第二十四章 HDD、SSD、NVMe对比可以简单理解存储特点数据库影响HDD随机访问非常昂贵尽量顺序IOSATA SSD随机IO明显提升LSM/BTree均可NVMe SSD高IOPS、低延迟更关注并发和写放大24.1 HDDHDD磁头移动 盘片旋转随机Read A Seek Read B Seek Read C非常慢。所以Sequential IO优势巨大。LSM Tree非常适合这种思路。24.2 NVMeNVMePCIe | SSD Controller | Flash可以同时处理大量IO。于是Compaction可以使用多个线程 多个IO队列第二十五章 AI数据集应该选什么假设1000万图片 每张 100KB ~ 5MB目标训练读取方案一LMDB图片 ↓ LMDB ↓ DataLoader ↓ GPU非常合适。尤其写一次 读很多次方案二LevelDB也可以。但是Compaction对于大Value并不一定理想。方案三RocksDB适合持续更新 数据不断写入 大规模服务但如果只是训练集静态读取LMDB通常更加直接。第二十六章 日志系统应该选什么假设每秒 100万条日志核心要求高吞吐 顺序写 后台整理LSMRocksDB LevelDB会更加自然。第二十七章 缓存系统应该选什么如果目标微秒级访问 大量热点数据 TTL Counter List Set那么Redis更加适合。因为数据 | Memory而不是Disk | BTree第二十八章 嵌入式设备应该选什么假设工业设备 Windows/Linux 单机 配置数据 状态数据可以考虑SQLite LMDB bbolt如果需要SQL 复杂查询 关系选择SQLite如果Key-Value 读多写少 追求极低读取开销可以考虑LMDB第二十九章 Go项目应该选什么如果Go 嵌入式KV可以考虑bbolt BadgerDB Pebble大致BTree | bbolt LSM | Badger Pebble第三十章 分布式数据库应该选什么如果已经进入多机器 多副本 故障恢复 一致性 事务就不应该只考虑LMDB LevelDB RocksDB因为这些本质上主要是Local Storage Engine需要Raft Replication Transaction Distributed Scheduling此时可以考虑TiKV FoundationDB CockroachDB第三十一章 Storage Engine与Database的区别这是非常重要的概念。很多初学者会把RocksDB直接理解成完整数据库系统实际上更准确的是RocksDB ↓ Storage Engine而TiKV ↓ Distributed Database ↓ RocksDB同样MongoDB ↓ Database ↓ WiredTiger ↓ Storage Engine所以可以形成Database | v Storage Engine | v File System | v SSD第三十二章 数据库的分层现代数据库大致可以拆成Application | v Query Layer | v Transaction | v Storage Engine | ---------------------- | | Memory Disk | | Cache/MemTable SST/BTree | | ---------------------- | v File System | v SSD如果是分布式数据库Client | v Distributed Layer | -------------------- | | | Node Node Node | | | Storage Storage Storage第三十三章 为什么没有“最好的数据库”这是数据库选择中最重要的结论。因为数据库性能不是一个单一数字。必须考虑Read Write Latency Throughput Space Consistency Transaction Scale Availability例如LMDBRead ★★★★★ Write ★★★ Distributed ☆RocksDBRead ★★★★ Write ★★★★★ Distributed ☆RedisMemory Read ★★★★★ Memory Write ★★★★★ Disk Storage 取决于持久化策略SQLiteSQL ★★★★★ Embedded ★★★★★ Distributed ☆因此数据库不是越复杂越好而是要匹配访问模式。第三十四章 从访问模式选择数据库这是比记数据库名字更加重要的方法。场景一读多写少Read Write考虑LMDB BTree场景二写多读多Write ≈ Read考虑RocksDB LSM场景三超低延迟缓存Memory考虑Redis场景四需要SQLSQL考虑SQLite PostgreSQL MySQL而不是RocksDB然后自己实现SQL。场景五分布式KVMulti Node考虑TiKV FoundationDB第三十五章 AI/视觉行业数据库选择结合视觉行业可以得到一个比较实用的选择表。数据类型推荐方案原因静态图片数据集LMDB读性能好、简单点云数据集LMDB / RocksDB取决于读写比例Tensor数据集LMDB顺序读取方便推理结果SQLite需要查询和统计实时设备状态Redis低延迟高频日志RocksDB高写入本地配置SQLite / LMDB单机嵌入式大规模分布式KVTiKV分布式一致性Go本地KVbbolt / Badger / PebbleGo生态MongoDB底层WiredTiger文档数据库存储引擎第三十六章 一个工业视觉系统应该如何组合实际项目通常不会整个系统只选择一种数据库。而是Vision System | -------------------------- | | | v v v Redis SQLite LMDB | | | 实时状态 元数据 图片数据 | v Device Cache例如Camera | ---- Image ------ LMDB/NAS | ---- Result ------ SQLite | ---- Status ------ Redis | ---- Log --------- RocksDB这才是实际工程更加常见的架构。第三十七章 BTree与LSM Tree的最终理解可以用一句话概括BTree直接维护最终的数据结构。Write ↓ Tree ↓ DiskLSM Tree先接受写入再通过后台合并维护最终的数据结构。Write ↓ Memory ↓ SST ↓ Merge ↓ Final State因此BTree Write Cost ↑ Read Cost ↓而LSM Write Cost ↓ Read/Compaction Cost ↑当然这是总体趋势不是绝对规律。现代数据库通过Cache Bloom Filter Prefetch Compaction Index Compression Batch Parallelism不断缩小这种差距。第三十八章 从LMDB到LevelDB再到RocksDB整个系列可以串成一条技术发展路线。Database | ---------------- | | v v BTree LSM Tree | | v v LMDB LevelDB | v RocksDB | ---------------------------- | | | v v v TiKV Pebble Badger然后进一步Local Storage Engine | v Distributed Database | -------- | | TiKV FoundationDB第三十九章 现代数据库真正的核心技术如果从源码和工程角度继续深入实际上最终会发现现代数据库真正重要的是下面这些技术。1. BTree 2. LSM Tree 3. WAL 4. MVCC 5. Snapshot 6. Copy-On-Write 7. Cache 8. Bloom Filter 9. Compaction 10. Transaction 11. Lock 12. Iterator 13. Serialization 14. Compression 15. Checksum 16. Recovery 17. Concurrency 18. Replication而LMDB LevelDB RocksDB SQLite TiKV只是这些技术不同组合的结果。第四十章 数据库学习路线如果希望真正达到能够阅读数据库源码推荐按照下面的顺序学习。第一阶段 Array Linked List Hash Tree Heap ↓ 第二阶段 BST AVL Red-Black Tree B Tree BTree ↓ 第三阶段 Disk IO Page Buffer Pool WAL Transaction ↓ 第四阶段 LMDB BTree mmap MVCC Copy-On-Write ↓ 第五阶段 LSM Tree SkipList MemTable SSTable Bloom Filter ↓ 第六阶段 LevelDB ↓ 第七阶段 RocksDB Compaction Cache Column Family SSD Optimization ↓ 第八阶段 Distributed Storage Raft MVCC Replication Sharding ↓ 第九阶段 TiKV FoundationDB CockroachDB第四十一章 如果要阅读源码应该先看什么对于C开发者建议不要一开始直接阅读整个RocksDB。可以按照LevelDB作为入口。因为LevelDB代码量相对较小 设计思想清晰 核心模块集中建议阅读顺序DBImpl ↓ Write ↓ MemTable ↓ SkipList ↓ WAL ↓ VersionSet ↓ SSTable ↓ Block ↓ Iterator ↓ Compaction理解LevelDB之后再看RocksDB会容易很多。第四十二章 最终总结整个系列最终可以浓缩成下面这张图Key-Value Storage | ---------------------------- | | v v BTree LSM | | ---------------- ---------------- | | | | | | LMDB SQLite bbolt LevelDB RocksDB Pebble | | | | mmap SQL SSTable | | Compaction | MVCC | v TiKV而不同数据库实际上是在解决不同的问题LMDB 解决 如何让嵌入式BTree读取非常快 LevelDB 解决 如何把随机写转换成顺序写 RocksDB 解决 如何把LSM做到高吞吐、高并发、适合SSD SQLite 解决 如何在一个文件里提供完整关系型数据库 Redis 解决 如何提供极低延迟的内存数据结构 TiKV 解决 如何把KV存储扩展到分布式环境 FoundationDB 解决 如何构建强事务、可组合的分布式KV基础设施最终应该形成这样一个认知数据库不是一堆API而是一套“数据结构 内存管理 磁盘布局 并发控制 事务 崩溃恢复”的系统工程。BTree解决的是如何组织磁盘上的有序数据LSM Tree解决的是如何降低随机写成本WAL解决的是程序崩溃以后如何恢复MVCC解决的是读写并发时如何看到一致的数据Bloom Filter解决的是如何快速判断数据大概率不存在Compaction解决的是如何把大量SSTable重新整理Cache解决的是如何减少昂贵的磁盘访问Raft解决的是多个机器之间如何保持一致而这些技术组合起来才形成我们今天看到的SQLite LMDB LevelDB RocksDB Redis TiKV FoundationDB MongoDB CockroachDB因此真正掌握现代数据库的关键不是记住“哪个数据库性能最高”而是看到一个业务需求后能够判断数据规模 ↓ 读多还是写多 ↓ Value大小 ↓ 是否需要范围查询 ↓ 是否需要事务 ↓ 是否需要SQL ↓ 是否需要分布式 ↓ 延迟还是吞吐 ↓ HDD / SSD / NVMe ↓ 最终选择合适的Storage Engine这也是从数据结构学习数据库最终走向数据库系统设计的关键一步。