写在前面

最近在学习 Druid，索性整理了一下从 Google 的 BigTable 论文衍生出的这一系列数据产品架构思路。该文章中通过对 BigTable 文章的介绍到 Hbase 再到 Druid，读者会发现这三者非常的相似，但是又由于不同的使用场景而做了其他的优化。由于作者也是初学者，所以多是对网上文章的整理汇总，也算初有脉络，但是总的来说还是一篇纸上谈兵的文章，仅作为对学习的记录。之后应该会在分布式系统上有更多的实战文章。

BigTable

Bigtable 是一个分布式的结构化数据存储系统，它被设计用来处理海量数据。

这是论文开篇的概括，也作为这篇博客的开始吧。

数据模型

1

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

整个 BigTable 的数据模型可以看作是一个很简单的映射，分别是 row，cloumn，time 到一个具体数据的映射。如上图是一个简单的例子，行名是一个反向 URL。contents 列族存放的是网页的内容，anchor 列族存放引用该网页的锚链接文本。 CNN 的主页被 Sports Illustrator 和 MY-look 的主页引用，因此该行包含了名为 anchor:cnnsi.com 和 anchhor:my.look.ca 的列。每个锚链接只有一个版本，而 contents 列则有三个版本，分别由时间戳 t3，t5 和 t6 标识，最新的时间戳会放在最前面。

架构组件

这整个系统当中主要有三部分的组件，分别是 Master 服务器，Tablet 服务器和 Chubby 服务器构成。在后面对其他框架的介绍当中，会发现基础架构有很高的相似性。

Master 服务器（控制者）

主要工作：

• 为 Tablet 服务器分配 Tablets。
• 检测新加入的或者过期失效的 Tablet 服务器。
• 对 Tablet 服务器进行负载均衡、以及对保存在 GFS 上的文件进行垃圾收集。
• 除此之外，它还处理对模 式的相关修改操作，例如建立表和列族。

Tablet 服务器（工作者）

主要工作：管理一个 Tablet 的集合（通常每个服务器有大约数十个至上千个 Tablet）。每个 Tablet 服务器负责处理它所加载的 Tablet 的读写操作，以及在 Tablets 过大时，对其进行分割。

Chubby（协调者）

在说 Chubby 之前想插入一个小话题，到底是什么是 分布式一致性问题(Distributed consensus problem) 。其实在接触分布式系统开始这个问题基本上在每一篇分布式系统的文章中都会被提及，但是在感性的认识下，我发现自己很难用简洁的语言进行概括，所以去查阅了一些文章，有一段是我很认同的简介描述：

在一个分布式系统中，有一组的 Process，他们需要确定一个 Value。于是每个 Process 都提出一个 Value， 一致性就是指只有其中的一个 Value 能够被选中作为最后确定的值，并且当这个值被选出来后，所有的 Process 都需要被通知到。

表面上看，这个问题很容易解决。比如设置一个server，所有的process都 向这个server提交一个Value，这个server可以通过一个简单的规则来挑选出一个Value（例如最先到达的Value被选中），然后由这个 server通知所有的Process。但是在分布式系统中，就会有各种的问题发生，例如，这个server崩溃了怎么办，所以我们可能需要有几台 server共同决定。还有，Process提交Value的时间都不一样，网络传输过程中由于延迟这些Value到达server的顺序也都没有保证。

有一个很具象的例子：

在Google File System(GFS) 中，有很多的server，这些server需要选举其中的一台作为master server。这其实是一个很典型的consensus问题，Value就是master server的地址。GFS就是用Chubby来解决的这个问题，所有的server通过Chubby提供的通信协议到Chubby server上创建同一个文件，当然，最终只有一个server能够获准创建这个文件，这个server就成为了master，它会在这个文件中写入自己 的地址，这样其它的server通过读取这个文件就能知道被选出的master的地址。

对应于 Chubby 就会有一个众所周知的开源项目 Zookeeper，两者从作用到架构上都非常的相似。但是又存在一些差别，文章后面会简单叙述一下两者的不同，不过可以类比 Zookeeper 来理解 Chubby。

