dot Redis 8 已发布，并且它是开源的

了解更多
White Redis Logo 返回
搜索

t-digest: Redis Stack 中的一种新型概率数据结构

LinkedIn-icon
分享
LinkedIn-icon分享到 LinkedIn
Lior Kogan, Principal Product Manager, Redis

Lior Kogan

Pieter Cailliau, Director of Product Management, Redis

Pieter Cailliau

随着最新版本 Redis Stack 的推出，我们迎来了一种新型概率数据结构：t-digest。 

当您的输入是一系列测量值（例如温度或服务器延迟）时，您可以使用 t-digest 高效地估计百分位数（例如，第 50th、90th 和 99th 百分位数）。这只是一个例子；我们在下面会解释更多用途。

对 t-digest 的支持扩展了 Redis Stack 的现有功能及其对数据模型和处理引擎的支持，其中包括 RedisInsight、搜索和查询、JSON、时序数据 和 概率数据结构。

在此，我们将解释什么是 t-digest，何时是使用它的好时机，以及如何使用它。

Redis 中的概率数据结构

Redis 已经有很多概率数据结构：HyperLogLog、Bloom filter、Cuckoo filter、Count-min sketch 和 Top-k。您可以使用它们来回答关于数据流和大型数据集的常见问题：

  • 数据流中出现了多少个唯一值？(HyperLogLog)
  • 值 v 是否出现在数据流中？(Bloom filter 和 Cuckoo filter)
  • 值 v 在数据流中出现了多少次？(Count-min sketch)
  • 数据流中出现频率最高的 k 个值是什么？(Top-k)

获取精确答案可能需要大量的内存。但是，如果您愿意牺牲准确性，则可以大幅降低内存需求。这些数据结构中的每一个都允许您在准确性和内存消耗之间进行可控的权衡。除了需要更小的内存占用外，概率数据结构通常比精确算法快得多。

正如您所见，概率数据结构真的很有趣！（好吧，至少对软件开发者来说是这样。）

什么是 t-digest？

t-digest 是一种概率数据结构，可以帮助您回答以下问题：

  • 数据流中有多大比例的值小于给定值？
  • 数据流中有多少个值小于给定值？
  • 数据流中有百分之 p 的值小于哪个值？什么是 p 百分位值？
  • p1 百分位值和 p2 百分位值之间的平均值是多少？
  • 数据流中第 nth 小（或最大）值是什么？[反向] 排名为 n 的值是什么？

Ted Dunning 于 2013 年首次引入了 t-digest，并在多篇出版物中进行了描述：

实际上，t-digest 在很多方面都很有帮助。以下是一些场景：

硬件/软件监控 

您正在测量在线服务器的响应延迟，并想知道

  • 测量延迟的第 50th、90th 和 99th 百分位数是多少？
  • 有多少百分比的测量延迟低于 5 毫秒？
  • 忽略异常值后的平均延迟是多少？或者更准确地说：第 10 百分位数和第 90 百分位数之间的平均延迟是多少？

在线游戏

数百万人正在您的在线平台上玩游戏。您想为每位玩家提供以下信息：

  • 您的得分优于 x% 的游戏会话
  • 大约在 y 个游戏会话中，人们的得分高于您
  • 要得分优于 90% 的游戏会话，您的得分应该是 z

网络流量监控

您正在测量网络上传输的每秒 IP 数据包数量。您想快速检测潜在的拒绝服务攻击。您可能需要查询：

  • 最后一秒的数据包数量是否超过了之前观察到的值的 99.9%？
  • 在正常网络条件下，我预计会看到多少数据包——例如，在 0.5 百分位和 99.5 百分位之间？

预测性维护

您正在测量机器的读数，例如噪音水平或电流消耗。为了检测可疑行为，您可以查询：

  • 测量的参数是否异常？也就是说，它是否超出了 [1st 百分位 … 99th 百分位] 的范围？或者，添加您的逻辑：在过去一小时内，测量的参数是否异常了至少 10 秒？
  • 我应该将警报设置为哪些值？

