用 HyperLogLog 計算不重複使用者 • PostgreSQL 的藝術

如果你有在追蹤統計領域的新發展，可能聽過這個最先進的基數估計（cardinality estimation）演算法：HyperLogLog。這項技術已透過 postgresql-hll 擴充套件（https://github.com/citusdata/postgresql-hll）進入 PostgreSQL，並由社群打包資源支援 Debian、RHEL 等多種作業系統。

HyperLogLog#

HyperLogLog 是一種非常特殊的雜湊值：它把足夠的資訊聚合成單一純量值，可以在有限精度損失下計算不重複值的數量。

假設要計算不重複訪客：用 HyperLogLog，每天只需維護一個值，之後把這些值做聯集（union），就能得到每週或每月的不重複訪客數！

 select to_char(date, 'YYYY/MM') as month,
        round(#hll_union_agg(users)) as monthly
   from daily_uniques
group by month;

  month  │ monthly
─────────┼─────────
 2013/02 │ 1960380
(1 row)

磁碟上只保留每日聚合值（一般每天僅 1280 位元組），就能用 HyperLogLog 的數學算出當月不重複數的近似值——不必重新掃描整個月的記錄。

安裝 postgresql-hll#

作業系統套件裝好後，一句 create extension hll; 即可。擴充提供新資料型別 hll，可用 \dx+ hll 查看隨附的支援（共 71 個 SQL 物件）。

延伸輸出：\dx+ hll 物件清單（節錄）

                          Objects in extension "hll"
                               Object description
══════════════════════════════════════════════════════════════════════════════
 cast from bigint to hll_hashval
 cast from bytea to hll
 function hll_add(hll,hll_hashval)
 function hll_add_agg(hll_hashval)
 function hll_cardinality(hll)
 function hll_empty()
 function hll_hash_any(anyelement,integer)
 function hll_hash_bigint(bigint,integer)
 function hll_hash_integer(integer,integer)
 function hll_hash_text(text,integer)
 ...
 operator #(NONE,hll)
 operator <>(hll,hll)
 operator =(hll,hll)
 operator ||(hll,hll)
 operator ||(hll,hll_hashval)
 type hll
 type hll_hashval

從輸出可以認識 hll 的運算子，例如有趣的 #——作用在 hll 值上的一元運算子，稍後詳述。

計算推文的不重複訪客#

以「資料操作與並行控制」一章介紹過的推文應用為例，來計算推文的不重複訪客。hll 型別的兩個主要操作：

從輸入值（例如 IP 位址）建立雜湊。
用該雜湊更新既有的 hll 值。

hll 的核心想法是每個顆粒度只保留一個 hll 值——這裡是每則推文、每天一個。也就是說每次有新訪問，就要 UPDATE 對應的 hll 集合。但前一章看過，同一列被反覆更新的 UPDATE 重度情境下，並行性是硬傷。所以再次採兩階段作法：每次訪問先 INSERT 一筆，再由背景程序把這些訪問轉成對「每推文每日單一 hll 聚合值」的 UPDATE。

記錄每次訪問的訪客表：

create table tweet.visitor
 (
   id          bigserial primary key,
   messageid   bigint not null references tweet.message(messageid),
   datetime    timestamptz not null default now(),
   ipaddr      ipaddress,

   unique(messageid, datetime, ipaddr)
 );

測試資料同樣用 Common Lisp 寫一個很簡單的 COPY 載入程式產生。程式刻意鎖定較小的 IP 範圍（192.168.0.0/16 子網）與一個月的日期區間，製造碰撞，讓同一 IP 出現多次訪問。

延伸範例：產生訪問資料的 Common Lisp 程式

(defparameter *connspec* '("appdev" "dim" nil "localhost"))
(defparameter *visitor-table*   "tweet.visitor")
(defparameter *visitor-columns* '("messageid" "ipaddr" "datetime"))

(defun insert-visistors (messageid n &optional (connspec *connspec*))
  (pomo:with-connection connspec
    (let ((count 0)
          (copier (open-db-writer connspec *visitor-table* *visitor-columns*)))
      (unwind-protect
          (loop :for i :below n
             :do (let ((ipaddr    (generate-ipaddress))
                       (datetime (format nil "~a" (generate-timestamp))))
                   (db-write-row copier (list messageid ipaddr datetime))
                   (incf count)))
       (close-db-writer copier))

      ;; and return the number of rows copied
      count)))

;;;
;;; select '192.168.0.0'::ip4::bigint; == 3232235520
;;;
(defparameter *ip-range-start* 3232235520)
(defparameter *ip-range-size* (expt 2 16))

(defun generate-ipaddress (&optional
                             (range-size *ip-range-size*)
                             (range-start *ip-range-start*))
  "Generate N random IP addresses, as strings."
  (int-to-ip (+ range-start (random range-size))))

(defun generate-timestamp ()
  "Generate a random timestamp between now and a month ago."
  (local-time:timestamp- (local-time:now) (random #. (* 24 60 31)) :minute))

在 REPL 互動式產生 100,000 筆訪問，實測不到 8 秒完成。拜 COPY 串流協定之賜，數字產生與傳輸給 PostgreSQL 可以交錯進行——這種速度對資料模型的互動式探索綽綽有餘，在 PostgreSQL 上「先試了再說」很容易。

驗證 messageid 3 的十萬筆訪問：

  select messageid,
         datetime::date as date,
         count(*) as count,
         count(distinct ipaddr) as uniques,
         count(*) - count(distinct ipaddr) as duplicates
     from tweet.visitor
    where messageid = 3
 group by messageid, date
 order by messageid, date
   limit 10;

 messageid │    date    │ count │ uniques │ duplicates
═══════════╪════════════╪═══════╪═════════╪════════════
         3 │ 2018-08-07 │   746 │     742 │          4
         3 │ 2018-08-08 │  3298 │    3211 │         87
         3 │ 2018-08-09 │  3260 │    3191 │         69
         3 │ 2018-08-10 │  3156 │    3077 │         79
         ...
(10 rows)

即使只用 16 位元的 IP 範圍，已經出現多筆同 IP 的重複訪問。

用 HLL 做有損的不重複計數#

同一個查詢可以改用 hll 型別重寫——雖然此刻還不太有用（完整訪問記錄都在，精確計數算得起）：

  select messageid,
         datetime::date as date,
         # hll_add_agg(hll_hash_text(ipaddr::text)) as hll
    from tweet.visitor
   where messageid = 3
group by grouping sets((messageid),
                       (messageid, date))
order by messageid, date nulls first
   limit 10;

查詢用了幾個 hll 的新函式與運算子：

#：一元運算子（像階乘的 !），套用在 hll 值上時，計算 hyperloglog 集合中估計的不重複項目數。
hll_add_agg()：把新的雜湊累積進 hyperloglog 集合的聚合函式。
hll_hash_text：計算文字值的 hyperloglog 雜湊——這裡把 IP 位址當文字用。也可以把 IP 當 32 位元整數用 hll_hash_integer，但那樣就不支援需要 128 位元的 IPv6 位址了。

 messageid │    date    │       hll
═══════════╪════════════╪══════════════════
         3 │ 2018-08-07 │ 739.920627061887
         3 │ 2018-08-08 │ 3284.16386418662
         3 │ 2018-08-09 │ 3196.58757626223
         3 │ 2018-08-10 │ 3036.32707701154
         ...
(10 rows)

這樣用 hll 其實沒什麼意義——處理的列數一樣多，結果卻損失精度。在這裡示範是為了兩件事：一、示範 hll 運算子與函式的查詢用法；二、證明即使基數這麼低，hll 的估計值也相當準。

把訪問記錄變成不重複計數#

真正的生產情境有這些條件與限制：

推文發布後，網路上的使用者會來訪問；應用程式每次訪問都在 tweet.visitor 插入一列（IP 位址與精確時間戳記）。
預期應用會相當成功，因此保不住全部訪客日誌，也無法每次有人要看不重複訪客數時即時計算還維持服務品質。
這些數字用於行銷而非帳務，可以容忍精度損失——若有損能換來更寬鬆的儲存與處理需求，我們求之不得。

hll 正是解方。現在從 tweet.visitor 計算每則訊息每天的單一 hyperloglog 值：

begin;

with new_visitors as
  (
    delete from tweet.visitor
          where id = any (
                            select id
                              from tweet.visitor
                          order by datetime, messageid
                        for update
                       skip locked
                             limit 1000
                     )
      returning messageid,
                cast(datetime as date) as date,
                hll_hash_text(ipaddr::text) as visitors
 ),
     new_visitor_groups as
 (
     select messageid, date, hll_add_agg(visitors) as visitors
       from new_visitors
   group by messageid, date
 )
 insert into tweet.uniques
       select messageid, date, visitors
         from new_visitor_groups
 on conflict (messageid, date)
    do update set visitors = hll_union(uniques.visitors, excluded.visitors)
            where uniques.messageid = excluded.messageid
              and uniques.date = excluded.date
    returning messageid, date, # visitors as uniques;

rollback;

這個查詢靠可寫入的 CTE 分成多個階段：

new_visitors：從緩衝表 tweet.visitor 一次刪除一千列，並使用 PostgreSQL 9.5 新增的 skip locked。預設情況下，刪除被其他交易（update 或 delete）占用的列必須等待對方釋放鎖；加了 skip locked，PostgreSQL 可直接略過該列、不鎖不等。被略過的列可能出現在下一批，也可能已被另一批並行處理。因此同一查詢可以多個交易同時跑——處理進度嚴重落後時特別有用。
第一個 CTE 同時用 CAST 從時間戳記取出日期、從 IP 算出 hll 雜湊，為下一階段做準備。
new_visitor_groups：把個別雜湊聚合成每 messageid 每日期一個 hll 集合。
把這些每日不重複訪客 hll 集合插入彙總表 tweet.uniques；若同訊息同日已有集合，就用 hll_union 把新舊集合聯集後更新。
最後用 insert 的 returning 子句回傳本批處理結果。

腳本結尾用 rollback，方便反覆除錯打磨查詢。這種 5 階段、29 行的 SQL 靠 CTE 把動作分得清清楚楚，維護不難，但也不會一次就在文字檔裡寫對——它是在你慣用的 SQL 提示符下慢慢「熬」出來的；因為是 DML 查詢，寧可 rollback 重試，也不要弄髒資料集再收拾。

排程估計值計算#

知道怎麼從 insert 重度的表計算不重複訪客近似值後，還需要一個定期執行的背景程序。最簡單的做法是在後端加一個 API 端點，用 cron 類工具按排程呼叫；但緊急時能互動式執行也很重要。兩者兼得的解法：把 SQL 查詢包成預存程序。

本書不涵蓋預存程序，但把現成的敘述包成 SQL 函式很容易：

begin;

create function tweet.update_unique_visitors
  (
    in  batch_size  bigint default 1000,
    out messageid   bigint,
    out date        date,
    out uniques     bigint
  )
  returns setof record
  language SQL
as $$
with new_visitors as
 (
   delete from tweet.visitor
         where id = any (
                            select id
                              from tweet.visitor
                          order by datetime, messageid
                        for update
                       skip locked
                             limit update_unique_visitors.batch_size
                     )
     returning messageid,
               cast(datetime as date) as date,
               hll_hash_text(ipaddr::text) as visitors
 ),
       new_visitor_groups as
 (
       select messageid, date, hll_add_agg(visitors) as visitors
         from new_visitors
     group by messageid, date
 )
 insert into tweet.uniques
       select messageid, date, visitors
         from new_visitor_groups
 on conflict (messageid, date)
    do update set visitors = hll_union(uniques.visitors, excluded.visitors)
            where uniques.messageid = excluded.messageid
              and uniques.date = excluded.date
    returning messageid, date, cast(# visitors as bigint) as uniques;
$$;

commit;

互動測試（一樣先 BEGIN、看完 ROLLBACK）：

appdev> begin;
BEGIN
appdev>* select * from tweet.update_unique_visitors();
 messageid │    date    │ uniques
═══════════╪════════════╪═════════
         3 │ 2018-08-07 │     740
         3 │ 2018-08-08 │     258
(2 rows)

appdev>* rollback;
ROLLBACK

確認可行後，就能在後端 API 還沒實作前先互動式使用。接著一次處理整個資料集：

select * from tweet.update_unique_visitors(100000);

函式如預期回傳 32 列——每個 messageid 每天一列（我們的訪問全在 messageid 3 上）。跑完之後 tweet.visitor 一列不剩（select count(*) 回傳 0）：在這個實作裡，tweet.visitor 是當前活動的緩衝區，呼叫 tweet.update_unique_visitors() 時彙總進 tweet.uniques。

合併不重複訪客#

現在可以享受 hyperloglog 集合的美妙性質了：

  select to_char(date, 'YYYY/MM') as month,
         to_char(date, 'YYYY IW') as week,
         round(# hll_union_agg(visitors)) as unique,
         sum(# visitors)::bigint as sum
    from tweet.uniques
group by grouping sets((month), (month, week))
order by month nulls first, week nulls first;

新函式 hll_union_agg 是能計算多個 hyperloglog 集合聯集的聚合函式，合併多組不重複訪客時，它知道哪些訪客在全域仍是不重複的——相當神奇：

  month  │  week   │ unique │  sum
═════════╪═════════╪════════╪═══════
 2018/08 │ ¤       │  45300 │ 75699
 2018/08 │ 2018 32 │  15119 │ 16589
 2018/08 │ 2018 33 │  18967 │ 21461
 2018/08 │ 2018 34 │  19226 │ 22104
 2018/08 │ 2018 35 │  14046 │ 15545
 2018/09 │ ¤       │  18640 │ 21415
 2018/09 │ 2018 35 │   6143 │  6299
 2018/09 │ 2018 36 │  13510 │ 15116
(8 rows)

這裡用 grouping sets 更能凸顯 hyperloglog 聯集運算的威力：直接把各期間的不重複數相加（sum 欄）會把一大部分人重複計算，而 hyperloglog 技術知道如何避免這種重複計數！