更多精彩内容：请登录http://ke.sandata.com.cn/

前言

HLL是 HyperLogLog数据结构的简称。PostgresSQL通过插件的形式引入了这种新的数据类型hll。HyperLogLog是一个具备固定大小，相似于汇合构造，用于可调精度的不同值计数。例如，在1280字节的hll数据结构中，它能够在很小的误差范畴内估算出数百亿的不同值计数。

算法

hll能够被视为层次结构的不同汇合/不同值计数算法的组合，并向上挪动该层次结构的规定。为了辨别上述形容算法，将其命名为以下:

♠ EMPTY

示意空集的常量值

♠ EXPLICIT

汇合中确定的，惟一的，排序残缺的整数列表，该列表放弃一个固定的基数

♠ SPARSE

HyperLogLog是基于映射的“惰性”实现，是一种基于概率汇合的数据结构。仅将非零寄存器的索引和值存储在 map中，直到非零寄存器的数量超过固定的基数。

♠ FULL

HyperLogLog是一个齐全物化，基于列表的实现。它将每个寄存器的值显式存储在按寄存器索引排序的列表中。

基本概念

  • 基数计数

用来统计一个汇合中不反复的元素的个数。

  • 基数计数实现

假如一个汇合为Su,用列举法示意{2,3,1,4,5,9},如果此时有一个新的元素Xi=3要退出到汇合Su中。如果Su中蕴含该元素,那么该元素将不会被退出到汇合Su中，否则，退出该元素到汇合中，计数值为Su，即基数值为元素的中非雷同值的个数。如汇合中{1,2,3,5,2}，基数为4，因为2是 DV（Distinct Value），不被计算到基数中。

该实现有两个问题：

  1. 当汇合有限减少，元素增多时，相应的存储内存也会有限增长
  2. 当汇合无线减少，元素增多，判断是否蕴含待退出元素的老本也将减少。

实现动机

最后裁减原始HLL算法如下：

  • 个别状况下，一个HLL占用 regwidth * 2^log2m 位存储。
  • 典型应用中，log2m = 11 和 regwidth = 5时，将申请须要10240位或者1280个字节。即 5 2^11 = 5 2048 = 10240
  • 还有一种就是有很多的字节

最后的HLL算法的第一个补充来自于实现1280个字节须要160个64位整数的大小。因而，如果心愿在低基数下取得更高的准确性，则能够将一组明确的输出保留为64位整数的排序列表，直到达到第161个不同的值为止。这将为提供流中不同值的实在示意，同时须要雷同数量的内存。 （这是EXPLICIT算法）。

第二个是不须要存储值为零的寄存器。能够简略地将一组具备非零值的寄存器示意为从索引到值的映射。该映射存储为索引值对的列表，这些索引值对是长度为log2m + regwidth的bit-packed的“short words”。 （这是SPARSE算法。）

联合这两种加强，失去了一个“promotion hierarchy”，能够对算法进行调整以进步准确性，内存或性能。

初始化和存储新的hll对象将仅调配一个小的小标记值，该值示意空集（EMPTY）。当增加前几个值时，惟一整数的排序列表存储在EXPLICIT集中。当心愿进行衡量内存的准确性时，已排序列表中的值将“promoted”为基于SPARSE映射的HyperLogLog构造。最初，当有足够的寄存器时，基于映射的HLL将转换为位打包的FULL HLL构造。

天然地，EMPTY和EXPLICIT示意的基数预计是精确的，而SPARSE和FULL示意的准确性受原始HLL算法提供的保障的束缚。

装置和应用HLL

解压安装包

[postgres@pgserver plugin]$ lspostgresql-hll-2.15.1  postgresql-hll-2.15.1.tar.gz[postgres@pgserver plugin]$ cd postgresql-hll-2.15.1[postgres@pgserver postgresql-hll-2.15.1]$ lsCHANGELOG.md  expected     include  Makefile   REFERENCE.md  srcDEVELOPER.md  hll.control  LICENSE  README.md  sql           update

编译装置

[postgres@pgserver postgresql-hll-2.15.1]$ make -j24 && make install

测试