没有 t-digest，我就不能做所有这些吗？

当然可以。但 t-digest 使其更容易。让我们比较一下使用前后的场景。

假设您想测量您运营的网站的 HTTP 请求延迟。HTTP 延迟是指从用户发出请求到响应返回给该用户所需的时间）。 

延迟因多种因素而差异很大，因此通常测量延迟的第 50th、90th 和 99th 百分位数。简单来说，一半的请求在低于第 50th 百分位数的时间内得到服务，90% 的请求在低于第 90th 百分位数的时间内得到服务，依此类推。

没有 t-digest，您将如何确定这些统计数据？最简单的方法是将所有测量的延迟（每天可能有数百万或数十亿）存储在一个排序数组中。例如，要检索第 90th 百分位数，您需要从排序数组中读取索引等于其大小的 90% 的值。可以使用更复杂的数据结构和算法，但这通常需要在给定的一组假设下进行，例如延迟范围和分辨率、其分布以及将被查询的固定百分位数集合。

使用 t-digest，则无需此类假设。此外，内存占用很小，并且添加和查询数据非常快速。

那么有什么不足之处呢？您需要准备好容忍估计中一个非常小的（通常可以忽略不计的）相对误差。在绝大多数与统计相关的场景中，估计器中的小误差是可以接受的。

如何使用 t-digest？

让我们来看看实际操作，了解它是如何工作的。 

让我们继续 HTTP 请求延迟的示例。一种选择是使用 TDIGEST.CREATE 创建一个 t-digest，然后使用 TDIGEST.ADD 添加观察值（或者如果您更喜欢，称为测量值）。

TDIGEST.CREATE key [COMPRESSION compression] 

这将初始化一个新的 t-digest 数据结构（如果键已存在则会报错）。COMPRESSION 参数指定了准确性和内存消耗之间的权衡。默认值为 100。值越高表示准确性越高。

要将新的浮点值（观察值）添加到 t-digest，请使用

TDIGEST.ADD key value [value ...]

例如，要创建一个名为 t、压缩设置为 1000（非常准确）的 digest，并添加 15 个观察值，我们可以输入：

TDIGEST.CREATE t COMPRESSION 1000
TDIGEST.ADD t 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5

只要有新的观察值，您就可以重复调用 TDIGEST.ADD。要按分位或排名估算值，请使用 TDIGEST.QUANTILE

TDIGEST.QUANTILE key quantile [quantile …] 

对于每个输入的分位，它返回一个值（浮点数）的估计，该值小于给定比例的观察值。换句话说，分位 0.9 相当于第 90th 百分位数。

以下查询检索小于 0%、10%、20%、…、100% 已观察延迟的延迟值：

TDIGEST.QUANTILE t 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
1) "1"
2) "2"
3) "3"
4) "3"
5) "4"
6) "4"
7) "4"
8) "5"
9) "5"
10) "5"
11) "5"

该查询包含 11 个分位；因此回复是一个包含 11 个延迟值的数组。

当分位为 0 (0%) 时，结果是最小的观察值——在本例中为 1。类似地，当分位为 1 (100%) 时，结果是最大的观察值（在本例中为 5）。对于这两个分位，结果总是准确的。任何其他分位的结果都是估计值。

您可以看到，10% 的延迟小于或等于 2；20% 和 30% 的延迟小于或等于 3；40%、50% 和 60% 的延迟小于或等于 4；最后，70%、80%、90% 和 100% 的延迟小于或等于 5。

您还可以查询前 n 个最小的测量延迟。为此，请使用 TDIGEST.BYRANK。

TDIGEST.BYRANK key rank [rank …]

对于每个输入的排名，它返回具有该排名的值（浮点数）的估计。

