（1）作者专业：阿里巴巴和贝壳找房专家撰写
（2）内容实用：深入LevelDB架构与源码，精通键-值数据库
（3）更上层楼：掌握谷歌Bigtable数据库单机版设计精髓
（4）学以致用：基于LevelDB，开发分布式数据库
本书详细剖析LevelDB从使用到设计实现的方方面面，读后可了解谷歌Bigtable数据库的设计精髓，逻辑上可分为两部分。 第一部分着重讲解LevelDB的基础知识，主要内容如下。 1）基本数据结构，这是理解后续内容的基础，也可以加深对比较器、迭代器等常见数据结构的理解。 2）基本使用，如数据库打开、关闭以及基本的读写操作。 3）总体架构与设计思想，读后可掌握LevelDB的整体情况与设计思路。 4）公用基础类，读后可了解LevelDB中如何实现数值编码、内存管理以及文件读取等。 第二部分着重讲解LevelDB各模块的实现细节，主要内容如下。 1）Log模块的实现细节，以及如何通过Log进行崩溃恢复，并生成一个MemTable文件。 2）MemTable模块的实现细节，以及MemTable超过内存阈值时如何生成一个SSTable文件。 3）SSTable模块的实现细节。 4）Compaction原理与多版本管理。
廖环宇，中南大学硕士、阿里云高级算法专家与工业大脑算法团队负责人，长期致力于人工智能算法与工业大数据技术的研究和实践，主导过许多大型数据智能平台的开发与应用。
张仕华，贝壳找房资深软件开发工程师，毕业于北京科技大学，曾就职于360、滴滴。热衷源码研究与探究技术本质，合著有《Redis 5设计与源码分析》。
前言 第1章 初识LevelDB1 11 键-值数据库的提出与价值1 12 LevelDB的诞生过程2 13 LevelDB的特性3 14 LevelDB的性能分析4 15 LevelDB的衍生产品5 151 RocksDB6 152 SSDB7 16 小结8 第2章 基本数据结构9 21 string与Slice9 22 错误处理Status10 23 key比较函数接口Comparator11 24 迭代器接口13 25 系统参数14 251 DB参数Options14 252 读操作参数ReadOptions16 253 写操作参数WriteOptions16 26 小结17 第3章 LevelDB使用入门18 31 源码简介18 311 目录结构18 312 安装与编译19 313 引用头文件20 32 创建（打开）与关闭数据库21 33 数据的读、写与删除23 34 数据批量操作24 35 迭代器与key的查询操作26 351 前向与反向迭代循环遍历26 352 按key的范围进行查询27 36 性能优化方案28 361 启用压缩28 362 启用Cache29 363 启用FilterPolicy30 364 key的命名设计30 37 小结31 第4章 总体架构与设计思想32 41 键-值存储系统的基本要求32 42 Bigtable与LevelDB 33 43 主要模块功能介绍34 44 主要操作流程分析36 441 数据库Open流程分析36 442 数据Get流程分析39 443 数据Put与Write流程分析42 444 快照生成与读取分析46 45 小结48 第5章 公用基础类49 51 LevelDB跨平台编程49 511 LevelDB操作系统可移植方案49 512 LevelDB移植到操作系统接口规范50 513 POSIX可移植操作系统接口55 514 原子指针与内存屏障61 52 文件操作66 521 顺序文件操作66 522 随机文件操作73 523 Log文件操作77 53 Env操作环境抽象接口81 531 PosixEnv对象84 532 EnvWrapper与InMemoryEnv93 54 int数值编码99 541 什么是编码99 542 int定长数值编码100 543 int变长数值编码102 55 内存管理104 551 Arena内存池的基本思想105 552 Arena内存池的定义与原理105 553 Arena内存的分配108 554 内存使用率统计114 555 非内存池的内存分配优化115 56 小结116 第6章 Log模块117 61 Log文件格式定义117 62 Log文件读写操作119 621 Log文件写入119 622 Log文件读取122 63 记录Log文件124 64 从Log文件恢复MemTable125 65 小结126 第7章 MemTable模块127 71 MemTable插入与查找127 711 MemTable插入128 712 MemTable查找129 72 SkipList插入与查找131 721 SkipList插入132 722 SkipList查找134 73 MemTable生成SSTable136 74 小结137 第8章 SSTable模块139 81 SSTable文件格式139 811 SSTable的组成140 812 块格式141 813 数据索引区域145 814 数据区域145 815 元数据索引区域145 816 元数据区域146 82 SSTable的读写流程148 821 生成块148 822 读取块151 823 生成SSTable152 824 读取SSTable156 83 布隆过滤器的实现158 831 布隆过滤器的设计160 832 布隆过滤器的使用162 84 LRU Cache的实现166 841 LRU Cache的设计167 842 LRU Cache的使用173 85 小结174 第9章 多版本管理与Compaction原理176 91 多版本管理机制177 911 VersionEdit机制177 912 Version机制182 913 VersionSet机制187 914 Manifest机制189 92 Compaction原理189 921 触发时机190 922 文件选取191 923 执行流程195 924 文件清理197 93 小结199 附录 LevelDB的演进200
为什么要写这本书 笔者在滴滴工作期间，公司某团队实现了一个兼容Redis协议的分布式NoSQL数据库Fusion。Fusion是构建在SSD磁盘上的存储服务，底层使用存储引擎RocksDB来保存数据。因为兼容Redis协议，所以在数据量特别大的一些场景下，我们开始使用Fusion替代之前使用的Redis。 RocksDB，是一个基于LevelDB开发、实现持久性键-值存储的C++库。而LevelDB则是由Google的Jeff Dean与Sanjay Ghemawat于2011年开发完成并且开源的键-值嵌入式C++库。 虽然同属键-值存储，但Redis是一个基于内存的数据存储引擎，而LevelDB会将数据写入硬盘。出于好奇，笔者业余时间开始阅读LevelDB的源码并零零散散写了一些文章。由于之前写作《Redis 5设计与源码分析》一书时结识了高婧雅编辑，而高编辑跟进的一本LevelDB源码分析的书籍正好需要一名合著者。于是，本书就这样诞生了。 本书特色 虽然国内各大互联网厂商有各类基于LevelDB（或者RocksDB）的分布式键-值存储，但还没有一本系统分析LevelDB实现原理的中文书籍。本书首先介绍LevelDB的基本使用，然后介绍LevelDB的三大基本操作——读取、写入及删除，接着详细介绍LevelDB中的公用基础类，包括文件操作、数值编码、内存管理等。掌握这些基础之后，开始分模块介绍LevelDB的实现，包括Log模块、MemTable模块以及SSTable模块，最后介绍LevelDB中层级的原理以及如何管理各个层级。 通过阅读本书，读者会对很多问题有更加深入的了解，例如： 如何实现快照读取； Redo Log（重做日志）如何设计； LevelDB为何会分多个层级； LSM树到底是什么，为何该数据结构适用于写多读少的场景。 许多底层知识其实是相通的，我们常用的关系型数据库MySQL也有重做日志，也有快照读取。 LevelDB中的SSTable在各种存储引擎中得到了广泛的应用，包括HBase、Cassandra等。LevelDB中的布隆过滤器、归并排序以及LRU Cache等结构更是大量应用于各种场景。 学习LevelDB，不仅能了解如何设计高性能键-值存储，还能加深对数据库实现的整体认知，同时对各种数据结构的实现和使用场景有更加直观的了解。 读者对象 数据库从业人员 应用开发人员 计算机相关专业学生 对数据库技术感兴趣的人员 如何阅读本书 本书从逻辑上分为两大部分。 第一部分着重讲解LevelDB的基础知识。 第1章介绍LevelDB的诞生、特性及其衍生产品。 第2章介绍LevelDB的基本数据结构，了解这些基本数据结构有助于对后续知识的理解。阅读本章，也可以加深对比较器、迭代器等常见数据结构的理解。 第3章介绍LevelDB的基本使用，包括数据库打开、关闭以及基本的读写操作。 第4章介绍LevelDB的总体架构与设计思想，通过本章可以了解LevelDB的模块组成。 第5章介绍LevelDB的公用基础类，帮助读者了解在LevelDB中如何实现数值编码、内存管理以及文件读取等。 第二部分着重讲解LevelDB各模块的实现细节。 第6章介绍LevelDB中Log模块的实现细节，以及如何从Log文件恢复并生成一个MemTable。 第7章介绍LevelDB中MemTable模块的实现细节，以及MemTable超过内存阈值时如何生成一个SSTable。 第8章介绍LevelDB中SSTable模块的实现细节。 第9章介绍LevelDB中的Compaction原理与多版本管理。 附录简要介绍RocksDB对LevelDB的优化。 通过阅读本书，不只可以熟悉LevelDB的底层原理，还可以加深对整个数据库实现的了解。 勘误和支持 由于笔者水平有限，编写时间仓促，书中难免会出现错误或者不准确的地方，恳请读者批评指正。如果你有更多的宝贵意见，可以通过https://githubcom/erpeng联系笔者，期待能够得到你们的真挚反馈，在技术之路上互勉共进。 致谢 感谢本书的合作者——环宇，因为你，才有了这本书的诞生。 感谢伟大的开源运动促进了计算机行业的蓬勃发展。 感谢Jeff Dean与Sanjay Ghemawat创造了LevelDB。 特别致谢 最后，我要特别感谢我的父母、妻子与女儿，为写作这本书，我牺牲了很多陪伴他们的时间。同时因为他们的鼓励与支持，我才能坚持写下去。 感谢高婧雅编辑，得益于她的专业与耐心审稿，才进一步提升了本书的质量。 谨以此书献给热爱计算机行业的朋友们！ 张仕华
