灰色的灵魂

自从Nathan Marz同学写了那篇著名的How to beat the CAP theorem的Blog，以及Storm发布之后，俨然成为了技术界新偶像。顺着他本人的blog，翻了一下他过去几年的写的技术文章，发现老美的牛人们都爱总结，能够把技术实践提升到理论高度，然后抽象出新的设计和产品，比起我等只能每天苦逼苦逼应对实际需求的人来说，还是强出很多。我自己觉得那么多年，虽然觉得做什么都能做了，但是现在还是只能谈到模仿，做不到提炼总结和超越。

和著名的CAP的那篇Blog，Nathan Marz还有很多其他非常有料值得一读的博客，与其在国内的各种Hadoop大会上听大家泛泛而谈架构，还不如多看看老外们总结下来的技术博呢，比如这篇The mathematics behind Hadoop-based systems，比起大家简单列列机器数字来说，有价值得多。

我曾经写过，数学对于称为一名优秀的程序员是很重要的，但这不一定意味着一定要是多高深的数学。Nathan的这篇Blog用到的数学只有初中难度，但是的确写明白了我们遇到的很多Estimation以及集群数量预估的实际问题，我想一定也有很多人用hadoop但是和我们一样，对于很多机器数量或者workflow的管理是很粗放的，相信这篇blog对很多人都会有用，所以把它翻译成中文，全文如下

基于Hadoop的系统背后的数学

我希望一年之前我就知道这些。现在，根据一些简单的数学，我就可以回答：

• 为什么在我将处理能力翻倍之后，我的workflow的速度没有翻倍？
• 为什么10%的任务失败率会导致我的运行时间上升到原来的300%？
• 如果通过优化了我的workflow的运行时间的30%导致运行时间下降了80%？
• 我的集群中到底需要多少机器可以满足性能和容错的需要？

所有这些问题都可以通过这样一个简单的等式干净地回答：

运行时间(Runtime) = 额外开销(Overhead) / (1-{处理一小时数据需要的时间})

我们很快就可以推导出这个等式。首先，让我们简单地讨论一下什么是我所说的“基于Hadoop的系统”¹。Hadoop的一个常见的用例，就是通过运行一个workflow来处理来连续进入的流数据。这个工作流运行一个”while(true)”的循环，然后每个workflow的迭代，都处理自从上个迭代依赖累积的数据。

下面的这些分析的灵感可以在一个简单的示例中概括出来。假如说你有一个workflow需要运行12小时，然后它会在每个迭代中处理12个小时的数据。然后假如说你加强了这个workflow去做一些额外的分析，然后你估计你在当前的这个workflow中需要多花两个小时来处理。然后麻烦来了。你的workflow增加的运行时间可能远超过两小时。它可能增加了10个小时，100个小时，或者这个workflow可能呈螺旋式上升地在每个迭代中花费越来越多的时间知道无限。

为什么？

问题在于，你将处理12个小时数据的workflow的运行时间增加到了14个小时。这意味着当下一次workflow运行的时候，有14小时的数据需要处理。既然下一个迭代有更多的数据，他要花费更多时间运行。这意味着下一个迭代会有更多的数据，等等。

为了确定什么时候运行时间，让我们做一些简单的算术。首先，让我们写下一个只有一个迭代的workflow的运行时间的等式

运行时间 = 额外开销 + {处理一小时数据的时间} * {多少小时的数据}

额外开销(Overhead)指的是花费在workflow上的任何常数项时间。例如，开始一个job需要的时间会计入额外开销。使用distributed cache来分发文件的时间会计入额外开销。你会把任何独立于数据规模的时间花费放到“额外开销”的分类中去。

“处理一小时数据的时间”指的是workflow中的动态时间。这是你忽视那些额外开销，花费在处理实际数据上的时间。如何一小时的数据会增加你半小时的运行时间上，这个值应该是0.5。如果一小时的数据会增加你一小时的运行时间，这是值就是2。

为了简洁，让我们把上面那个等式通过变量来重新写一下：

T = O + P * H

为了确定workflow的稳定的运行时间，我们需要找到workflow的运行时间在哪个点上正好等于累积了的需要处理的数据量。为了做这个，我们可以简单地插入 T=H 来求解T:

T = O + P * T
T = O / (1 - P)