以下查询检索第一个、第二个、… 和第九个最小的观察延迟：

TDIGEST.BYRANK t 0 1 2 3 4 5 6 7 8 9
1) "1"
2) "2"
3) "2"
4) "3"
5) "3"
6) "3"
7) "4"
8) "4"
9) "4"
10) "4"

该查询包含 10 个排名；因此回复是一个包含 10 个值的数组。

当排名为 0 时，结果是最小的观察值（本例中为 1）。类似地，当排名等于观察值数量减一时，结果是最大的观察值。对于这两个排名，结果总是准确的；任何其他排名的结果都是估计值。当排名等于或大于观察值数量时，结果为 inf。

您可以看到，第二和第三小的延迟（排名分别为 1 和 2 的观察值）是 2。类似地，第三、第四和第五小的延迟（排名分别为 3、4 和 5 的观察值）是 3，第六、第七、第八和第九小的延迟（排名分别为 6、7、8 和 9 的观察值）是 4。

当然，您也可以查询前 n 个最大的测量延迟。请使用 TDIGEST.BYREVRANK 来完成此操作。

TDIGEST.BYREVRANK key reverse_rank [reverse_rank …]

对于每个输入的反向排名，它返回具有该反向排名的值（浮点数）的估计。

以下查询检索第一个、第二个、… 和第九个最大的观察延迟：

TDIGEST.BYREVRANK t 0 1 2 3 4 5 6 7 8 9
1) "5"
2) "5"
3) "5"
4) "5"
5) "5"
6) "4"
7) "4"
8) "4"
9) "4"
10) "3"

该查询包含 10 个反向排名；因此回复是一个包含 10 个值的数组。

当反向排名为 0 时，结果是最大的观察值（本例中为 5）。类似地，当反向排名等于观察值数量减一时，结果是最小的观察值。对于这两个反向排名，结果总是准确的。任何其他反向排名的结果都是估计值。当反向排名等于或大于观察值数量时，结果为 -inf。

您可以看到，第一、第二、第三、第四和第五大的延迟（反向排名分别为 0、1、2、3 和 4 的观察值）是 5。类似地，第六、第七、第八和第九大的延迟（反向排名分别为 5、6、7 和 8 的观察值）是 4。

要按值估算分位，请使用 TDIGEST.CDF： 

TDIGEST.CDF key value [value …]

对于每个输入的值，它检索小于给定值的观察值比例加上等于给定值的一半观察值比例的估计。

以下查询分别检索小于 0、1、2、3、4、5 和 6 毫秒延迟的比例：

TDIGEST.CDF t 0 1 2 3 4 5 6
1) "0"
2) "0.033333333333333333"
3) "0.13333333333333333"
4) "0.29999999999999999"
5) "0.53333333333333333"
6) "0.83333333333333337"
7) "1"

该查询包含七个延迟值；因此回复是一个包含七个比例的数组。

正如您所见，在此简单示例中，所有估计都是准确的：小于 0 的延迟比例加上等于 0 的延迟的一半是 0。类似地，小于 1 的延迟比例加上等于 1 的延迟的一半是 3.33%，等等。

有时，您想估计观察值的数量，而不是观察值的比例。为此，您可以使用 TDIGEST.RANK 和 TDIGEST.REVRANK。 

以下查询分别检索小于 0、1、2、3、4、5 和 6 毫秒的延迟数量：

TDIGEST.RANK key value [value …]

这与 TDIGEST.CDF 类似，但它返回的是一个估计，对于每个输入的值，该估计表示小于给定值的观察值数量加上等于给定值的一半观察值的数量。

TDIGEST.RANK t 0 1 2 3 4 5 6
1) "-1"
2) "1"
3) "2"
4) "5"
5) "8"
6) "13"
7) "15"

该查询包含七个延迟值；因此回复是一个包含七个排名的数组。

