时间戳

首页 > 解决方案 > 如何在 Cassandra 中获得 X% 百分位数

cassandra - 如何在 Cassandra 中获得 X% 百分位数

问题描述

考虑一个具有结构的表：

CREATE TABLE statistics (name text, when timestamp, value int, 
PRIMARY KEY ((name, when)));

例如，按名称计算 50% 值百分位数的最佳方法是什么？我想过：

a）编写自定义聚合函数+查询，例如：

SELECT PERCENTILE(value, 0.5) FROM statistics WHERE name = '...'

b）首先按名称计算元素

SELECT COUNT(value) FROM statistics WHERE name = '...'

然后在按值升序排序时找到带有分页的第（0.5/count）行值。比如说，如果计数是 100，它将是第 50 行。

c) 你的想法

我不确定案例 A 是否可以处理该任务。当行数为奇数时，情况 B 可能会很棘手。

标签： cassandracqlcassandra-3.0

解决方案

只要您始终提供name- 如果不指定分区并将所有内容都包含在一个中，此请求可能会非常昂贵。我假设您的意思是((name), when)不在((name, when))您的表中，否则如果没有全表扫描（使用 hadoop 或 spark），您的要求是不可能的。

UDA 可以工作 - 但除非您愿意接受近似值，否则它可能会很昂贵。要让它完全准确，您需要进行 2 次传球（即计数，而不是第 2 次传球以将 X 放入设置，但由于没有隔离，这也不会是完美的）。因此，如果您需要它完全准确，您最好的选择可能是在statistics[name]计算之前将整个分区拉到本地或让 UDA 在地图中构建整个集合（或大多数）（如果分区变大，则不推荐）。IE：

CREATE OR REPLACE FUNCTION all(state tuple<double, map<int, int>>, val int, percentile double)
  CALLED ON NULL INPUT RETURNS tuple<double, map<int, int>> LANGUAGE java AS '
java.util.Map<Integer, Integer> m = state.getMap(1, Integer.class, Integer.class);
m.put(m.size(), val);
state.setMap(1, m);
state.setDouble(0, percentile);
return state;';

CREATE OR REPLACE FUNCTION calcAllPercentile (state tuple<double, map<int, int>>)
  CALLED ON NULL INPUT RETURNS int LANGUAGE java AS 
  'java.util.Map<Integer, Integer> m = state.getMap(1, Integer.class, Integer.class);
  int offset = (int) (m.size() * state.getDouble(0));
  return m.get(offset);';

CREATE AGGREGATE IF NOT EXISTS percentile (int , double) 
  SFUNC all STYPE tuple<double, map<int, int>>
  FINALFUNC calcAllPercentile
  INITCOND (0.0, {});

如果愿意接受一个近似值，您可以使用一个采样库，例如您存储的 1024 个元素，并且随着您的 UDA 获取元素，您以逐渐减少的统计机会替换其中的元素。（维特算法 R）这很容易实现，如果您的数据集预计具有正态分布，将为您提供一个不错的近似值。如果您的数据集不是正态分布，这可能相去甚远。对于正态分布，实际上还有很多其他选项，但我认为 R 是最容易在 UDA 中实现的。喜欢：

CREATE OR REPLACE FUNCTION reservoir (state tuple<int, double, map<int, int>>, val int, percentile double)
  CALLED ON NULL INPUT RETURNS tuple<int, double, map<int, int>> LANGUAGE java AS '
java.util.Map<Integer, Integer> m = state.getMap(2, Integer.class, Integer.class);
int current = state.getInt(0) + 1;
if (current < 1024) {
    // fill the reservoir
    m.put(current, val);
} else {
    // replace elements with gradually decreasing probability
    int replace = (int) (java.lang.Math.random() * (current + 1));
    if (replace <= 1024) {
        m.put(replace, val);
    }
}
state.setMap(2, m);
state.setDouble(1, percentile);
state.setInt(0, current);
return state;';

CREATE OR REPLACE FUNCTION calcApproxPercentile (state tuple<int, double, map<int, int>>)
  CALLED ON NULL INPUT RETURNS int LANGUAGE java AS 
  'java.util.Map<Integer, Integer> m = state.getMap(2, Integer.class, Integer.class);
  int offset = (int) (java.lang.Math.min(state.getInt(0), 1024) * state.getDouble(1));
  if(m.get(offset) != null)
      return m.get(offset);
  else
      return 0;';

CREATE AGGREGATE IF NOT EXISTS percentile_approx (int , double) 
  SFUNC reservoir STYPE tuple<int, double, map<int, int>>
  FINALFUNC calcApproxPercentile
  INITCOND (0, 0.0, {});

在上面，百分位函数会很快变慢，使用采样器的大小可以给你或多或少的准确性，但太大了，你开始影响性能。通常，超过 10k 值的 UDA（即使是简单的函数，如count）开始失败。在这些场景中认识到这一点也很重要，虽然单个查询返回单个值，但要获得它需要做大量工作。所以很多这样的查询或者很多并发会给你的协调员带来很大的压力。对于CASSANDRA-10783，这确实需要 >3.8（我会推荐 3.11.latest+）

注意：我不保证我没有在示例 UDA 中错过 1 个错误 - 我没有完全测试，但应该足够接近，你可以让它从那里工作

推荐阅读