前面说了这么多，那 Chubby 到底是一个什么服务。首先它是一个分布式的文件系统，可以提供机制使得 client 可以在 Chubby service 上创建文件和执行一些文件的基本操作。从更高一点的语义层面上。Chubby 是一个分布式的锁系统，“锁” 就是文件，加锁操作就是创建文件成功的那个 server 抢占到了 “锁”。用户通过打开、关闭和读取文件，获取共享锁或者独占锁；并且通过通信机制，向用户发送更新信息。

Tablet（数据聚合单位）

INDEX

Index 是一个三层的B树，由于 Root tablet 不会分裂，所以永远是三层。真正的 Tablet 位置信息存储在第三层每一个行关键字下，而第二层只是对第三层的索引。Root tablet 储存在 Chubby 中。在客户端会缓存 Tablet 的位置信息，如果客户端没有缓存或者发现它的缓存地址不正确，就在树状的存储结构中递归的查询 Tablet 位置信息。如果客户端缓存是空的，那么需要三次寻址。如果是过期了则需要6次，3次是在缓存中寻找，3次是更新缓存。

分配

在任何一个时刻，一个Tablet 只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的 Tablet 服务器、哪些 Tablet 分配给了哪些 Tablet 服务器、哪些 Tablet 还没有被分配。当一个 Tablet 还没有被分配、 并且刚好有一个 Tablet 服务器有足够的空闲空间装载该 Tablet 时，Master 服务器会给这个 Tablet 服务器发送一个装载请求，把 Tablet 分配给这个服务器。

BigTable 使用 Chubby 跟踪记录 Tablet 服务器的状态。当一个 Tablet 服务器启动时，它在 Chubby 的一个 指定目录下建立一个有唯一性名字的文件，并且获取该文件的独占锁。Master 服务器实时监控着这个目录（服务器目录），因此 Master 服务器能够知道有新的 Tablet 服务器加入了。如果 Tablet 服务器丢失了 Chubby 上的独占锁，比如由于网络断开导致 Tablet 服务器和 Chubby 的会话丢失 — 它就停止对 Tablet 提供服务。（Chubby 提供了一种高效的机制，利用这种机制，Tablet 服务器能够在不增加网络负担的情况下知道它是否 还持有锁）。只要文件还存在，Tablet 服务器就会试图重新获得对该文件的独占锁；如果文件不存在了，那么 Tablet 服务器就不能再提供服务了，它会自行退出。

冲写

在 BigTable 中一次写操作会先被记录在日志文件当中，然后被记入 memtable 中。这里 memtable 实际上就是一个写缓存，随着写操作的执行，memtable 的大小不断增加。当 memtable 的尺寸到达一个门限值的时候，这个 memtable 就会被冻结，然后创建一个新的 memtable；被冻结住 memtable 会被转换成 SSTable，然后写入 GFS。这个过程被称为 Minor Compaction， 它有两个目的：收缩 Tablet 服务器使用的内存，以及在服务器灾难恢复过程中，减少必须从 提交日志里读取的数据量。在 Compaction 过程中，正在进行的读写操作仍能继续。

而每一次 Minor Compaction 都会创建一个新的 SSTable。如果 Minor Compaction 过程不停滞的持续进行下去，读操作可能需要合并来自多个 SSTable 的更新。通过定期在后台执行 Tablet 的合并，来限制这类文件的数量，加速存储使用率和读速度，这个过程被称为 Merging Compaction。

这两个步骤在 BIGTABLE 系统中非常的重要，这也是在读写分离架构中，得以优化读写效率的根本，在后面其他系统的设计当中能也能看到类似的优化设计。

存储结构

Tablet 是逻辑层面的存储单元，而实际的存储单元是 SSTable，SSTable 是一个持久化的、排序的、不可更改的 Map 结构，而 Map 是一个 key-value 映射的数据结构，key 和 value 的值都是任意的 Byte 串。可以对 SSTable 进行如下的操作：查询与一个 key 值相关的 value，或者遍历某个 key 值范围内的所有的 key-value 对。从内 部看，SSTable 是一系列的数据块（通常每个块的大小是 64KB，这个大小是可以配置的）。SSTable 使用块索 引（通常存储在 SSTable 的最后）来定位数据块；在打开 SSTable 的时候，索引被加载到内存，来提高查询、读取效率。

