我們是如何刪除 PB 級重復數據的？

　　作者丨Karthick Ramachandran

　　譯者丨良言

　　Mixpanel 通過網絡從移動端、瀏覽器端和服務器端的客戶接入了千萬億字節的事件數據。由于網絡的不可靠性，客戶可能會不斷重復發送事件請求，直到他們收到來自 Mixpanel 的 200 OK（連接成功）消息。雖然這種重試策略避免了數據丟失，但是在系統中創建了大量的重復事件。對這類重復事件的數據的分析也非常容易產生問題，因為它對所發生的事給出了一個不準確的描述，這也會導致 Mixpanel 偏離其它正在同步的客戶端數據系統，如數據倉庫。這也是為什么我們非常關心數據完整性的原因。

　　今天，我們很高興在這里分享我們的 PB 級規模的事件數據去重解決方案。

　　要 求

　　為解決這個問題，我們需要一個能夠滿足以下要求的方案：

　　可擴展性：能夠擴展到百萬事件 / 秒的接入量

　　低成本：為接入、存儲和查詢優化成本 / 性能負載

　　可追溯性：能夠對任意發送的事件進行重復識別

　　可恢復性：保留重復數據從而在配置錯誤時可以回滾

　　可維護性：最小化運營負載

　　最新技術：接入 - 時間去重

　　業界有很多富有創造性的方法來解決數據去重問題。其核心策略是在接入層構建一個能夠去重的的基礎設施?？蛻舭l送的每個事件都有一個唯一的 insertid 屬性標識。數據去重基礎設施會將所有事件的 insert_id 保存一定期限（例如 7 天），期間將會與每個新事件進行匹對，以查找去重標識。鍵值通常是用存儲的分片的 RocksDB 或 Cassandra。通過使用布隆過濾器來優化存儲中的查找成本。這種架構能夠確保在系統入口點就將重復內容清除。

　　但是，這種方法并不符合我們的要求，原因如下：

　　√ 擴展性：分片鍵值存儲可以水平擴展

　　× 低成本：需要一個單獨的數據庫和基礎設施來保存重復數據

　　× 可追溯性：只能抓取一定時間段的重復數據

　　× 可恢復性：抓取時丟棄數據，不能回滾

　　× 可維護性：刪除重復數據成為一個額外的服務，必須 24x7 不間斷

　　我們的方案

　　我們的方案是接入所有事件并在讀取時去重，該方案也滿足了前面所有的要求。每次查詢時，通過構建一個包含所有 $insert_id 的哈希表可以很容易地在讀取時實現去重；但是，這會給我們的系統增加一些額外的開銷。在詳細介紹這個方案之前，讓我們先回顧一下 Mixpanel 架構的幾個關鍵技術。

　　Mixpanel 架構

　　基于項目、用戶和時間的分片

　　Mixpanel 的分析數據庫 Arb 按照項目、用戶和時間對數據文件進行了分片。這可以確保指定用戶的所有數據都可以共同保存在一個位置，查詢時也可以在相關的時間段同時覆蓋多個用戶。

　　Lambda 架構

　　在 Arb 中，所有事件都被寫入 AOF（只允許追加的文件），這些文件被周期性地索引（壓縮）到后臺的柱狀文件中。AOF 在達到某個大小或時間閾值時，就會被索引。Arb 通過掃描小型的、實時的 AOF 和大型的、歷史的、索引的文件，從而確保查詢的實時性和高效性。

　　Mixpanel 架構

　　我們主要利用架構中的這兩類文件來提高讀時去重的效率。根據第一準則，重復事件具有以下屬性：

　　重復事件屬于同一項目

　　重復事件項屬于同一用戶

　　重復事件屬于同一事件時間

　　根據這些屬性特征，我們可以：

　　在搜索空間中搜索項目、用戶和日期的重復事件，即搜索單個 Arb 碎片。

　　通過與 lambda 架構一起攤銷來最小化去重開銷，從而維護查詢的實時和高效。

　　這幫助我們實現了一個滿足所有要求的解決方案。

　　數據去重架構

　　在 Mixpanel 的基礎設施中，在索引和查詢時都可以去重。

　　Mixpanel 架構

　　我們的索引器在內存中維護了一個 hashset，該 hashset 通過 $insert_id 保存了被索引文件中的所有事件。如果某個事件命中，則對該事件設置一個索引格式的重復標記位。這個過程的開銷很小，畢竟索引是在細粒度分片級別進行的。

　　查詢時，由于使用了 lambda 架構，我們可以同時掃描索引文件和 AOF。對于索引文件，我們可以檢查是否設置了重復位，如果設置了，則跳過處理事件。對于那些小的 AOF，查詢可以對 $insert_id 基于散列去重。這可以讓我們既實時又高效，充分發揮了 lambda 架構的優勢。

　　性 能

　　我們從實驗中發現，當索引含有 2% 重復的文件時會增加 4% 到 10% 的時間開銷。但這并沒有對用戶體驗產生直接影響，因為索引是一個離線過程。

　　對于查詢時間，我們發現當額外讀取一個事件的標志位時會增加大約 10ns 的時間。由于增加了額外的列，這使查詢時間增加了近 2%。每讀取 1000 萬個事件會增加約 0.1 秒（100 毫秒）的時間開銷。作為參考，由于采取了基于項目、用戶和時間的分片，Mixpanel 目前最大的柱狀文件包含大約 200 萬個事件。陸家嘴數據恢復我們認為在時間成本上的損失是完全可以接受的，因為我們在數據的保留期限和運營成本上都獲得了更大的回報。

　　未來工作

　　我們的解決方案并不完美，還有以下場景有待改善：事件可能因為分別保存在 AOF 和索引文件而造成重復。我們可以分別在索引文件或 AOF 中識別出重復項，但不能識別出不同文件中的重復。我們之所以選擇忽略這種情況，主要原因如下：

　　這種情況極其罕見：99.9% 的客戶的數據都非常小，以至于一整天的接入量都可以放入一個 AOF 文件中。這意味著 99.9% 的客戶不會受到這個問題的影響。

　　對于可能遇到此問題的大數據客戶，我們估計一個事件及其重復數據分別保存到兩個文件的幾率為 0.5%。

　　我們的系統會在當日結算時自我修復，當天所有的數據都會重新索引到一個文件中。所以重復數據只會在這一天中短暫出現。

　　我們發現，這種方法的優勢大大超過了其弊端。未來，我們會實現不同文件間的實時去重以及最近幾天文件的數據去重。

　　結 語

　　在文中，我們討論了在索引層分發重復標識和在查詢層分發重復過濾的架構。這個方案已經在 Mixpanel 內部成功運行了 6 個月的時間。

　　原文鏈接：

　　https://engineering.mixpanel.com/2019/07/18/petabyte-scale-data-deduplication/