t-digest

t-digest 是一种概率数据结构,允许您估计数据流的百分位数。

t-digest 是 Redis Stack 中的一种草图数据结构,用于从数据流或大数据集中使用紧凑的草图估计百分位数。

它可以回答如下问题:

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

什么是t-digest?

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

t-digest 也可以用于估计与百分位数相关的其他值,如修剪均值。

一个修剪平均值是从草图中计算的平均值,不包括低于低百分位和高百分位的观测值。例如,0.1修剪平均值是草图的平均值,不包括最低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 将返回草图中小于 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百分位数之间的平均值。

合并草图

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

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

如果 destKey 不存在 - 将创建一个新的草图。

如果 destKey 是一个现有的草图,它的值将与源键的值合并。要覆盖目标键的内容,请使用 OVERRIDE

检索草图信息

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

当草图为空时,两者都返回nan

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

使用 TDIGEST.INFO racer_ages 来检索关于该草图的一些额外信息。

重置草图

学术资源

参考文献

RATE THIS PAGE
Back to top ↑