写点什么

时序数据库中的乱序问题 - 写不动的老程序员带你解读

作者:Greptime
  • 2023-05-15
    美国
  • 本文字数:2986 字

    阅读完需:约 10 分钟

时序数据库中的乱序问题-写不动的老程序员带你解读

时序数据库是为时序数据而设计的领域数据库,具有高效的并发写入、数据压缩和查询性能。随着物联网设备的普及,大量的时序数据被产生和收集,欢迎阅读时序数据库是什么了解更多。


时序数据库在优化方面是针对时序场景特点权衡来的,比如写入多,更新和删除少,数据按照时间顺序写入等等。理想情况下,我们认为数据都是实时顺序写入的,可是在真实的世界中,往往要复杂很多,并不能完全保证数据是顺序写入的,数据往往会因为传感器故障、网络延迟等原因出现乱序,给时序数据库带来一些挑战,比如:


  1. 数据插入与更新:乱序数据会导致数据插入与更新操作变得复杂,影响写入性能。

  2. 数据压缩:乱序数据可能影响数据压缩算法的效果,增加存储空间的需求。

  3. 查询性能:乱序数据可能导致查询性能下降,增加计算资源的消耗。


为了更好的说明,这里先解释一下什么是乱序数据。时序场景中,通常有数据生成端和接收端,数据从生成端到达接收端会有一定延迟,如果说接收的数据序列和生成的数据序列一致,则是顺序接收,若存在先生成的数据后接收,一般就认为出现了乱序数据,具体如下图:



上图中 Point1 就是一个乱序数据。


很多的时序数据库在存储模型上会采用 LSMT(log-structured merge-tree)[1],这是由 Patrick O'Neil 等人在 1996[2] 年提出在持续不断高并发写入(和删除)的场景下,基于磁盘、满足实时低成本索引的 key-value 数据结构。这种数据结构和时序场景非常符合,持续高并发写入,时间维度有序。GreptimeDB 存储引擎[3]也采用了 LSM Tree,一个简化的结构图如下:



LSM Tree 的主要结构由:


  • MemTable: 一个有序的内存数据结构,工程上,通常会用 Skip List 实现,也有用 B-Tree 实现

  • Immutable MemTable: 和 MemTable 是一样的有序的内存数据结构,唯一不同是只读,当 MemTable 达到其大小限制时创建

  • SSTable(Sorted String Table): 与 Immutable MemTable 类似,只读有序的数据结构,但持久化在了磁盘,主流实现一般是将 Immutable MemTable 直接写入磁盘


为了查询和存储效率,往往还会对 SSTable 做 Compaction,Compaction 操作中通常会将同一层的 SSTable 块再归并,生成新的时间跨度的 SSTable 作为 L+1 层,可能还会做其他的优化,比如降精度以节省空间等。


为了更好的理解,这里我们不做证明的引用两个事实前提[4]


  • Skip List 的实现中,插入一条数据的平均时间复杂度是 O(logN) ;

  • Skip List 的实现中,查找一条数据的平均时间复杂度是 O(logN);其中 N 是指一个 Memtable 中可以包含的最大 KV 对。


接下来,我们回到乱序数据的问题,在 LSM Tree 模型下,到底如何处理乱序数据呢?


所谓处理乱序数据,最终要的效果是:查询的时候,可以将数据按照时间顺序返回,无论当时接收的时候是否是有序接收


在理想情况下,假设时序数据都是按时间采集并且有序接收并写入到数据库内,那就不用做任何其他操作,直接写入即可,写入复杂度就是 O(logN),这时候每个 SSTable 都是文件内有序,文件之间也有序,不存在 overlap。当查询的时候,比如查询某个时间范围内的数据,只需要将和查询时间范围有交集的 SSTable 取出来(可能包含 Immutable Memtable 和 Memtable),在第一个和最后一个 SSTable 文件查询,找到起点和终点,接下来就是将文件的内容串联拼接,时间复杂度可以控制在 O(2* logN + k), k 为常数。关于如何更快的拷贝数据到内存中并返回了,就不再这里赘述。(当然在这种理想世界里面,完全可以用一个 append-only 的数据结构做到写入 O(1) 的时间复杂度)。


