Druid架构设计思想详解
目录
Druid 的目标是提供一个能够在大数据集上做实时数据消费与探索的平台。对普遍的数据平台来说，数据的高效摄入与快速查询往往是一对难以两全的指标，但Druid 是怎么做到的呢？这很大程度上得益于其独到的架构设计和基于DataSource 与Segment 的数据结构。
对于目前大多数Druid 的使用场景来说，Druid 本质上是一个分布式的时序数据库，而对于一个数据库的性能来说，其数据的组织方式至关重要。为了更好地阐述Druid 的架构设计思想，我们得先从数据库的文件组织方式聊起。
数据库索引与树结构的选择
众所周知，数据库的数据大多存储在磁盘上，而磁盘的访问相对内存的访问来说是一项很耗时的操作，对比如下。因此，提高数据库数据的查找速度的关键点之一便是尽量减少磁盘的访问次数。
图：磁盘与内存的访问速度对比
为了加速数据库数据的访问，大多传统的关系型数据库都会使用特殊的数据结构来帮助查找数据，这种数据结构叫作索引（Index）。对于传统的关系型数据库，考虑到经常需要范围查找某一批数据，因此其索引一般不使用Hash算法，而使用树（Tree）结构。然而，树结构的种类很多，却不一定都适合用于做数据库索引。
图：索引对树结构的选择
1. 二叉查找树与平衡二叉树
最常见的树结构是二叉查找树（Binary Search Tree），它就是一棵二叉有序树：保证左子树上所有节点的值都小于根节点的值，而右子树上所有节点的值都大于根节点的值。其优点在于实现简单，并且树在平衡的状态下查找效率能达到 O(log₂n)；缺点是在极端非平衡情况下查找效率会退化到 O(n)，因此很难保证索引的效率。
图：二叉查找树的查找效率
针对上述二叉查找树的缺点，人们很自然就想到是否能用平衡二叉树（Balanced Binary Tree）来解决这个问题。但是平衡二叉树依然有个比较大的问题：它的树高为 log₂n——对于索引树来说，树的高度越高，意味着查找所要花费的访问次数越多，查询效率越低。
况且，主存从磁盘读数据一般以页为单位，因此每次访问磁盘都会读取多个扇区的数据（比如4KB大小的数据），远大于单个二叉树节点的值（字节级别），这也是造成二叉树相对索引树效率低下的原因。正因如此，人们就想到了通过增加每个树节点的度来提高访问效率，而B+树（B+-tree）便受到了更多的关注。
2. B+树
在传统的关系型数据库里，B+树（B+-tree）及其衍生树是被用得比较多的索引树。
图：B+树结构
B+树的主要特点如下：
- 每个树节点只存放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。
- 叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询；并且所有叶子节点与根节点的距离相同，因此任何查询的效率都很相似。
- 与二叉树不同，B+树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。
正是由于B+树的上述优点，它成了传统关系型数据库的宠儿。当然，它也并非无懈可击，它的主要缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘IO，以致严重影响到性能。
3. 日志结构合并树（LSM-tree）
众所周知，数据库的数据大多存储在磁盘上，而无论是传统的机械硬盘（Hard Disk Drive, HDD）还是固态硬盘（Solid State Drive, SSD），对磁盘数据的顺序读写速度都远高于随机读写。
图：磁盘顺序与随机访问吞吐对比
然而，基于B+树的索引结构是违背上述磁盘基本特点的——它会需要较多的磁盘随机读写，于是，1992年，名为日志结构（Log-Structured）的新型索引结构方法便应运而生。日志结构方法的主要思想是将磁盘看作一个大的日志，每次都将新的数据及其索引结构添加到日志的最末端，以实现对磁盘的顺序操作，从而提高索引性能。不过，日志结构方法也有明显的缺点，随机读取数据时效率很低。1996年，一篇名为 The log-structured merge-tree（LSM-tree）的论文创造性地提出了日志结构合并树（Log-Structured Merge-Tree）的概念，该方法既吸收了日志结构方法的优点，又通过将数据文件预排序克服了日志结构方法随机读性能较差的问题。尽管当时LSM-tree新颖且优势鲜明，但它真正声名鹊起却是在10年之后的2006年，那年谷歌的一篇使用了LSM-tree技术的论文 Bigtable: A Distributed Storage System for Structured Data 横空出世，在分布式数据处理领域掀起了一阵旋风，随后两个声名赫赫的大数据开源组件（2007年的HBase与2008年的Cassandra，目前两者同为Apache顶级项目）直接在其思想基础上破茧而出，彻底改变了大数据基础组件的格局，同时也极大地推广了LSM-tree技术。
LSM-tree最大的特点是同时使用了两部分类树的数据结构来存储数据，并同时提供查询。其中一部分数据结构（C0树）存在于内存缓存（通常叫作memtable）中，负责接受新的数据插入更新以及读请求，并直接在内存中对数据进行排序；另一部分数据结构（C1树）存在于硬盘上(这部分通常叫作sstable)，它们是由存在于内存缓存中的C0树冲写到磁盘而成的，主要负责提供读操作，特点是有序且不可被更改。
图：LSM-tree的C0与C1部分
LSM-tree的另一大特点是除了使用两部分类树的数据结构外，还会使用日志文件（通常叫作commit log）来为数据恢复做保障。这三类数据结构的协作顺序一般是：所有的新插入与更新操作都首先被记录到commit log中——该操作叫作WAL（Write Ahead Log），然后再写到memtable，最后当达到一定条件时数据会从memtable冲写到sstable，并抛弃相关的log数据；memtable与sstable可同时供查询；当memtable出问题时，可从commit log与sstable中将memtable的数据恢复。
我们可以参考HBase的架构来体会其架构中基于LSM-tree的部分特点。按照WAL的原则，数据首先会写到HBase的HLog(相当于commit log)里，然后再写到MemStore（相当于memtable）里，最后会冲写到磁盘StoreFile（相当于sstable）中。这样HBase的HRegionServer就通过LSM-tree实现了数据文件的生成。HBase LSM-tree架构示意图如下图。
图：HBase LSM-tree架构示意图
LSM-tree的这种结构非常有利于数据的快速写入（理论上可以接近磁盘顺序写速度），但是不利于读——因为理论上读的时候可能需要同时从memtable和所有硬盘上的sstable中查询数据，这样显然会对性能造成较大的影响。为了解决这个问题，LSM-tree采取了以下主要的相关措施：
- 定期将硬盘上小的sstable合并（通常叫作Merge或Compaction操作）成大的sstable，以减少sstable的数量。而且，平时的数据更新删除操作并不会更新原有的数据文件，只会将更新删除操作加到当前的数据文件末端，只有在sstable合并的时候才会真正将重复的操作或更新去重、合并。
- 对每个sstable使用布隆过滤器（Bloom Filter），以加速对数据在该sstable的存在性进行判定，从而减少数据的总查询时间。
Druid总体架构
LSM-tree显然比较适合那些数据插入操作远多于数据更新删除操作与读操作的场景，同时Druid在一开始就是为时序数据场景设计的，而该场景正好符合LSM-tree的优势特点，因此Druid架构便顺理成章地吸取了LSM-tree的思想。
Druid的类LSM-tree架构中的实时节点（Realtime Node）负责消费实时数据，与经典LSM-tree架构不同的是，Druid不提供日志及实行WAL原则，实时数据首先会被直接加载进实时节点内存中的堆结构缓存区(相当于memtable)，当条件满足时，缓存区里的数据会被冲写到硬盘上形成一个数据块(Segment Split)，同时实时节点又会立即将新生成的数据块加载到内存中的非堆区，因此无论是堆结构缓存区还是非堆区里的数据，都能够被查询节点（Broker Node）查询。
图：实时节点数据块的生成示意图
同时，实时节点会周期性地将磁盘上同一个时间段内生成的所有数据块合并为一个大的数据块（Segment）。这个过程在实时节点中叫作SegmentMerge操作，也相当于LSM-tree架构中的数据合并操作（Compaction）。合并好的Segment会立即被实时节点上传到数据文件存储库（DeepStorage）中，随后协调节点（CoordinatorNode）会指导一个历史节点（Historical Node）去文件存储库，将新生成的Segment下载到其本地磁盘中。当历史节点成功加载到Segment后，会通过分布式协调服务（Coordination）在集群中声明其从此刻开始负责提供该Segment的查询，当实时节点收到该声明后也会立即向集群声明其不再提供该Segment的查询，接下来查询节点会转从该历史节点查询此Segment的数据。而对于全局数据来说，查询节点会同时从实时节点（少量当前数据）与历史节点（大量历史数据）分别查询，然后做一个结果的整合，最后再返回给用户。Druid的这种架构安排实际上也在一定程度上借鉴了命令查询职责分离模式（Command Query Responsibility Segregation，CQRS）——这也是Druid不同于HBase等LSM-tree系架构的一个显著特点。Druid对命令查询职责分离模式（CQRS）的借鉴如下图。
图：Druid对命令查询职责分离模式（CQRS）的借鉴
Druid的上述架构特点为其带来了如下显著的优势：
- 类LSM-tree架构使得Druid能够保证数据的高速写入，并且能够提供比较快速的实时查询，这十分符合许多时序数据的应用场景。
- 由于Druid在设计之初就不提供对已有数据的更改，以及不实现传统LSM-tree架构中普遍应用的WAL原则，虽然这样导致了Druid不适应于某些需要数据更新的场景，也降低了数据完整性的保障，但Druid相对其他传统的LSM-tree架构实现来说也着实减少了不少数据处理的工作量，因此让自己在性能方面更胜一筹。
- Druid对命令查询职责分离模式的借鉴也使得自己的组件职责分明、结构更加清晰明了，方便针对不同模块进行针对性的优化。
基于DataSource与Segment的数据结构
与Druid架构相辅相成的是其基于DataSource与Segment的数据结构，它们共同成就了Druid的高性能优势。
1. DataSource结构
若与传统的关系型数据库管理系统（RDBMS）做比较，Druid的DataSource可以理解为RDBMS中的表（Table）。正如前面章节中所介绍的，DataSource的结构包含以下几个方面：
- 时间列（TimeStamp）：表明每行数据的时间值，默认使用UTC时间格式且精确到毫秒级别。这个列是数据聚合与范围查询的重要维度。
- 维度列（Dimension）：维度来自于OLAP的概念，用来标识数据行的各个类别信息。
- 指标列（Metric）：指标对应于OLAP概念中的Fact，是用于聚合和计算的列。这些指标列通常是一些数字，计算操作通常包括Count、Sum和Mean等。
DataSource结构如图下。
无论是实时数据消费还是批量数据处理，Druid在基于DataSource结构存储数据时即可选择对任意的指标列进行聚合（RollUp）操作。该聚合操作主要基于维度列与时间范围两方面的情况：
- 同维度列的值做聚合：所有维度列的值都相同时，这一类行数据符合聚合操作，比如对于所有维度组合”publisher、advertiser、gender、country”维度值同为”http://ultratrimfast.com、http://google.com、Male、USA”或同为”http://bieberfever.com、http://google.com、Male、USA”的行。
- 对指定时间粒度内的值做聚合：符合参数queryGranularity指定的范围，比如时间列的值为同1分钟内的所有行，聚合操作相当于对数据表所有列做了Group By操作，比如”GROUP BY timestamp, publisher, advertiser, gender, country :: impressions = COUNT(1), clicks = SUM(click), revenue = SUM(price)“。下图显示的是执行聚合操作后DataSource的数据情况。
图：DataSource聚合后的数据情况
相对于其他时序数据库，Druid在数据存储时便可对数据进行聚合操作是其一大特点，该特点使得Druid不仅能够节省存储空间，而且能够提高聚合查询的效率。
2. Segment结构
DataSource是一个逻辑概念，Segment却是数据的实际物理存储格式，Druid正是通过Segment实现了对数据的横纵向切割（Slice and Dice）操作。从数据按时间分布的角度来看，通过参数segmentGranularity的设置，Druid将不同时间范围内的数据存储在不同的Segment数据块中，这便是所谓的数据横向切割。这种设计为Druid带来一个显而易见的优点：按时间范围查询数据时，仅需要访问对应时间段内的这些Segment数据块，而不需要进行全表数据范围查询，这使效率得到了极大的提高。
图：通过Segment将数据按时间范围存储
同时，在Segment中也面向列进行数据压缩存储，这便是所谓的数据纵向切割。而且在Segment中使用了Bitmap等技术对数据的访问进行了优化。