mapreduce笔记

MapReduce is  a programming model and an associated implementation for processing and generating large data sets.
首先它是一种编程模型, 它的使用场景是处理/生成大量数据集

1. 编程模型
Map: 获取输入(key-value),生成中间数据(key-value). 所有相同key的中间数据聚为一组
Reduce: 输入为中间数据, 合并这些数据得到较小的结果数据集
伪代码(统计单词总数):

类型:
这里举每个单词出现频率统计的例子:
k1,v1 调用时 k1-为单词, v1-为出现次数,这里为1
list(k2,v2) map的结果, 得到的是单词与对应出现次数的集合, 这里为: (a,1),(b,1),(a,1),(a,1)….
k2,list(v2) 对前面中间数据聚合 (a, 1,1,1) (b,1)
list(v2) 最终结果 (3,1)

适用场景列举:
分布的grep
统计URL访问频率
reverse web-link graph
term-vector per host
inverted index
distributed sort

2. 实现

2.1 执行流程:

2.2 master数据结构
master中保存: 
a. map/reduce任务的状态(执行中,完成)
b. 所有worker的标识
c. map产生的中间数据的位置
2.3容错
a. worker failure
b. master failure
c. semantics in the presence of failures
2.4 locality
为了节约带宽, 优先处理本地数据
由于使用GFS, 数据会分布到所有的集群机器,此时需要根据数据的保存位置优先处理那些位于本地的数据.从而减少带宽耗用.
2.5任务粒度
理论上任务粒度(M,R)是可以计算出来的, master需要进行O(M+R)次的调度决策, 保存O(M*R)个状态在内存.
2.6 backup任务
避免某一个任务因为某种(机器,网络)原因没有完成,导致堵塞其他任务.
when a mapreduce operation is close to comletion(不懂), the master schedules backup executions of the remaining inprogress tasks.
定义当多少task完成时为close to completion. 这样当达到这个值时,启动剩余task的后备task, 这样当任意一个task或它的后备完成时即认为task完成.
3优化, mapreduce库的一些特性
3.1 partition function
结果数据分块函数, hash(key) mod R, hash(Hostname(urlkey)) mod R…

3.2 保持顺序
在一个分区内按照key对结果排序, 从而提高对结果进行基于key的随机访问查找的效率

3.3 合并
通过将相似的结果进行简单合并,从而减少master的调度和带宽耗用, 如统计单词出现次数,在map时会到到很多<a,1>的中间结果, 将这些合并为<a,100>

3.4自定义的输入/输出参数类型

3.5 side-effect
不支持产生多个结果文件的2阶段提交策略,需要user自己控制

3.6 skip bad record
Each worker process installs a signal handler that catches segmentation violations and bus errors. Before
invoking a user Map or Reduce operation, the MapReduce library stores the sequence number of the argument
in a global variable. If the user code generates a signal,Each worker process installs a signal handler that
catches segmentation violations and bus errors. 
Before invoking a user Map or Reduce operation, the MapReduce library stores the sequence number of the argument
in a global variable. If the user code generates a signal,

3.7 本地调试工具

3.8 状态监控

3.9计数器

4.性能表现 略

ec2的sudo问题

sudo: sorry, you must have a tty to run sudo

由于ec2上所有涉及到root权限的操作都要sudo. 所以如果远程操作会报错. 我是使用ant的sshexec在本地操作.
sudo时就会报这个错.

通过google找到这个:
vi /etc/sudoers (最好用visudo命令)
注释掉 Default requiretty 一行
#Default requiretty

意思就是sudo默认需要tty(终端)。注释掉就不需要了.

创业夜未眠: 让创业者无法入眠的23个问题

创业夜未眠: 让创业者无法入眠的23个问题

Sleepless In Startupville: 23 Questions That Keep Entrepreneurs Up

作者:Dharmesh Shah
我常常和处于各种不同阶段的创业者交谈. 在这些交谈中, 有一些”主题”会经常光顾. 这里是一些创业者在夜深人静时候经常问自己的问题.
当然, 如果已经对某些问题有了答案是很有用的 – 但这时候就需要读者您了. 如果你有关于这些问题的解答和想法, 请不吝分享. 发推或者发到OnStartup的facebook主页.

分类信息的成本效用公式

信息覆盖度 = (效用/获取成本)* 区域物流成本系数

n  物流成本系数, 取决于区域大小/物流的发达程度/以及商品本身的一些特质

n  效用, 因人而异可以是一个0~无穷大的值, 但如果商品确定的情况下,其效用值的范围还是满足正态分布的. 这里要注意相对于普通商品, 二手商品更存在随机效用的情况,也就是为什么用”淘”,而不是”买”

n  可以根据该公式映射覆盖度和物品分类, 有针对性的提供服务.

比如工作, 是因为一份合适的工作效用很大,获取成本即使比较大(可能会花一些中介费获取信息), 招聘信息的物流成本很低,这里为1

再如二手自行车, 效用不是很大,但获取成本如果较大,则必须要在较小的覆盖度内.或者物流成本系数会影响(比如可能该城市的快递费比较低,或者有比较顺路的朋友可以代取)

分类信息网站的类型

在线分类的价值体现在相较传统纸媒,更广更大的覆盖率(visibility),但在线分类又存在两种

n  垂直分类(如大众点评,包括垂直搜索如,去哪, 51job)

n  水平分类(如百姓,58)

二者都有生活圈的局限,但是前者由于信息较为集中和全面,因而生活圈范围较大(城市或者城市圈),后者信息比较有限,因而生活圈相对较小(城市或者城市以下的区域)

举个例子, 如果找工作我一定会去51job/智联这样的网站,并且工作地点的选择可以考虑整个城市,即便是比较远的地方,如果环境和薪酬合适,也会考虑. 我是想过百姓网找工作,但是家附近并没有找到我心仪的机会.但如果我想买一辆二手自行车,我不大会考虑离家3公里以外的地方,因为相对收益来说成本会太高.

这里51job的效用圈可以覆盖整个城市, 而百姓网的找工作/二手板块仅仅覆盖到某个地区. (当然百姓网的某些板块也是可以覆盖到城市级别的,比如二手车),覆盖度完全取决于所买卖的商品的成本和对于潜在买家 的效用 – 成本效用理论. 也许你会说, 我也可以通过百姓网找工作呀, 是的, 的确. 但是工作性质和工作内容也是不同的, 百姓网上大多数都是收入较低的工作岗位, 这个时候收益考虑又占了上风.

初创公司CEO应该遵守的14条准则

初创公司CEO应该遵守的14条准则
(14 Ways To Be A Great Startup CEOhttp://onstartups.com/tabid/3339/bid/34321/14-Ways-To-Be-A-Great-Startup-CEO.aspx)
great startup ceo mark zuckerberg resized 600
初创公司的CEO生活并非我们想像的那么光鲜, 初创公司的生活也许也并非像媒体报道的那样多彩. 你知道我在指哪些媒体…那些谈论融资是多么容易,用户量扩大到多少,做CEO有多好. 很少能听到做CEO多么”操蛋”以及每个创始人都不想成为企业家. 我最近花了一些时间思考如何成为一个创始人兼CEO, 下面是一些结果.