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

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

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

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

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

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

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

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

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