t-digest

t-digest 是一种概率型数据结构,用于估计数据流的百分位数。

t-digest 是 Redis 开源版中的一种 sketch 数据结构,用于使用紧凑的 sketch 估计数据流或大型数据集的百分位数。

它可以回答以下问题:

  • 数据流中有多大比例的值小于给定值?
  • 数据流中有多少值小于给定值?
  • 数据流中小于 p 百分比值的最高值是什么?(即 p 百分位数值是多少?)

什么是 t-digest?

t-digest 是一种数据结构,它可以在无需存储和排序集合中的所有数据点的情况下估计百分位点。例如:要回答“我的数据库操作中 99% 的平均延迟是多少?”这个问题,我们必须存储每个用户的平均延迟,对值进行排序,去掉最后 1%,然后才能找到其余所有值的平均值。这种过程不仅在排序这些值所需的处理方面成本高昂,而且在存储这些值所需的空间方面也成本高昂。这正是 t-digest 解决的问题。

t-digest 还可以用于估计与百分位数相关的其他值,例如截断均值(trimmed means)。

截断均值是 sketch 中的平均值,不包括低于和高于截止百分位数的观测值。例如,0.1 截断均值是 sketch 中的平均值,不包括最低的 10% 和最高的 10% 的值。

用例

硬件/软件监控

您测量在线服务器响应延迟,并希望查询

  • 测得延迟的第 50、90 和 99 百分位数是多少?

  • 测得延迟中有多大比例小于 25 毫秒?

  • 忽略异常值后的平均延迟是多少?或者,第 10 和第 90 百分位数之间的平均延迟是多少?

在线游戏

数百万人在您的在线游戏平台上玩游戏,您想向每位玩家提供以下信息?

  • 您的分数高于 x% 的游戏会话分数。

  • 约有 y 个游戏会话中,人们的得分高于您。

  • 要获得比 90% 的游戏玩家更高的分数,您的分数应为 z。

网络流量监控

您测量每秒网络传输的 IP 数据包,并尝试通过询问以下问题来检测拒绝服务攻击:

  • 最后一秒的数据包数量是否超过之前观察到的值的 99%?

  • 正常网络条件下,我预计会看到多少数据包?(答案:介于 x 和 y 之间,其中 x 代表第 1 百分位数,y 代表第 99 百分位数)。

预测性维护

  • 测量的参数(噪声水平、电流消耗等)是否异常?(不在 [第 1 百分位数...第 99 百分位数] 范围内)?

  • 我应该将警报设置为哪些值?

示例

在下面的示例中,您将创建一个压缩度为 100 的 t-digest 并向其中添加项目。COMPRESSION 参数用于指定精度和内存消耗之间的权衡。默认值为 100。值越高表示精度越高。注意:与其他一些概率型数据结构不同,如果键不存在,TDIGEST.ADD 命令不会创建新结构。

每当有新的观测值可用时,您可以重复调用 TDIGEST.ADD

按值估计比例或排名

t-digest 的另一个有用特性是 CDF(排名的定义),它为我们提供了小于或等于某个值的观测值的比例。此命令对于回答诸如“值小于或等于 X 的观测值百分比是多少”之类的问题非常有用。

更精确地说,TDIGEST.CDF 将返回 sketch 中小于 X 的观测值比例加上等于 X 的观测值数量的一半的估计值。我们还可以使用非常相似的 TDIGEST.RANK 命令。它不返回比例,而是返回值的 ----估计---- 排名。 TDIGEST.RANK 命令也是可变参数的,这意味着您可以使用单个命令检索一个或多个值的估计值。

这里有一个示例。给定一组骑行者的年龄,您可以问一个问题:“年龄小于 50 岁的自行车赛车手占多少百分比?”

最后,TDIGEST.REVRANK key value... 类似于 TDIGEST.RANK,但对于每个输入值,它返回一个估计值,该值等于(大于给定值的观测值数量 + 等于给定值的观测值数量的一半)。

按比例或排名估计值

TDIGEST.QUANTILE key fraction... 对于每个输入的比例,返回小于该比例观测值的估计值(浮点数)。TDIGEST.BYRANK key rank... 对于每个输入的排名,返回具有该排名的估计值(浮点数)。

TDIGEST.BYREVRANK key rank... 对于每个输入的反向排名,返回具有该反向排名的(浮点数)的估计值。

估计截断均值

使用 TDIGEST.TRIMMED_MEAN key lowFraction highFraction 检索指定比例之间的平均值估计。

这对于计算忽略异常值后的平均值特别有用。例如,计算第 20 百分位数和第 80 百分位数之间的平均值。

合并 sketches

有时合并 sketches 很有用。例如,假设我们测量了 3 台服务器的延迟,并想计算所有服务器合并后的 90%、95% 和 99% 延迟。

TDIGEST.MERGE destKey numKeys sourceKey... [COMPRESSION compression] [OVERRIDE] 将多个 sketches 合并为一个 sketch。

如果 destKey 不存在,则会创建一个新的 sketch。

如果 destKey 是一个已存在的 sketch,其值将与源键的值合并。要覆盖目标键的内容,请使用 OVERRIDE

检索 sketch 信息

分别使用 TDIGEST.MINTDIGEST.MAX 检索 sketch 中的最小值和最大值。

当 sketch 为空时,两者都返回 nan

这两个命令都返回精确结果,分别等同于 TDIGEST.BYRANK racer_ages 0TDIGEST.BYREVRANK racer_ages 0

使用 TDIGEST.INFO racer_ages 检索有关 sketch 的一些额外信息。

重置 sketch

学术资源

参考资料

评价此页面
返回顶部 ↑