大数据那些事（13）:乱入的卖书的

大西雅图地区是云的故乡。这里一年超过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一年再回来，这样我就可以名正言顺的长一级了。