NoSQL学习——列存储数据库与BigTable

列存储的诞生背景

数据库的读写始终是数据库最关键的操作。由于不同应用中读写的比例不同，读写操作类型的占比也不同，而数据库不能同时满足这些操作的性能优化，不同的数据库就有了不同的设计考量。例如为了加速读操作添加索引会导致写操作变慢，为了加速单例数据的查找使用哈希索引不能同时加速范围索引。

在这样的限制下，面对拥有大量地写操作和相对较少的读操作的应用（例如银行事务、图书馆新书等的记录），一种基于列的数据库BigTable就诞生了，BigTable的开源实现即为Apache Hadoop HBase。这种数据库主要用于处理有大量写操作而读操作主要查询最近的范围记录的场景。

LSM Tree

LSM(Log structured merge) Tree是一种典型的面向这种写多读少场景的数据系统。其特征是数据按照时间顺序只进行追加操作，由于数据的时效性，LSM对其按照分层结构处理，以平衡内存访问时间和内存占用并减少磁盘IO时间。

一种典型的LSM系统是，在内存中维持新鲜的数据并对其建立索引以加速查询；当数据达到某种阈值时，将其重构为一个包含索引的文件存储到磁盘上，以便可能发生的旧数据查询。

Google BigTable

BigTable是一个宽列数据模型数据库，也是一种使用和改进了LSM的典型系统，是“一种稀疏的、分布式的、存储多维有序映射的数据库”。

基本概念

BigTable中的基本概念包括表table、行row、列族column family、列column和时间戳timestamp，通常一条数据表示为(rowKey:string, columnFamily:columnKey:string, timestamp:int64)->value:string。其中，

• rowKey是一个任意的字符串，按照字典序排列，并使用rowKey数量动态地划分数据，每个划分被称为一个tablet，由一个节点持有。
• 一个columnFamily表示一种概念，可包含多个column，用于存储不同的但性质相似的数据。列族是模式定义的一部分，通常保持在一个较小的量级和较稳定的状态，而其中的列则可以任意变化，这就是其"宽列"性质的来源，也因此，有时一个tablet可能只存储一行。
• 时间戳是一种用于保留表格中的历史数据的方式，在不被指定时，会返回最新版本。通常，系统只会保持最近的一些版本或是一定时间内的版本。

对BigTable/HBase的操作主要基于两类API，其一是数据定义API，用于创建或删除表格和列族或更新其元数据；其二是数据操作API，通常用于写入和删除某些行和列，查找特定的行，扫描一部分行。第二类操作支持单行事务。

BigTable存储原理

BigTable的存储建立在GFS上，在Hadoop中与之对应的是HDFS。GFS用于存储实际的日志和数据文件，并提供集群环境下的复制和容错。在GFS中存储的文件以SSTable的形式组织，内部是有序字符串表（Sorted String Table），每个SSTable由默认64KB的块存储有序且不可变的键值对映射和相应的块映射组成。每个块都存储一个范围内的数据。

在集群结构上，BigTable采用一个主节点+多个tablet节点的方式组织。主节点上记录了tablet归属的节点信息，并可以处理负载平衡、垃圾文件回收、源数据变动；tablet节点采用动态机制进入或退出集群，每个tablet节点管理一组tablet（通常为10-1000个）并负责处理实际的读写请求，当其中的tablet数据过大时，这些节点还要负责对其进行拆分。

主节点中的元数据表包含了所有tablet的位置，这个表格在物理上不一定由一个表格表示，而是被拆分为多个元数据tablet从而分布到多个节点上。在此之前有一个根tablet存储这些元数据tablet的位置。这个根表不可拆分，且由一个分布式锁Chubby控制。每个tablet仅由一个节点管理，无论其属性。