HBase

HMaster

没有单点故障问题，启动多个 HMaster，通过 Zookeeper 的 Master Election 机制保证同时只有一个 HMaster 处于 Active，其他处于热备份的状态，定期从 Active 的 Master 同步其最新状态。

主要作用：

• 管理 HReigonServer，实现其负载均衡
  • 启动时HRegion的分配，以及负载均衡和修复时 HRegion 的重新分配
  • 监控集群中所有 HRegionServer 的状态（通过 Heartbeat 和监听 Zookeeper 中的状态）
• 管理和分配 HRegion
• 实现 DDL 操作 (Data Defintion Language, namespace 和 table 的增删改，column family的增删改等)
• 管理 namespace 和 table 的元数据
• 权限控制

HRegionServer（工作者)

HRegionServer一般和DataNode在同一台机器上运行，实现数据的本地性。

存放和管理本地HRegion。
读写HDFS，管理Table中的数据。
Client直接通过HRegionServer读写数据
可以发现 HRegionServer 的作用与 BigTable 中 Tablet 服务器的作用几乎一摸一样，下面介绍更多它内部的机制：

WAL（WRITE AHEAD LOG）

所有的写操作都会保证将数据写入 LOG 文件以后，才会真正更新 MemStore（写缓存），最后写入 HFile 中。采用这种模式，可以保证HRegionServer宕机后，我们依然可以从该Log文件中读取数据，Replay所有的操作，而不至于数据丢失。这个Log文件会定期Roll出新的文件而删除旧的文件(那些已持久化到HFile中的Log可以删除)。

BLOCKCACHE（读缓存）

基于分空间局部性和时间局部性原理，将数据预读取到内存中，以提升读性能。HBase 提供了两种 BlockCache 的实现，默认是 on-heap LRUBlockCache 和 BucketCache(off-heap)。通常BucketCache的性能要差于LruBlockCache，然而由于GC的影响，LruBlockCache的延迟会变的不稳定，而BucketCache由于是自己管理BlockCache，而不需要GC，因而它的延迟通常比较稳定，这也是有些时候需要选用BucketCache的原因。在 BlockCache 101 - Nick Dimiduk 中更加详细的对比。

HSTORE（最小单位）

一个Table可以有一个或多个Region，他们可以在一个相同的HRegionServer上，也可以分布在不同的HRegionServer上，一个HRegionServer可以有多个HRegion，他们分别属于不同的Table。HRegion由多个Store(HStore)构成，每个HStore对应了一个Table在这个HRegion中的一个Column Family，即每个Column Family就是一个集中的存储单元，因而最好将具有相近IO特性的Column存储在一个Column Famil。

MEMSTORE（写缓存）

所有数据的写在完成WAL日志写后，会 写入MemStore中，由MemStore根据一定的算法将数据Flush到地层HDFS文件中(HFile)，通常每个HRegion中的每个 Column Family有一个自己的MemStore。

• 每一次Put/Delete请求都是先写入到MemStore中，当MemStore满后会Flush成一个新的StoreFile(底层实现是HFile)，即一个HStore(Column Family)可以有0个或多个StoreFile(HFile)。有以下三种情况可以触发MemStore的Flush动作，需要注意的是MEMSTORE的最小FLUSH单元是HREGION而不是单个MEMSTORE。
• 当一个HRegion中的所有MemStore的大小总和超过了size。当前 HRegion 下的所有 MemStore 进行 flush。
• 当全局MemStore的大小总和超过了size，当前 HRegionServer 下的所有 MemStore 进行 flush.
• 当前HRegionServer中WAL的大小超过了size，当前 HRegionServer 下的所有 MemStore 进行 flush。依照时间先后顺序，直到 WAL 少于 size。

HFILE

用于存储HBase的数据。

Zookeeper

在产品定位上，Zookeeper 是一个 Distributed process coordinator 而 Chubby 是一个 Distributed lock service。而高一致性与它的使用场景密切相关，由于 Chubby 主要处理少量的写更多的读操作的场景，提供粗力度的锁，所以是需要缓存的。而如果需要进行一次数据更新，Chubby 会先保证所有的缓存都进行更新以后才宣布这次更新完成。而这样的缓存机制在 Zookeeper 中是不存在的，所以当你在 Zookeeper 中进行数据更新，更新作用到 A 副本上，但是没来得及同步到 B 副本上是，就会出现 AB 副本数据不一致的情况。

