就像在Venture Beat上所宣布的那樣，雅虎開源了DataSketches，這是一個用Java編寫的隨機(jī)流算法庫。DataSketches允許進(jìn)行通常來說開銷很大的操作，像計算變量不同的值在流中出現(xiàn)的次數(shù)，而且消耗的時間少，占用的內(nèi)存小，誤差可預(yù)測。

正如他們在技術(shù)博客上所作的說明，雅虎內(nèi)部已經(jīng)使用DataSketches來提升多個產(chǎn)品的性能，包括Flurry。Sketch是DataSketches的一個基本概念，這是一個流的“匯總（summary）”，其中每次更新都按同樣方式處理，而不考慮歷史更新。這個概念是DataSketches性能的核心，因為傳統(tǒng)的流處理需要保存一個隨著時間增長的歷史。例如，如果要計算每個唯一值出現(xiàn)的次數(shù)，就需要保存每個新出現(xiàn)的唯一值，這樣，對于后來的唯一值，檢查時間將會增加；因此，每次更新都會以一種不同的、開銷更大的方式處理。另一方面，sketch的構(gòu)造方式使它只能保存固定數(shù)量的、需要保存的信息，也就是說，所有的更新都以完全相同的方式執(zhí)行。

如果仔細(xì)研究下DataSketches背后的科學(xué)原理，那么我們就會發(fā)現(xiàn)，它以整合了KMV和自適應(yīng)采樣算法的Theta-Sketch框架為基礎(chǔ)。感興趣的讀者可以讀下這篇論文，它提供了該框架的形式化描述和特性說明，但在這里，我們將提供一種簡化的、更為直觀的描述。

就讓我們將這個問題置于實時計算一個網(wǎng)站的獨(dú)立訪客的場景下。計算一個流中不同的變量值出現(xiàn)的次數(shù)，主要的問題是需要為每個已知的、不同的變量值存儲一個副本。除此之外，變量的每個新實例（例如，每次新訪問網(wǎng)站）都需要對照已知的、不同的變量值所組成的列表進(jìn)行檢查，看看這是一個新訪客，還是一個已有的訪客。這就是說，假如獨(dú)立訪客的數(shù)量為N，則系統(tǒng)需要的內(nèi)存為O（N），每次網(wǎng)站訪問需要花費(fèi)長為O（log N）的時間來檢查是否是一個獨(dú)立訪客。

KMV（第k個最小值）算法的策略是以存儲更少的值（k個值）為基礎(chǔ)，從中可以估計出N的大小，而且誤差范圍固定。要存儲的值使用哈希函數(shù)計算得出，該函數(shù)將要測量的變量（在這個例子中是指對頁面的獨(dú)立訪問）映射成0到1之間的一個值；實際上，這個哈希函數(shù)是什么并不重要，只要結(jié)果可以均勻地分布在0到1之間就可以。每次測量變量的一個新實例，我們就計算它的哈希值，并查看我們是否已經(jīng)存儲了該哈希值，如果沒有，就存儲它。實際上，主要的不同點是，在任何時刻，只有k個最小的值會被保存：如果有一個新值加入到組中，那么第k+1個值會被移除，保證內(nèi)存占用一直為O（k），時間成本一直為O（log k）。這樣，不同值出現(xiàn)的次數(shù)就可以估計為（k-1）/KMV，其中，KMV為第k個最小值，或者是組中存儲的、幸存下來的、最大的哈希值。

從檢查結(jié)果表達(dá)式很容易推斷出，如果我們比較兩個流的數(shù)據(jù)，一個流中出現(xiàn)不同值的次數(shù)多于另一個，那么出現(xiàn)更多不同值的流會產(chǎn)生更多的哈希值，因此，存儲的第k個哈希值將會比另一個流的第k個哈希值小。在k相同的情況下，第k個哈希值越小，上述表達(dá)式計算得出的值越大。由此可以得出結(jié)論，該表達(dá)式至少是與出現(xiàn)不同值的實際數(shù)量成正比的。

有多篇研究論文已經(jīng)證明了，上文從形式上闡述的表達(dá)式是一個很好的估計，不過，一個簡單的試驗就可以提供描述性的證據(jù)。假設(shè)一個數(shù)據(jù)流出現(xiàn)199個不同的值，而且我們在算法中讓k=20。如果一個哈希函數(shù)將結(jié)果均衡分布在0到1之間，那出現(xiàn)的199個不同的值大體上將映射為0.005、0.01、0.015等等，直到0.995。如果我們只保存20個最小的值，那么第20個值將是0.1，將這個值帶入上述表達(dá)式，結(jié)果是（20-1）/0.1=190。

除了性能外，DataSketches還有其他特性，例如，它能夠組合已經(jīng)分別計算好的sketch，并得到一個綜合結(jié)果，而不需要要檢查底層數(shù)據(jù)。這使用戶可以計算單個組的數(shù)據(jù)或者數(shù)據(jù)分區(qū)，然后根據(jù)需要組合它們。Maven Central中提供了DataSketches庫，以及用于Hadoop Pig、Hadoop Hive和Druid的適配器。

查看英文原文：Yahoo Open-Sources DataSketches for Faster Operations Over Streams