Chubby服务是基于paxos共识算法的锁服务，能够确保集群只有一个主节点、存储根表的位置并跟踪所有节点状态。如果Chubby不可用，则BigTable不可用。这一服务能够通过API提供面向节点组织的类UNIX文件系统（此后的etcd等分布式锁服务也采用了类似的设计），并使其在集群中一致。由此，Chubby向所有tablet节点提供一个文件锁，并使其定时更新，以监视所有节点的状态。

当一个节点失去其锁时，该节点要么重新申请，要么退出集群，从而确保整个系统可用。当一个节点丢失，主节点就需要参与进来对与其相关的文件进行恢复。主节点有一个额外的Chubby锁，并在实际上监控Chubby中其他节点的锁。当错误发生时，主节点会要求删除该节点对应的文件并重新将其分配给其他节点。当主节点不能使用Chubby时，其自身就会退出。

分配tablet的原因可能有：集群启动时主节点对负载进行平衡，数据变动时（主节点根据表的创建和删除发起、tablet合并时主节点发起、tablet拆分时tablet节点发起），tablet节点不可用时和新的tablet节点加入时。主节点发起的分配会使tablet节点扫描元数据（日志文件、SSTable文件列表），然后读取内存中的块索引，从相应的块中读取数据并根据日志文件重建内存表。

BigTable查询的执行

在主节点启动时，它会从Chubby获取一个独一的主节点锁，然后找到所有在线节点，将这些节点的tablet信息组织起来并扫描元数据表比对，找出未分配的tablet交给新的节点。

当一个查询发生时，需要首先找到对应数据的tablet位置，然后使客户端对对应的节点发起操作数据请求。在寻找tablet位置的过程中通常有三次查询，第一轮查询时向chubby服务查找根表的位置；第二轮查询向根表节点发送，获取查询的数据的元数据存储的位置；第三轮查询元数据节点，获得实际存储tablet的节点位置，并缓存该位置以便后续的查询。最后，客户端会像实际存储的节点发起查询。

BigTable的写操作

BigTable的tablet采用了LSM的模式组织，首先包含提交日志记录操作，然后使用一张内存表memTable记录变化的数据，再使用一些SSTable异步地持久化内存表，最后通过后面两者实现读操作。

写操作发生时，BigTable首先会检查语法和客户端认证，然后系统更新提交日志，读取数据操作后，将变化后的数据插入到内存表格memTable中。对于删除操作，通常是在数据上追加一个特殊的墓碑标记，表示其已被删除。因此BigTable在写入时只会引入一个更新提交日志的硬盘操作，从而确保了在具有持久性的基础上减少磁盘IO的效果。

当大量写操作发生后，内存表memTable大小达到阈值，此时，该表就会被冻结并转化为一张SSTable，然后存储到GFS中，然后新的内存表被创建，这一步被称为minor compaction。这样做的原因是减少内存中的记录数量（因为查询较少，更旧的数据很可能用不到，而且对应更新的操作也不再需要高速的记录）。

由于minor compaction操作中memTable都是新建的，其生成的SSTable可能包含大量存在重合范围的记录。因此，被称为Merge compaction的操作就会合并这些SSTable以及内存表中的内容，将其打包到一个新的SSTable。

经过一段时间，这些合并的SSTable也不太具有较强的时效性，BigTable会将其再次合并（Major compaction），并移除被操作删除的数据以减少空间占用。

BigTable的数据读取

在上面的几节中，我们知道读取发生在找到实际的tablet节点后，通过与该节点直接通信查找数据。在查找数据前，会检查操作的语法和认证信息，然后才进行查找。

根据前几节的描述我们可以知道，最新的数据一般都存储在内存表中，因此会先从该表中查询，如果查不到，再依次查询硬盘中的SSTable，按minor-merge-major依次查询，最终将这些数据组合起来返回给客户端。

总结

本章中我们了解了列数据库的由来，并着重了解了bigTable这一典型的列数据库的数据模型和存储原理。从中，还理解了LSM这类设计在读写上的取舍与实现的方法。