17
Jan

Hadoop系统背后的数学

原文地址: http://nathanmarz.com/blog/hadoop-mathematics/

我希望我在一年前就知道这些。现在,通过一些简单的数学我终于可以回答下面的问题:

  • 当机器的处理能力加快一倍, 为什么整个系统运行的速度没有增加一倍?
  • 如果故障率增加10%,为什么整体的运行时间增加了300%?
  • 为了得到最优的性能和容错表现, 一个计算机群应该部署多少机器?

一个简单的数学公式可以巧妙的回答所有这些问题:

运行时间=系统开销/(1 - (1小时数据量的处理时间) )

我们将在稍后证明这个等式。首先,让我们简要地讨论一下“Hadoop为基础的系统。(分布式系统)”1 Hadoop的一个常规应用是处理一个连续输入的数据流。这种工作流运行在一个“while(true)”循环当中,每一次处理的数据是上一次的运行结果。

接下来的分析可以归纳为一个简单的例子。假设你有一个工作流程需要12小时运行,因此,它每运行一次需要处理数据12小时。现在让我们假设需要做一些额外的计算工作,估计将在现有的工作流上增加两小时处理时间。问题来了。整个系统的运行增加的时间可能会远远多于两小时。它可能会增加10个小时,几百个小时,或者可能失去控制并且每一轮运行越来越慢。

为啥呢?

关键是你将系统需要12小时处理的数据运行时间增加到了14小时。这意味着下一次运行的工作流程,将有14小时的数据需要处理。由于下一个迭代有更多的数据,将需要更长的时间运行。这意味着下一次迭代会有更多的数据,等等。

要确定怎么让运行稳定,让我们做一些简单的数学。首先,让我们写了一个系统运行一次的公式:

运行时间=系统开销+(单机处理1小时数据的运行时间)*(总数据量/单击处理1小时的数据量)

系统开销是指任何常数时间的消耗。例如,启动一个程序的开销。任何运行时间同数据量无关的开销将属于这个“系统开销”这个类别。

“单击处理1小时数据的运行时间”指的是系统中的动态处理数据时间这是处理的实际数据量花费的时间,去掉了固定的系统时间开销。如果每个小时数据在系统中需要运行半小时,这个值为0.5。如果每个小时数据需要运行两小时,这个值为2。

阅读全文…

18
Jul

Just for fun for 随机排列算法的一个证明

对n个元素的数组,一个极简单有效的随机排列算法如下所示:

for(int i = n-1; i > 0; i–){
swap(i,rand()%(i+1));
}

这个算法初看起来并不自然,但其实是很简单的。直观地看,排列过程中,数组分为两部分:排列就绪部分(长度为n-i)和候选元素部分(长度为i)。每次从候选元素部分随机取一元素(rand()%(i+1)),放到排列就绪部分头部,将所占据位置上原来的元素扔进候选元素部分。注意到,候选元素部分的顺序是无关紧要的,因为一个元素无论处于什么位置,下一次被选到的概率都是1/候选部分长度。因此为了算法复杂度低和简单起见,每次都将被占据位置的元素与被选到的元素交换(这两者有可能是同一元素)。简单地说,它的思想就是从一堆元素中随机选出一个来,再从剩下的元素里随机选择,直到选完为止。

严格证明的话,用数学归纳法是简单的,对n进行归纳即可。但好久不做数学题,头脑快生锈了,因此尝试一下复杂一些的证明,证明思想是对原位置i的元素进行跟踪。

阅读全文…

11
Jul

“左”"右”政治

一. 先来说说什么是”左”和”右”

1. 左翼(left-wing)和右翼(right-wing)的历史

以左右来划分政治派别, 起源于法国大革命. 在那个叫路易XX为国王的波旁王朝最后掌权的年代, 法国议会的右边坐着保皇党人, 而左边则是激进改革派. 从那时候起, 为政治派别首先划分开了阵营, 便于扎堆和排队, 区分敌友.

2. 传统意义上的”左”"右”二元区分

先来看看, 左右翼阵营划分之初, 两边的区分

左翼 右翼
更多的经济干预 更多的经济自由
以消除不平等为目的 承认不平等的存在
绝对意义上的平等 获得机会的平等
自由主义 保守主义
无神论政府 宗教政府
法律支配文化 文化支配法律

从这个最基本的分歧上, 后续产生了分居两边的各种主义和体系, 社会主义/共产主义/资本主义, 大陆法系/英美法系等等