而开源有开源的好处，在 Zookeeper 客户端上有 Apache 项目 Curator 进行了高度的封装，提供了这样的缓存机制，提升了 Zookeeper 的一致性等级。所以使用 Zookeeper 加上 Curator 的话是等于 Chubby 的。

下面再介绍一下它是如何在 HBase 中的作用：

• 在HMaster和HRegionServer连接到ZooKeeper后创建Ephemeral节点，并使用Heartbeat机制维持这个节点的存活状态，如果某个Ephemeral节点实效，则HMaster会收到通知，并做相应的处理。
  协调多个热备份的 HMaster 节点，通过监听 /hbase/master 来确认 Active Master 节点的状态，如果节点消失，则得到通知，并将自己转为 Activer HMaster。
• Hbase 使用 RowKey 将表水平切割成多个 HRegion，每个 HRegion 都记录了它的 StartKey 和 EndKey，且有序。HRegion 由 HMaster 分配到相应的 HRegionServer 中，然后由 HRegionServer 复杂 HRegion 的启动和管理，和 Client 的通信，负责数据的读（使用 HDFS）。每个 HRegionServer 可以同时管理1000个左右的 HRegion。现在很多的分布式存储都使用这种横向切割，列式存储的方式。

HRegion（数据聚合单位)

Hbase 使用 RowKey 将表水平切割成多个 HRegion，每个 HRegion 都记录了它的 StartKey 和 EndKey，且有序。HRegion 由 HMaster 分配到相应的 HRegionServer 中，然后由 HRegionServer 复杂 HRegion 的启动和管理，和 Client 的通信，负责数据的读（使用 HDFS）。每个 HRegionServer 可以同时管理1000个左右的 HRegion。现在很多的分布式存储都使用这种横向切割，列式存储的方式。

INDEX

可以发现这张图和 BigTable 的 Tablet 索引图几乎一摸一样，不过有趣的是在 0.96 以后，HBase 觉得自己不需要这么大的地址空间，并以每次查询多一次寻址的代价。所以改为了两层结构，并且也保证了 META Table 像之前的 Root table 一样是不可切割的，保证这棵 B 树永远只有两层结构。同样提供客户端缓存。

Druid

底层模型的演进

在中插一个小话题，说说数据存储系统底层模型的一个演进之路。从最开始的平衡树到 B+ 树再到 LSM树：

• 平衡树缺点：树高为 log2(N)，对于索引树来说树高越高，意味着查找所要的花费的访问次数越多，查询效率越低。（常数代价高）况且主存从磁盘读数据一般以页为单位，每次访问磁盘读取多个扇区的数据（大约4kb），远大于单个二叉树节点的值，造成了不必要的查询浪费。

• B+ tree 缺点：叶子节点慢慢分裂，可能导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的 IO，影响性能。

• LSM-tree 特点：在磁盘的访问中，顺序访问的速度是远大于随机访问的速度。而 LSM-tree 正是顺应了这个特点，保证数据的有序性以将一个请求转化为顺序的磁盘访问。在 LSM-tree 中同时使用两部分类树的结构来存储数据，并同时提供查询。其中一部分数据存放在内存中，负责接受新的数据插入更新以及读请求，并直接在内存中对数据进行排序。另外一部分存放在硬盘上，它们是由存放在内存中的 c0 树冲写到磁盘而成，主要提供读，特点是有序且不可别更改。再通过 WAL 原则来容灾恢复，使用 bloom filter 来快速判断数据的存在性。而其更适合插入操作远多于数据更新删除操作与读操作的场景。

Druid 在架构上借鉴了 LSM-tree 的思想，但是也因为使用场景的关系有一些取舍。由于不支持数据修改，所以直接去掉了 WAL 原则。数据直接进入内存的堆区，到达条件后冲写到硬盘上形成一个数据块，同时实时节点又会立即将新生成的数据块加载到非堆区。会周期性的堆 Segment split 进行合并，合并好的会立即被实时节点上传到数据文件存储库中，随后协调节点会指导一个历史节点去文件存储库，将新生成的 Segment 下载到其本地磁盘中。当历史节点成功加载到 Segment 后，会通过协调服务在集群中声明其从此刻开始负责提供该 Segment 的查询。实时节点收到该声明后就不再提供 Segment 的查询服务。

