【CSDN報道】幾天前，CSDN編譯了國外AddThis公司的數據分析副總監Matt Abrams在High Scalability上發表的一篇文章，Matt Abrams在這篇文章中向讀者介紹了AddThis僅用了1.5KB內存就計算了十億個不同的對象，充分展示了算法的魅力。
這篇文章在微博上得到了廣泛關注，並得知一淘的算法也同樣出彩。為此，CSDN采訪了一淘數據部的張洋（他曾先後就讀於煙台大學和北京航空航天大學，2011年在北京航空航天大學取得計算機理論碩士學位，同年加入淘寶，目前在一淘數據部工作），請他講解一下一淘的相關算法。
圖：一淘數據部工程師 張洋
CSDN：首先請您介紹一下自己以及平時的工作？
張洋：我叫張洋，在公司的花名是夜沨。目前是一淘數據部一名普通碼農，和千千萬萬碼農一樣，每天以敲代碼寫程序為工作，同時也將其視為人生第二大樂趣（第一大樂趣是吃）。我對PHP、Nginx、數據挖掘、機器學習、算法、編譯器和分布式存儲計算等技術興趣濃厚，喜愛數學和歷史。我很喜歡寫程序這個工作，也希望能將編程作為畢生的職業。寫程序之余也喜歡研究數學和算法，同時我很樂於將自己學到的東西總結成文章發表在博客上和大家分享，有興趣的朋友可以來我博客逛逛：codinglabs.org。
我在一淘數據部的職位是前端開發，但是我這個“前端開發”比一般意義上的前端工程師做的事要雜一些，除了負責HTML、CSS和JavaScript外，也開發PHP、Lua的後台程序，偶爾也會根據興趣和需要來開發一些C和算法的程序（我很喜歡寫C和算法，十分樂在其中），同時我還做一些運維工作，例如搭建服務器環境和維護線上服務器。
CSDN：是什麼原因促使您對算法感興趣的？
張洋：可能是源自我對數學的興趣吧，我一直很喜歡數理性的東西。正式接觸算法是大二的時候，當時買了一本算法導論，才真正開始了解漸近復雜度、算法分析、動態規劃、貪心算法、NP問題等一系列算法領域最基本的東西。看的時候就覺得很神奇，感覺書中的每個算法都閃耀著人類的智慧，閱讀和學習這些東西給我帶來一種難以用語言表達的滿足感和快感。在後來的學習和工作中我不斷從實際應用中了解和領會算法是如何解決各個領域的實際問題，推動人類文明的發展，這更加深了我對算法的崇敬。
CSDN：一淘數據部為什麼會開發這個基數估計算法？
張洋：一淘數據部主要在電子商務領域做一些數據的分析挖掘，並將這些技術與業務緊密結合形成一些數據產品和服務，例如數據分析、推薦系統等我們都有做。這些數據產品既對外服務，也會對公司或集團內部的運作提供支持。
在電子商務的數據分析領域有一些很關鍵的指標（例如unique visitor，簡稱UV，指在一定的時間空間維度約束下獨立訪客的數量）的計算是很常見的任務。一般來說我們首先會通過某種手段給每一個獨立訪客做一個標記（例如通過cookie），然後會在所有訪問日志中記錄下訪客的標記，這樣一來，UV的計算就等價為在一個可重復的用戶標記集合中計算不重復元素的個數，也就是數學上的基數。
基數的計算有兩個難點：
一是不利於實時流計算的實現。例如我們的一些產品中經常會提供實時UV，也就是從某個時間點開始（例如今天零點）到目前的獨立訪客數。為了做到這點，需在內存中為每一個UV數值維護一個查找性能高的數據結構（例如B樹），這樣當實時流中新來一個訪問時，能快速查找這個訪客是否已經來過，由此確定UV值是增加1還是不變。如果我們要為100萬家店鋪同時提供這種服務，就要在內存中維護100萬個B樹，而如果還要分不同來源維度計算UV的話，這個數量還會迅速膨脹。這對我們的服務器計算資源和內存資源都是一個很大的挑戰。
第二點就是傳統的基數計算方法無法有效合並。例如，前一小時和這一小時的UV雖然分別計算出來了，但是要看這兩個小時的總UV依然要重新進行一遍復雜的計算。使用bitmap數據結構的方案雖然可以快速合並，但是空間復雜度太高，因為時間段的任意組合數量與時間段數量呈冪級關系，所以不論是B樹還是簡單的bitmap在大數據面前都不是一個有效的方案。
基於以上背景，一淘數據部的技術專家王曉哲（花名清無）研究了基數估計的相關算法及Clearspring的一個java實現（stream-lib），並率先在我們的全息效果平台（代號月光寶盒）的項目中引入了基數估計算法，目前已成功實現利用少量內存對大量UV進行計算的技術難題，並承擔了雙十一和雙十二大促中天貓和淘寶所有會場坑位的效果實時計算任務。
為了方便更多的非Java項目使用此類算法，王曉哲和我根據相關論文並參考stream-lib給出了一個C版本的實現ccard-lib，接著一淘數據部的工程師張維（花名民瞻）又實現了PHP的擴展。目前這個C的實現已經在一淘數據部多個產品中開始使用，並且也已經通過github進行了開源。
CSDN：能不能向讀者詳細介紹一下一淘數據部的基數估計算法？
張洋：我們使用的算法主要是Adaptive Counting算法，這個算法出現在 “Fast and accurate traffic matrix measurement using adaptive cardinality counting” 這篇論文裡，但是我同時在ccard-lib裡也實現了Linear Counting、LogLog Counting和HyperLogLog Counting等常見的基數估計算法。
這些算法是概率算法，就是通過犧牲一定的准確性（但是精度可控，並可以通過數學分析給出控制精度的方法），來大幅節省計算的資源使用。例如我們僅僅使用8k的內存就可以對一個數億量級的UV進行估計，而誤差不超過2%，這比使用B樹或原始bitmap要大幅節省內存。同時基數估計算法用到了經過哈希變換的bitmap空間，在大幅節省內存的同時依然可以實現高效合並，這就同時解決了上面提到的兩個難點。
使用2^16（64K）位時，估算結果如下：
Linear Counting with Murmurhash:
actual: 50000, estimated: 50062, error: 0.12%
actual: 100000, estimated: 99924, error: 0.08%
actual: 150000, estimated: 149865, error: 0.09%
actual: 200000, estimated: 199916, error: 0.04%
actual: 250000, estimated: 250123, error: 0.05%
actual: 300000, estimated: 299942, error: 0.02%
actual: 350000, estimated: 349801, error: 0.06%
actual: 400000, estimated: 400101, error: 0.03%
actual: 450000, estimated: 449955, error: 0.01%
actual: 500000, estimated: 500065, error: 0.01%
Linear Counting with Lookup3hash:
actual: 50000, estimated: 49835, error: 0.33%
actual: 100000, estimated: 99461, error: 0.54%
actual: 150000, estimated: 149006, error: 0.66%
actual: 200000, estimated: 198501, error: 0.75%
actual: 250000, estimated: 248365, error: 0.65%
actual: 300000, estimated: 298065, error: 0.65%
actual: 350000, estimated: 347504, error: 0.71%
actual: 400000, estimated: 397292, error: 0.68%
actual: 450000, estimated: 446700, error: 0.73%
actual: 500000, estimated: 495944, error: 0.81%
Hyperloglog Counting with Murmurhash:
actual: 50000, estimated: 50015, error: 0.03%
actual: 100000, estimated: 100048, error: 0.05%
actual: 150000, estimated: 149709, error: 0.19%
actual: 200000, estimated: 201595, error: 0.80%
actual: 250000, estimated: 250168, error: 0.07%
actual: 300000, estimated: 299864, error: 0.05%
actual: 350000, estimated: 348571, error: 0.41%
actual: 400000, estimated: 398583, error: 0.35%
actual: 450000, estimated: 448632, error: 0.30%
actual: 500000, estimated: 498330, error: 0.33%
Hyperloglog Counting with Lookup3hash:
actual: 50000, estimated: 49628, error: 0.74%
actual: 100000, estimated: 99357, error: 0.64%
actual: 150000, estimated: 148880, error: 0.75%
actual: 200000, estimated: 200475, error: 0.24%
actual: 250000, estimated: 249362, error: 0.26%
actual: 300000, estimated: 299119, error: 0.29%
actual: 350000, estimated: 349225, error: 0.22%
actual: 400000, estimated: 398805, error: 0.30%
actual: 450000, estimated: 448373, error: 0.36%
actual: 500000, estimated: 498183, error: 0.36%
Adaptive Counting with Murmurhash:
actual: 50000, estimated: 50015, error: 0.03%
actual: 100000, estimated: 100048, error: 0.05%
actual: 150000, estimated: 149709, error: 0.19%
actual: 200000, estimated: 201059, error: 0.53%
actual: 250000, estimated: 249991, error: 0.00%
actual: 300000, estimated: 300067, error: 0.02%
actual: 350000, estimated: 349610, error: 0.11%
actual: 400000, estimated: 399875, error: 0.03%
actual: 450000, estimated: 450348, error: 0.08%
actual: 500000, estimated: 500977, error: 0.20%
Adaptive Counting with Lookup3hash:
actual: 50000, estimated: 49628, error: 0.74%
actual: 100000, estimated: 99357, error: 0.64%
actual: 150000, estimated: 148880, error: 0.75%
actual: 200000, estimated: 199895, error: 0.05%
actual: 250000, estimated: 249563, error: 0.17%
actual: 300000, estimated: 299047, error: 0.32%
actual: 350000, estimated: 348665, error: 0.38%
actual: 400000, estimated: 399266, error: 0.18%
actual: 450000, estimated: 450196, error: 0.04%
actual: 500000, estimated: 499516, error: 0.10%
Loglog Counting with Murmurhash:
actual: 50000, estimated: 59857, error: 19.71%
actual: 100000, estimated: 103108, error: 3.11%
actual: 150000, estimated: 150917, error: 0.61%
actual: 200000, estimated: 201059, error: 0.53%
actual: 250000, estimated: 249991, error: 0.00%
actual: 300000, estimated: 300067, error: 0.02%
actual: 350000, estimated: 349610, error: 0.11%
actual: 400000, estimated: 399875, error: 0.03%
actual: 450000, estimated: 450348, error: 0.08%
actual: 500000, estimated: 500977, error: 0.20%
Loglog Counting with Lookup3hash:
actual: 50000, estimated: 59870, error: 19.74%
actual: 100000, estimated: 103044, error: 3.04%
actual: 150000, estimated: 150435, error: 0.29%
actual: 200000, estimated: 199895, error: 0.05%
actual: 250000, estimated: 249563, error: 0.17%
actual: 300000, estimated: 299047, error: 0.32%
actual: 350000, estimated: 348665, error: 0.38%
actual: 400000, estimated: 399266, error: 0.18%
actual: 450000, estimated: 450196, error: 0.04%
actual: 500000, estimated: 499516, error: 0.10%
限於篇幅，我在這裡不能具體描述這些算法的細節，之前我在博客上發表了一篇翻譯的文章，不過內容也是概括性描述。但是我已經在准備寫博文詳細介紹基數估計算法了，那裡面會包括算法的數理細節以及對論文的一些解讀，歡迎有興趣的朋友關注我的博客。
CSDN：看到您微博上自稱“代碼潔癖重度患者”，這是一個很有趣的稱呼，那麼是否可以理解為您對代碼的規范性很在意，您在平時在編碼過程中如何保持代碼的規范？
張洋：這麼說其實是有點自嘲的意思吧。對代碼格式我確實是很在意的，如果看到代碼不規范、不整齊甚至多一個空行我都會覺得非常不舒服，骨子裡對代碼格式有一種完美主義傾向。
不過這個事情要分兩面看，如果是我自己開發的比較專的東西，如算法庫，可以堅持這種完美主義，但需要多人合作的場合實際上是不太合適的。實事求是的說，業務代碼總是不可能一直很漂亮，需要在業務進度和代碼質量中間做一個權衡。在保持代碼規范方面，我始終認為不能完全靠程序員的自覺和代碼規范的宣講，通過工具（例如lint）和流程去保證會更有效一些。
CSDN：還有哪些困難是需要在未來工作中克服的？
張洋：需要克服的困難主要來自兩方面吧。
一方面是算法本身改進的困難，這世界不存在完美無暇的算法，例如上面的基數估計算法，雖然大大降低了內存使用，但是如果維度爆炸的話，內存使用仍然會很誇張，而且合並bitmap也不是沒有代價，有時需要進行內存和磁盤bitmap的合並，當bitmap量過大時磁盤IO會稱為瓶頸，因此如何結合具體場景來優化和改進算法就成為一個難點。一個方法是查閱相關論文，了解和借鑒目前全球各大研究機構和公司對相關算法的最新研究成果。另一個方法就是自己進行改進，這塊需要對算法本身極其相關的數學分析有非常深入掌握，因此對相關工程師的理論水平要求較高。
另一方面就是算法和業務產品的結合方案。算法畢竟是較為形式化的東西，要具體應用到產品中還有很長一段路要走。尋求算法與產品的最佳契合點和結合方案也是工作中的重點和難點之一。
2012已經過去，我們度過了世界末日，迎來世界新篇章。在2013年，我們也會進入互聯網發展的新時代，各種數據充斥在網絡中，大數據成為各個互聯網公司都要面對的問題之一。如何消耗最小的資源來獲得盡可能多的有用信息，這應該是每個互聯網公司都要考慮的問題。通過最近關於算法的兩篇文章，想必各位讀者都能心中有數。當然，每種算法都有各自的優缺點，我們還是要根據在平時工作中的實際使用情況來對算法進行選擇，不能一概而論。（王旭東/作者 包研/審校）
