一般來說，我很喜歡隨機化演算法，但其中有一個我特別喜愛，因為即使你已經理解它的運作原理，從程式設計師的角度來看，它依然充滿神奇感。它以極少的時間與空間成本，完成了一件近乎不合邏輯的事。這個演算法叫做 HyperLogLog（超對數），而今天，它作為 Redis 的全新資料結構正式推出。

計算不重複項目
===

通常，要計算不重複的事物——例如今天連上你網站的不重複 IP 數量，或是使用者執行的不重複搜尋次數——需要記住至今遇過的所有不重複元素，以便將下一個元素與已看過的集合進行比對，只有在該新元素從未出現過時才遞增計數器。

這需要與欲統計集合的基數（項目數量）成正比的記憶體，這在許多情況下是完全無法承受的。

有一類演算法利用隨機化，僅使用固定且少量的記憶體，就能提供集合中不重複元素數量的近似值。目前已知這類演算法中表現最佳的稱為 HyperLogLog，其由 Philippe Flajolet（菲利普·弗拉若萊）提出。

HyperLogLog 的卓越之處在於，即使使用極少的記憶體，也能對集合的基數提供非常好的近似值。在 Redis 的實作中，每個鍵僅使用 12k 位元組就能以 0.81% 的標準誤差進行計數，而且可計數的項目數量沒有上限，除非接近 2^64 項（這似乎不太可能發生）。

該演算法的相關文件記載於原始論文 [1]，其實務實作與變體則在 Google 於 2013 年發表的一篇論文 [2] 中有深入探討。

