分享：数据库存储与索引技术（二） 分布式数据库基石——LSM树

欢迎访问 OceanBase 官网获取更多信息：https://www.oceanbase.com/

本文来自OceanBase社区分享，仅限交流探讨。原作者马伟，长期从事互联网广告检索系统的研发，对数据库，编译器等领域也有浓厚兴趣。

---

上文讲到，传统单机数据库受制于底层存储技术及扩展瓶颈，无法满足互联网席卷而来的海量存储和并发读写事务需求。由此衍生出各类数据库扩展技术，其中以NewSQL为代表的分布式数据库多采用LSM树用于构建底层的存储系统，对存储和读写请求的扩展都有非常好的支持。那么，LSM树到底有何独特之处？本文从应用及操作层面进行介绍。

1. 概念介绍

LSM-Tree 全称是 Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分利用磁盘的顺序写性能要远高于随机写性能这一特性，将批量的随机写转化为一次性的顺序写。其最早是在1996年的论文[《The Log-Structured Merge-Tree (LSM-Tree)》](https://open.oceanbase.com/blog/The Log-Structured Merge-Tree (LSM-Tree))中提出。

LSM树由两个或以上的存储结构组成，比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中，称为C0 tree，具体可以是任何方便健值查找的数据结构，比如红黑树、map之类，甚至可以是跳表。另外一个存储结构常驻在硬盘中，称为C1 tree，具体结构类似B树。

在LSM树中，最低一级即最小的C0树位于内存,而更高级的C1、C2…树都位于磁盘里。数据会先写入内存中的C0树，当它的大小达到一定阈值之后，C0树中的全部或部分数据就会刷入磁盘中的C1树，如下图所示。在实际应用中，为防止内存因断电等原因丢失数据，写入内存的数据同时会顺序在磁盘上写日志，类似于预写日志(WAL)，这就是LSM这个词中Log一词的来历。

1.1. BigTable

LSM树在前互联网时代并未得到很好的重视，传统的关系型数据库的存储和索引结构依然以基于页面(Page)的B+树和HashTable为主。随着互联网规模的扩大和普及，在面对十亿级的用户接入，以及PB规模数据的写入，传统的关系型数据库已经难以支撑。Google 2006年发表的论文《Bigtable: A Distributed Storage System for Structured Data》提出了利用LSM树在GFS上构建可线性扩展的KV系统的方案，即大名鼎鼎的BigTable系统。

1.1.1. 数据模型

BigTable的数据模型，每一个键值对的 Key 都为 Row key + Column key + Timestamp 的结构，Value 则是任意二进制字符串：

(row:string, column:string,time:int64) -> string

举一个具体的例子：比如，一个存储了大量网页及其相关信息的表 Webtable，Webtable 使用 URL 作为行名，使用网页的某些属性作为列名，网页的内容存入 contents 列中，并使用获取该网页的时间戳标识同一个网页的不同版本。在 Bigtable 中，Webtable 的存储范例如下图所示：

BigTable引入了RowKey, ColumnFamily, ColumnKey, TimeStamp等概念来方便用户抽象和管理自己的数据。其各自作用如下：

• Row Key
  BigTable的RowKey概念与关系数据库的PrimaryKey类似，是一行数据的唯一标识。RowKey可以是任意二进制字符串，最大容量为 64KB。但是在大多数场景下，字节数只有 10～100 Bytes 左右。Bigtable 的表按照 RowKey的字典序组织数据。即BigTable表中的数据是全局有序的。
• Column Key 与 ColumnFamily
  ColumnKey类似关系数据库中的列，一般表示一种数据类型，也可以是一个复杂Object序列化后的一串二进制字符串。若干个有业务含义的ColumnKey聚合在一起被称为ColumnFamily(列族)。ColumnFamily 是 access control（访问控制）、disk and memory accounting（磁盘和内存计算）的基本单元。
• TimeStamp

Bigtable 中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是 64 位整型，既可以由系统赋值也可由用户指定。时间戳通常以 us（微秒）为单位。时间戳既可以由 Bigtable 进行分配，也可以由客户端进行分配，如果应用程序希望避免冲突，应当生产唯一的时间戳。
表项的不同版本按照时间戳倒序排列（大的在前，时间戳越大表明数据加入的时间越晚），即最新的数据排在最前面，因而每次查询会先读到最新版本。为了简化多版本数据的管理，每个列族都有两个设置参数用于版本的自动回收，用户可以指定保存最近 N 个版本，或保留足够新的版本(如最近 7 天的内容)。

1.1.2. BigTable中LSM树实现

BigTable的数据模型，在概念上抽象出了完整的Table, Row, Column等概念，方便应用进行业务抽象。但是在实现上，BigTable是如何何LSM树进行结合的呢？我们前面提到，LSM是一个K-V结构的数据结构，在BigTable中，每个Table即对应一棵LSM树。BigTable通过分隔符(这里假定为"