概念及入門

前言

在數(shù)據(jù)領(lǐng)域，有幾類經(jīng)典的查詢場(chǎng)景：

• 想要統(tǒng)計(jì)某段時(shí)間內(nèi)訪問某網(wǎng)站的 UV 數(shù)，或是統(tǒng)計(jì)某段時(shí)間內(nèi)既訪問了頁面 A 又訪問了頁面 B 的 UV 數(shù)，亦或是統(tǒng)計(jì)某段時(shí)間內(nèi)訪問了頁面 A 但未訪問頁面 B 的 UV 數(shù)，通常我們對(duì)這種查詢叫做基數(shù)統(tǒng)計(jì)。
• 想要觀察某些指標(biāo)的數(shù)據(jù)分布，例如統(tǒng)計(jì)某段時(shí)間范圍內(nèi)訪問頁面 A 與頁面 B 各自的瀏覽時(shí)長 95 分位數(shù)、50 分位數(shù)，則需要用到分位數(shù)統(tǒng)計(jì)。
• 想要統(tǒng)計(jì)某段時(shí)間內(nèi)播放量最多或者點(diǎn)擊率最高的 10 個(gè)視頻或者文章（熱榜列表），則需要用到 TopN 統(tǒng)計(jì)。

這幾類問題在數(shù)據(jù)量不大的情況下都是非常容易處理的。我們可以通過遍歷+排序輕易而準(zhǔn)確的解決這種問題。但一旦數(shù)據(jù)到達(dá) Billion 量級(jí)，常規(guī)算法可能要花費(fèi)數(shù)小時(shí)甚至數(shù)天的時(shí)間，并且即使提供充足的計(jì)算資源也于事無補(bǔ)，因?yàn)檫@幾類問題都難以并行化處理。

DataSketches[1] 就是為了解決大數(shù)據(jù)和實(shí)時(shí)場(chǎng)景下的這幾類典型問題而誕生的一組算法，最初由雅虎開源。這些算法以犧牲查詢結(jié)果的精確性為代價(jià)，可以在極小的空間內(nèi)并行、快速地解決上述幾類問題。

Sketch 結(jié)構(gòu)的核心思想

Sketch 結(jié)構(gòu)即「數(shù)據(jù)草圖」結(jié)構(gòu)，主要是為了計(jì)算海量的流式數(shù)據(jù)的概率指標(biāo)而設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)。一般占用固定大小的內(nèi)存，不隨著數(shù)據(jù)量的增加而增大。這種結(jié)構(gòu)通過巧妙地保存或丟棄一些數(shù)據(jù)的策略，將數(shù)據(jù)流的信息抽象存儲(chǔ)起來，匯總成 Sketch 結(jié)構(gòu)，最終能根據(jù) Sketch 結(jié)構(gòu)還原始數(shù)據(jù)的分布，實(shí)現(xiàn)基數(shù)統(tǒng)計(jì)、分位數(shù)計(jì)算等操作。

Sketch、Summary 都可以理解為數(shù)據(jù)草圖，不同論文中使用的稱呼不太一致，但是符號(hào)一般都是大寫的 S。

Sketch 一般具有以下幾個(gè)特征：

1. 單次遍歷

可以把 Sketch 理解為一個(gè)狀態(tài)存儲(chǔ)器，它時(shí)刻承載著數(shù)據(jù)流迄今為止的所有歷史信息，因此 Sketch 通常是 single-pass 的，只需要遍歷一遍數(shù)據(jù)即可取得所需的統(tǒng)計(jì)信息。

2. 占用空間小

傳統(tǒng)的統(tǒng)計(jì)方式需要維護(hù)一個(gè)巨大的數(shù)據(jù)列表，且隨著數(shù)據(jù)的輸入越來越大。Sketch 可以在很小的常量空間內(nèi)攝入海量的數(shù)據(jù)，通常在 KB 量級(jí)。這使得 Sketch 在海量數(shù)據(jù)的統(tǒng)計(jì)中非常有優(yōu)勢(shì)。

對(duì)于一個(gè)包含上億條數(shù)據(jù)、包含多個(gè)維度組合的數(shù)據(jù)集，可以在每個(gè)維度組合上轉(zhuǎn)化生成一個(gè) KB 大小的 Sketch 結(jié)構(gòu)，從而加快查詢。

3. 可合并性

可合并性使得 Sketch 可以自由地分布式并行處理大量數(shù)據(jù)，因此具有快速、高效的優(yōu)勢(shì)。以基數(shù)統(tǒng)計(jì) (Distinct Value, DV)為例，要解決的問題是從具有重復(fù)元素的數(shù)據(jù)流中查找不同元素的數(shù)量，Sketch 可以輕易地將局部統(tǒng)計(jì)結(jié)果合并為全局統(tǒng)計(jì)結(jié)果，而直接計(jì)數(shù)則做不到這一點(diǎn)，即：

• DV(uid | city=北京 or 上海) ≠ DV(uid | city=北京) + DV(uid | city=上海)
• Sketch(uid | city=北京 or 上海) = Sketch(uid | city=北京) + Sketch(uid | city=上海)

PS: 第二個(gè)式子中的加號(hào)代表 Sketch 的合并操作。

在分布式計(jì)算中，兩個(gè)處在不同機(jī)器的 Sketch 的局部統(tǒng)計(jì)結(jié)果可以直接通過一個(gè) Query 方法合并成一個(gè) Sketch 結(jié)構(gòu)，進(jìn)行最終的分位數(shù)查詢。

4. 誤差可控的近似值