这就是我之前展示的等式。你可以看到，一个workflow的稳定的运行时间是和workflow中的额外开销呈线性比例的。所以如果你可以将额外开销减少25%，那么你的workflow运行时间就会减少25%。然而，一个workflow的稳定运行时间和动态处理的速率“P”不是呈线性比例的。这背后的隐含含义就是每为集群加入一台机器带来的性能提升是在减少的。

通过这个等式，我们可以回答我在文章开始时候写下的问题了。让我们一起来过一些这些问题：

为什么在我将处理能力翻倍之后，我的workflow的速度没有翻倍？

将你的机器数翻倍，会将你的“处理一小时数据需要的时间”减少50%²。这个的效果和你的运行时间的关系是完全依赖于之前的P值的。让我们用数学来展示一下。假如说你的workflow在集群的机器数量翻倍之前的运行时间是“T1”，翻倍之后是“T2”。这给了我们两个等式：

T1 = O / (1-P)
T2 = O / (1 - P/2)

那么性能加速就会是 T2/T2，新的运行时间和旧的运行时间的比值。这给到我们

T2 / T1 = (1 - P) / (1 - P/2)
T2 / T1 = 1 - P / (2 - P)

对这个式子作图，我们可以得到如下的图，其中原始的P在x轴上，性能加速在y轴³上：

这个图说明了一切。如果你的P非常高，比如说，需要54分钟来处理一小时的数据，那么将你的集群数量翻倍会使得你新的运行时间是原来的18%，足足有82%的性能加速！这是一个非常违背直觉的结论 —— 我强烈推荐读者们仔细思考这种情况出现的背后的机制。

然后，如果你之前的P没有那么高（例如，需要6分钟的动态运行时间来处理1小时的数据），那么将集群数量翻倍对于运行时间几乎没有效果 —— 可能只有类似6%。由于运行时间被额外开销所主导，这是很合乎情理的，动态运行时间在运行时间中占得很小。

为什么10%的任务失败率会导致我的运行时间上升到原来的300%？

这个问题解释了workflow稳定性的属性。在一个大集群中，你总是会有不同的机器故障，所以任务失败率的峰值不会干掉mission critical系统的性能是非常重要的。关于这个问题的分析会和上一个问题看起来非常相似，除了我们会将动态运行时间变差而不是提高它之外。10%的任务失败率意味着我们需要多运行11%的任务来处理完我们的数据⁴。由于任务依赖于我们所拥有的数据量，这意味着，我们的“处理一小时数据需要的时间”会上升11%。类似于上一个问题，让我们将T1作为没有任务失败所需要的运行时间，T2作为有任务失败的运行时间

T1 = O / (1 - P)
T2 = O / (1 - 1.11*P)
T2 / T1 = (1 - P) / (1 - 1.11*P)

对此作图，我们得到：

(译著: 上图中X轴为P值，Y轴为花费时间增加的比例)

你可以看到，任务失败对于运行时间的影响在你的集群有“额外容量”减少的情况下戏剧性地增长。所以让保持你的P低是非常重要的。我们可以看到你的P越高，由于任务失败率的增加，你就更有可能进入“毁灭循环”的风险⁵。

如果通过优化掉我的workflow的运行时间的30%而导致运行时间下降了80%？

这个问题是使得我真正找出workflow的运行时间的模型。我曾在一个workflow中有一个荒谬的瓶颈，导致了大概10小时的额外开销⁶，然后整个workflow的运行时间大概是30小时。在我优化了这个瓶颈(大约占据了30%的运行时间)之后，运行时间像石头一样坠落，最终稳定在6小时(减少了80%)。使用我们的模型，我们可以确定为什么这发生了：

30 = O / (1 - P)
6 = (O - 10) / (1 - P)
O = 12.5, P = 0.58

所以那10小时，占据了workflow中的80%的额外开销，这解释了整个的性能提升。

我的集群中到底需要多少机器可以满足性能和容错的需要？

这基本上是一个费效比分析的练习。我们可以看到，通过增加集群中机器数据来提高性能到回报在减少，而一旦P(“处理一小时数据需要的时间”)下降到30分钟以下(0.5)，通过增加机器获得的性能提升是次线性的⁷。我们也同样看到将P保持得低是很重要得，不然任务失败的增加或者其他的任务使用集群，会严重影响你的运行时间。所以，你需要运行一些数据来确定对你的应用最佳的机器数量⁸。

