一般來說，我很喜歡隨機化演算法，但其中有一個我特別偏愛——即使你已經理解它的運作原理，從程式設計師的角度來看，它依然充滿魔力。它以極少的時間與空間需求，完成了一件幾乎不合邏輯的事。這個演算法叫做 HyperLogLog，而今天，它將作為 Redis 的全新資料結構登場。

計算不重複項目
===

通常要計算不重複項目的數量，例如今天連上你網站的不重複 IP 數量，或是使用者執行的不重複搜尋次數，就必須記住目前為止遇過的所有不重複元素，以便將下一個元素與已見過的集合比對，只有在該元素從未出現過時才讓計數器加一。

這需要的記憶體用量與我們正在計算的集合基數（項目數量）成正比，往往高到完全無法負擔。

有一類演算法利用隨機化，只用固定且少量的記憶體，就能對集合中不重複元素的數量提供近似估計。目前這類演算法中最優秀的就叫做 HyperLogLog，由 Philippe Flajolet 所提出。

HyperLogLog 的出色之處在於，即使只用極少的記憶體，也能對集合的基數提供非常好的近似估計。在 Redis 的實作中，每個 key 只需要 12kbytes 就能以 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 每個值只需要 12k 位元組來存放 16k 個暫存器。

由於使用了 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」是為了向 Philippe Flajolet 致敬 [4]。

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

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

該指令在底層的 HyperLogLog 有被修改時回傳 1，否則回傳 0。
這對使用者來說很有用，因為隨著加入的元素越來越多，實際會修改到暫存器的機率會逐漸降低。API 能夠提示是否產生了新的基數，讓持續加入元素、只在有新基數可用時才擷取近似基數的程式得以實現。

PFCOUNT 會回傳估計的基數，如果 key 不存在則為零。

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

由此可見，HyperLogLog 是完全可平行化的，因為可以將一個集合切成 N 個子集合分別獨立計算，之後再合併這些值以取得總基數的近似估計。Redis 中的 HLL 只是字串，這也讓 HLL 值在不同實例之間搬移變得容易。

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

Redis 的 HLL 由 16k 個以 6 位元整數打包而成的暫存器組成。這帶來了幾個必須解決的效能問題，才能提供一個可以不假思索呼叫的指令 API。

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

人們可能會想改用完整的位元組而非 6 位元整數來加速計算，但這麼做很可惜，因為每個 HLL 就會從 12k 變成 16k，這個差距並不小，因此這條路一開始就被排除了。透過以下修改，該指令比初始實作加速了約 3 倍：

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

經過上述修改帶來的 3 倍加速後，該指令在高速硬體上每秒可執行約 6 萬次呼叫。然而，這仍然遠低於從使用者角度來看概念上類似的指令（如 SCARD）所能達到的數十萬次呼叫。

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

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

做了這個改動後，即使以管線一次 32 個元素、同時 50 個客戶端以最高速度嘗試加入元素，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

線性計數是一種不同的基數估計器，其概念很簡單。我們有一個 N 位元的位元圖。每當要計算一個新元素時，就對其進行雜湊，並用雜湊值來索引位元圖中的一個隨機位元，將其設為 1。位元圖中未被設定的位元數量，可以透過以下公式讓我們推估目前已加入了多少元素：

    cardinality = m*log(m/ez);

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

線性計數對於大基數的表現不如 HyperLogLog，但對於小基數則表現非常好。由於 HLL 的暫存器本身也會產生類似線性計數位元圖的副作用，透過計算零暫存器的數量，就能在 HLL 表現不佳的範圍內套用線性計數。請注意，這之所以可行，是因為我們在更新暫存器時，並不是真的只使用最長的零連續長度，而是最長零連續長度加一。這表示如果加入一個元素且其對應的暫存器從未被定址過，該暫存器就會從 0 變為不同的值（至少為 1）。

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



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

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

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

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



雖然在兩種演算法的切換點上仍有些微偏差，但相較於未經處理的 HLL 演算法，結果已經相當令人滿意，不過或許還能使用更貼合偏差曲線的曲線。我還沒有時間進一步研究。

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

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

未來工作
===

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

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

結論
===

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

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