但”左”"右”的划分和阵营不是一个绝对的划分, 而是相对的概念

当法国大革命轮到罗伯斯比尔和雅各宾派上台的时候, 自由主义的左派在砍了国王的脑袋以后, 也开始为了维护自己的政权疯狂的砍其他异见者的脑袋.这一点上讲, “左”和”右”都可能成为保守派, 只要在他们掌权以后; 同时也都可能是改革派, 那是他们在野的时候.

阅读全文…

10
Jul

倾国又倾城

倾国倾城的典故出自汉武帝
他在四五十岁平定内忧外患并且泰山封禅三年之后面对滔滔江山写了那首《秋风辞》
秋风起兮白云飞,草木黄落兮雁南归。
兰有秀兮菊有芳,怀佳人兮不能忘。
泛楼船兮济汾河,横中流兮扬素波。
萧鼓鸣兮发棹歌,欢乐极兮哀情多。
少壮几时兮奈老何!

一切忧愁源于对时光流逝的恐惧
而男人对时光流逝的恐惧感总是比女人要晚一二十年才出现并且表现点有所差别
女人的恐惧源于时光的蹉跎青春一转眼就不见,却还有那么多事来不及完成那么多欲望来不及满足那么多幸福来不及体验
而男人的恐惧源于在过去的几十年间,埋头苦干外拼事业内辅家庭,把自己的生活带上蓝图之后,一下几十年过去了,却不知道自己真的想干什么
刘彻也是在这个时候心生感慨
不过这个是题外话
阅读全文…

07
Jul

旷世孤独——淇淇七年之祭

7年前的7月14日,一条名为“淇淇”的白鳍豚在武汉白鳍豚馆度过了22个春秋之后,在这一天孤独的离开了世界。

淇淇是人类见过的最后一条活着的白鳍豚。虽曾于2004年发现过白鳍豚的尸体,然而之后数次大规模的监测活动中却再也没能找到它们的身影。两年前的8月8日,这种我们从小熟知的“长江女神”,“水中大熊猫”,终于被宣告灭绝。

在白鳍豚馆里的22年中,淇淇虽然有过短暂的伴侣,绝大部分时间都是在孤独中度过的。设想一下,如果你是世间幸存的最后一个人,对于你这意味着什 么?是不是旷世的孤独、绝望与无助?这样不幸的事情正发生在它的身上。再也找不到谁与它结伴而游,喜欢结群的它只能在池中独自游弋;任凭它引吭高唱,这世 界上已没有谁能理解它的声音。 阅读全文…

26
Jun

温故而知新

假如你有1000万要办一个网站。下面两种方案:

1,用800万买性能高的服务器,200万雇专业能力一般的技术人员;

2,用200万买性能一般的服务器,800万雇专业能力优秀的技术人员。

哪种更划算呢?

之前想了几次这个问题,但一直没得到一个简便的答案。后来突然想到,这个事情在算法教科书里经常提到。大意就是,假如你的程序使用的算法的复杂度是高于线性的,那么你买一个性能提高了N倍 的机器,你的程序单位时间内处理的数据量并不会提高N倍。

那么机器与人的区别就是,更贵的机器为你的程序带来的性能提升是线性的;而一个优秀的技术人员,通过设计时间复杂度更低的算法,则可能帮你将一个性能较差的程序的性能以平方、立方甚至指数级别提升。如果这样想的话,第2种方案更为划算。

这是一个很开放的问题。这里只是从性能这个角度去考虑,而且纯粹是理论上的。实际中需要考虑的因素更多。大家有何想法呢?

21
Jun

A naive social model

作为一个纯真的少年,心目中的社会模型首先是这样的:

最低级的社会,是森林那样的社会,不需要任何组织和上层建筑,唯一的法则是“弱肉强食”。但是随着社会的进一步发展,弱肉强食的法则显然行不通了,比如我们总不能让相对较弱的妇女儿童随便被“弱肉强食”掉,或者有些人比较有远见、有些人较有智谋,但身体相对较弱,总不能让这些对群体有用的人也被“弱肉强食”掉。因此需要一个统治阶层,形成一套社会组织,来行使更有利于群体发展的社会法则。从这位纯真少年的朴素社会模型来看,统治天然是服务性质的。

