从零写一个时间序列数据库

研究存储改造的最初设法是办理序列分流的题目。基于块的机关镌汰了查询所要思量的序列总数。因此假设我们索引查找的伟大度是 O(n^2)，我们就要想法镌汰 n 个相等数目的伟大度，之后就相等于改造 O(n^2) 伟大度。——恩，等等……糟糕。

快速回首一下“算法 101”课上提示我们的，在理论上它并未带来任何甜头。假如之前就很糟糕，那么此刻也一样。理论是云云的残忍。

现实上，我们大大都的查询已经可以相等快相应。可是，超过整个时刻范畴的查询如故很慢，尽量只必要找到少部门数据。追溯到全部这些事变之前，最初我用来办理这个题目的设法是：我们必要一个更大容量的倒排索引。

倒排索引基于数据项内容的子集提供了一种快速的查找方法。简朴地说，我可以通过标签 app="nginx" 查找全部的序列而无需遍历每个文件来看它是否包括该标签。

为此，每个序列被赋上一个独一的 ID ，通过该 ID 可以恒按时刻内检索它（O(1)）。在这个例子中 ID 就是我们的正向索引。

示例：假如 ID 为 10、29、9 的序列包括标签 app="nginx"，那么 “nginx”的倒排索引就是简朴的列表 [10, 29, 9]，它就能用来快速地获取全部包括标签的序列。纵然有 200 多亿个数据序列也不会影响查找速率。

简而言之，假如 n 是我们序列总数，m 是给定查询功效的巨细，行使索引的查询伟大度此刻就是 O(m)。查询语句依据它获取数据的数目 m 而不是被搜刮的数据体 n 举办缩放是一个很好的特征，由于 m 一样平常相等小。

为了简朴起见，我们假设可以在恒按时刻内查找到倒排索引对应的列表。

现实上，这险些就是 V2 存储体系具有的倒排索引，也是提供在数百万序列中查询机能的最低需求。敏锐的人会留意到，在最坏环境下，全部的序列都含有标签，因此 m 又成了 O(n)。这一点在预料之中，也相等公道。假如你查询全部的数据，它天然就会耗费更多时刻。一旦我们扳连上了更伟大的查询语句就会有题目呈现。

标签组合

与数百万个序列相干的标签很常见。假设横向扩展着数百个实例的“foo”微处事，而且每个实例拥稀有千个序列。每个序列城市带有标签 app="foo"。虽然，用户凡是不会查询全部的序列而是会通过进一步的标签来限定查询。譬喻，我想知道处究竟例吸取到了几多哀求，那么查询语句即是 __name__="requests_total" AND app="foo"。

为了找到满意两个标签选择子的全部序列，我们获得每一个标签的倒排索引列表并取其交集。功效集凡是会比任何一个输入列表小一个数目级。由于每个输入列表最坏环境下的巨细为 O(n)，以是在嵌套地为每个列表举办暴力争解brute force solution下，运行时刻为 O(n^2)。沟通的本钱也合用于其他的荟萃操纵，譬喻取并集（app="foo" OR app="bar"）。当在查询语句上添加更多标签选择子，淹灭就会指数增添到 O(n^3)、O(n^4)、O(n^5)……O(n^k)。通过改变执行次序，可以行使许多能力以优化运行服从。越伟大，越是必要关于数据特性和标签之间相干性的常识。这引入了大量的伟大度，可是并没有镌汰算法的最坏运行时刻。

这即是 V2 存储体系行使的根基要领，荣幸的是，看似细小的窜改就能得到明显的晋升。假如我们假设倒排索引中的 ID 都是排序好的会怎么样？

假设这个例子的列表用于我们最初的查询：

__name__="requests_total"   ->   [ 9999, 1000, 1001, 2000000, 2000001, 2000002, 2000003 ]
     app="foo"              ->   [ 1, 3, 10, 11, 12, 100, 311, 320, 1000, 1001, 10002 ]
 
             intersection   =>   [ 1000, 1001 ]

它的交集相等小。我们可觉得每个列表的起始位置配置游标，每次从最小的游标处移动来找到交集。当二者的数字相称，我们就添加它到功效中并移动二者的游标。总体上，我们以锯齿形扫描两个列表，因此总淹灭是 O(2n)=O(n)，由于我们老是在一个列表上移动。

两个以上列表的差异荟萃操纵也相同。因此 k 个荟萃操纵仅仅改变了因子 O(k*n) 而不是最坏环境下查找运行时刻的指数 O(n^k)。

我在这里所描写的是险些全部全文搜刮引擎行使的尺度搜刮索引的简化版本。每个序列描写符都视作一个简短的“文档”，每个标签（名称 + 牢靠值）作为个中的“单词”。我们可以忽略搜刮引擎索引中凡是碰着的许多附加数据，譬喻单词位置和和频率。

关于改造现实运行时刻的要领好像存在无限无尽的研究，它们凡是都是对输入数据做一些假设。不出料想的是，尚有大量技能来压缩倒排索引，个中各有利弊。由于我们的“文档”较量小，并且“单词”在全部的序列里大量一再，压缩变得险些无关紧急。譬喻，一个真实的数据集约有 440 万个序列与约莫 12 个标签，每个标签拥有少于 5000 个单独的标签。对付最初的存储版本，我们僵持行使根基的要领而不压缩，仅做细小的调解来跳过大范畴非交错的 ID。

尽量维持排序好的 ID 听起来很简朴，但实践进程中不是总能完成的。譬喻，V2 存储体系为新的序列赋上一个哈希值来看成 ID，我们就不能等闲地排序倒排索引。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!