而真实世界是充满不确定性,乱序数据总会存在,从上面的情况就能看出来,SSTable 就无法保障文件间的绝对有序。特别是在 L0 层。那到底会产生什么影响呢?当我们无法保障 SSTable 之间是有序的,那最糟糕的情况下,查询的时候,需要将所有和查询时间有交集的 SSTable 做多路归并,常规算法(最小堆多路归并)的时间复杂度就在 O(N* logM),其中 N 是 K-V 所有待返回的数据点,而 M 是 SSTable 个数。所以相比理想情况下的 O(k* logN) 时间复杂度要高很多。


好在真实世界始终是善良的,并不总是出现最糟糕的情况。那不同情况下的乱序数据,对查询有什么影响呢?



  • Case 1: 乱序数据的时间戳只在 t3 ~ t4 间,也就是 MemTable 层: 这种情况和理想情况是一样的,因为 MemTable 本身就是有序数据,当有乱序数据进来时,在写入时刻就会进行排序。

  • Case 2: 乱序数据的时间戳在 t2 ~ t3 间,也就是可能在 Immutable MemTable 层: 这种情况和 Case1 类似,在查询时只需要将 MemTable 和 Immutable MemTable 同时读取,做归并排序即可,都在内存中操作,而且数据块不多,所以影响也不大。

  • Case 3: 乱序数据的时间戳在 t1 ~ t2 间,这就比较麻烦了,因为涉及到了磁盘上的存储,一方面可能涉及到的要归并的数据文件比较多,另外也又有磁盘 I/O 的操作。

  • Case 4: 乱序数据的时间戳在 t0 ~ t1 间,这种情况和 Case3 类似,但会更麻烦了,相当于在 L1 层 SSTable 也无法保证数据文件间有序,也就是需要处理的归并排序操作增多。


简单来讲,归并操作越多,磁盘操作越多,性能损耗和资源利用代价就越高。而乱序数据的不同情况,主要牵涉到的也是这两个维度。


知道了原因,也就可以做相应的优化,比如最简单是在产品上做设定,只允许短时间内的乱序数据写入,也就是让乱序数据发生在 Case 1 和 Case2 内,之外的数据就丢弃不处理,对于时序场景而言,可能已经可以满足大部分情况了。当然了,在非常严格的场景下,必须得满足到 Case4 层面的乱序数据处理,也可以在细节中优化,比如当新数据到达时,如果与最新数据的时间戳相差较大,可以考虑写入另外一个 MemTable 中,延迟写入到磁盘中,从而降低归并操作的频率,但还是会牺牲查询性能。这就是功能与性能的权衡。


在时序数据库中,也有不使用 LSM Tree 模型的,比如 TimescaleDB 是基于 PostgreSQL 的,在处理乱序数据的时候是利用自己的 hypertable 和 PG 自带的能力,相对会受限较多。GreptimeDB 是基于 LSM Tree 模型的时序数据库,原生就支持乱序数据的写入,同时为了保障用户的场景可以更丰富,我们也在不断优化不同情况下乱序数据的处理方式,会在之后的文章中分享,敬请关注。

参考

[1] https://en.wikipedia.org/wiki/Log-structured_merge-tree

[2] https://www.cs.umb.edu/~poneil/lsmtree.pdf

[3] https://greptime.com/blogs/2022-12-21-storage-engine-design

[4] https://en.wikipedia.org/wiki/Skip_list




关于 Greptime

Greptime 格睿科技于 2022 年创立,目前正在完善和打造时序数据库 GreptimeDB 和格睿云 GreptimeCloud 这两款产品。

GreptimeDB 是款用 Rust 语言编写的时序数据库。具有分布式,开源,云原生,兼容性强等特点,帮助企业实时读写、处理和分析时序数据的同时,降低长期存储的成本。

GreptimeCloud 基于开源的 GreptimeDB,为用户提供全托管的 DBaaS,以及与可观测性、物联网等领域结合的应用产品。利用云提供软件和服务,可以达到快速的自助开通和交付,标准化的运维支持,和更好的资源弹性。GreptimeCloud 已正式开放内测,欢迎关注公众号或官网了解最新动态!

官网:https://greptime.com/

公众号:GreptimeDB

GitHub: https://github.com/GreptimeTeam/greptimedb

文档:https://docs.greptime.com/

Twitter: https://twitter.com/Greptime

Slack: https://greptime.com/slack

LinkedIn: https://www.linkedin.com/company/greptime/


用户头像

Greptime

关注

专注于 Infra 技术分享 2022-09-23 加入

分布式、高性能、存储计算分离的开源云原生时序数据库

评论

发布
暂无评论
时序数据库中的乱序问题-写不动的老程序员带你解读_云原生_Greptime_InfoQ写作社区