小编说：Druid 的目标是提供一个能够在大数据集上做实时数据消费与探索的平台。对普遍的数据平台来说，数据的高效摄入与快速查询往往是一对难以两全的指标，但Druid 是怎么做到的呢？这很大程度上得益于其独到的架构设计和基于DataSource 与Segment 的数据结构。 本文选自《Druid实时大数据分析原理与实践》。
对于目前大多数Druid 的使用场景来说，Druid 本质上是一个分布式的时序数据库，而对于一个数据库的性能来说，其数据的组织方式至关重要。为了更好地阐述Druid 的架构设计思想，我们得先从数据库的文件组织方式聊起。
众所周知，数据库的数据大多存储在磁盘上，而磁盘的访问相对内存的访问来说是一项很耗时的操作，对比如下。因此，提高数据库数据的查找速度的关键点之一便是尽量减少磁盘的访问次数。
磁盘与内存的访问速度对比
为了加速数据库数据的访问，大多传统的关系型数据库都会使用特殊的数据结构来帮助查找数据，这种数据结构叫作索引（ Index）。对于传统的关系型数据库，考虑到经常需要范围查找某一批数据，因此其索引一般不使用 Hash算法，而使用树（ Tree）结构。然而，树结构的种类很多，却不一定都适合用于做数据库索引。
- 索引对树结构的选择
1. 二叉查找树与平衡二叉树
最常见的树结构是二叉查找树（ Binary Search Tree），它就是一棵二叉有序树：保证左子树上所有节点的值都小于根节点的值，而右子树上所有节点的值都大于根节点的值。其优点在于实现简单，并且树在平衡的状态下查找效率能达到 O(logଶ)；缺点是在极端非平衡情况下查找效率会退化到 O()，因此很难保证索引的效率。
二叉查找树的查找效率
针对上述二叉查找树的缺点，人们很自然就想到是否能用平衡二叉树（ Balanced Binary Tree）来解决这个问题。但是平衡二叉树依然有个比较大的问题：它的树高为 logଶ——对于索引树来说，树的高度越高，意味着查找所要花费的访问次数越多，查询效率越低。
况且，主存从磁盘读数据一般以页为单位，因此每次访问磁盘都会读取多个扇区的数据
（比如 4KB大小的数据），远大于单个二叉树节点的值（字节级别），这也是造成二叉树相对索引树效率低下的原因。正因如此，人们就想到了通过增加每个树节点的度来提高访问效率，而 B 树（B -tree）便受到了更多的关注。
2. B 树
在传统的关系型数据库里， B 树（ B -tree）及其衍生树是被用得比较多的索引树。
B 树
B 树的主要特点如下。
- 每个树节点只存放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。
- 叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询；并且所有叶子节点与根节点的距离相同，因此任何查询的效率都很相似。
- 与二叉树不同， B 树的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。
正是由于 B 树的上述优点，它成了传统关系型数据库的宠儿。当然，它也并非无懈可击，它的主要缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘 IO，以致严重影响到性能。
3. 日志结构合并树
众所周知，数据库的数据大多存储在磁盘上，而无论是传统的机械硬盘（ HardDiskDrive, HDD）还是固态硬盘（ Solid State Drive, SSD），对磁盘数据的顺序读写速度都远高于随机读写。
磁盘顺序与随机访问吞吐对比
然而，基于 B 树的索引结构是违背上述磁盘基本特点的——它会需要较多的磁盘随机读写，于是， 1992年，名为日志结构（ Log-Structured）的新型索引结构方法便应运而生。日志结构方法的主要思想是将磁盘看作一个大的日志，每次都将新的数据及其索引结构添加到日志的最末端，以实现对磁盘的顺序操作，从而提高索引性能。不过，日志结构方法也有明显的缺点，随机读取数据时效率很低。 1996年，一篇名为 Thelog-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 QueryResponsibility 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结构如图下。
DataSource结构
无论是实时数据消费还是批量数据处理， Druid在基于 DataSource结构存储数据时即可选择对任意的指标列进行聚合（ RollUp）操作。该聚合操作主要基于维度列与时间范围两方面的情况。
- 同维度列的值做聚合：所有维度列的值都相同时，这一类行数据符合聚合操作，比如对于所有维度组合“publisheradvertisergendercountry”维度值同为“ultratrimfast.com google.com Male USA”或同为“bieberfever.com 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等技术对数据的访问进行了优化。
