完美世界有声小说全集,听中国有声小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

大規(guī)模實時分位數(shù)計算——QuantileSketches簡史

概念及入門

前言

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

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

創(chuàng)新互聯(lián)建站成都網(wǎng)站建設(shè)按需策劃設(shè)計，是成都網(wǎng)站開發(fā)公司,為成都汽車玻璃修復(fù)提供網(wǎng)站建設(shè)服務(wù),有成熟的網(wǎng)站定制合作流程，提供網(wǎng)站定制設(shè)計服務(wù)：原型圖制作、網(wǎng)站創(chuàng)意設(shè)計、前端HTML5制作、后臺程序開發(fā)等。成都網(wǎng)站推廣熱線：13518219792

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

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

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

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

Sketch 一般具有以下幾個特征：

1. 單次遍歷

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

2. 占用空間小

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

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

3. 可合并性

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

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

PS: 第二個式子中的加號代表 Sketch 的合并操作。

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

4. 誤差可控的近似值

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

一個 Sketch 算法的使用流程通常如下：

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

Quantile 的定義

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

舉個例子，如果給定 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ù)近似算法的時候可能會出現(xiàn)分位數(shù)計算結(jié)果不準(zhǔn)確的問題。此外，不同的分位數(shù)定位方法也會導(dǎo)致數(shù)據(jù)有細(xì)微的差距，后面會提及。

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

Quantile 的誤差

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

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

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

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

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

Example

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

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

在計算分位點的時候有兩種定位分位點的規(guī)則，LT (less-than) 和 LE (less-than or equals)。兩者在舉例中有區(qū)別，但是上升到泛化問題上則區(qū)別不大，都屬于可接受誤差范圍內(nèi)，在這個例子中我們對比 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 實現(xiàn)

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

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

Spark

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

Hive

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

DataSketches

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

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

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

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

Quantile Sketches 算法的演進過程

問題定義

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

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

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

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

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

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

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

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

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

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

最簡單的壓縮

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

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

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

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

權(quán)重增加

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

Batch 思想

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

下圖中的例子結(jié)合了數(shù)據(jù)丟棄和權(quán)重增加兩個策略。其中，第一行是輸入數(shù)據(jù)被切分成一個個小 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ù)的時候 Rank 不發(fā)生改變，如果是奇數(shù)則會相對加一或減一。按照這個過程就可以構(gòu)建一個最簡單的 Sketch 結(jié)構(gòu)。

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

壓縮與合并

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

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

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

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

MRL 算法原理簡介

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

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

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

k 的大小直接影響數(shù)據(jù)準(zhǔn)確性，甚至還決定了這個算法能否收斂，比較合適的取值為 k = O(ε^{?1} _ log^2(εn))。MRL 算法在每一層級只需要兩個 Sketch 結(jié)構(gòu)存儲數(shù)據(jù)。層級數(shù)決定了所需要的總共空間大小，而層級數(shù)的是根據(jù)總數(shù)據(jù)量和單個 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)有一億個數(shù)字，我們想要對其中的某一個數(shù)字 x 求他的 Rank 是多少，Reservoir-Based Random Sampling with Replacement from Data Stream[12] 告訴我們，通過隨機抽樣我們可以用下面的公式從樣本估計整體的 Rank：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

INSERT

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

QUERY

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

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

DELETE and COMPRESSDELETE and COMPRESS

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

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

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

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

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

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

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

需要注意的是，GK 算法是一個 mergeable 的算法，準(zhǔn)確來說，是一個 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 算法不能夠分布式進行，否則誤差不在可控范圍內(nèi)，而 Fully mergeable 的算法可以，雖然論文中對這點描述的不是特別清楚，但是詳細(xì)證明指路這幾篇講解 [18][19][20]。

GK 到底好在哪？

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

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

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

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

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

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

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

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

KLL 算法原理簡介

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

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

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

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

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

第一層為使用空間指數(shù)級增大的 Sketch 結(jié)構(gòu)的算法。
第二層將部分低層級的 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è)計

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

Bernoulli Sampler

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

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

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

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

追求極致

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

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

總結(jié)

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

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

網(wǎng)頁名稱：大規(guī)模實時分位數(shù)計算——QuantileSketches簡史
網(wǎng)頁地址：http://m.fisionsoft.com.cn/article/ccidppe.html