同样，本例中的所有估计都是准确的：没有小于 0 的延迟；因此，结果排名为 -1。小于 1 的延迟数量加上等于 1 的延迟的一半是 1。类似地，小于 2 的延迟数量加上等于 1 的延迟的一半是 2，等等。

TDIGEST.REVRANK key value [value …]

这与 TDIGEST.RANK 类似，但它返回的是一个估计，对于每个输入的值，该估计表示大于给定值的观察值数量加上等于给定值的一半观察值的数量。

以下查询分别检索大于 0、1、2、3、4、5 和 6 毫秒的延迟数量：

TDIGEST.REVRANK t 0 1 2 3 4 5 6
1) "15"
2) "14"
3) "13"
4) "10"
5) "7"
6) "2"
7) "-1"

该查询包含七个延迟值；因此回复是一个包含七个反向排名的数组。

再次，您可以看到本例中的所有估计都是准确的：大于 0 的延迟数量加上等于 0 的延迟的一半是 15。类似地，大于 1 的延迟数量加上等于 1 的延迟的一半是 14。没有延迟等于或大于 6；因此结果反向排名为 -1。 

我们可以看到，对于介于最小和最大观察值之间的任何 v，TDIGEST.RANK(v) + TDIGEST.REVRANK(v) 等于观察值的数量。

计算平均测量值是一个常见的操作。然而，有时测量值会存在噪声或包含无效值。例如，考虑一个噪声大、无效的延迟值 999999999 毫秒。在这种情况下，一种常见的做法是计算忽略异常值的所有观察值的平均值。例如，您可能想计算第 20 百分位数和第 80 百分位数之间的平均值。

要估计指定分位之间的平均值，请使用 TDIGEST.TRIMMED_MEAN

TDIGEST.TRIMMED_MEAN key lowFraction highFraction

TDIGEST.TRIMMED_MEAN t 0.2 0.8
"3.8888888888888888"
TDIGEST.TRIMMED_MEAN t 0.1 0.9
"3.7692307692307692"
TDIGEST.TRIMMED_MEAN t 0  1
"3.6666666666666665"

有时，合并 t-digest 数据结构非常有用。例如，假设我们测量了三台服务器的延迟，每台服务器都有自己的 t-digest，但随后我们想计算所有服务器组合起来的 90%、95% 和 99% 延迟。

使用此命令将多个 t-digest 数据结构合并为一个：

TDIGEST.MERGE destKey numKeys sourceKey… [COMPRESSION compression] [OVERRIDE] 

TDIGEST.CREATE s1
TDIGEST.ADD s1 1 2 3 4 5
TDIGEST.CREATE s2
TDIGEST.ADD s2 6 7 8 9 10
TDIGEST.MERGE sM 2 s1 s2
TDIGEST.BYRANK sM 0 1 2 3 4 5 6 7 8 9
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
 

分别使用 TDIGEST.MIN 和 TDIGEST.MAX 来检索 t-digest 数据结构中的最小值和最大值。

当数据结构为空时，两者都返回 nan。

TDIGEST.MIN t
"1"
TDIGEST.MAX t
"5"

这两个命令都返回准确的结果，并且分别等同于 TDIGEST.BYRANK key 0 和 TDIGEST.BYREVRANK key 0。

使用 TDIGEST.INFO 来检索关于 t-digest 的额外信息，包括添加到数据结构的观察值数量以及为数据结构分配的字节数。

要清空 t-digest 数据结构并重新初始化它：

TDIGEST.RESET key 

后续步骤

t-digest 扩展了 Redis 不断增长的概率数据结构集合，帮助您解决更多与流数据和大型数据集相关的用例。它以亚毫秒级延迟、亚线性内存需求和极高的准确性来实现这一点。

这篇博客文章是一个概览。所有 t-digest 命令都在 redis.io 上有详细解释。

从我们的下载中心下载最新版本，或通过 FlatHub 或 Snapcraf 安装。

相关文章