「PostgreSQL高级特性」PostgreSQL 数据库的近似算法

在较早的博客文章中，我写了关于如何将问题分解为MapReduce样式的方法可以如何为您提供更好的性能。当我们能够在集群中所有核心之间并行化工作负载时，我们发现Citus比单节点数据库快几个数量级。虽然计数（*）和平均数很容易分解成较小的部分，但我立即想到了一个问题，即计数不重复数，列表中的最高值或中位数是什么？

公认的是，在大型分布式设置中，确切的非重复计数更难解决，因为它需要在节点之间进行大量数据转换。Citus确实支持不重复计数，但是在处理特别大的数据集时有时会很慢。任何中型到大型数据集的中位数都可能对最终用户完全禁止。幸运的是，几乎所有这些算法都有近似算法，可以提供足够接近的答案，并且具有令人印象深刻的性能特征。

HyperLogLog的近似唯一性

在某些类别的应用程序中，例如网络分析，物联网（物联网）和广告，计算某事物发生的不同次数是一个共同的目标。HyperLogLog是PostgreSQL数据类型扩展，它允许您获取原始数据并将其压缩为一段时间内存在的唯一身份值。

将数据保存到HLL数据类型的结果是，星期一的值将为25，而星期二的值将为20。与原始数据相比，此数据压缩后的压缩量要大得多。但是真正令人赞叹的是，您可以然后合并这些存储桶，通过合并两个HyperLogLog数据类型，您可以返回星期一和星期二有25个唯一身份，因为星期二您有10个重复访客：

SELECT hll_union_agg(users) as unique_visitors FROM daily_uniques; unique_visitors ----------------- 35 (1 row)

于HyperLogLog可以通过这种方式拆分和组合，因此还可以跨Citus群集中的所有节点很好地并行化

使用TopN查找重要事项

我们通常在Web分析，广告应用程序和安全性/日志事件应用程序中发现的另一种计数形式是希望知道已发生的最主要的操作或事件集。这可能是您在Google Analytics（分析）中看到的首页视图，也可能是事件日志中发生的主要错误。

TopN利用基础JSONB数据类型存储其所有数据。但随后会维护一个列表，其中是最重要的项目以及有关这些项目的各种数据。随着订单的改组，它会清除旧数据，从而使其现在必须维护所有原始数据的完整列表。

为了使用它，您将以与HyperLogLog类似的方式插入它：

# create table aggregated_topns (day date, topn jsonb); CREATE TABLE Time: 9.593 ms # insert into aggregated_topns select date_trunc('day', created_at), topn_add_agg((repo::json)->> 'name') as topn from github_events group by 1; INSERT 0 7 Time: 34904.259 ms (00:34.904)

在查询时，您可以轻松获取数据的前十名列表：

SELECT (topn(topn_union_agg(topn), 10)).* FROM aggregated_topns WHERE day IN ('2018-01-02', '2018-01-03'); ------------------------------------------------+----------- dipper-github-fra-sin-syd-nrt/test-ruby-sample | 12489 wangshub/wechat_jump_game | 6402 ...

不只是计数和列表

前面我们提到过，像中位数这样的运算可能会困难得多。尽管扩展可能尚不存在，但未来可以支持这些操作。对于中位数，存在多种不同的算法和方法。可以应用于Postgres的两个有趣的方法：

• T-digest -提供大约百分位数
• HDR (high dynamic range) -提供更好的压缩效果，但只专注于前99％和更高的百分位数

如果答案能在数TB的数据范围内达到亚秒级响应，那么答案是否完全接近但又不能完全满足您的需求？以我的经验，答案通常是肯定的。

因此，下次您认为分布式设置中不可能实现某些功能时，请研究一下存在哪些近似算法。

原文：https://www.citusdata.com/blog/2019/02/28/approximation-algorithms-for-your-database/

本文：http://jiagoushi.pro/node/925

讨论：请加入知识星球或者微信圈子【首席架构师圈】

微信公众号 如果喜欢仙翁的分享，请关注微信公众号【首席架构师智库】

仙翁小号 如果想进一步讨论，请加仙翁小号【intelligenttimes】，注明你希望加入的群：架构，云计算，大数据，数据科学，物联网，人工智能，安全，全栈开发，DevOps，数字化，产品转型。

微信圈子 如果想和志趣相投的同好交流，请关注仙翁的微信圈子【首席架构师圈】。

如果想向大咖提问，近距离接触，或者获得私密分享，请加入知识星球【首席架构师圈】