阿里巴巴时序数据库——Timon
背景
- 能见度延迟：新数据在流系统中聚合时，会有一定延迟；
- 读-修改-写：需要一个 ReadModifyWrite 操作来读取和更新外部存储上以前聚合的值。
- 大规模长期事件分析：场景为大规模海量数据接入通道。
解决办法
- 将窗口操作和无序处理下放到存储层；
- blind-write方式相较于读修改写处理无序事件具有更多优势；
- 结合LSM树和分段树结合提出了TS-LSM树；
- 用户友好工具和设施。
盲写
大量数据从终端发送到计算节点，但是我们保证正确的消息至少被传输一次。部分迟到的数据到来的时候，需要应用程序正确处理这些乱序的数据。
常见的两种处理方法
- 简单地丢弃无序事件
- 读-修改-写：以前处理过的窗口的结果需要从外部存储中获取。在与新到达的无序事件合并后，更新后的结果将被写回到存储中。
本文解决办法
当一个乱序的时间戳记录到达时，它将被转换成这些结构中的一个或多个，并定期与以前的结果合并。
Timon 中支持一组关联和交换运算符，包括sum、max、 min、avg、分位数、stddev和distinct。
幂等性：对于用户对于同一操作发起的多次请求的结果是一致的，不会由于点击次数不同而产生副作用。
在盲写和运算符满足关联和交换性质下，我们只需要将聚合值存储在Timon中。如果在写入数据点时发生故障转移，我们必须删除已成功写入的点。否则，聚合值将包含同一点两次。
消息在消息队列中被划分为多个分区，每个记录都被分配了一个offset的本地顺序标识符，对于每个分区流式处理会在偏移量上按升序读取消息。
Timon 保留每个分区遇到的最大偏移量。这样，通过将其偏移量与当前最大值进行比较，可以很容易地检测到重复的消息，这使得整个过程是原子的，以确保一致性。
系统设计
每一行都包含时间戳、度量集 中的值以及相应标记集中的值。
- Write Module：通过元数据模块将标签映射到UUID，根据UUID的哈希值将(UUID，流集)发送到阶段队列；
- 内存模块：将数据插入TS-LSM树中的WALs和MemTables；
- 存储模块：在MemTables已满，存储模块会刷新到磁盘。
标签和流集分开存储。它们的关系由元数据模块管理，该模块将标签映射到 UUIDs(即。流集)。
详细设计
Timon将所有数据划分为多个分区，每个分区由一个内存模块和一个存储模块进行管理。
TSLM树
如果事件时间至少比上次刷新表的结束时间早一个指定时间，它将被放入后期事件记忆表。通常来说这个时间称为等待时间。
MemTable
MemTable 的目标：以低成本执行热数据聚合。
page是内存表中的基本内存管理单元，最多可以存储 600 条记录。分区中的每个活动UUID至少有一页page，同一个page中的所有记录都来自于同一个UUID。新到达的记录被附加到相应的页面上，没有排序。当一个页面已满时，它将会聚合，这意味着该页面中的所有记录都按时间戳排序，具有相同时间戳的记录将被聚合。
所有新到达的带有时间戳的时间，首先会存储在MemTable的内存结构中。
在这里不需要事先排序，直接乱序插入即可，插入之后再进行排序的过程。
在这个阶段，由于元素没有排序，需要扫描整个页面来查询。由于在Timon中页面的长度是固定的，所以未密封页面的扫描成本仍然是有限的(尽管延迟很高)。
SSTable
内存中的数据会定期的flush成SSTable，内存中的page对应于block。一个SSTable中包含很多block，按时间戳排序，并且没有overlap，这样可以精准查询，因为late单独存，所以没有overlap。为了避免有太多的小表文件，它们将被定期合并，这就是所谓的压缩过程。一个表由多个块组成，每个块存储多达 600 个具有相同 UUID 的序列化记录，类似于内存页。
SSTable由四部分组成：元区域、桶区域、碰撞区域和数据区域
- 元区域记录表的元信息，例如所包含记录的最小和最大时间戳；
- 桶区域和碰撞区域是一个持久化哈希映射，将UUID映射到其时间序列描述，描述包含相应时间序列的摘要信息。对于每个UUID， 其时间序列数据存储在数据区中，该数据区由时间划分树和多个块组成。
一个表可能包含大量UUIDs，持久哈希映射的帮助下，可以在常数时间内完成表中的 UUID 查找。
层次结构中的每一层都以更精细的粒度提供了时间跨度的分解，也为其数据项提供了更精细的分辨率。将数据项和索引分开，索引节点中只有索引和摘要信息。
时间索引树本质上是一个左完备的 K 元树，其中除了最右边的节点之外，每个节点都有 K 个子节点。
惰性合并
由于时间戳数据乱序的比例比较小，但是时间跨度比较大，给现有数据库带来很大的挑战。这乱序的数据高度碎片化并且不紧凑，导致随机磁盘IO性能下降。
为了解决这个问题，设计了一个延迟到达记录模块，将延迟到达的记录识别为异常，在刷新操作阶段，异常值将转移到单独的后期表中。这样就可以实现标准表的时间范围比较紧凑，尽管延迟表的时间跨度很大，但是由于延迟表的数目较少，因此延迟表总数很少。
并非所有的无序事件都放在“延迟表”中。只有在最后一次刷新表的结束时间之前至少等待一段时间的事件才会被放入延迟记忆表，该表被刷新为延迟记忆表。这样可以避免Late SSTable的快速增长。
将延迟到达的数据单独进行存放，然后在后期查找的时候降低扫描标准表的时间复杂度。
查询性能。盲写可以解决无序事件的问题。但是，它将数据合并的计算交给了查询层，降低了查询性能。