Twitter-Storm的部署

九月 28th, 2011 by klose | No Comments | Filed in 海量数据存储与处理

Strom 是Twitter最新的开源系统,下面就test它: 1)安装 Storn使用大量的Clojure动态编程语言,Clojure会将clj或者javascript编译成JVM下的bytecode。 Storm使用了Clojure Building Clojure Projects with Leiningen Everybody who once used Java, struggled with Java’s classpath at some point during their career. You have to put all the right paths in there, the right .jar files and so on, both when compiling and running your Java project. To make this somewhat simpler you typically end up doing it either in an IDE, or using a tool like Ant or Maven. These are pretty heavy weight tools, and the latter too involve writing XML, which hardly anybody does for fun anymore. Leiningen is a simple build tool fo

ZeroMQ 消息内核

九月 20th, 2011 by klose | No Comments | Filed in 海量数据存储与处理

总在寻找一种高效的消息传递方式中不断徘徊,最近发现了它,它的性能让人眼前一亮。ZeroMQ 熟悉分布式消息总线的朋友,可以不假思索地脱口而出Kafka,ActiveMQ,***MQ等,但是,ZeroMQ的设计另辟了新天地。 它的特性: 1)ZeroMQ位于(TCP/IP协议层次结构)会话层和应用层之间。ZeroMQ 并不是一个对 socket 的封装,不能用它去实现已有的网络协议。 2)无消息服务器缓存数据。它不同于传统消息中间件通过服务器缓存转发消息的方式,而是优化点对点的消息传输。ZeroMQ能缓存消息,但是是在发送端缓存。ZeroMQ里有水位设置的相关接口来控制缓存量。当然,ZeroMQ也支持传统的消息队列(通过zmq_device来实现)。 3)强调消息收发模式。 在点对点的消息传输上ZeroMQ将通信的模式做了归纳,比如常见的订阅模式(一个消息发多个客户),分发模式(N个消息平均

自己动手构建Key-Value Store系统

九月 19th, 2011 by klose | No Comments | Filed in 海量数据存储与处理

之前做过key-value store相关的工作,一直没有时间进行详细的总结,在面试的时候被问到该项目的时候,因为过了很长时间,回答起来总是捉襟见肘,下面就把当初的设计整理了下来。 在启动设计自己的Key-Value Store的时候,遇到了如下的一些问题: 1)key-value是一对一,还是一对多,假设为1:n,这里的n是变化的还是固定的呢? 2) key-value的长度是固定的还是变化的? 3)key-value本身是分布式的还是单节点的? 如果系统做得越灵活,系统的复杂性也就越高,在复杂性的设计中需要各种策略。这也给我很大的Motivation去阅读包括MemCached、Redis在内的in-momory key-value store,以及基于列存储的HBase。接下来blog中将新开一个专题来讨论分布式存储的设计策略。 ok,由于这是我们设计的第一个Key-Value Store系统,我们尽量简化设计的难度,做如下的

链表问题总结

九月 16th, 2011 by klose | No Comments | Filed in 求职技术

链表是否有环的解决方案: 链表在面试中出现的频率很高,有的比较正常,考链表的常规操作,主要看基本功是否扎实,有些就比较难,难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。 首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法不能破坏链表。 这里我们可以想到有三种解决的方法。 第一种方法,将所有的遍历过的节点用某个结构存储起来,然后每遍历一个节点,都在这个结构中查找是否遍历过,如果找到有重复,则说明该链表存在循环;如果直到遍历结束,则说明链表不存在循环。 这个结构我们可以使用hash来做,hash中存储的值为节点的内存地址,这样查找的操作所需时间为O(1),遍历操作需要O(

面试智力题(不断更新,鼠标选中即可查看答案)

九月 9th, 2011 by klose | No Comments | Filed in 求职技术

这部分的内容取自  http://blog.sina.com.cn/s/blog_604d011e0100ws85.html 1、考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币,每次必需且只能放置一枚硬币,要求硬币完全置 于桌面内(不能有一部分悬在桌子外面),并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币,谁就输了。游戏的先行者还是后行者有必胜策略?这种策略 是什么? 答案:先行者在桌子中心放置一枚硬币,以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样,只要后行者能放,先行者一定也有地方放。先行者必胜。   2、一个矩形蛋糕,蛋糕内部有一块矩形的空洞。只用一刀,如何将蛋糕切成大小相等的两块? 答案:注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线,这条线

构建Hadoop第三者的源码级实施方案

九月 7th, 2011 by klose | No Comments | Filed in mapreduce

Hadoop作为生产系统的一个重要组件,在海量数据处理领域发挥了重要作用。在实践的过程中,发现了如下的问题: 1)定时收集Hadoop的状态信息,及时向集群资源管理系统反馈。目前,Hadoop-0.21.0已经有了Cluster类,可以提供一些作业执行信息参数,另外也有通过JSP的网页获取的方式。具体参见http://blog.sina.com.cn/s/blog_4a1f59bf0100nv03.html 。 这种方式有一个问题是,接口固定,不易在功能上扩展。 2)JobTracker分布化。当前JobTracker单节点故障问题,成为了制约Hadoop执行作业规模、和节点扩展性的一个重要瓶颈。因此,如果能将网络拓扑结构、集群资源负载等因素考虑进去,提供多层的JobTracker的功能,将有助于提高系统的可扩展性,增强高可用性。 3)TaskTracker动态伸缩。Berkeley大学提出的Mesos,从系统资源复用的角度出发,提高了集群

智力题其实是数学题(不断更新,欢迎网友分享)

九月 2nd, 2011 by klose | No Comments | Filed in 求职技术

1、卡塔兰数 卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 卡塔兰数的一般项公式为 前几项为 (OEIS中的数列A000108): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … 性质 Cn的另一个表达形式为 所以,Cn是一个自然数;这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。) 卡塔兰数满足以下递推关系 它也满足 这提供了一个更快速的方法来计算卡塔兰数。 卡塔兰数的渐近增长为 它的含义是左式除以右式的商趋向于1当

JSON vs. XML

九月 1st, 2011 by klose | No Comments | Filed in 互联网应用

最近参加一些公司的笔试,有些题目围绕着XML和JSON来进行的。现在对于这两种数据组织技术进行介绍和对比。 JSON介绍: JSON(JavaScript Object Notation),是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。 它基于JavaScript Programming Language, Standard ECMA-262 3rd Edition – December 1999的一个子集。 JSON采用完全独立于语言的文本格式。JSON 是 JavaScript 原生格式,这意味着在 JavaScript 中处理 JSON 数据不需要任何特殊的 API 或工具包。 JSON建构于两种结构: “名称/值”对的集合(A collection of name/value pairs)。 值的有序列表(An ordered list of values)。在大部分语言中,它被理解为数组(array)。 JSON例子: { “programmers”: [   { "firstName": "Brett"