Sketch 為了節(jié)省空間必然會(huì)丟失一部分信息，因此統(tǒng)計(jì)結(jié)果不可能是完全精確的。但在現(xiàn)實(shí)中，許多分析和決策也并不要求數(shù)據(jù)是絕對(duì)精確的，有時(shí)候知道某個(gè)統(tǒng)計(jì)數(shù)據(jù)在 1% 的誤差范圍內(nèi)往往跟精確的答案一樣有效。Sketch 可以在計(jì)算復(fù)雜度與誤差之間進(jìn)行權(quán)衡，足以滿足大數(shù)據(jù)場(chǎng)景下大部分的統(tǒng)計(jì)需求。

一個(gè) Sketch 算法的使用流程通常如下：

原始數(shù)據(jù)經(jīng)過轉(zhuǎn)化生成一個(gè) Sketch 結(jié)構(gòu)，當(dāng)要進(jìn)行查詢的時(shí)候，從 Sketch 生成一個(gè) Estimator 返回查詢結(jié)果

Quantile 的定義

分位點(diǎn)/分位數(shù)（Quantile）：考慮誤差近似，即給定誤差 ε 和分位點(diǎn) φ，只需要給定排序區(qū)間[(φ - ε)*N, (φ + ε)*N] 內(nèi)的任意元素即可(N 為元素個(gè)數(shù)）。

舉個(gè)例子，如果給定 input 序列如下，在 ε= 0.1 的情況下，求 PCT50（即 φ = 0.5）。返回 24、39、51 都是可以滿足條件的。但如果 ε= 0.01，只有返回 39 才是正確的結(jié)果。

φ= 0.5 and ε = 0.1

Rank = [4, 5, 6] → V = [24, 39, 51]

這也就是為什么我們使用 DoublesSketch UDF 或者 Spark 的分位數(shù)近似算法的時(shí)候可能會(huì)出現(xiàn)分位數(shù)計(jì)算結(jié)果不準(zhǔn)確的問題。此外，不同的分位數(shù)定位方法也會(huì)導(dǎo)致數(shù)據(jù)有細(xì)微的差距，后面會(huì)提及。

圖中，在當(dāng)前維度下的數(shù)據(jù)只有兩條，針對(duì)這兩條數(shù)據(jù)求 50 分位數(shù)的結(jié)果會(huì)不一樣。在小基數(shù)求分位數(shù)問題的時(shí)候，數(shù)據(jù)會(huì)出現(xiàn)較大的誤差。

Quantile 的誤差

quantile 和 rank 實(shí)際上是兩個(gè)函數(shù)：

我們期待一對(duì)完美的函數(shù)，使得 q = quantile(rank(q)) 或者 r = rank(quantile(r))，但現(xiàn)實(shí)中，我們往往只能得到兩個(gè)有誤差的函數(shù) r' = rank(q)和 q' = quantile(r)

分位數(shù)問題其實(shí)就是 quantile(r)問題，即給定 r，根據(jù)估計(jì)出來的 quantile 函數(shù)求出 q'。

函數(shù)的誤差由多種途徑帶來：

• 海量數(shù)據(jù)必然導(dǎo)致我們需要對(duì)數(shù)據(jù)進(jìn)行有條件的整合和過濾，由此引入誤差。但合理的整合、過濾機(jī)制能夠?qū)⒄`差控制在一定范圍內(nèi)。為此，無數(shù) researcher 貢獻(xiàn)了各種 idea，這也是文檔后半部分介紹的主要內(nèi)容。
• 重復(fù)值也會(huì)帶來誤差。但實(shí)際上，如果我們對(duì)分位點(diǎn)的定義和邊界條件做了正確的假設(shè)，那么這種誤差已經(jīng)被考慮在了算法之內(nèi)，本文不再做詳細(xì)解釋。舉一個(gè)簡(jiǎn)單的例子給大家感受一下，不同分位數(shù)定位方法與重復(fù)值是如何帶來誤差的：

Example

有五個(gè)數(shù)據(jù)輸入進(jìn)來計(jì)算分位點(diǎn)：{10, 20, 20, 20, 30}

上邊是原始數(shù)據(jù)經(jīng)過排序后的數(shù)值和位置對(duì)應(yīng)圖，下邊則可以想象成一個(gè)簡(jiǎn)單的存儲(chǔ)了這些數(shù)據(jù)的 Sketch 結(jié)構(gòu)。

在計(jì)算分位點(diǎn)的時(shí)候有兩種定位分位點(diǎn)的規(guī)則，LT (less-than) 和 LE (less-than or equals)。兩者在舉例中有區(qū)別，但是上升到泛化問題上則區(qū)別不大，都屬于可接受誤差范圍內(nèi)，在這個(gè)例子中我們對(duì)比 LT 和 LE 規(guī)則下得到的結(jié)果，能發(fā)現(xiàn)在重復(fù)值 20 上的 Rank' 和 Quantile' 是不一樣的，并且在邊界上的值的 Rank' 和 Quantile' 也有誤差。

LT (less-than) & GT(greater-than)

LE (less-than or equals) & GE(greater-than-or-equal)

想了解 LT 和 LE 規(guī)則的區(qū)別可以瀏覽 DataSketches 官網(wǎng)里關(guān)于 Quantiles 的定義[2]

業(yè)界 Quantile 實(shí)現(xiàn)

Quantile Sketches 經(jīng)過層層迭代和不斷的演進(jìn)，已經(jīng)形成多種變種。以 Apache DataSketches 中的實(shí)現(xiàn)總結(jié)[3]為例，很多 Sketches 算法早已應(yīng)用在了諸如 Spark、Hive、Druid 等等大數(shù)據(jù)開發(fā)常用框架中，當(dāng)我們?cè)?SQL 中調(diào)用 percentile 類函數(shù)的時(shí)候，不同框架會(huì)調(diào)用其對(duì)應(yīng)的算法。但由于不同框架實(shí)現(xiàn)的算法不一樣，實(shí)現(xiàn)的效率也有高低，最終會(huì)導(dǎo)致在使用的時(shí)候能明顯感知到計(jì)算速度的差異。

KLL 和 GK 算法應(yīng)該是目前被應(yīng)用最廣泛的算法。這里，我們選取兩個(gè)大數(shù)據(jù)開發(fā)場(chǎng)景下最常用的兩個(gè)框架 Spark 和 Hive 來舉例，對(duì)比其中的分位數(shù)計(jì)算函數(shù) percentile_approx 與一個(gè)由 Apache DataSketches 提供的算法實(shí)現(xiàn)，并簡(jiǎn)單講解一下如何將 Apache DataSketches 提供的更高效的算法引入日常開發(fā)工作中。

Spark

在 Spark 中計(jì)算分位數(shù)不需要引入 UDF，Spark 中的 ApproximatePercentile[4] 類實(shí)現(xiàn)了 GK 算法，以 QuantileSummaries[5] 的結(jié)構(gòu)作為數(shù)據(jù) Sketch，后面會(huì)提到 GK 算法并且簡(jiǎn)單解釋其概念。這個(gè)函數(shù)在數(shù)據(jù)量小的時(shí)候的計(jì)算效率是比較快的。

Hive

同樣，在 Hive 中計(jì)算分位數(shù)可以直接使用原生的分位數(shù)計(jì)算方法，但該方法背后算法并沒有 Spark 中的算法效率高效。Hive 中的 GenericUDAFPercentileApprox[6] 是通過計(jì)算近似數(shù)據(jù)直方圖的方式估算分位數(shù)。如 Hive 源碼提示，這個(gè)函數(shù)在數(shù)據(jù)量巨大的時(shí)候可能存在 OOM 的問題。此外，Hive 實(shí)現(xiàn)估計(jì)直方圖的算法主要依據(jù) A Streaming Parallel Decision Tree Algorithm[7]。值得一提的是，這個(gè)算法的核心想法是如何在有限的內(nèi)存中構(gòu)建數(shù)據(jù)的直方圖。

DataSketches

如果在面對(duì)海量數(shù)據(jù)的時(shí)候，Spark 原生分位數(shù)計(jì)算函數(shù)會(huì)顯得乏力，這時(shí)候就推薦引入 DataSketches 提供的分位數(shù)計(jì)算方法。該算法不光在空間占用上更優(yōu)，其計(jì)算效率也更高。DataSketches 的 DoubleSketch[8] 是根據(jù) Mergeable Summaries[9] 中提到的 Low Discrepancy Mergeable Quantiles Sketch 算法實(shí)現(xiàn)的。這篇論文主要討論了什么是 Mergeability 并對(duì)之前著名的算法的 Mergeability 進(jìn)行了證明。同時(shí)提出了一個(gè)結(jié)合抽樣的 Randomized Mergeable Quantiles Sketch 算法。

作為大數(shù)據(jù)開發(fā)同學(xué)，對(duì)于該算法需要了解以下幾點(diǎn)：

1. 這個(gè)算法的 Sketch 結(jié)構(gòu)能夠分布式進(jìn)行。
2. 由于算法引入隨機(jī)，每次的結(jié)果可能不同（但可以通過指定隨機(jī)種子來固定）。
3. 算法實(shí)現(xiàn)上通過壓縮、位圖等操作進(jìn)一步節(jié)省時(shí)空開銷。
4. 能用這個(gè)算法就用這個(gè)算法，快得很！

算法落地到日常開發(fā)也很容易，Datasketches 已經(jīng)提供了多種 UDF、UDAF，基本能夠滿足常見業(yè)務(wù)需求。需要先在 pom 文件中加入 org.apache.datasketches 依賴，然后可以根據(jù)業(yè)務(wù)需求，對(duì) datasketches 提供的 UDF、UDAF 再次封裝。打包成 jar 包并注冊(cè) UDF 之后，就可以在 SQL 中使用了。

Quantile Sketches 算法的演進(jìn)過程

問題定義

Quantile Sketches 算法最早可以追溯到上世紀(jì) 90 年代，當(dāng)流式數(shù)據(jù)以及分布式計(jì)算的概念剛剛在學(xué)術(shù)界得到普遍的認(rèn)可，這個(gè)問題被拋了出來。如何在海量數(shù)據(jù)中，甚至無限數(shù)據(jù)中，使用有限的空間，找到其中的某一個(gè) rank 對(duì)應(yīng)的值，或找到某一個(gè)數(shù)對(duì)應(yīng)的 rank。

Quantile Sketches 算法的發(fā)展依據(jù)重要的算法的推出，形成了幾個(gè)重要的階段。實(shí)際上，這個(gè)領(lǐng)域的初心是如何使用最小的內(nèi)存空間，解決一個(gè)最泛化的問題。

什么是最泛化的問題呢？學(xué)術(shù)界把這種問題稱為 All Quantiles Approximation Problem，其定義如下：

與最泛化問題相對(duì)應(yīng)，狹義問題被稱為 Single Quantile Approximation Problem。當(dāng)然還有很多問題的變體，例如，給定 rank 求對(duì)應(yīng)的數(shù)值（最常見的分位數(shù)問題）或者已知流數(shù)據(jù)大小求解 rank 或分位數(shù)等。

在明確了問題定義后，同樣也需要明確對(duì)算法的定義，一個(gè)合格的 Quantile Estimators 應(yīng)該具備以下四種特性：

1. 提供可調(diào)節(jié)的、可以被明確的誤差區(qū)間。
2. 與輸入數(shù)據(jù)獨(dú)立。
3. 只遍歷一次所有數(shù)據(jù)。
4. 應(yīng)使用盡可能小的內(nèi)存。

合格的 Estimator 并沒有對(duì)可合并性作出什么顯性的要求，mergeability 只是一個(gè) nice to have 的特性。問題定義中并沒有考慮 mergeability 的問題，所以有些算法沒有實(shí)現(xiàn) mergeability，導(dǎo)致無法完全適配實(shí)際生產(chǎn)中的分布式計(jì)算模式。即使適配，往往也需要更多空間，更高的計(jì)算復(fù)雜度。

空間優(yōu)化的終點(diǎn)在哪里？

業(yè)界和學(xué)術(shù)對(duì)于探索未知的東西往往具有相同的方法論：先找到最小內(nèi)存占用的天花板在哪里。通過構(gòu)造特殊的對(duì)抗數(shù)據(jù)流并且證明了在極端情況下，任何算法都需要的最小的內(nèi)存。如何找到這個(gè)問題的天花板并不是本文的重點(diǎn)，感興趣的讀者可以閱讀論文 An Ω (1/ε log 1/ε) Space Lower Bound for Finding ε-Approximate Quantiles in a Data Stream[10] 進(jìn)一步了解。

從壓縮出發(fā) - MRL 算法[11]

最簡(jiǎn)單的壓縮

數(shù)據(jù)丟棄

回想之前講解基礎(chǔ)概念的時(shí)候提及的例子，我們可以直觀的感受到，Sketch 數(shù)據(jù)結(jié)構(gòu)的一個(gè)特性就是對(duì)數(shù)據(jù)進(jìn)行合理的壓縮。壓縮后的數(shù)據(jù)盡可能的能夠全面還原數(shù)據(jù)原本的分布。為了實(shí)現(xiàn)這一原理，最直觀的想法就是針對(duì)每一個(gè)輸入數(shù)據(jù)通過某種規(guī)則選擇丟棄或保留，并確保將誤差控制在 ε 以內(nèi)。那么問題就變成了如何找到合適的丟棄規(guī)則。

舉個(gè)例子，可以根據(jù)數(shù)據(jù)的 index 來判斷是否丟棄：對(duì)于一個(gè)未排序的數(shù)據(jù)流，丟棄所有偶數(shù)位的數(shù)字，而保留奇數(shù)位的數(shù)字。但這顯然是一個(gè)有缺陷的方法，而且很容易證明：只需要構(gòu)建一個(gè)數(shù)據(jù)流，將所有較小的數(shù)據(jù)都放在偶數(shù)位，那么留下的數(shù)據(jù)則都是較大的數(shù)據(jù)，其中最小的數(shù)據(jù)也會(huì)大于或等于中位數(shù)。

從這個(gè)例子中得到啟發(fā)，我們可以先對(duì)數(shù)據(jù)流進(jìn)行排序，然后再根據(jù)上面的原則來丟棄數(shù)據(jù)，那么這個(gè)方法就變得可行了。

權(quán)重增加

另一個(gè)顯而易見的邏輯是，丟棄的數(shù)據(jù)不能單純地丟棄，它的信息必須以某種方式保存在未丟棄的數(shù)據(jù)中。繼續(xù)上例，偶數(shù)位置的數(shù)據(jù)被丟棄，可以同時(shí)增大它前一個(gè)奇數(shù)位置數(shù)據(jù)的權(quán)重，使得一個(gè)奇數(shù)位數(shù)字表示原本一個(gè)奇數(shù)位+偶數(shù)位的數(shù)字。這樣，數(shù)據(jù)量的信息就保存了下來，權(quán)重越大，也就意味著在這個(gè)區(qū)域內(nèi)的數(shù)據(jù)越多。

Batch 思想

然而流數(shù)據(jù)并不支持實(shí)時(shí)排序，并且隨著數(shù)據(jù)規(guī)模增大，排序所需要的時(shí)間和空間開銷都會(huì)不斷增長。一個(gè)自然的想法是，可以把流數(shù)據(jù)劃分成一個(gè)個(gè)的 batch，在每一個(gè) batch 內(nèi)部排序。

下圖中的例子結(jié)合了數(shù)據(jù)丟棄和權(quán)重增加兩個(gè)策略。其中，第一行是輸入數(shù)據(jù)被切分成一個(gè)個(gè)小 batch 并經(jīng)過內(nèi)部排序后的樣子。第二行表示丟棄所有偶數(shù)位的數(shù)據(jù)，并增加前一位奇數(shù)位數(shù)據(jù)的權(quán)重（小方格的高度增大了一倍）。第三行表示丟棄所有奇數(shù)位的數(shù)據(jù)，并增加后一位偶數(shù)位數(shù)據(jù)的權(quán)重。可以觀察到，一些位置的 Rank 發(fā)生改變，如果 Compactor 內(nèi)部數(shù)據(jù)是偶數(shù)的時(shí)候 Rank 不發(fā)生改變，如果是奇數(shù)則會(huì)相對(duì)加一或減一。按照這個(gè)過程就可以構(gòu)建一個(gè)最簡(jiǎn)單的 Sketch 結(jié)構(gòu)。

單個(gè) batch 數(shù)據(jù)壓縮問題的思路得到了初步的驗(yàn)證，那么問題來了，單個(gè) batch 如何推演到多個(gè) batch 甚至流數(shù)據(jù)上的呢？

壓縮與合并

假設(shè)有兩個(gè) Sketch 結(jié)構(gòu)，我們想要達(dá)成的效果是，當(dāng)把這兩個(gè) Sketch 結(jié)構(gòu)合并成一個(gè)之后，仍然能夠提供準(zhǔn)確的 Rank。

如下圖所示，紅點(diǎn)表示數(shù)據(jù) s_i < v，當(dāng)我們把兩個(gè) Sketch 結(jié)構(gòu)合并后發(fā)現(xiàn)，v 在合并后的數(shù)據(jù)集中的 Rank 就等于兩個(gè) Sketch 分別統(tǒng)計(jì)紅點(diǎn)個(gè)數(shù)的和，合并數(shù)據(jù)集的 Rank 不會(huì)因?yàn)椴鸱纸y(tǒng)計(jì)而變化。

因此，我們得到兩條推論：

但如果單純地把兩組數(shù)據(jù)拼接在一起，顯然會(huì)面臨數(shù)據(jù)量增加帶來的空間開銷增大的問題。此時(shí)再回到之前提到的壓縮、合并的思路，可以將這個(gè)過程不斷循環(huán)起來，即合并、壓縮、再合并、再壓縮……

MRL 算法原理簡(jiǎn)介

Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets[11]（MRL 算法）就是在壓縮、合并思想上加以改進(jìn)得來的。MRL 算法構(gòu)建了一個(gè)樹狀多層級(jí)壓縮合并結(jié)構(gòu)：

選擇一個(gè)固定大小的 k 作為 Sketch 結(jié)構(gòu)的大小。根據(jù)流數(shù)據(jù)量大小可以反推需要壓縮的層級(jí)數(shù) H。顯然，k 越大壓縮層級(jí)越少，相對(duì)丟失的信息就越少，結(jié)果就越精確。

過程很簡(jiǎn)單，原始流數(shù)據(jù)輸出到 level0 的一個(gè) Sketch 結(jié)構(gòu)中，當(dāng)數(shù)據(jù)填滿了大小為 k 的 Sketch 結(jié)構(gòu)后，如果 level0 沒有其他 Sketch，則這個(gè) Sketch 暫時(shí)緩存下來，等待另一個(gè) Sketch 到來。如果有另一個(gè) Sketch，則將兩個(gè) Sketch 歸并排序后保留所有奇數(shù)位置的數(shù)據(jù)，將 2k 大小的數(shù)據(jù)壓縮為 k 大小并傳入下一層級(jí)。同樣，如果下一層級(jí)已經(jīng)存在一個(gè) Sketch，那么進(jìn)行類似的歸并排序和丟棄壓縮后，將 Sketch 傳入下一層級(jí)，層層遞進(jìn)。

k 的大小直接影響數(shù)據(jù)準(zhǔn)確性，甚至還決定了這個(gè)算法能否收斂，比較合適的取值為 k = O(ε^{?1} _ log^2(εn))。MRL 算法在每一層級(jí)只需要兩個(gè) Sketch 結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)。層級(jí)數(shù)決定了所需要的總共空間大小，而層級(jí)數(shù)的是根據(jù)總數(shù)據(jù)量和單個(gè) Sketch 結(jié)構(gòu)大小推演得到的：

O(H) = O(log^2(n/k)) = O(log^2(εn))， 總共空間 O(kH) = O(ε^{-1} _ log^2(εn))。

從抽樣出發(fā) - Sample 算法[12]

假如現(xiàn)有一億個(gè)數(shù)字，我們想要對(duì)其中的某一個(gè)數(shù)字 x 求他的 Rank 是多少，Reservoir-Based Random Sampling with Replacement from Data Stream[12] 告訴我們，通過隨機(jī)抽樣我們可以用下面的公式從樣本估計(jì)整體的 Rank：

但這個(gè)是一個(gè)近似公式。一個(gè)嚴(yán)謹(jǐn)?shù)乃惴ㄐ枰闱宄@東西有多近似。碰巧存在這么一個(gè)不等式 Hoeffding's inequality 并根據(jù) Hoeffding's inequality 推出了這么一個(gè)定理

作為使用方，能理解證明是最好的，所以指路這篇文章的 VI 部分[13]。但是如果不理解證明，那么下面這段話會(huì)告訴你這個(gè)證明干了什么，有什么重要的意義（個(gè)人理解，可能存在不準(zhǔn)確的地方，歡迎指正）。

本質(zhì)上，Hoeffding's inequality 給出了隨機(jī)變量的和與其期望值偏差的概率上限。這個(gè)不等式是一個(gè) Bernoulli 過程的一個(gè)衍生（關(guān)于 Hoeffding's inequality 更詳細(xì)的指路這里[14]）。這種隨機(jī)抽樣到估計(jì)一個(gè)數(shù)字的 Rank 也是存在聯(lián)系的（誤差上限）。這種上限恰巧能夠讓把估計(jì)誤差限定在一個(gè)范圍內(nèi)，滿足了 Quantile Sketch 算法的要求。況且抽樣的過程將 Rank 結(jié)果與數(shù)據(jù)量 n 獨(dú)立開來。結(jié)果的誤差只取決于 m。而 m 是我們可以設(shè)定的一個(gè)數(shù)，換句話說，m 是我們可以設(shè)定的一個(gè)內(nèi)存大小，這個(gè)內(nèi)存大小決定了抽樣后估計(jì)的 Rank 的誤差上限。

可以觀察到，這里所需要的內(nèi)存大于 MRL 算法。但是它的最大意義在于移除了與數(shù)據(jù)量大小 n 的關(guān)系。需要明確的是，這種抽樣需要預(yù)先知道數(shù)據(jù)量大小 n，如果不知道數(shù)據(jù)量大小 n，抽樣仍然是有用的，但需要隨著數(shù)據(jù)量增大而降低抽樣概率。詳情見[13]

從結(jié)構(gòu)出發(fā) - GK 算法[15]

Summary 結(jié)構(gòu)設(shè)計(jì)

GK 算法 Space-Efficient Online Computation of Quantile Summaries[15] 的靈感來源于下面這個(gè)想法：假設(shè)我們收到的流數(shù)據(jù)的第一個(gè)數(shù)字就是中位數(shù)，那么我們只需要隨著數(shù)據(jù)的輸入統(tǒng)計(jì)大于這個(gè)數(shù)的數(shù)量和小于這個(gè)數(shù)的數(shù)量，最后就能很輕易的驗(yàn)證這個(gè)數(shù)是不是中位數(shù)。我們能不能對(duì) k 個(gè)輸入的數(shù)據(jù)都保持這個(gè)一個(gè)結(jié)構(gòu)，記錄大于這個(gè)結(jié)構(gòu)的數(shù)據(jù)的個(gè)數(shù)和小于這個(gè)結(jié)構(gòu)的數(shù)據(jù)的個(gè)數(shù)，那能找到對(duì)應(yīng)數(shù)字的 Rank 是多少了。

存在下面一個(gè)結(jié)構(gòu)，每一個(gè) tuple 存儲(chǔ)真實(shí)值、最小 Rank、最大 Rank，每一個(gè) tuple 叫 Summary：

對(duì)于任意數(shù)據(jù)，只要滿足下面的公式，那么算法總體誤差就是收斂的。

但是這個(gè)結(jié)構(gòu)存在缺陷。在處理流數(shù)據(jù)的時(shí)候，如果新來的數(shù)據(jù)需要插入中間，那么每次都需要更新后面所有的 Summary。這樣更新的復(fù)雜度實(shí)在太高了。GK 算法就此提出了一個(gè)針對(duì)插入數(shù)據(jù)操作更友好的 Summary 結(jié)構(gòu)：

將絕對(duì)位置轉(zhuǎn)化成相對(duì)位置進(jìn)行表示。

• g 表示兩個(gè)相鄰 Summary 的相對(duì)位置差異，根據(jù) g 和一個(gè)起始點(diǎn)我們能夠推演出這個(gè)起始點(diǎn)和 Summary 的距離是多少。
• Δ 表示這個(gè) Summary 覆蓋的 Rank 的范圍是多少。

根據(jù)這個(gè)上面這個(gè)定義能推論出一下三條性質(zhì)，詳細(xì)的推論這里不再贅述，有興趣的可以看這篇文章[16][17]

結(jié)合 Summary 結(jié)構(gòu)的一些操作

經(jīng)過一番數(shù)據(jù)公式的狂轟濫炸后，好像又摸不著 GK 算法在干什么了。如果想了解 GK 算法的細(xì)節(jié)，指路原始論文[15]。但如果僅僅想了解算法的思想，那么上面這都不重要，下面這段話告訴你這么一圈折騰到底為了什么。

如同數(shù)據(jù)庫的增刪改查一樣，構(gòu)建這么一個(gè)特殊的 Summary 結(jié)構(gòu)并推到這么多性質(zhì)，只是為了更快、更方便的實(shí)行以下這些操作：

1. 構(gòu)建一個(gè) Summary + 一個(gè)特殊的 INSERT() 方法 -> 使得更新數(shù)據(jù)特別快。
2. 構(gòu)建一個(gè) Summary + 一個(gè)特殊的 QUERY() 方法 -> 使得查詢滿足誤差約束。
3. 構(gòu)建一個(gè) Summary + 一個(gè)特殊的 DELETE() 方法 + 一個(gè)特殊的 COMPRESS() 方法 -> 使得空間保持不變且最優(yōu)。

INSERT

最大最小情況都很好理解。對(duì)于一般情況，新插入的數(shù)據(jù) i 顯然對(duì) i-1 前面的任何數(shù)據(jù)都沒有影響，但是后面的數(shù)據(jù)每一個(gè) Rank 都應(yīng)該增加一位 ，所以 g = 1。精妙之處就在于用相對(duì)位置的變化累加而表示了絕對(duì)位置的變化。Δ = g_i + Δ_i - 1 的原因后文會(huì)提及。

QUERY

All Quantiles Approximation Problem 有一條必須要滿足的性質(zhì)就是所有 x 都應(yīng)該滿足|R'(x) ? R(x)| ≤ εn，白話文解釋就是，當(dāng)我們發(fā)起一個(gè)查詢的時(shí)候（查詢 x 對(duì)應(yīng)的 Rank）返回值的誤差都應(yīng)該保持在一個(gè)與數(shù)據(jù)量成正比的線性關(guān)系中。

巧妙的設(shè)置查詢的方式就能將總體誤差控制在收斂范圍內(nèi)。

DELETE and COMPRESSDELETE and COMPRESS

面對(duì)海量的數(shù)據(jù)，單純的增加信息而不對(duì)信息做壓縮刪減顯然是不合理的。刪除規(guī)則如下：

刪除操作只改變 v_i+1 所在 Summary 的 g_i+1， 并不改變 Δ_i+1。也就是說 Δ 越小，在滿足誤差約束下，具有合并更多 Summary 的潛力。

為了更加高效的對(duì)數(shù)據(jù)進(jìn)行壓縮 GK 算法又提出了 Fullness、Capacity 和 Bands 三個(gè)概念。

這三個(gè)概念的誕生就是為了輔助進(jìn)行 COMPRESS 操作的，簡(jiǎn)單講，每個(gè) Summary 對(duì)應(yīng)的 Capacity 大小，從右向左來看，大小稱指數(shù)級(jí)倍數(shù)增大 ，而壓縮也是從右向左進(jìn)行的。下圖展示了不同大小 Sketch 對(duì)應(yīng)的每一個(gè)小的 Summary 的 Capacity 大小的關(guān)系，

下面的偽代碼展示了一個(gè)壓縮過程。滿足壓縮條件時(shí)，對(duì) Summary 結(jié)構(gòu)從右向左進(jìn)行合并，使得 Summary 先嘗試最少的內(nèi)存方法。

滿足壓縮條件后，相鄰 Summary 經(jīng)過 COMPRESS 操作后，數(shù)據(jù)更新到 Band 值較小的 Summary 上。由于 DELETE 操作并不改變 Δ 的特性，如果保留 Band 值大的 Summary 結(jié)構(gòu)，便有了更大的 Capacity，后期也就能夠容納更多的 Summary（將更多的 Summary 壓縮到一起）。

此外，GK 算法還引入了樹模型，通過右先序遍歷二叉樹，實(shí)現(xiàn)對(duì)于子節(jié)點(diǎn)的快速有序 COMPRESS 到父節(jié)點(diǎn)操作，不過，這里不再詳細(xì)介紹，感興趣的同學(xué)可以指路原始論文[15]。

需要注意的是，GK 算法是一個(gè) mergeable 的算法，準(zhǔn)確來說，是一個(gè) One-way mergeable 的算法。

One-way mergeability is a weaker form of mergeability that informally states that the following setting can work: The data is partitioned among several machine, each creates a Summary of its own data, and a single process merges all of the summaries into a single one. 換句話說，One-way mergeability merge 算法不能夠分布式進(jìn)行，否則誤差不在可控范圍內(nèi)，而 Fully mergeable 的算法可以，雖然論文中對(duì)這點(diǎn)描述的不是特別清楚，但是詳細(xì)證明指路這幾篇講解 [18][19][20]。

GK 到底好在哪？

說了這么多 GK 算法的原理，這算法到底好在哪里？

• GK 算法以一種獨(dú)特的方式存儲(chǔ)了數(shù)據(jù)信息，實(shí)現(xiàn)了海量數(shù)據(jù)的高效查詢，高效插入。
• GK 算法在原本的樹狀模型上引入了不同層級(jí)則不同大小的 Summary 結(jié)構(gòu)，更高效的利用了空間。

融合之開端 - ACHPWY 算法[9]

中國古話常講，取其精華，去其糟粕。后面的算法切實(shí)貫徹了這種思想。ACHPWY 算法 Mergeable Summaries[9] 的 Low Discrepancy Mergeable Quantiles Sketch 是一個(gè)基于 MRL 算法的衍生算法。在 MRL 算法上又增加隨機(jī)抽樣的方式，使得最終得到的 Quantile Estimator 是一個(gè)無偏的 Estimator。ACHPWY 算法的整體架構(gòu)和 MRL 算法一樣，都采用相同的大小為 k 的 Sketch 結(jié)構(gòu)，組成多層級(jí)樹狀模型。唯一不同的是，在進(jìn)行 Sketch 合并的時(shí)候，引入隨機(jī)變量 F 來決定取奇數(shù)位置數(shù)據(jù)還是偶數(shù)位置數(shù)據(jù)。

原本 MRL 算法在任何合并時(shí)只取奇數(shù)位，隨機(jī)的引入帶來了 unbiased Estimator，并且?guī)砀俚目臻g使用空間的。如同上文解釋的一樣，如果需要探討隨機(jī)變量的和與其期望值偏差的概率上限，那么 Hoeffding's inequality 一定不會(huì)缺席的。具體的證明和講解請(qǐng)參考[9][13]。

而對(duì)空間使用大小的估計(jì)和 MRL 算法原理一樣，都是需要選擇一個(gè)合適的 k 作為 Sketch 結(jié)構(gòu)的大小以達(dá)到空間最優(yōu)的目的。總共需要的內(nèi)存大小在 MRL 算法基礎(chǔ)上更進(jìn)一步。

此外，相較于其他算法，ACHPWY 算法更加清楚的定義并證明了 One-way mergeability 在其算法的可行性。并且證明了 Same-weight merges 情況和 Uneven-weight merges 情況下的的可行性（誤差收斂），使得分布式的 merge 操作實(shí)現(xiàn)有了基礎(chǔ)。

融合之大鍋燉 - KLL 算法[21]

KLL 算法原理簡(jiǎn)介

KLL 算法 Optimal Quantile Approximation in Streams[21] 可以理解為融合了之前提及的所有算法的優(yōu)點(diǎn)，在空間上做出了極致的壓縮，并且全面的證明了 KLL 算法能解決 All Quantiles Approximation Problem。

根據(jù)以往經(jīng)驗(yàn)可知：

1. 多層級(jí)的樹狀模型能滿足空間要求并且解決 All Quantiles Approximation Problem（MRL 算法）。
2. 對(duì)數(shù)據(jù)流的隨機(jī)抽樣策略解耦了誤差與數(shù)據(jù)量大小的關(guān)系，但是單獨(dú)使用空間效率不如 MRL 算法高（Sample 算法）。
3. 相對(duì)距離表示的數(shù)據(jù)結(jié)構(gòu) + 不同層級(jí)不同 Sketch 大小的策略提高了空間利用率（GK 算法）。
4. 融合多層級(jí)樹狀壓縮模型 + 隨機(jī)抽樣的策略能夠產(chǎn)生 unbiased Estimator 并且?guī)砀咝У目臻g利用率（ACHPWY 算法）。

KLL 算法則把這四點(diǎn)融合起來，并加以改進(jìn)，形成了這個(gè)更優(yōu)的算法。

下圖展示了 KLL 算法融合迭代的過程:

• 第一層為使用空間指數(shù)級(jí)增大的 Sketch 結(jié)構(gòu)的算法。
• 第二層將部分低層級(jí)的 Sketch 替換為 Sampler 的結(jié)構(gòu)。
• 第三層將頂層 Sketch 結(jié)構(gòu)替換為等大小的 Sketch 結(jié)構(gòu)并使用 MRL 算法的思想。
• 第四層再次將頂層 Sketch 結(jié)構(gòu)替換成等大小的 Sketch 結(jié)構(gòu)并使用 GK 算法的思想。

Sketch 空間指數(shù)增加設(shè)計(jì)

首先，為了節(jié)約空間，KLL 算法在 ACHPWY 算法基礎(chǔ)上將多層級(jí)同樣大小的壓縮結(jié)構(gòu)轉(zhuǎn)化為指數(shù)級(jí)增大的壓縮結(jié)構(gòu)。原理很好理解，數(shù)據(jù)剛輸入的時(shí)候沒有經(jīng)過過多的壓縮，沒有帶來更多的誤差，自然需要更大的空間去限制誤差的增大。但隨著數(shù)據(jù)不斷壓縮合并，丟失的信息越來越多，自然需要更大的空間去限制誤差增大的趨勢(shì)。

Bernoulli Sampler

隨著層級(jí)的降低，低層級(jí)的 Sketch 結(jié)構(gòu)空間大小不斷減小逐漸趨近于最小空間 2。如果空間小于 2，那么 Sketch 結(jié)構(gòu)沒有辦法進(jìn)行正常的壓縮。如果空間等于 1，Sketch 結(jié)構(gòu)將變成一個(gè)沒有意義的數(shù)據(jù)傳輸通道。那為何不把這些等于 2 的 Sketch 結(jié)構(gòu)換成一個(gè)簡(jiǎn)單的 Bernoulli Sampler 呢？這樣能夠在解耦合數(shù)據(jù)量大小的時(shí)候還將 Quantile Estimator 轉(zhuǎn)化成一個(gè) unbiased Estimator，還能更進(jìn)一步節(jié)省空間。空間大小將不再與數(shù)據(jù)量大小有任何關(guān)系（即是這個(gè)空間大小大約之前提到的算法的最優(yōu)解）。這種方法的所需空間大小為：

要想理解為什么這個(gè)結(jié)構(gòu)能夠?qū)⑺杩臻g和數(shù)據(jù)大小獨(dú)立開來，需要想象這么一個(gè)過程。隨著新的數(shù)據(jù)不斷的流入，在原本的最高層級(jí) H 被裝滿后，自然會(huì)壓縮合并出下一個(gè)更高層級(jí) H+1。那么假設(shè) H+1-> H，我們知道，為了保證誤差的收斂，對(duì)于 Sketch 大小是根據(jù)下面這個(gè)公式算出來的。不難發(fā)現(xiàn)，當(dāng)新的一個(gè)層級(jí)取代舊層級(jí)后，每一層級(jí)的 Capacity 其實(shí)都縮小了 1/c 倍。直到這個(gè)層級(jí)大小小于 2 的時(shí)候，Sketch 結(jié)構(gòu)便轉(zhuǎn)化成一個(gè) Bernoulli Sampler。將過小的 Sketch 結(jié)構(gòu) 吸收到 Sampler 結(jié)構(gòu)里使得整體的空間大小保持不變，是這個(gè)結(jié)構(gòu)的核心優(yōu)勢(shì)。

上層空間的進(jìn)一步優(yōu)化

在此基礎(chǔ)上，KLL 另一個(gè)核心發(fā)現(xiàn)是，大量的誤差主要由最上面的幾層 Sketch 結(jié)構(gòu)導(dǎo)致。優(yōu)化最上面幾層的結(jié)構(gòu)將大大降低誤差。KLL 算法提出將最上層的 s 個(gè) Sketch 從指數(shù)大小關(guān)系轉(zhuǎn)化成固定大小關(guān)系（新的 Sketch 的空間大小不一定等于最高一層 Sketch 的空間大小），換句話說，將最上層的 s 個(gè) Sketch 用 MRL 算法來實(shí)現(xiàn)。這種方法的所需空間大小為：

追求極致

為了追求極致的空間要求。KLL 算法提出用 GK 算法取代用 MRL 算法來實(shí)現(xiàn)最上層的 s 個(gè) Sketch，因?yàn)槔碚撋?GK 算法的所需空間更加的小。KLL 算法提出，將上層 s 個(gè) MRL Sketch 拆分成兩個(gè)緊密相連的 GK Sketch，使得在任何合并的時(shí)候，都會(huì)至少有一個(gè) GK Sketch 有數(shù)，并給出證明這種大融合的結(jié)構(gòu)能夠達(dá)到的最優(yōu)空間為：

但是不得不提及的是 KLL 算法作者們沒有給出 Fully mergeable 的證明，也無法保證 Fully mergeable 的存在。因?yàn)?GK 算法只支持 One-way mergeable，本身就不是 Fully mergeable 的。所以業(yè)界實(shí)現(xiàn)的時(shí)候，通常選用上層為 MRL Sketch 的方法實(shí)現(xiàn)。

總結(jié)

到這里，這篇文章從 Sketch 結(jié)構(gòu)的定義和特性出發(fā)，解釋了 Sketch 結(jié)構(gòu)如何解決大數(shù)據(jù)計(jì)算場(chǎng)景中海量數(shù)據(jù)計(jì)算痛點(diǎn)，明確了 Quantile 問題的定義。其次，結(jié)合大數(shù)據(jù)開發(fā)中常用組件，討論了如何將 Quantile Sketch 算法帶入工程實(shí)踐中。本文著重介紹了 Quantile Sketches 算法原理，涵蓋了算法發(fā)展的幾個(gè)重要階段和重要產(chǎn)物。筆者嘗試用最簡(jiǎn)單的語言和邏輯講解了每一個(gè)算法的核心思想、優(yōu)點(diǎn)和缺陷，嘗試將多種算法的發(fā)展串聯(lián)起來，方便沒有相關(guān)背景的人從零開始了解這個(gè)領(lǐng)域。但實(shí)際上 Quantile Sketches 算法仍然有很多的變種，例如為解決長尾分布而優(yōu)化的 Quantile Sketches 算法，為計(jì)算精確 PCT 邊界值而設(shè)計(jì)的 Digest 類算法[22][23]，根據(jù) Histogram 估計(jì)分位數(shù)的 Sketches 算法等……

希望大數(shù)據(jù)開發(fā)同學(xué)能夠了解算法推論、證明、衍生，期待有朝一日能看到以你們名字命名的 Quantile Sketches 算法。