你应该在Twitter上follow我。

更新：看看本文的后续内容

¹ 事实上，这个等式适用于任何批量处理连续数据流的系统。
² 这里假设你的处理是完全分布式的，并且没有持有任何中心点，这对于一个基于Hadoop的workflow来说通常是真的。一个可能的例外是，你所有的tasks都通过一个中心的数据库进行通信。事实上，增加更多的机器会在额外开销(更多的机器去处理)以及数据处理速率(mapper需要将数据分发到更多的reducer中去)有少量的不利影响。对于这个分析的目的来说，我们可以忽略这些。
³ 该图通过FooPlot生成。
⁴ 比如说我们通过100个task来处理数据，现在，当你运行这些task的时候，其中有10个会失败。当你重新运行这10个的时候，9个会成功，还有1一个会失败。所以你实际运行了111个task而不是100个，这意味着task的数量增加了11%。
⁵ 或者其他的运行在集群上的东西，比如一次性的查询或者其他的workflow。
⁶ 这是由于Berkeley DB在ext3的文件系统上会生成很多碎片。
⁷ 事实上，我没有展示这个，但是你可以通过模型来自己推导。我把这个作为一个练习留给读者。
⁸ 如果你需要的话，你可以让这个模型变得更加全面。比如，这个模型没有区分新进入的数据和已经存在需要被查询的数据(并且在每个迭代中都会增加)。这个变量必然会影响到你的长期扩展需求，记住它是非常重要的。对于那些知识对于这些workflow的性能有获得一个直觉的目的来说，这不是必须的。

互联网公司和软件公司最大的不同在于，即使对于技术团队来说，开发工作也只是一小部分工作，如何使得整个系统运营起来，才是重头戏，这是过去一年感悟最深的一点；而对于像广告质量这样的技术团队来说，运营和开发可以说是完全不可分离的。过去一年，在这点上，走了很多弯路，犯了很多错误，有很多可以总结的地方。从Quora上看到这样一个问题，“What are the keys to operationalizing a machine learning ranking system from an organization / engineering management point of view?”

觉得唯一的一个回答就很好，翻译一下以记之，虽然做不到信达雅，但是基本意思应该能描述对。

这个问题的大概内容是这样的:

• 将你的成功的指标定义为让用户高兴。传统的精确性的指标，比如precision, square error, ROC等等并不能捕捉到那些你真正关心的——用户对于你的模型是如何反应的。例如，如果你运营一个广告系统，你的指标应该是每个PV的收入以及点击率。完全有可能，由于辛普森悖论，你有一个error rate减少了的模型，但是他带来的收入却降低了。
• 核心指标下降是很严重的问题。你需要把核心指标的大幅下降当成和一个服务器当机或者数据库中数据损坏一样严重的问题。Oncall的人需要尝试尽快诊断问题，并且必要时把别人拉进来一起解决问题
• 对每次Model的Launch做A/B测试。你应当始终并行运行两个模型，给不同的用于用不同的模型，然后比较用户行为。这是唯一可以确保你知道你在做正确的事情的办法。
• 小心丑小鸭效应。机器学习系统会在从自己的错误中学习的过程中变得更加准确。这意味着，新的模型有一个与生固来的缺陷：你的历史训练数据包含着过去模型中的错误，但不是你新训练的模型的错误。导致你的新模型一开始可能像一个丑小鸭，但是如果你用他来决策用户看到的内容，他最后会变成一个漂亮的天鹅。你可以通过将一小部分流量切给新模型，来部分抵消丑小鸭效应，然后慢慢随时间提高这个百分比。
• 使得算法对于噪声Feature健壮。类似于L1 regularization这样的技术可以使得你的机器学习算法对Feature进行剪枝，修剪掉那些对于预测的准确性贡献很小的Feature。这可以帮助你很好地拆分你的团队：一些人专注于算法，另一些人写Feature喂给算法。那些寻找Feature的人，可以直接“把东西扔进锅里”，然后让算法找出他们究竟好还是不好。（类似的，你应该通过确保合理的收敛性来选择一个算法）
• 你可以部分地将架构和算法团队解耦合。基本上，大部分机器学习算法都是在累计一个分布式的hash table的统计信息，然后将这些统计信息合并成一个分数。开发一个分布式的hash table是和开发一个用于累计的算法不同的任务，可以由不同的子Team完成。然后，让这些人一起工作仍然是很重要的。例如，一些算法在写入和写入可用之前延时的“最终一致”的系统中（例如Dynamo），会有所波动。所以这只是一个部分解耦合，你仍然需要团队中有连接架构和算法的“桥梁”人员。
• 在在线系统和批处理系统之间选择的时候要小心。一个在线系统可以实时学习，对于新的用户行为，可以在发生之后的几分钟内有所反应。但是这回带来巨大的开销，一个在线系统需要2-3倍的时间区开发和维护，而且他对瞬间的变化更加敏感。举个例子，如果你突然接收到了很多垃圾信息，这些噪声会立刻被吸收进你的系统并且开始降低用户的体验。类似的，一台机器如果没有可运行的内容了，如果网络连接中断了，或者一个特定的机器变慢了（导致Feature“歪了”），模型的某个输入开始生产垃圾，等等。
• 为所有东西打上版本。一个训练过的模型依赖于稳定的标识，如果你更改了某个标识，模型立刻就过时了。例如，如果你将用户的语言(“en-us”)作为一个feature。那么当有些人提交了一个一行的修改，用下划线替换了短横线(“en_us”)。这使得模型立刻“忘记”了所有从”en-us”中学到的，使得所有的语言看起来都是一样的。所以为所有会在你模型中生成标识的代码和数据的变更都打上版本。
• 你需要咬碎100-1000倍于实时的数据。如果你的训练数据来自于整整一年的历史数据，然后你的学习过程是10倍于实时，那他需要一个月来测试一个新Feature。把所有的东西都写成Map-Reduce或者Storm Topology使得你可以在数据变得足够大的时候仍然可以扩展。

