FourInOne（中文名字“四不像”）是一个四合一分布式计算框架，在写这个框架之前，我对分布式计算进行了长时间的思考，也看了老外写的其他开源框架,当我们把复杂的hadoop当作一门学科学习时，似乎忘记了我们想解决问题的初衷：我们仅仅是想写个程序把几台甚至更多的机器一起用起来计算，把更多的cpu和内存利用上，来解决我们数量大和计算复杂的问题，当然这个过程中要考虑到分布式的协同和故障处理。如果仅仅是为了实现这个简单的初衷，为什么一切会那么复杂，我觉的自己可以写一个更简单的东西，它不需要过度设计，只需要看上去更酷一点，更小巧一点，功能更强一点。于是我将自己对分布式的理解融入到这个框架中，考虑到底层实现技术的相似性，我将Hadoop,Zookeeper,MQ,分布式缓存四大主要的分布式计算功能合为一个框架内，对复杂的分布式计算应用进行了大量简化和归纳。 fourinone-1.11.09 hadoop-0.21.0 体积 82K 71M 依赖关系 就一个jar,没有依赖 约12项jar包依赖 配置 就一个配置文件 较多配置文件和复杂属性 集群搭建 简单，每台机器放一个jar和配置文件 复杂，需要linux操作基础和ssh等复杂配置，还需要较多配置文件配置 计算模式 提供两种计算模式：包工头和工人直接交互方式，包工头和工人通过消息中枢方式交互，后者不需要工人节点可直接访问 计算更多倾向于文件数据的并行读取，而非计算过程的设计。JobTracke 跟TaskTracker直接交互， 查询NameNode后，TaskTracker直接从Datanode获取数据。 并行模式 N*N，支持单机并行，也支持多机并行，多机多实例并行 1*N，不支持单机并行，只支持多机单实例并行 内存方式 支持内存方式设计和开发应用，并内置完整的分布式缓存功能 以hdfs文件方式进行数据处理，内存方式计算支持很弱 文件方式 自带文件适配器处理io Hdfs处理文件io 计算数据要求 任意数据格式和任意数据来源，包括来自数据库，分布式文件，分布式缓存等 Hdfs内的文件数据，多倾向于带换行符的数据 调度角色 包工头，可以有多个，支持链式处理，也支持大包工头对小包工头的调度 JobTracke，通常与NameNode一起 任务执行角色 农民工，框架支持设计多种类型的工人用于拆分或者合并任务 TaskTracker，通常与Datanode一起 中间结果数据保存 手工仓库，或者其他任意数据库存储设备 Hdfs中间结果文件 拆分策略 自由设计，框架提供链式处理对于大的业务场景进行环节拆分数据的存储和计算拆分根据业务场景自定义 以64m为拆分进行存储，以行为拆分进行计算 实现map接口，按行处理数据进行计算 合并策略 自由设计，框架提供农民工节点之间的合并接口，可以互相交互设计合并策略，也可以通过包工头进行合并 TaskTracker不透明，较少提供程序控制，合并策略设计复杂 实现reduce接口进行中间数据合并逻辑实现 内存耗用 无需要制定JVM内存，按默认即可，根据计算要求考虑是否增加JVM内存 需要制定JVM内存，每个进程默认1G，常常namenode，jobtracker等启动3个进程，耗用3G内存 监控 框架提供多环节链式处理设计支持监控过程，通过可编程的监控方式，给于业务开发方最大灵活的监控需求实现，为追求高性能不输出大量系统监控log 输出较多的系统监控log，如map和reduce百分比等，但是会牺牲性能，业务监控需要自己实现 打包部署 脚本工具… Read more »
Posts Categorized: Study & Reading
五个最佳的Hadoop项目
本文来自SD Times高级编辑Alex Handy同学。他列出了当前使用Hadoop的项目中他认为最成功的五个。下面是这五个列表。 原文链接：The top five most powerful Hadoop projects 1.Cascading：Cascading是基于Hadoop集群之上的数据处理API。它通过实现了丰富的功能化API，使你不需要接触MapReduce任务就能使用分布式计算能力，其核心概念是基于管道和流的数据处理。 2.Mahout：Mahout是一个基于Hadoop实现各种机器学习与数据挖掘算法库。被用来提供推荐服务。 3.Hive：Hive由Facebook出品，它为Hadoop提供了一种类似于SQL的操作接口。 4.Avro：Avro是一个基于二进制数据传输高性能的中间件。Avro通过将数据进行序列化，以使得大批量数据交互过程更方便。 5.Storm：Storm由BackType Technology出口，其口号是“实时的Hadoop系统”。
Hive使用笔记
Hive是为提供简单的数据操作而设计的下一代分布式数据仓库。它提供了简单的类似SQL的语法的HiveQL语言进行数据查询。同时，HiveQL语言能力不足时，它也能允许使用传统的map/reduce进行复杂数据分析。 Hive是搭建在Hadoop平台之上的。Hive并不是一个真正的数据库，它的元数据需要存储在其他数据库中(例如mysql)。。Hadoop平台提供了HDFS分布式存储系统和map/reduce分布式计算系统，而Hive在这两个系统之上，使得用户只需使用熟悉SQL语言就能进行分布式计算，而map/reduce编程往往是相当复杂的。Hive在少量数据运算或是短时间内的重复查询上，是不能和Oracle那样的数据库相比的。它的查询量通常相当大，一个大的job运行几个小时算是正常的。 数据类型 。HiveQL只支持以下几种基本数据类型TINYINT, SMALLINT, INT, BIGINT, DOUBLE, STRING。 支持的复杂数据类型有Structs, Maps, Arrays。 创建表。 Hive不同于其他数据库，它只有一个默认数据库”default” ，所有的table都保持在里面。 CREATE TABLE user(id BIGINT, name STRING); 可以指定将表创建到外部hdfs文件系统中。 CREATE EXTERNAL TABLE foo(id INT) STORED AS TEXTFILE LOCALTION ‘/user/foo/foo_data’; 将数据文件导入到Hive表中。 LOAD DATA [LOCAL] INPATH ‘/data/userdata’ [OVERWRITE] INTO TABLE user; 使用LOCAL选项将使用本地文件系统 ，否则将使用hdfs文件系统。使用OVERWRITE选项将删除原来table中的数据，否则将新数据添加到文件末尾。 Load data导入数据将仅仅将文件拷贝到hive管理的目录下，并用table的元数据去解释这个文件。所以必须保证数据文件的结构必须和table的结构一 致，否则可以load data成功但是数据解释不正确。特别注意fields分隔符和lines分隔符要和Table一致。我使用自定义分隔符导入数据，一直没有成功。不管我 怎么指定，Hive总是使用默认的分隔符来解释我的文件（默认使用001(ctrl-A)分隔列，012(\n)分隔行 ）。问题未解决。 查询语句。 这里列出一些和标准SQL不同的地方。 不能使用select count(*)；需要指定count的列下标，select count(1)… Read more »
提问的智慧
IT技术这个行业混久了，作为一路走到现在的人，很多事情看不习惯，很多新手非常的浮躁，总是问，学什么赚钱，我要是知道学什么赚钱，我自己就去了，还轮到你么？再说不管什么行业，只要你处于金字塔的中上层，钱都不会少的。钱不是目的，他只是提升的自己的一个过程。新手遇到问题，劈头就问怎么解决，怎么办？甚至问题都不想清楚就问，我非常讨厌这样的提问方式。国内产出文章质量比较高的社区之一 —啄木鸟社区为想做程序员这个行当的人树立了很好的榜样，建议新人去看看，你不一定要学Python，但是其中的一些精髓是值得每个程序员学习的。 提问的智慧 全文在此，图如下：
《Rework》
这本书是近来难得一见的好书，认识字的都应该去读几遍，中文最近也出版了，各大售书网站都可以买到，打完折二十几块钱，非常物有所值，尽管英文版我已经读过，依然忍不住买一本中译本收藏，虽然中译本的名字我觉得很恶俗，这本书和商业思维没有太多的关系，中译本的作者自作聪明的加上这个小标题，有点恶心，另外将rework翻译成“重来”个人觉得也有点欠妥当，还不如不翻译，意思可能会更明确一点。虽然中译本有这样那样的问题，整体来说翻译的不错，不喜欢英文的可以买来看看，鼎力推荐——我本人不会有任何好处 那来的从错误中学习 中国人常说的一句话是：失败是成功他妈。作者引用哈佛商学院的报告证明，失败的创业者再次创业并不比从未创业的人成功的概率更高。有一类人非常明白这个道理，他们有个名字叫VC（风险投资人），VC非常喜欢那些已经或者曾经创业并且干得不错的人，换句话说这些人往往能从VC那里以比较小的代价（损失较小的股份或者少费周折）搞到很多很多的钱用于再次创业或者公司发展 。 何必壮大 这个观点有点意思，几乎所有的企业家都想将自己企业做大，富士康的员工超过百万，而作者觉得大未必是最优的，我非常认同作者的观点，我身边就有很多的公司每年几个亿的业务却只有10个左右的员工。公司越大责任就越大，不仅要自己赚钱还要照顾好这些员工，是一个有责任的企业家应该做到的，而不是压榨。如果你不能，那么就尽量提高效率，少招几个人吧，与人与己都是好事。 工作狂 引用里面的几句话：工作狂实际取得的成就并不比正常人高，他们自诩为完美主义者，但这仅仅代表他们浪费了大量的时间去关注次要的细节，而不是推动下一项任务。真正的英雄是早已想出办法、搞定一切，然后回家了。 Start making Something 我们身边总有这样的人在叹息“XXX我早就想到了，只是没有下手，如果当初我干了，现在也亿万富翁了”，这个观点很可笑，你大脑中有创意跟你实际去创建这样的事情一点关系也没有，在你人生中最有意义的使你做了什么，而不是你想过什么、说过什么或者计划过什么 没有时间不是借口 当你拥有某种极其强烈的渴望时，你就能挤出时间来，不管你身上是否还背负着其他的责任，事实上大部分的渴望不是那么强烈，于是他们总是拿没有时间来做借口进行自我保护。如果我不是这样，我今天已经做出了好几个开源作品了。 =====未完待续======
代码调优法则–编程珠玑笔记
1、空间换时间法则 这个东西，稍微有点程序经验的人应该都接触过，比如在设计数据时候冗余了部分数据，避免关联表查询，减少开销，实际上也减少了查询时间，所谓空间换时间。还比如，我们将一个有点开销的计算结果存储起来，避免下次再次运算，减少时间消耗，再如，CPU的设计，设置了高速缓存，一级缓存，二级缓存，主存（通常所说的内存），其实一个硬盘和一个CPU也可以干活，只是干得不怎么样，因为硬盘和CPU之间速度实在是差别太大了，如是就有人想把可能要用到的数据预先加载到高速缓存或者主存中，慢慢形成了今天的个人计算机架构。 2、以时间换空间法则 这个其实也是天天在用的一个法则，只是一般技术人员看到“压缩”二字的时候，没联想到那么多，压缩就是最典型的拿时间换空间的例子，就是不断的重复前面已经存储过的存储地址，用来避免存取真实的数据。 3、循环法则 大部分稍微有点经验的人不会在同一个函数中循环两次同样的变量，但是仅限于同一个函数，假如在一个函数里调用了另外一个函数，那么就不一定了，很多人为了看似解耦的一个操作，在两个函数对同一个变量做了多次的循环。循环法则有几个比较经典细则： 第一、将代码移除循环，这是最容易想到的，当然，可以移除的条件是，每次循环都执行同样的某次操作。 第二、合并测试条件，高效的内循环应该包含尽量少的测试条件，最好只有一个，因此，程序员尽量用一些退出条件来模拟循环的其他退出条件。 第三、哨兵法则，在数据结构边界上放一个哨兵以减少测试是否已经搜索结束的开销。 第四、展开循环，展开循环可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也有很大帮助。 第五、删除赋值，赋值的开销实际上在整个程序的执行过程中占的开销可以忽略不计，但假如你要在一个循环十万次的循环中赋值，那么开销就不能不计了，尽可能的在循环中减少赋值吧。 第六，消除无条件分支，快速的循环中不应该包含无条件分支，通过旋转循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。 第七、循环合并，如果你不小心做了傻事，那么合并两个对同一个变量循环操作吧 4、逻辑法则 利用等价的代数表达式。如果逻辑表达式的求值开销太大就将其替换为开销较小的等价代数表达式。 短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到这个阈值就不在需要计算任何变量了。 对测试机条件重新排序。在组织逻辑测试的时候，应该是降低开销的，经常成功的测试放在高开销的，很少成功的测试前面。 5、过程法则 打破函数层次。对于（非递归地）调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。 并行性。在底层硬件条件下，我们构建的程序应该尽可能多的挖掘并行性。 6、表达式法则 编译时初始化。在程序执行前，应该尽可能多的变量初始化。 利用等价的代数表达式。如果表达式的求值开销过大，就将其替换为开销更小的等价的代数表达式，比如换一种算法 消除公共子表达式。如果两次对同一个表达式求值，其所有变量都没有任何改动，那么我们可以用下面方法避免二次求值：存储第一次的计算结果并用其取代第二次求值。
UDP hole punching 翻译
3.3. UDP hole punching UDP打洞技术 The third technique, and the one of primary interest in this document, is widely known as “UDP Hole Punching.” UDP hole punching relies on the properties of common firewalls and cone NATs to allow appropriately designed peer-to-peer applications to “punch holes” through the middlebox and establish direct connectivity with each other,… Read more »
N-Gram学习笔记
统计语言模型 假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)： 这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定： N-Gram模型 当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。 N-Gram模型被称为一阶马尔科夫链。 N的值不能太大，否则计算仍然太大。 根据最大似然估计，语言模型的参数： 其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数 平滑技术的引入 传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求： N>>K 其中K为随机变量能够取到的值的个数。 实际语言模型中往往无法满足这个要求。 例如：词性标注问题，共有140个可能的标记，考虑当前词前后两个词的影响的三阶模型。 K=140*140*140=2,744,000 给定一个10万词左右的人工标注训练集，即 N=100,00，可见训练数据显得非常不足。 假设k泛指某一事件，N(k)表示事件k观察到的频数，极大似然法使用相对频数作为对事件k的概率估计： p(k)=N(k)/N 在语言模型中，训练语料中大量的事件N(k)=0，这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。 这种零值的概率估计会导致语言模型算法的失败，例如：概率值作为乘数会使结果为0，而且不能做log运算。 计数等价类 根据对称性原理，事件除了出现次数之外不应具有细节特征，即所有具有相同计数r=N(k)的事件k（事件出现的次数称为事件的计数）应当具有相同的概率估计值，这些计数相同的事件称为计数等价，将它们组成的一个等价类记为计数等价类Gr。 对于计数为r的计数等价类，定义nr为等价类中成员的个数，pr为等价类中事件的概率，R是最大可能出现的计数次数，则 交叉检验 交叉检验就是把训练样本分为m份，其中一份作为保留部分，其余m-1份作为训练部分。训练部分作为训练集估计概率pr，保留部分作为测试集进行测试。 我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计，即使对数似然函数最大化： 使用拉格朗日乘子解决约束条件下的最大值问题，即： 对pr求偏导，得到交叉检验估计： 如果测试部分也作为保留部分的话，就是典型的极大似然估计： 留一估计 留一方法是交叉检验方法的扩展，基本思想是将给定N个样本分为N-1个样本作为训练部分，另外一个样本作为保留部分。这个过程持续N次，使每个样本都被用作过保留样本。 优点：充分利用了给定样本，对于N中的每个观察，留一法都模拟了一遍没有被观察到的情形。 对于留一方法，pr的极大似然估计为： Turing-Good公式 因为nRpR与1相比一般可以忽略，留一估计公式可以近似为： 留一估计可以利用计数r=1的事件来模拟未现事件，对于未现事件有如下估计： 这个公式就是著名的Turing-Good公式。 空等价类 留一估计中要求么个nr均不为0，在实际问题中当r=5时，这个要求通常都不能满足，即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序： 对应的出现r(l)次的事件的个数记为nr(l)，在进行留一估计时，使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1，留一估计公式变为： 式中对空的等价类没有估计概率，因为空等价类并没有对应任何有效事件。 Turing-Good估计的优缺点和适用范围 缺点：( 1 )无法保证概率估计的“有序性”，即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似，好的估计应当保证pr<=r/N。 优点：其它平滑技术的基础。 适用范围：对0<r<6的小计数事件进行估计。 约束留一估计 单调性约束：pr-1<=pr；折扣约束：p<=r/N。 约束留一估计：让计数估计r*=pr•N处于距其最近的绝对频数之间： 在这个约束下，单调性约束自然满足。 计算方法：计算m时检查每个pr是否满足约束，不然就用约束的上下界进行裁剪，然后重新计算m，一直迭代下去直到所有pr满足约束。 折扣模型… Read more »
代码格式规范的List
《代码大全》是本好书啊，推荐所有有志于改善自己的程序，或者在编码上寻找进一步提高的人应该仔细研究研究。以下是摘抄自《代码大全》第二版中谈到关于怎样的代码格式更适合人类阅读，更能令人愉悦的Check List。对照List进行自检和反省，令人欣慰的是List中80%以上我都做到了，在我的上一个项目中做得比较失败，由于时间的原因，很多注释没有加上，逻辑也不够清晰。在重构中解决，借此反省。 一般问题： 格式化主要是为了展现代码的逻辑结构吗？ 2、你的布局方案能统一运行吗？ 3、 你的布局方案能让代码易于维护吗？ 4、你的布局方案是否有利于代码的可读性？ 控制结构的布局 1、你的代码中避免begin-end 或对｛｝的双重缩进了吗？ 2、相邻的块之间用空行分割了吗？ 3、对复杂表达式格式化时考虑到可读性吗？ 4、对只有一条语句的块布局始终如一吗？ 5、case语句与其他控制结构的格式化保持一致了吗？ 6、对goto语句格式化是否让其显眼了呢？ 还好目前PHP只有5.3以上版本才会有goto 单条语句的布局： 1、为逻辑表达式、数组下标和子程序参数的可读性使用了空格了吗？ 2、不完整的语句在行末似乎以明显又错的方式结束吗？ 3、后续行按照标准数码缩进了吗？ 4、每行顶多只有一条语句吗？ 这一点是团队中比较头痛的问题，很多人不按照这个规则来做，结果它成了一种风气 5、所写的每个语句都没有副作用吗？ 6、每行顶多只声明一个数据吗？ 注释布局： 1、注释与其所注释的代码所尽量相同吗？ 2、注释风格便于维护吗？ 子程序的布局： 1、你对每个子程序的参数格式化方式便于看懂、修改、注释吗？ 2、采用空行分割子程序各部分了吗？ 4、文件中子程序用空行清楚分开了吗？ 5、在没有更好的组织形式的场合，所有子程序都按字母排列了吗？ 这一点我没有做到，没有做到是没有想到这一点，以后编码注意了……
程序语言评估标准
1、可读性。判断一个语言的优劣的一个最重要的标准是用它写的程序要好读，好懂。 一种语言的整体简单性极大的影响着他的可读性。一种具有大量基本结构的语言较只有少量基本结构的语言要难学得多，当然，过少也会非常难学，汇编就是如此。 2、正交性。正交性是指使用该语言中一组相对少量的基本结构，经过相对少的组合步骤，可以构成该语言的控制结构与数据接哦股。而且，它的基本结构的任何组合都是合法和有意义的。 3、控制语句。在20世纪50年代和60年代，一批程序设计语言由于缺乏控制语句，导致很差的可读性。随后的语言都兴起了结构化程序设计的革命。尤其是人们普遍意识到滥用goto会降低程序设计的可读性。 4、数据类型和数据结构。在程序设计语言中给出定义数据类型和数据结构的合理机制，是语言可读性的又一个重要辅助。 5、可写性。可写性是程序设计语言的在应用领域产生程序的难以程度的一种度量。大多数影响可读性的语言特征可以影响可写性。 6、支持抽象。抽象指的是以合法的省略许多细节的方式，来定义并且使用复杂结构或复杂运算的能力。 7、表达性。语言的表达性可以指语言中几种不同特征。一种是具有一些功能很强的运算符。一种是程序语言具有相对方便，非繁琐的方式来说明运算。 8、可靠性。如果一个程序在任何条件下的运行都能 达到他的说明标准。我们称这饿程序是可靠的。 9.代价。第一是训练程序员使用这种语言的代价。第二是使用这种语言来编写程序的代价。第三是编译程序的代价。第四是程序运行的代价。
Recent Comments