【博客481】prometheus-----数据压缩算法与搜索算法

prometheus-----数据压缩算法与搜索算法

压缩算法（Gorilla）

timestamp的压缩：

value的压缩：

优势：

将一个16byte(8字节的timestamp + 8字节的value)的数据点压缩后，大小仅为1.37byte

倒排索引

怎么快速找到某个或某几个标签(非全部标签)的数据呢。这就需要引入以Label为key的倒排索引。我们先给出一组标签集合

{__name__:http_requests}{group:canary}{instance:0}{job:api-server}   
{__name__:http_requests}{group:canary}{instance:1}{job:api-server}
{__name__:http_requests}{group:production}{instance:1}{job,api-server}
{__name__:http_requests}{group:production}{instance:0}{job,api-server}
1
2
3
4

倒排索引引入的原因：

可以看到，由于标签取值不同，我们会有四种不同的memSeries。如果一次性给定4个标签，应该是很容易从map中直接获取出对应的memSeries(尽管Prometheus并没有这么做)。但大部分我们的promql只是给定了部分标签，如何快速的查找符合标签的数据呢？这就引入倒排索引。

注意，这边倒排索引存储的refId必须是有序的。这样，我们就可以在O(n)复杂度下顺利的算出交集,另外，针对其它请求形式，还有并集/差集的操作。

正则支持

事实上，给定特定的Label:Value还是无法满足我们的需求。我们还需要对标签正则化，例如取出所有ip为1.1.*前缀的http_requests监控数据。为了这种正则，Prometheus还维护了一个标签所有可能的取值

组合查询

如果查询的语句是：__name __ =“requests_total” AND app =“nginx”，那么分别找出对应的倒排索引：

那么再求交集，这个复杂度不是 O(N2）了吗？这里 TSDB 又做了一个优化，就是保证在 Index 中，倒排索引中的 SeriesID 是有序的，如果双方的 SereisID 都是有序的，那么可以保证在 O(N) 的时间复杂来找到最终的结果，只要从小的那个出发一直双向遍历，遇到大的不符合就停止了，因为后面肯定就都不符合了。然后在前面的数据里找到符合的就好了
这里有个难点就是保证 Label 的倒排索引中的 SeriesID 是有序的，TSDB 对此的处理方式是只有在 Index 被完全读入内存的情况下，才会写出这个 Index 文件，而这通常在两种情况下出现，分别是 写出内存WAL 和 压缩持久数据 的时候。