看了一下，里面有不少错误我们都犯过，包括过去一个Q我们觉得由于团队小应该快点冲而省略掉的东西，现在看来也还是省略不掉的，而之前做对的部分也都是来自老大们的经验，希望今年少走弯路效果好啊。

这一阵为了工作上的关系，花了点时间学习了一下LDA算法，说实话，对于我这个学CS而非学数学的人来说，除了集体智慧编程这本书之外基本没怎么看过机器学习的人来说，一开始还真是摸不太到门道，前前后后快要四个月了，算是基本了解了这个算法的实现，记录一下，也供后来人快速入门做个参考。

一开始直接就下了Blei的原始的那篇论文来看，但是看了个开头就被Dirichlet分布和几个数学公式打倒，然后因为专心在写项目中的具体的代码，也就先放下了。但是因为发现完全忘记了本科学的概率和统计的内容，只好回头去看大学时候概率论的教材，发现早不知道借给谁了，于是上网买了本，花了几天时间大致回顾了一遍概率论的知识，什么贝叶斯全概率公式，正态分布，二项分布之类的。
后来晚上没事儿的时候，去水木的AI版转了转，了解到了Machine Learning的圣经PRML，考虑到反正也是要长期学习了，搞了电子版，同时上淘宝买了个打印胶装的版本。春节里每天晚上看一点儿，扫了一下前两章，再次回顾了一下基本数学知识，然后了解了下贝叶斯学派那种采用共轭先验来建模的方式。于是再次尝试回头去看Blei的那篇论文，发现还是看不太懂，于是又放下了。然后某天Tony让我准备准备给复旦的同学们share一下我们项目中LDA的使用，为了不露怯，又去翻论文，正好看到Science上这篇Topic Models Vs. Unstructured Data的科普性质的文章，翻了一遍之后，再去PRML里看了一遍Graphic Models那一张，觉得对于LDA想解决的问题和方法了解了更清楚了。之后从search engine里搜到这篇文章，然后根据推荐读了一部分的Gibbs Sampling for the Uninitiated。之后忘了怎么又搜到了Mark Steyvers和Tom Griffiths合著的Probabilistic Topic Models，在某个周末往返北京的飞机上读完了，觉得基本上模型训练过程也明白了。再之后就是读了一下这个最简版的LDA Gibbs Sampling的实现，再回过头读了一下PLDA的源码，基本上算是对LDA有了个相对清楚的了解。