系统结构

实时节点（工作者 内存读写）

主要负责即时摄入实时数据，以及生成 Segment 数据文件。如 Kafka 的消费，可以开多个节点对多个 Partition 进行同时消费，在 Zookeeper 上记录 partition offset，保证 at least one。

上图是实时节点的数据流图，可以看到实时数据会先被写入堆内存当中。在写到一定数量以后，会形成一个 Segement split 持久化保存到硬盘中，且堆内存能保证 Segement split 内部的有序性。而一个 Segement split 马上会被从硬盘里读取到非堆内存中，而此时堆内存中相同的数据会被清理掉。一个查询请求会同时到堆内存和非堆内存里查询数据再进行拼接以后进行返回。

协调节点（历史节点的控制者）

负责历史节点的数据负载均衡，以及通过规则管理数据的生命周期。Druid 通过对每个 DataSource 设置的规则来加载或丢弃具体的数据文件，以管理数据生命周期。在历史节点推出系统的时候，协调节点还没有把其身上携带的 Segment 负载到其他节点身上的时候，会出现短暂的数据无法访问。而Druid 允许通过 创建 Segment 的副本来解决该问题。

历史节点（工作者 读）

历史节点负责加载已经生成好的数据文件以提供查询，并且由协调节点来进行负载均衡。历史节点在启动的时候，首先检查自己的本地缓存中已经存在的 Segment 数据文件，然后从 DeepStorage 中下载属于自己但目前不在自己本地磁盘的 Segment 数据。无论是何种查询，历史节点都会将相关的 Segment 先加入到自己的内存中，然后提供查询服务。

历史节点的查询速度与其内存空间大小和所负责的Segment 数据文件大小之比成正比。Druid 对历史节点进行分层，可以根据数据温度来协调数据的存储位置。

通过 Zookeeper 来协调高可用和高拓展性，新的历史节点被添加后，会通过 Zookeeper 被协调节点发现，然后协调节点将会自动分配相关的 Segment 给它。原有的历史节点被移除的时候，同样会被协调节点发现。

查询节点（工作者）

对外提供查询服务，从历史节点和事实节点查询数据，合并后回传。提供缓存机制，使用多个查询节点来防止单点故障，使用 Nginx 来做负载均衡。保证每个查询节点在对同一个请求相应的时候返回相同的结果。

Segment（数据聚合单位）

总览

实线是数据请求的流向，虚线是实时数据的流向。

实时数据会先进入实时节点的堆内存，在堆内存的大小达到一定的数量以后，会形成 Segment split 冲写到硬盘里，同时这个 Segement split 会被加载到非堆内存中以供访问。并且会提供周期性的 Merging Compaction，由几个小的 Segment split 合成一个 Segement，并存入到存储节点中。存储完成以后会告之协调节点，由协调节点进行负载均衡，决定把这个 Segement 交给一个历史节点，之后这个历史节点会声明对这个 Segement 的查询提供服务，而实时节点收到这个消息以后就不再对这个 Segement 的查询提供服务了，并清理掉相关数据。

一个请求进入系统以后会先到查询节点，查询节点再通过现在各节点对数据的负责情况，分别到实时节点和历史节点上进行查询，最后将结果合并进行返回。并且在查询节点上会提供各等级的缓存，历史节点则提供 Block cache。

End

相信你在阅读以后能明显的感受到三个系统的相似与区别，并对这种分布式架构有个大体上的理解。本篇博客大部分内容都是对现有文章的整理，汇总。所以最后感谢这些文章及其作者：

• BigTable 翻译版
• BigTable 原版
• Paxos Made Simple
• Google利器之Chubby
• 深入HBase架构解析（一） - 上善若水

• BlockCache 101 - Nick Dimiduk
• chubby & zookeeper: different consistency level
• 浅谈命令查询职责分离(CQRS)模式 - yangecnu