但是随着纯真少年年龄的增长和阅历的加深,他变成一个理工男,并且看到了中国社会的很多现象都不符合这个朴素模型,甚至对这个模型进行修正也行不通。好奇的理工男于是慢慢形成了一套新的社会模型,来帮助自己理解新观察到的现象。就像物理模型一样,它摒弃了大量的繁琐的细节(有可能是重要的细节),只留下简单的一个社会过程。

一个模型通常需要定义一些极端简化的实体,这里也不例外。首先,有必要对好人和坏人来做一下定义。好人和坏人并不是两个截然分开的集合,而是数轴上的两个端点。极端的好人倾向于善待社会群体中的其他人,做事更倾向于责任、信仰,而不是受个人利益倾使;坏人则相反,更倾向于通过侵犯他人的利益来最大化自己的利益,做事更倾向于受个人利益趋使。

刚才提到的朴素社会模型,盲点之一在于统治阶层的形成过程。这个形成过程我们希望它是有序的、被有利于群体的法则支配的。但是悖论在于,统治阶层形成之前,新的法则尚不存在,社会基本上仍被“弱肉强身”法则支配,因此这个统治阶层形成的过程就大有问题。在这个新的社会模型中,统治阶层形成的过程中发生了一件重要的事情,与“劣币驱逐良币类似”,那就是“坏人驱逐好人”。

阅读全文…

16
Jun

信息过载和meme

互联网从信息饥渴到信息过载,  几乎是瞬间完成的. web 2.0的普及更是带来了一个信息爆炸的时代.

web1_0-vs-web2_0

对于海量数据的网络, 人们有哪些需求?

一种是”找”, 用户知道自己想要什么, 就像从杂物间里面找硬币一样. 另一种是”听”, 我不知道我要什么, 你来告诉我这里有什么好玩的东西, 也许我会感些兴趣.

十几年前, 有种叫搜索引擎的东西被造出来替人们去做第一件事情.但对于第二件事情,  却很难有个聪明的机器去替我们做, 因为机器还没智能到可以在没有任何人类提示的情况下, 从一堆一堆垃圾里面找到精华.

这里面唯一值得一提的就是新闻聚合,  把新闻网站的内容聚出焦点来.  这是一个好的开始, 但还不够.如果我怀着一颗好奇的心, 那么我该去”听”谁的呢? 网络时代之前的做法被沿用了下来.

1) 相信专业: 媒体编辑的职业就是干这活的, 天天看, 天天选. 他先替你一层一层选一遍, 你跟着他混就行了.这招准确率还行, 覆盖率不够. 同时严重依赖编辑的水平和操守, 最可怕的是遇到新闻联播型的媒体.

2) 相信大众: 别人都说好的, 咱也别错过. 这个依赖于群体智慧的整体水平.

3) 相信自己: 把所有东西看一遍, 自己来筛选精华.  这个方法好, 但似乎代价太大了……

阅读全文…

11
Jun

读书: 中国文化的深层次结构

s1915975-thumb s3161076-thumb

“中国文化的核心之一就是一个“仁”字。仁者,二人也(圣人的诠释),换句话说,一个人是不是仁者,是他人决定的,而不是自己。如果大家都认为你是仁者,那么,仁者,便无敌了。”

据传简体中文版, 略有删节, 未找到电子未删节繁体中文版.

http://www.douban.com/subject/1068912/

其实所谓仁者, 往往都是忍者.

5445ca086968c2016b60fbe8

07
Jun

请多给我一个选择, 哦不,还是让我有自己的答案

今天又是高考日

又一年和标准答案和出题老师搏斗的日子

对于”你是如何理解文中划线句子的意思?? ”

是A, 还是B? 抑或是C, D?

在经过10年的训练之后, 智商正常的人都会自动的在脑中翻译成

“出题老师是如何理解文中划线句子的意思????”

在那问题背后的是在那一刻你能否被标准答案附体

从那一点一点的线索里面推测出出题人在那一晚的心情

和从做过千遍的习题里面找出这类生物共同的思维方式

等着被标准答案宠幸是我很多年以前在考场上的心情

这种非黑即白的方式, 让我们自然对于权威有了无限的尊敬

同时, 也让我深信, 答案里面肯定有一个是正确的,

当你认为正确的应该是E的时候, 那么一定是完全的错了,

因为E连进入选择范围的机会都没有, 当你选择坚持

在试卷的小角落里面, 写上除了ABCD之外的答案, 等待你的也只有一份没有了

阅读全文…