分享

科技一周~夜空里，有多少星辰的进程？

2014/03/22

某一个夜晚，我独自仰望星空，幻想宇宙，看那遥远的星辰，罗列似棋，浩如烟海，但不知渺渺深处，来自何方，又归去何处？时空既然一致，奈何一个有初始，而另一却无边界？星河灿灿，是有序而列，还是并无因果？我只是一个普通到不能的人，自然无法破解心中之疑问，但这世上，毕竟有太多的天才，她（他）们定可勘破宇宙，洞悉天机。就像本年度图灵奖得主，Leslie Lamport，或许那无数的星辰，在他的眼里，不过是千万个计算的节点，而整个宇宙，又岂不是诺大的一个分布式系统？

• 本周的头条计算机科技新闻，不是来自FLAG（Facebook、Linkedin、Amazon、Google），而是来自学术界：美国计算机协会ACM，将2013年度的图灵奖（A.M. Turing Award）授予微软研究院的科学家，Leslie Lamport，以表彰其在分布式并发系统领域里所做出的基础性贡献[1]。在分布式系统研究里，Lamport发明并定义了一系列极其重要的概念，譬如，因果性（Causality）、逻辑时钟条件（Logic Clock Condition）、物理时钟条件（Physical Clock Condition）、时序一致性（Sequential Consistency）。正是因为这些精确概念的出现，才把原本混乱的分布式系统，变得井然起来，因果有序，再无杂陈。
• 尽管被加州学生起诉侵犯教育隐私[2]，但Google毫不挂心，迄今为止，关于侵犯隐私一事，Google已不知受到了多少口诛笔伐，又岂在乎这区区一件？重要的新闻是，Google在本周发布了为穿戴式设备特别设计的操作系统，Android Wear[3]。不得不说，这是一个远期正确的决定，就像智能手机有别于个人电脑，穿戴式设备也因其独具的物理特性，而与智能手机有着极大的区别，想靠着智能手机操作系统来包打穿戴式设备的天下，已然是件不太可能的事情。所以，一切需要重新来过，为穿戴式设备量身定制一个操作系统才是王道。
• 来自英国的一个团队，设计出一个基于ARM处理器的乐高机器人，Cubestormer 3，用来专门解决三阶魔方，并以3.253秒的成绩刷新了三阶魔方的世界记录。联想到被冠以“天才学霸”的搜狗CEO王小川，在今年第一财经的《波士堂》节目里，花费数分钟方才解决魔方，我只能说，这个游戏已经不是我们人类所擅长了。慢慢地，人类就只剩下一个聊以自豪的能力：设计机器人；再慢慢地，连机器人也是由机器人来设计，咱们人类可以彻底退休，永无牵挂了：）

本周科普聊天，讲讲新科图灵奖得主Lamport在其经典论文里所提及的“如何解决分布式系统中的互斥问题”。所谓“互斥问题”，是指在系统中的某一资源，在任何一个时间点上只能接受一个线程的请求，直到该线程把资源释放之后，该资源才可以再接受其它线程的请求。如果互斥问题没有解决好，很有可能导致几个线程互相死锁，从而使整个系统停止。我无意去使用艰深的学术词汇，在这里，仅仅用一个生动的事例来说明之。

清朝乾隆四十六年，兼任户部尚书的军机大臣和珅，有感于往年黄河洪灾之害，特别定制了一套洪灾救援方案：位于黄河上游之省份若发生洪灾，其巡抚不仅要向军机处发出钱粮求援文件，还要同时向其下游之省份发出“本省已遇洪灾”的警告；下游之省份在收到上游洪灾警告后，如果也遭受了洪灾，需在其钱粮救援文件的开篇加注“上游省份先受灾”。

这样一套方案的好处是，不会扰乱救援的“因果”（happened-before）顺序，先受灾的省份将会先得到救援。举例来说，河南省在山东省的上游，按照以前旧的方案，当河南遭受洪灾，开封府向北京发出求援信，需要约3天时间才能到达京城；通常在河南遭受洪灾之后约2天，山东省就会遭灾，而从济南府发送求援信到京城，只需约1天。这样的结果是，山东省的求援信有可能会比河南先到京城，从而令军机处给后遭灾的山东先发去了钱粮。因为钱粮是一种“紧缺资源”，军机处需要重新筹措，于是河南的灾民就会处于一种长时间得不到救援的状态。这与“先遭灾先救援”的准则相矛盾。

改换为新方案后，开封通知济南的时间小于2天，所以济南会在洪灾到来之前，就知道河南先受灾。这样，即使山东的信件先到京城，由于其上加盖了上游河南先遭灾的说明，军机处很容易知道河南在山东之前已经遭灾，于是可以稍等片刻，待河南信件到达，则先把救援钱粮发送到河南；而后再筹措下一批钱粮予以山东。这样就会与救灾准则相吻合。

其实，和珅的方案暗含了Lamport在其经典论文[5]中所设计的“化偏序为全序”和“逻辑时钟”的概念。如果把河南、山东、北京三个地区当做三个分布式并发进程，受灾与求援是两种事件，那么三地之间所“传递的信件关系”则定义了这些事件的一个“全序”（Total Order）；在全序的基础上，河南和山东各自在自己的求援信里都注明了“逻辑”的时间戳，从而可以保证因果序列的一致性。

怎么样，大贪官也可以是天才吧，和珅可是比Lamport大了191岁呦！（注：严格说来，这种时间戳是基于真实的“物理时钟”，至于“逻辑时钟”和“物理时钟”的解释，留待下期讨论）

[1]. ACM.org, http://amturing.acm.org/award_winners/lamport_1205376.cfm , Mar 2014.

[2]. Ryan W. Neal, Google sued for data-mining, http://www.ibtimes.com/google-sued-data-mining-california-students-claim-violation-educational-privacy-1562198 , Mar 2014.

[3]. Brad Molen, Google announces android wear, http://www.engadget.com/2014/03/18/google-android-wear/ , Mar 2014.

[4]. Colin Druce-McFadden, LEGO robot defeats Rubik’s cube in world record time,

http://www.dvice.com/2014-3-17/lego-robot-defeats-rubiks-cube-world-record-time , Mar 2014.

[5]. Lamport, L. “Time, clocks, and the ordering of events in a distributed system”, Communications of the ACM, 1978, 21(7): 558-565.

图1. [1].

图2. [3].

图3. [4].

分享