就像在Venture Beat上所宣布的那樣，雅虎開源了DataSketches，這是一個用Java編寫的隨機流算法庫。DataSketches允許進行通常來說開銷很大的操作，像計算變量不同的值在流中出現的次數，而且消耗的時間少，占用的內存小，誤差可預測。
正如他們在技術博客上所作的說明，雅虎內部已經使用DataSketches來提升多個產品的性能，包括Flurry。Sketch是DataSketches的一個基本概念，這是一個流的“匯總（summary）”，其中每次更新都按同樣方式處理，而不考慮歷史更新。這個概念是DataSketches性能的核心，因為傳統的流處理需要保存一個隨著時間增長的歷史。例如，如果要計算每個唯一值出現的次數，就需要保存每個新出現的唯一值，這樣，對于后來的唯一值，檢查時間將會增加；因此，每次更新都會以一種不同的、開銷更大的方式處理。另一方面，sketch的構造方式使它只能保存固定數量的、需要保存的信息，也就是說，所有的更新都以完全相同的方式執行。
如果仔細研究下DataSketches背后的科學原理，那么我們就會發現，它以整合了KMV和自適應采樣算法的Theta-Sketch框架為基礎。感興趣的讀者可以讀下這篇論文，它提供了該框架的形式化描述和特性說明，但在這里，我們將提供一種簡化的、更為直觀的描述。
就讓我們將這個問題置于實時計算一個網站的獨立訪客的場景下。計算一個流中不同的變量值出現的次數，主要的問題是需要為每個已知的、不同的變量值存儲一個副本。除此之外，變量的每個新實例（例如，每次新訪問網站）都需要對照已知的、不同的變量值所組成的列表進行檢查，看看這是一個新訪客，還是一個已有的訪客。這就是說，假如獨立訪客的數量為N，則系統需要的內存為O（N），每次網站訪問需要花費長為O（log N）的時間來檢查是否是一個獨立訪客。
KMV（第k個最小值）算法的策略是以存儲更少的值（k個值）為基礎，從中可以估計出N的大小，而且誤差范圍固定。要存儲的值使用哈希函數計算得出，該函數將要測量的變量（在這個例子中是指對頁面的獨立訪問）映射成0到1之間的一個值；實際上，這個哈希函數是什么并不重要，只要結果可以均勻地分布在0到1之間就可以。每次測量變量的一個新實例，我們就計算它的哈希值，并查看我們是否已經存儲了該哈希值，如果沒有，就存儲它。實際上，主要的不同點是，在任何時刻，只有k個最小的值會被保存：如果有一個新值加入到組中，那么第k+1個值會被移除，保證內存占用一直為O（k），時間成本一直為O（log k）。這樣，不同值出現的次數就可以估計為（k-1）/KMV，其中，KMV為第k個最小值，或者是組中存儲的、幸存下來的、最大的哈希值。
從檢查結果表達式很容易推斷出，如果我們比較兩個流的數據，一個流中出現不同值的次數多于另一個，那么出現更多不同值的流會產生更多的哈希值，因此，存儲的第k個哈希值將會比另一個流的第k個哈希值小。在k相同的情況下，第k個哈希值越小，上述表達式計算得出的值越大。由此可以得出結論，該表達式至少是與出現不同值的實際數量成正比的。
有多篇研究論文已經證明了，上文從形式上闡述的表達式是一個很好的估計，不過，一個簡單的試驗就可以提供描述性的證據。假設一個數據流出現199個不同的值，而且我們在算法中讓k=20。如果一個哈希函數將結果均衡分布在0到1之間，那出現的199個不同的值大體上將映射為0.005、0.01、0.015等等，直到0.995。如果我們只保存20個最小的值，那么第20個值將是0.1，將這個值帶入上述表達式，結果是（20-1）/0.1=190。
除了性能外，DataSketches還有其他特性，例如，它能夠組合已經分別計算好的sketch，并得到一個綜合結果，而不需要要檢查底層數據。這使用戶可以計算單個組的數據或者數據分區，然后根據需要組合它們。Maven Central中提供了DataSketches庫，以及用于Hadoop Pig、Hadoop Hive和Druid的適配器。
查看英文原文：Yahoo Open-Sources DataSketches for Faster Operations Over Streams
京公網安備 11010502049343號