这样前前后后，也过去了三个月，其实不少时间都是浪费掉的，比如Blei的论文在没有任何相关知识的情况下一开始读了好几次，都没读完而且得到到信息也很有限，如果重新总结一下，我觉得对于我们这些门外汉程序员来说，想了解LDA大概需要这些知识:

• 有基本的概率论的知识，这个拿个大学的课本大概翻一下就好了
• PRML的前两章和Graphic Model那部分需要浏览一下，了解一下所谓的贝叶斯学派的方法论，然后理解共轭先验的概念，以及Graphic Model的图形表达的意思。
• 了解一下Gibbs Sampling的概念
• 直接读Steyvers的Probabilistic Topic Models，没必要一定去读Blei的论文，开创性的论文不一定好读，最典型的例子就是Paxos了，30多页里多少都是希腊人名，对于英文不够精通，学术训练比较少的工程师来说，其实很痛苦，意义也不大。
• 对照着Probabilistic Topic Models直接看LdaGibbsSampling.java的源码

基本上这样一圈下来，基本概念和算法实现都应该搞定了，当然，数学证明其实没那么容易就搞定，但是对于工程师来说，先把这些搞定就能干活了，这个步骤并不适合各位读博士发论文的同学们，但是这样先看看也比较容易对于这些数学问题的兴趣，不然，成天对这符号和数学公式，没有整块业余时间的我是觉得还是容易退缩放弃的。

发现作为工程师来说，还是看代码比较有感觉，看实际应用的实例比较有感觉，看来不能把大部分时间花在PRML上，还是要多对照着代码看。

这里可以下载，呃，不知道2009会不会是Rails再次爆发的一年？

广告一则:

Trilogy Ventures 创业沙龙（互联网 手机应用方向）

时间：3月2日18:00-21:00
地点：上海交通大学闵行校区光彪楼

欢迎去玩。

Update：补充一下，Trilogy去年和前年各投了一家，今年估计机会会多一些，因为专门成立了Trilogy Ventures China专门投早期，此外，当天Speech胜者貌似有3000块奖金。

其实开发过程中重要的不是采用了什么样的工具，流程甚至理念，重要的是作为开发人员开发团队应该把精力花在是你的开发变得更好上。无论是你喜欢XP这样的理念，还是因为喜欢Joel而简单地使自己的流程符合Joel Test上，这些问题出现的本质是让你把精力放在把事情变好而不是只是在做做事情。每日构建、单步构建和自动测试是把你从每天“做做构建”、“做做测试”这样的事务中解脱出来；使用源代码管理是让你避免浪费时间去反反复复做做过的事情；不要加班是让你意识到你要做得是效率上得改进而不是重复劳动来做体力活。无论是不是已经有了这些流程，开发人员始终可以做的是每天把精力花在使今天比昨天好上面。只要你有意识去花时间进行改建，那么你之前没有用源代码管理你自然会发现花了很多时间做出来得东西被猫吃了；你没有为每个bug添加test case自然会发现同一个bug会反复出现；你没有用单步构建和每日构建自然会发现每次要发布得时候都会手忙脚乱要通宵加班。而有了这样的意识，即使你已经符合了Joel Test的12条你仍然可以发现你可以使用自动发布来让客户看到每天的开发结果；你可以使用创建VM Image来解决不同开发人员开发环境不同，可能有遗漏的依赖没有放入源代码管理中；你会发现Git比SVN更好地解决了开branch的开销和常常需要它记录一部分不完整代码的问题。

所以，重要的是始终在开发过程中保持持续改进的意识，工具和方法论反而是第二位的。

越来越发现，这个时代实在是工具太多了，多到有点让人讨厌了。随便干点什么，都要会一堆东西；学点新东西，发现要能用要再学一堆新东西。最近用ROR做点东西，发现真要做点Production Quality的东西，至少要用一堆工具，比如New Relic，比如Capistrano，然后如果想要用得爽还有一堆RSpec等等的东西可以用，更不用说HTML/CSS/Javascript/MySQL/Git这些基本的工具。如果在Java世界的话，用的东西更是多到让人厌恶。比起要用的工具，人生时间实在是短到让人绝望，不过没办法，只能慢慢玩了……