[postgres@pgserver postgresql-hll-2.15.1]$ psql -d postgrespsql (13.2)Type "help" for help.postgres=# CREATE EXTENSION hll;CREATE EXTENSIONpostgres=#

构建数据

CREATE TABLE helloworld  (    id integer,    set hll  );--- Insert an empty HLLINSERT INTO helloworld  (id,    set  )  VALUES  (1,    hll_empty()  );--- Add a hashed integer to the HLLUPDATE  helloworldSETset = hll_add(set, hll_hash_integer(12345))WHERE  id = 1;--- Or add a hashed string to the HLLUPDATE  helloworldSETset = hll_add(set, hll_hash_text('hello world'))WHERE  id = 1;--- Get the cardinality of the HLLSELECT  hll_cardinality(set)FROM  helloworldWHERE  id = 1;postgres=# SELECTpostgres-#   hll_cardinality(set)postgres-# FROMpostgres-#   helloworldpostgres-# WHEREpostgres-#   id = 1postgres-# ; hll_cardinality -----------------               2(1 row)postgres=# SELECT * FROM helloworld ; id |                   set                    ----+------------------------------------------  1 | x128b7faaebcf97601e5541533f6046eb7f610e

从下面的示例中失去，首先构建了一个空的hll汇合，而后向该汇合中增加了两个值，那么失去的该hll的基数计数就是2。

接下来看一个更加实用的用例：

创立网站拜访事实表和用户日拜访表

CREATE TABLE facts (    date            date,    user_id         integer,    activity_type   smallint,    referrer        varchar(255));CREATE TABLE daily_uniques (    date            date UNIQUE,    users           hll);

而后给网站拜访表中插入过来1000天的拜访数据(此处因为没有理论的数据，只能模仿过来1000天的数据)

[postgres@pgserver ~]$ psql -d postgres -f ~/test.sql

查看表

postgres=# SELECT count(*) FROM facts ;  count   ---------- 50000000

5000万数据

而后依据日期，对user_id进行hash解决，聚合每天用户拜访网站的数据到 hll构造中。

INSERT INTO daily_uniques(date, users)    SELECT date, hll_add_agg(hll_hash_integer(user_id))    FROM facts    GROUP BY 1;

查看表数据

postgres=# SELECT count(*) FROM daily_uniques ; count -------  1000(1 row)

只有1000行数据

当初查找一下每天hll的基数计数值

postgres=# SELECT date, hll_cardinality(users) FROM daily_uniques LIMIT 10;    date    |  hll_cardinality  ------------+------------------- 2021-02-06 | 9725.852733707077 2021-02-21 | 9725.852733707077 2021-02-02 | 9725.852733707077 2021-02-08 | 9725.852733707077 2021-02-10 | 9725.852733707077 2021-02-03 | 9725.852733707077 2021-02-14 | 9725.852733707077 2021-02-22 | 9725.852733707077 2021-02-11 | 9725.852733707077 2021-02-20 | 9725.852733707077

此刻，可能会想，能够用 COUNT DISTINCT做到基数统计。然而这里只能看到每天多少个惟一身份的用户拜访了网站。

假使想要查看每一周的惟一值呢？

HLL能够这样解决

postgres=# SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '2018-10-02'::date AND date <= '2018-10-08'::date;  hll_cardinality  ------------------- 9725.852733707077(1 row)

或者查看一年中的每个月拜访状况

postgres=# SELECT EXTRACT(MONTH FROM date) AS month, hll_cardinality(hll_union_agg(users))postgres-# FROM daily_uniquespostgres-# WHERE date >= '2019-01-01' ANDpostgres-#       date <  '2020-01-01'postgres-# GROUP BY 1; month |  hll_cardinality  -------+-------------------     3 | 9725.852733707077     7 | 9725.852733707077     8 | 9725.852733707077    12 | 9725.852733707077     5 | 9725.852733707077    10 | 9725.852733707077    11 | 9725.852733707077     9 | 9725.852733707077     4 | 9725.852733707077     1 | 9725.852733707077     2 | 9725.852733707077     6 | 9725.852733707077

等等。因而，能够失去hll能够很好的来计算DV值，并且很快。

对于更多内容，大家能够去拜访github网站来获取。