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 Tagged: 编程技术
TF-IDF及文本相似性度量
TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与文本挖掘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，互联网上的搜寻引擎还会使用基 于连结分析的评级方法，以确定文件在搜寻结果中出现的顺序。 在一份给定的文件里，词频（term frequency，TF）指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被正规化，以防止它偏向长的文件。（同一个词语在长文件里可能会 比短文件有更高的词频，而不管该词语重要与否。）对于在某一特定文件里的词语 ti 来说，它的重要性可表示为： 以上式子中 ni,j 是该词在文件dj中的出现次数，而分 母则是在文件dj中所有字词的出现次数 之和。 逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到： 其中 |D|：语料库中的文件总数 ： 包含词语ti的文件数目（即的 文件数目） 然后 某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词 语，保留重要的词语。 =================文本相似性度量======================= 方法一：向量空间模型 在向量空间模型中，文本泛指各种机器可读的记录。用D（Document）表示，特征项（Term，用t表示）是指出现在文档D中且能够代表该文档内容的 基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D(T1，T2，…，Tn)，其中Tk是特征项，1<=k<=N。例如一篇 文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为D(a，b，c，d)。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示 其重要程度。即D＝D(T1，W1；T2，W2；…，Tn，Wn)，简记为D＝D(W1，W2，…，Wn)，我们把它叫做文本D的向量表示。其中Wk是 Tk的权重，1<=k<=N。在上面那个例子中，假设a、b、c、d的权重分别为30，20，20，10，那么该文本的向量表示为 D(30，20，20，10)。在向量空间模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的余弦值表示，公式为： 其 中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1<=k<=N。 在自动归类中，我们可以利用类似的方法来计算待归类 文档和某类目的相关度。例如文本D1的特征项为a，b，c，d，权值分别为30，20，20，10，类目C1的特征项为a，c，d，e，权值分别为 40，30，20，10，则D1的向量表示为D1(30,20,20,10,0),C1的向量表示为C1（40，0，30，20，10），则根据上式计算 出来的文本D1与类目C1相关度是0.86 方法二：字符串相似度 对于象字符串计算相似度的算法有很多，常用的有最大公共字串，编辑距离等。 编辑距离就是用来计算从原串（s）转换到目标串(t)所需要的最少的插入，删除和替换的数目，在NLP中应用比较广泛，如一些评测方法中就用到了 （wer,mWer等），同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫 Levenshtein Distance。
淘宝在数据处理领域的项目及开源产品介绍
淘宝在数据存储和处理领域在国内互联网公司中一直保持比较靠前的位置，而且由于电子商务领域独特的应用场景，淘宝在数据实时性和大规模计算及挖掘方面一直在国内保持着领先，因此积累了很多的实践的经验和产品。 TimeTunnel 基于Hbase打造的消息中间件，具有高可靠、消息顺序、事务等传统特性，还能按时间维度反复订阅最近历史的任意数据 高性能的broker，单节点达2万TPS，实际支持上千长链接并发 承载海量的数据传输，日同步数据达10TB，并且包含淘宝主营收入等关键性数据 在各IDC内，部署了超过2000个客户端，覆盖全网日志传输 Scribe、flume、activemq、ZeroMQ？我们可以做得更强大 TBFS 基于Hdfs 0.20进行全面改造，设计目标：单个集群可达10000台服务器，支持10亿文件、100PB的数据的存储 领先于社区的全新设计，彻底解决namenode单点问题，并可实现集群在线升级 期待你来挑战：snapshot、异地数据复制、多级的cache、软硬链接支持 Hbase 基于Hbase0.90.3进行改造，目前有上百台的Hbase服务器，支淘宝7个online应用，online数据存储达100T 支持本地化数据计算、二级引索 期待你来挑战：无阻塞的compact、更多的事务支持、更短的请求响应时间、更强大的索引（Lucene for hbase） Mapreduce 基于Hadoop0.19改造，最大单个集群规模达2000台服务器，兼容hadoop0.20 绝大多数API 实际存储数据超过10PB，日运行mapreduce job达5万个 期待你来挑战：更高效任务调度、更优雅的计算资源管理、更灵活的分布计算模型 Hive 基于hive0.6改造，修改的patch达上百个，支持SQL中间结果复用等众多特性 支持淘宝几乎所有的商业数据分析任务，是各行业数据分析师和数据开发工程师必备的技能 期待你来挑战：Hive & Pig能混合编程？现在不能，你敢想就可以来做！ Taobao-pamirs-schedule taobao-pamirs- schedule是一个基于分布式环境的多线程任务处理框架。目的是让一种批量任务或者不断变化的任务，能够被动态的分配到多个主机的JVM，不同的线程组中并执行。所有的任务能够被不重复，不遗漏的快速处理。它将需要执行的任务抽象成一致的任务模型，进行统一的管理和监控。运用schedule，任务能够比较均匀的分发到多台机器上进行处理，并且可以动态的进行水平扩展。 QLExpress 一个轻量级的脚本引擎，作为一个嵌入式规则引擎在业务系统中使用。让业务规则定义简便而不失灵活。让业务人员就可以定义业务规则。 支持标准的JAVA语法，还可以支持自定义操作符号、操作符号重载、函数定义、宏定义、数据延迟加载等。 UIC Uic是个海量数据的高稳定高并发高响应高可靠高一致性的系统。海量数据：现在整个用户中心的注册用户数接近6亿，加上地址，支付宝绑定数据，接近20亿。现在通过分库分表存在了16个库1024张表里面。高稳定,高可靠：用户中心是淘宝最为核心的系统之一，一个完整的交易流程需要访问UIC高达几十次，所以UIC的稳定是整个淘宝的重中之重，我们为了UIC的稳定做了很多容灾的方案，包括多机房的备份，缓存的容灾，mysql的容灾，流量的控制等等，可以说UIC的核心就是各种容灾体系和在各种极端情况的下解决措施高并发,高响应：每天访问UIC的数据在200亿左右，我们使用了tair做为缓存，使用protobuf序列化， 尽可能的提高缓存的命中率，现在用户数据的命中率在99%。 Prom 海量数据实时计算框架。基于搜索技术对海量明细数据做实时计算。目前主要对交易数据做分析，应用于数据魔方中 特点： 多维索引组合查询 支持任意维度的计算 实时响应(秒级) 结果精确 Andes Andes是基于HBase的任意数据长时间维度高性能数据查询集群系统。解放数据魔方在查询时间段上的限制。 采用key-list存储方式，对于任何时间长度的查询均仅需一次数据库访问即可完成，规避查询时间对于查询性能的影响。 KeyKeys 用户搜索query数据分析系统。应用于淘词中，提供实时匹配用户输入query做关键query、关键热词的查询计算。 Myfox/Nodefox MyFOX是一个针对海量统计数据设计的高性能分布式MySQL集群中间层，承担着数据魔方90%以上的数据存储和查询需求。MyFOX能够提供： •… Read more »
代码调优法则–编程珠玑笔记
1、空间换时间法则 这个东西，稍微有点程序经验的人应该都接触过，比如在设计数据时候冗余了部分数据，避免关联表查询，减少开销，实际上也减少了查询时间，所谓空间换时间。还比如，我们将一个有点开销的计算结果存储起来，避免下次再次运算，减少时间消耗，再如，CPU的设计，设置了高速缓存，一级缓存，二级缓存，主存（通常所说的内存），其实一个硬盘和一个CPU也可以干活，只是干得不怎么样，因为硬盘和CPU之间速度实在是差别太大了，如是就有人想把可能要用到的数据预先加载到高速缓存或者主存中，慢慢形成了今天的个人计算机架构。 2、以时间换空间法则 这个其实也是天天在用的一个法则，只是一般技术人员看到“压缩”二字的时候，没联想到那么多，压缩就是最典型的拿时间换空间的例子，就是不断的重复前面已经存储过的存储地址，用来避免存取真实的数据。 3、循环法则 大部分稍微有点经验的人不会在同一个函数中循环两次同样的变量，但是仅限于同一个函数，假如在一个函数里调用了另外一个函数，那么就不一定了，很多人为了看似解耦的一个操作，在两个函数对同一个变量做了多次的循环。循环法则有几个比较经典细则： 第一、将代码移除循环，这是最容易想到的，当然，可以移除的条件是，每次循环都执行同样的某次操作。 第二、合并测试条件，高效的内循环应该包含尽量少的测试条件，最好只有一个，因此，程序员尽量用一些退出条件来模拟循环的其他退出条件。 第三、哨兵法则，在数据结构边界上放一个哨兵以减少测试是否已经搜索结束的开销。 第四、展开循环，展开循环可以减少修改循环下标的开销，对于避免管道延迟，减少分支以及增加指令级的并行性也有很大帮助。 第五、删除赋值，赋值的开销实际上在整个程序的执行过程中占的开销可以忽略不计，但假如你要在一个循环十万次的循环中赋值，那么开销就不能不计了，尽可能的在循环中减少赋值吧。 第六，消除无条件分支，快速的循环中不应该包含无条件分支，通过旋转循环，在底部加上一个条件分支，能够消除循环结束处的无条件分支。 第七、循环合并，如果你不小心做了傻事，那么合并两个对同一个变量循环操作吧 4、逻辑法则 利用等价的代数表达式。如果逻辑表达式的求值开销太大就将其替换为开销较小的等价代数表达式。 短路单调函数。如果我们想测试几个变量的单调非递减函数是否超过了某个特定的阈值，那么一旦达到这个阈值就不在需要计算任何变量了。 对测试机条件重新排序。在组织逻辑测试的时候，应该是降低开销的，经常成功的测试放在高开销的，很少成功的测试前面。 5、过程法则 打破函数层次。对于（非递归地）调用自身的函数，通常可以通过将其改写为内联版本并固定传入的变量来缩短其运行时间。 并行性。在底层硬件条件下，我们构建的程序应该尽可能多的挖掘并行性。 6、表达式法则 编译时初始化。在程序执行前，应该尽可能多的变量初始化。 利用等价的代数表达式。如果表达式的求值开销过大，就将其替换为开销更小的等价的代数表达式，比如换一种算法 消除公共子表达式。如果两次对同一个表达式求值，其所有变量都没有任何改动，那么我们可以用下面方法避免二次求值：存储第一次的计算结果并用其取代第二次求值。
类设计
最近几乎天天加班，周末依然加班，好久没有更新博客了，非常累。不过此累非彼类。 在现有的很多面向过程开发的代码中，对我这个涉世不深的玩家来说，简直就是灾难，或许很多代码连面向过程都算不上，连函数都没有包装。一个函数可能会超过500行代码，语义不名，名称更不名。我曾经试图改造这些代码，并非技术上不可行，而是实现需要太多的时间，一个不可能完成的任务。 让一个缺乏面向对象的团队掌握面向对象很困难的，也许是我智商低，当年我花了两个月才能意会什么是对象，什么是面向对象编程，到现在也不会言传。 如果不能转向到面向对象，那么我们先转成类吧，或许技术上更能解决一点。类的最基本功能就是封装，如果我们撇去面向对象的东西，那么类就是把具有相似性的东西做一个集合，外部在使用这些功能的时候不需要知道具体实现，只要给类中的方法确需要的参数值，如果非要理解成一堆具有相似属性函数的集合，那也是可以的，毕竟这个比一个文件中的几千行代码，连个function都没有的代码好得多。 如果我们想得到更好的类，需要遵循一些基本的原则， 其中之一就是类应该短小，短小并不是说不完整，这和很多人学C的时候，老师告诉我们，函数要尽可能短小一样，到底多短小的类算是合适呢？我觉得根本无法用代码行数来描述，这取决于这个类所完成的功能，比如你要封装一个操作文章的类，那么至少需要，增删改查四个函数，也许还有基于这四个函数的别名和封装，以及必要的公共属性。 第二个重要原则就是单一权责（SRP），这个原则要做到非常 不容易，因为比第一条更难衡量，一般认为，衡量单一权责的标准是：类或者模块应该有且只有一条加以修改的理由。SRP实际上能给出控制类长度的指导方针。简单的理解就是一个类只有一个功能，假如你修改博客标题或者设置的时候，都要改动文章类，显然违背了单一权责的原则。 第三个原则–内聚。类应该只有少量实体变量。类中的每个方法都应该操作一个或者多个这种变量。通常而言，方法操作的变量越多，就越内聚到类上，如果一个类中的米一个变量都被每个方法所使用，则该类具有最大的内聚性。通常，创建一个这样极大化的内聚类是非常不容易的，也是不可取的，因为类的内聚性过高也就意味着类中的方法和变量相互依赖，互相结合成一个逻辑的整体，当修改类中的变量或者方法时，可能影响或者需要修改其他的方法或者属性。一般认为，类的内聚应该保持在较高的位置，但不是最高的位置，这样有利于降低维护成本。 前面提到在我目前的项目中，我碰到很多超过500行代码的函数，假如把数字降低到300，那么符合标准的函数将会增加十倍以上，在一个面向对象的团队中，一个单纯函数或者方法超过100行几乎都是不可接受的，因为这意味着这个函数可能包含过多的权责。其实我们如果真的遵循类的内聚和单一权责的原则，就会导致很多短小的类的产生。 一般程序员在拆解过大的函数的时候实际上就是将原来的代码复制出来，放到新建的函数中去，然后把需要的参数传递过去，实际上导致超大函数的产生的动机常常是因为有很多变量在这个函数的中被使用到，看似这个函数似乎是一个整体，因为拆分会导致新建的函数参数很多。为啥他们不想用一下类呢，假如拆解函数导致需要传递很多的参数，那么这个函数其实就是一个类，需要传递的函数需要提升为实体变量，这样就可以将函数拆成很小的小块，这样看起来似乎丧失了内聚性，因为堆积了越来越多的只为允许少量函数共享而存在的实体变量。如果这些函数想要公司向某些变量，为什么不让它拥有自己的类呢？当类丧失了内聚性，就应该拆了它。所以，将大的函数拆分为小函数，旺旺也是将类拆分为多个小类的时机，程序会更加有组织，更为透明的结构。 实际上很多时候，当你完成所有的功能的时候，产品经理会跑过来跟你说，我们不能把这个功能改成这样，这样用户体验更好，很可能你需要改动很多的代码很逻辑，甚至数据结构，所以如果我们能在设计的类的时候，注意一下可能的需求改动，我们可以借助接口或者抽象类来隔离修改细节对原来代码产生的破坏性更改。
软件构建中的理想设计特征
1、最小复杂度。设计的手艺好目标就是要复杂度最小，避免作出“聪明的”设计，因为“聪明的”设计常常难以理解 2、易于维护。 易于维护意味着在设计时为做维护的程序员着想。 3、松散耦合。松散耦合意味着在设计时让程序各个组织称部分之间的管理关系最小。通过应用类接口中合理还凑向、封装及信息隐藏等原则设计出相互关联尽可能小的类。减少关联也就是减少了集成、测试和维护时的工作量。 3、可扩展性。可扩展性是只可以增强系统功能而无须改变底层结构，可以改变某一个方面功能而不影响其他部分。 4、可重用性。可重用意味着代码可以在其他系统的组成部分中重复使用，降低整体的成本和提高生产效率。 5、高扇入。高扇入就是说让大量的类是有那个某个给定的类。这就是意味着设计出的系统很好的利用较低层次上的工具类。 6、低扇出。低扇出就是让一个类里少量或者适中的使用其他的类。高扇出说明了一个类使用了大量其他的类，因此可能变得过于复杂。 7、可移植性。可移植性是说应该设计的系统很方便的移植到其他的环境中。 8、精简性。精简就意味着系统没有多余的部分。这样有利于后面的单元测试。 9、层次性。层次性就意味着尽量保持系统各个层次保持可分解，使你能在任何层面观察系统。 10、标准技术。一个系统所依赖的外来的，古怪的东西越多，别人在第一次想要理解它的时候就越头痛。尽量使用标准化，常用的方法，让整个系统给人一种熟悉的感觉。
会话状态模式
个人觉得会话状态模式其实算不得一种模式，因为无非就两种，而且必须是其中的一种，一种存放在客户端，一种存放在服务端。两者都有风险和优点。 通常将会话保存在客户端是为了获得服务端的高度无状态特性，即服务端可以做到完全的无状态。Java中通常使用传输对象来进行数据传输，因为传输对象可以在网上进行序列化，即使是很复杂的数据也可以进行传输。当然序列化是有风险和代价的，不是所有的序列化数据都能够被反序列化回来，虽然出现反序列化回来的出错的概率很小。 如果使用HTML的话，选择相对多一点，URL参数，隐藏表单域和Cookie，URL对于较小数据量还是比较容易使用的，现代浏览放开了对URL长度的限制，但我们不得不考虑一些古董用户的需求，毕竟IE6及以下版本的浏览器还主导着WEB世界，而且URL过长，也不符合REST原则，更不美观。 隐藏表单域适合于POST方式的请求，POST方式可以避免因浏览器限制URL长度而导致的被截断的问题。隐藏表单域在我曾经的代码中经常使用，主要是为了跟踪和referer的referer，也就是跳转到一个页面之前的原来页面。 Cookie方式是最优争议的一种方式，PHPWind采用了这一种方法，从开发者口中得知，是为了减少服务器的负载，因为服务器不用维护session状态。通过把数据序列化或者加密后以文本方式放到Cookie中，我没有测试过，PHPWind这样做是不是真的能降低服务器的负载，根据我以前的测试，session维护成本对于服务器的影响是微乎其微的，还不如优化一条SQL来得更痛快，更有效，而且放在Cookie中会导致用户请求的流量变大，在很多上下带宽不对称的机房中，这是个严重的问题，比如blogbus之前存放在上海的**机房就是这样。而且为了获得Cookie中的数据还需要进行一些列运算，未必比维护session的成本小，而且会导致严重的安全问题。只要算法是可逆的，就一定能被人破解，何况我等庸人搞的算法。 服务器会话状态最简单的一种就是把会话数据放到应用服务器的内存中，可以将会话数据以会话标识号作为键标识放到内存映射表中，现在很多工具可以做到，比如memcache等key-value 的内存存储工具。 另一种是持久化，持久化也可以分为两种，一种以二进制序列化形式存放，但这样做的缺点是不容易阅读，更新起来成本有点高，如果每个会话都一个文件的话，在高并发的时候还得解决文件系统的巨量小文件查找效率问题。还有一种就是持久化到数据库，这个存放会话的模式，可能会因为维护会话状态而带来巨大的数据库开销问题，而且为了及时清除过期的会话，往往配合触发器来进行。 总结起来每种会话管理都有天生的缺陷，如果能多种结合能够提升一些效率，比如内存缓存配合持久化数据库，就是眼下很多高负载网站正在使用的模式，也许还有其他的更多的模式和方法有待探寻~~
开发环境的三大规则
1）使用源码控制 2） 使用单步创建 3）跟踪程序缺陷 每个人都有自己偏好的事情和做事方法，无论在开发那种大规模应用程序时，他们都会严格遵循这些作诗方法。具体的做事原则取决于所选择的特定的开发方法理论，但还是有一些普遍规则实际上是放之四海而皆准。对于大型Web应用程序的开发领域而言，以上三条在成功开发团队中屡见不鲜。可能是规则这个次太夸张了，称之为指导方针可能更适合一些。当然，不去应用这三条简单的规则也是可行的，仍然可以产出可用的产品。但这三条规则能够帮助你避开小规模应用程序迁移到大型程序时常常遇到的问题，并且帮助你更快的完成这个迁移过程。
数据完整性策略
数据完整性是工程应用程序成功的关键。接收、处理、存储数据，其实就是应用程序的全部内容。无论你怎样变换…
Recent Comments