译者注：本文原文来自Rails Guides，版本为January 3, 2009: First reasonably complete draft by Mike Gunderloy。本文根据原文，按照Creative Commons Attribution-Share Alike 3.0授权。

本指南涵盖了可用于Rails应用中的配置和初始化特性。通过本指南，你可以
1.调整Rails应用的行为
2.添加在应用启动阶段运行的代码

本指南的第一版是基于Rails 2.3的源代码撰写的。虽然不保证向前兼容，但是本指南涵盖的信息可广泛地用于Rails 2.2。

1. 初始化代码的位置

Rails（至少）提供了五个好位置来放置初始化代码：

• 预初始化器（preinitializers）
• environment.rb
• 针对特定环境的配置文件
• 初始化器(load_application_initializers)
• 后初始化器（After-Initializers）

2. 使用预初始化器

Rails允许你使用一个预初始化器，在框架自身被装载前来运行代码。如果你把代码存放在RAILS_ROOT/config/preinitializer.rb中，这些代码会在任何框架组件（Active Record, Action Pack, and so on）之前第一个被装载。如果你想要改变任何初始化过程中某些类的行为，你可以在这里（preinitializers文件）做。

3. 配置Rails组件

基本上来说，配置Rails所做的工作就是配置Rails自身以及配置Rails的各个组件。environments.rb文件以及针对特定环境的配置文件（比如config/environments/production.rb）允许你设定各个组件的设置。例如，默认的Rails2.3中的environment.rb文件中包含这样一条配置：

config.time_zone='UTC'

这是一条Rails自身的设置。如果你想要设定Rails的各个组件的设置，你也可以通过同样的这个config对象来做：

config.active_record.colorize_logging = false

Rails会使用这条设置来配置Active Record

3.1 配置Active Record

ActiveRecord::Base包含许多种配置选项：

• logger接收一个符合Log4r或者Ruby1.8.x Logger类的接口的logger，该logger会传递给所有的新创建的数据库连接。你可以在ActiveRecord的model类或者其实例上调用logger来获取该logger。把该值设为nil会经用日志功能。
• primary_key_prefix_type用于设置主键列的命名。Rails默认主键列的名字是id（该配置无需设定），但是你可以有两个别的选择：
  • :table_name会另Customer类的主键为customerid
  • :table_name_with_underscore会另Customer类的主键为customer_id
• table_name_prefix使你可以在表名的前面设置添加一个全局的字符串。如果你将该值设为northwest_，那么Customer类会映射到northwest_customers表。默认该值为一个空字符串
• table_name_prefix使你可以在表明的后面设置添加一个全局的字符串。如果你将该值设为_northwest，那么Customer类会映射到customers_northwest表。默认该值为一个空字符串。
• pluralize_table_names规定了Rails使用单词的单数还是复数来命名数据库中的表名。如果该值被设置为true（默认值），那么Customer类会使用customers表，如果该值被设置为false，那么Customer类会使用customer表
• colorize_logging（默认为true）规定了在ActiveRecord的日志信息中是否使用彩色的ANSI代码。
• default_timezone决定了在从数据库中读取日期和时间时，是使用Time.local（如果设置为:local）还是Time.utc（如果设置为:utc）。默认值为:local
• schema_format控制了从数据库中导出数据库模式到文件中所用的格式。选项:ruby（默认值）会使用一个数据库无关的migrations，选项:sql会使用（可能依赖于特定数据库的）SQL指令。
• timestamped_migrations控制了migrations的数字是使用连续的整数还是时间戳。默认值为true，代表使用时间戳，这在优多人共同开发同一个应用的时候是一个更好的选择。
• lock_optimistically控制了ActiveRecord是否使用乐观锁。默认该值为true

MySQL适配器增加了一个额外的配置选项：

• ActiveRecord::ConnectionAdapters::MysqlAdapter.emulate_booleans控制了ActiveRecord是否认为MySQL数据库中所有的tinyint(1)列为布尔值。默认该值为true

数据库模式的导出器（schema dumper）增加了一个额外的配置选项：

• ActiveRecord::SchemaDumper.ignore_table接受一个表名的数组，该数组中的表不应包含在任何生成的数据库模式文件中。该设置在ActiveRecord::Base.schema_format == :ruby时才会起作用。

config.after_initialize do
    SomeClass.init
end