大數據那些事（14）:亂入的賣書的

01-31

大西雅圖地區是雲的故鄉。這裡一年超過8個月的雨季讓有雲的天氣遍布夏天以外的每一天。華盛頓湖把大西雅圖地區劃成了東岸和西岸。東岸是鄉下，上個世紀微軟在這裡成就了它的軟體帝國。西岸是城裡，夜間常瀰漫著大麻的氣息，偶爾還會有突突突的槍聲。

我們今天要講的故事的主角其實大家都已經猜到了。這個公司有著很多的稱呼，它曾經被微軟前CEO 巴爾默親切的稱呼為湖對岸賣書的，自2000年的dotcom泡沫中存活，在2008年的經濟危機以後開始發家，09年到16年股票翻了10倍。這是一家以節儉著稱的公司。這家公司還因為工作環境的苛刻上了紐約時報。它就是亞馬遜。

大數據時代的亞馬遜依靠自己的雲計算平台，佔盡了很多很多的好處，賺了不少錢。然而我們必須說，這個公司對開源的貢獻是很有限的，對於拿來主義則是非常的擅長。leadership下面到底需要給我們展現的是什麼，是一個特別值得我們思考的問題。

這個賣書的很少發表有關他們的infrastructure的論文，儘管它有著這個世界上最為牛逼的deploy和monitoring 系統，Apollo和Brazil代表著業界在這個領域的巔峰。湖對岸那個上世紀腐朽的軟體帝國無法比，曾經代表DoNotEvil的DoEvil狗也不能比。當然，我們外界對它所知並不多，只有幾篇有限的blog。

破天荒的這個公司發表了一篇論文Dynamo，亞馬遜的key-value store。這是業界公開發表論文的除BigTable以外的第二個Key-Value store，因此升起了NoSQL的一片天。它的江湖地位自然不容置疑。其實其他的公司比如微軟比如Uber也都做了自己的Key-Value store，微軟的自然不值一提，Uber的傳聞是基於MySQL的，可能更是比較另類。

我寫大數據系列常常糾結於到底要對技術細節做多深入的介紹，還是要對八卦做更深入的介紹。Dynamo的基本技術思想其實也是大名鼎鼎，來自於2000年左右的著名P2P系統Chord的思想，採用的是Distributed Hash Table. 其核心思想是在整個hash值的範圍的圈圈上放進去若干台機器，每台機器可以服務從上個hash值到自己的所有對於hash的請求。然後在每台機器裡面設置好jump table就可以做到log的複雜度對內容進行查詢。至於機器的加入和退出也有成熟的協議。這個技術可能對很多人都很熟悉了，尤其是搞web的。Consistent Hash應該不是什麼特別的技術了，非常的大路貨。若干年前如果需要看各種老師的表演必不可少的某驢某騾某BT其實背後的協議也都差不多。另外順便八卦一句Chord的主要貢獻者也就是現在大數據當紅炸子雞Spark的主要貢獻者，的導師，如果我沒記錯的話。想來一個被迫要求實現過Chord的.

亞馬遜的Dynamo本質上是實現了一個Distributed Hash Table。總體來說有那麼幾點是有創新的。其一是用了virtual node的概念，一台機器serve若干個virtual node，來避免可能的data skew。其二是引進了gossip協議來判斷節點之間是不是還活著。最後，Dynamo實現了對eventual consistency和strong consistency的支持。其使用的方法比較有意思。基本上來說是要配置三個參數：全局有幾個copy N，讀成功必須要讀多少個copy R，寫成功需要寫多少個copy W。如果R+W比N大的時候就是strong consistency，否則是eventual consistency。

這個東西的證明其實不難了，用的是我們小學數學競賽的鴿洞原理。如果讀和寫的總次數大於N，那麼讀和寫必然至少有一個copy是相同的。也就是讀必然可以讀到最新寫的版本。

Dynamo出來的時候，做工很糙但是手快的活雷鋒Facebook就開源了一個他們的copycat，名字叫做Cassandra。很不幸的是，一年以後Facebook決定放棄在自己的產品里使用Cassandra，跑去了用HBase。後來有八卦傳出來說其實主要是Facebook比較粉Google，但是對亞馬遜的架構沒信心。因此他們就結束了對自己親兒子的支持。HBase的發展當然是如火如荼了。Cassandra就沒那麼順利了。但是最近Cassandra傍上了土豪Uber，Uber現在有全球最大的Cassandra的data center。

可能很多人會問，為什麼會拋棄掉Cassandra，其實估計只有Facebook自己知道了。大凡數據處理，無非兩個套路：sorting或者hashing。BigTable是個典型的sorting approach而Dynamo則是hashing。很遺憾的告訴大家我既沒摸過HBase也沒玩過Cassandra，所以我完全沒概念到底實際上來說誰比誰更好。如果單純從技術實現去分析，那麼我想Hashing更適合point query而Sorting能同時支持range query。但是對資源的利用的靈活度來說，hashing對新資源的加入或者老資源的離開都應該會表現出比sorting更加高的適用效率和更容易負載平衡。至於保存一個東西的多個timestamp的版本，那可能還是sorted map更容易返回最後一個版本，hashing-based就不是很好說了。

傳聞當年寫了Dynamo的人因為寫了這篇paper被Jeff Bezos罵泄露公司機密，傳聞雖然不可信，我還真的去搜了一下那些作者們，果然各奔東西了，有在亞馬遜的老司機，有去非死不可和其他地方混的。也許是正常人員流動。我原本以為寫了Dynamo以後應該會有幾個principal，但是據說亞馬遜的principal非常難，有一個老兄就先去了一個其他公司混了一年，再回亞馬遜終於principal了。我在想我是不是應該離開Tableau一年再回來，這樣我就可以名正言順的長一級了。