[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf

它是怎麼運作的？
===

有許多很棒的資源可以讓你更深入了解 HyperLogLog，例如 [3]。

[3] http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

在這裡，我只會透過一個在 [3] 中找到的非常巧妙的範例來說明其基本概念。想像一下，你告訴我你一整天都在擲硬幣，並計算連續出現正面的最長連續次數。如果你告訴我最長的連續正面是 3 次，我會猜想你其實沒有擲很多次硬幣。相反地，如果你最長的連續紀錄是 13 次，你大概花了很多時間在擲硬幣。

然而，如果你很幸運，第一次就擲出了 10 次正面——這是一個不太可能但確實可能發生的事件——然後就停止擲硬幣，那麼我對於你花費時間的估算就會非常不準確。因此我可能會請你重複這個實驗，但這次使用 10 枚硬幣和 10 張不同的紙，每枚硬幣對應一張紙，用來記錄最長的連續正面次數。這一次由於我能觀察到更多資料，我的估計就會更準確。

長話短說，這正是 HyperLogLog 所做的事：它會對你觀察到的每個新元素進行雜湊。雜湊值的一部分用來索引暫存器（在我們前面的例子中即是硬幣＋紙張的配對，基本上我們是將原始集合分割成 m 個子集）。雜湊值的另一部分則用來計算雜湊值中開頭連續零的最長長度（即我們例子中的連續正面）。出現 N+1 個零的機率是出現 N 個零機率的一半，因此透過觀察不同暫存器的值——這些暫存器被設定為在給定子集中目前觀察到的最長連續零——HyperLogLog 便能提供非常好的基數近似值。

Redis 的實作
===

HyperLogLog 的標準誤差為 1.04/sqrt(m)，其中「m」是使用的暫存器數量。Redis 使用了 16384 個暫存器，因此標準誤差為 0.81%。

由於 Redis 實作中所使用的雜湊函式輸出為 64 位元，而我們使用雜湊輸出中的 14 個位元來定址 16k 個暫存器，因此還剩下 50 個位元，所以我們可能遇到的最長連續零可以容納在一個 6 位元的暫存器中。這就是為什麼 Redis 的 HyperLogLog 值僅為 16k 個暫存器使用 12k 位元組。

由於使用了 64 位元輸出函式——這是 Google 在 [2] 中提出的演算法修改之一——我們可計數的集合基數實際上沒有限制。此外值得注意的是，對於非常小的基數，其誤差往往非常小。下圖顯示了該演算法針對兩個不同大型集合的一次執行結果。x 軸為集合的基數，y 軸為相對誤差（百分比）。



紅線與綠線是使用兩個完全不相關集合進行的兩次不同執行。它顯示了隨著基數增加，誤差保持一致。然而對於小得多的基數，你可以享有小得多的誤差：



綠線顯示了在基數至 100 範圍內單次執行的誤差，而紅線則是在 100 次執行中找到的最大誤差。在基數為數百以內的範圍內，該演算法極有可能產生非常小的誤差或提供完全正確的答案。當計算結果呈現給能夠直觀判斷答案是否正確的使用者時，這一點非常有價值。

Redis 實作的原始碼可在 Github 上取得：

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c

API
===

從 Redis 的角度來看，一個 HyperLogLog 就只是一個字串，恰好長度為 12k + 8 位元組（精確來說是 12296 位元組）。所有 HyperLogLog 指令在以恰好此大小的字串值呼叫時都會正常執行，否則會回報錯誤。然而無論字串中儲存了什麼內容，所有的呼叫都是安全的：你可以儲存垃圾資料，仍然要求估算其基數。在任何情況下都不會導致伺服器當機。

此外，整個表示法與位元組順序無關，且不受處理器字組大小影響，因此 32 位元大端序處理器可以讀取 64 位元小端序處理器產生的 HLL。

HyperLogLog 採用字串形式，避免了在 RDB 層級引入實際的型別。這使得這項工作能在接下來的幾天內被反向移植到 Redis 2.8，讓你能盡快使用 HyperLogLog。此外，該格式會自動序列化，且可以輕鬆地擷取與還原。

API 由三個新指令組成：

PFADD var element element … element
PFCOUNT var
PFMERGE dst src src src … src

指令前綴為「PF」，用以紀念菲利普·弗拉若萊 [4]。

[4] http://en.wikipedia.org/wiki/Philippe_Flajolet

PFADD 會將元素加入儲存在「var」的 HLL 中。如果該變數不存在，與所有 Redis API 呼叫一樣，會自動建立一個空的 HLL。該指令為可變參數，因此允許非常積極的管線化與批次插入。

該指令在底層的 HyperLogLog 被修改時回傳 1，否則回傳 0。這對使用者來說很有意思，因為隨著我們加入元素，某個元素實際修改暫存器的機率會降低。API 能夠提示是否有新的基數可用，讓持續加入元素並僅在有新基數可用時才擷取近似基數的程式成為可能。

PFCOUNT 會回傳估算的基數，若鍵不存在則為零。

最後，PFMERGE 可以將 N 個不同的 HLL 值合併為一個。結果產生的 HLL 所回報的估算基數，即為我們以不同 HLL 值計數的不同集合聯集的基數。這看起來很神奇，但之所以可行，是因為 HLL 雖然是隨機化的，卻是完全確定性的，因此 PFMERGE 只需對每個暫存器取 N 個 HLL 值中可用的最大值即可。給定的元素永遠會雜湊到同一個暫存器並具有相同的連續零長度，因此以這種方式執行的合併，僅會加入那些在不同 HLL 之間不共通的元素計數。

如你所見，HyperLogLog 是完全可平行化的，因為可以將一個集合分割成 N 個子集分別獨立計數，之後再合併這些值以取得總基數的近似值。Redis 中的 HLL 僅為字串，這有助於在不同執行個體之間搬移 HLL 值。

先求正確，再求快速
===

Redis 的 HLL 由封裝在 6 位元整數中的 16k 個暫存器組成。這帶來了幾個必須解決的效能問題，才能提供無需過多考量的快速 API 指令。

一個問題是，存取暫存器需要存取多個位元組、進行位移與遮罩，才能擷取正確的 6 位元值。對於每個元素僅觸及一個暫存器的 PFADD 來說，這不是大問題，但 PFCOUNT 需要使用全部 16k 個暫存器進行計算，因此如果存取每個暫存器都有不可忽略的固定時間成本，該指令就有可能變慢。此外，在存取暫存器的同時，我們還需要計算 pow(2,-register) 的總和，這涉及浮點數運算。

人們可能會想改用完整的位元組而非 6 位元整數來加速計算，然而這樣做會很可惜，因為每個 HLL 將會使用 16k 而非 12k，這是一個不小的差異，因此這條路一開始就被排除。透過以下變更，該指令相比初始實作獲得了約 3 倍的加速：

* 對於 m=16k，也就是 Redis 的預設值（實作本身更為通用，理論上可使用不同數值），實作會選擇一個具備展開迴圈的快速路徑，每次同時存取 16 個暫存器。暫存器透過固定的偏移／位移／遮罩來存取（透過某個每次迭代遞增 12 個位元組的指標）。
* 浮點數計算經過修改，以便在可能的情況下允許多個運算平行執行。這僅是加上括號的問題。浮點數運算不具交換律，但在這種情況下並未造成精度的損失。
* pow(2,-register) 項已在查詢表中預先計算。

透過上述變更帶來的 3 倍加速，該指令在快速的硬體上能夠達到每秒約 60k 次呼叫。然而，這仍遠不及那些從使用者角度來看概念上相似、如 SCARD 這類可達數十萬次呼叫的指令。

與其進一步最佳化近似基數的計算，還有一個更簡單的解決方案。基本上，演算法的輸出僅在某些暫存器發生變化時才會改變。然而如上所述，大多數的 PFADD 呼叫並不會導致任何暫存器改變。這基本上意味著可以快取最後一次的輸出，僅在某些暫存器發生變化時才重新計算。

因此，我們的資料結構在尾端額外包含了 8 個位元組，代表一個以小端序格式儲存的 64 位元無號整數。如果最高位元被設定，則表示預先計算的值已過時，需要重新計算，否則 PFCOUNT 可以直接使用它。PFADD 只需在某個暫存器被修改時打開「快取失效」位元即可。

經過這項變更後，即使嘗試以 50 個同時客戶端、管線化 32 個元素的方式以最大速度加入元素，PFCOUNT 也能表現得與任何其他具有極小固定時間的 O(1) 指令一樣好。

使用多項式迴歸進行偏差校正
===

為了具備實用性，HLL 演算法必須在任何基數範圍內都能同樣良好地運作。不幸的是，該演算法所做的原始估計在基數小於 m*2.5（對於 m=16384 約為 40000 個元素）時表現不佳，因為在此範圍內，演算法會輸出帶有偏差的結果，甚至在不同確切範圍內產生較大的誤差。

原始的 HLL 論文 [1] 建議，當 HLL 演算法第一階段所估計的原始基數小於 m*2.5 時，應切換為 Linear Counting（線性計數）[5]。

[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf

Linear Counting 是一種不同的基數估計器，使用一個簡單的概念。我們有一個 N 位元的點陣圖。每當必須計數一個新元素時，就會對其進行雜湊，並使用該雜湊來索引點陣圖中的一個隨機位元，將其設為 1。點陣圖中未設定位元的數量，透過以下公式可讓我們了解至今加入了多少元素：

    cardinality = m*log(m/ez);

其中 ‘ez’ 是零位元的數量，而 m 是點陣圖中位元的總數。

Linear Counting 對於大基數的表現不如 HyperLogLog，但在小基數時表現非常好。由於 HLL 暫存器本身也會作為線性計數點陣圖的副作用，透過計算零暫存器的數量，就有可能在 HLL 表現不佳的範圍內套用 Linear Counting。請注意，這之所以可行，是因為當我們更新暫存器時，我們實際上使用的並非最長連續零，而是最長連續零加一。這意味著如果加入一個元素並定址到一個從未被定址過的暫存器，該暫存器將從 0 變為不同的值（至少為 1）。

Linear Counting 的問題在於，隨著基數變大，其輸出誤差也變大，因此我們需要盡快切換回 HLL。然而當我們在 2.5m 時切換，HLL 仍存在偏差。在下圖中，相同的基數以 1000 個不同的集合進行測試，每次執行的誤差以一個點表示：



藍線是誤差的平均值。如你所見，在基數 40k 之前，也就是使用 Linear Counting 的區間，越往較大基數靠近，點的「光束」就越寬（誤差越大）。當我們切換到 HLL 原始估計時，誤差較小，但存在偏差：該演算法在 40k–80k 的範圍內會高估基數。

Google 的工程師們針對此問題進行了廣泛的研究 [2]，以校正偏差。他們的解決方案是建立一個基數值與對應偏差的經驗表格。他們修改後的演算法使用該表格與內插法，以便在給定範圍內取得偏差並據此進行校正。

我採用了不同的方法：你可以看到偏差並非隨機，而是看起來像一條非常平滑的曲線，因此我計算了一些基數-偏差樣本並執行多項式迴歸，以找出近似該曲線的多項式。

目前我在 40960–72000 的範圍內使用一個四階多項式進行校正，以下是偏差校正後的結果：



雖然在兩種演算法的切換點仍存在一些偏差，但與原始的 HLL 演算法相比，結果相當令人滿意，不過或許有可能使用更貼合偏差曲線的曲線。我沒有時間進一步研究這一點。

值得注意的是，在我的研究過程中我發現，至少對於 m=16384 的情況，若不使用偏差校正，從 Linear Counting 切換到 HLL 原始估計的最佳值實際上接近 3 而非 [1] 中提到的 2.5，因為值為 3 時既能改善偏差也能改善誤差。大於 3 的值會改善偏差（值為 4 時可完全校正偏差），但會對誤差產生不良影響。

原始的 HLL 演算法也會針對趨近 2^32 的值進行校正 [1][2]，因為一旦接近非常大的值，雜湊函式中的碰撞就開始成為問題。由於我們使用 64 位元雜湊函式與 6 位元計數器——這是 Google 工程師 [2] 提出的修改之一，並被 Redis 實作所採用——因此我們不需要此類校正。

未來工作
===

直觀上，似乎有可能在套用 Linear Counting 時，利用我們擁有的額外資訊來改善演算法輸出的誤差。在標準的 Linear Counting 演算法中，暫存器僅有 1 位元寬，因此我們只有兩種資訊：至今是否有元素雜湊到此位元。然而 HLL 演算法如最初在 [1] 中所提出，以及如在 Google [2] 修改後的版本，在回退到 Linear Counting 時，仍僅使用零暫存器的數量作為演算法的輸入。有可能同時利用暫存器中儲存的資訊來改善輸出。

例如在標準的 Linear Counting 中，假設我們有 10 個位元，我可能會加入 5 個元素，而它們恰好都定址到同一個位元。這是一個演算法無法校正的特殊情況，所提供的估計值很可能會小於實際基數。然而在 HLL 所使用的 Linear Counting 演算法中，在類似情況下，我們可能會發現唯一被設定的暫存器中的值，暗示了有多個元素在該處發生碰撞，從而允許對輸出進行校正。

結論
===

HyperLogLog 是一個令人驚艷的資料結構。我希望 Redis 的實作——將在數日內於穩定版本中提供（Redis 2.8.9 將會包含它）——能以即開即用的形式，為許多程式設計師提供這項工具。

HN 貼文在此： https://news.ycombinator.com/item?id=7506774