• 分布式系统笔记(二) 数据库的数据模型和 Query Language

    数据模型是指软件对于所处理数据的抽象, 它对软件的设计有很大影响:数据如何组织,某个操作如何实现,有些操作很快有些操作很慢,有些操作很自然有些操作很奇怪,这些问题都与数据模型有很大关系。(想想上一篇 Twitter 的例子) 在真实的系统中,往往存在多种数据模型。对数据库而言,最常见的数据模型有 Relational Model 和 Document Model。除此之外还有一些特殊的模型。 Relational Model 在 Relational Model 中,数据被组织成若干个 Relation(MySQL 中的 table),每个 Relation 包含了若干个无序的 tuple(MySQL 中的 row)。在很多关系型数据库中,每个 Relation 内部其实是有序的。如 Inno DB 中数据是以主键的大小顺序存储的,在某些特殊情况下,还会为某个 table 生成一个自增整数作为主键。 关系模型的优点主要有简单,高效,灵活,历史上,关系模型曾经一统江山长达数十年, 即使在今天,关系模型仍然占据极为重要的地位,以至于它是很多人心中“默认”的数据模型。 它的缺点之一是,当数据间的关系高度嵌套(树形数据)时,关系模型就显得不那么自然。这造成了一种叫 Object-Relation Mismatch 的问题, 某些情况下我们不得不做多次 join 才能得到某个对象中的一条数据。 某些关系型数据库正在尝试引入数组类型,嵌套类型(JSON 类型)来减轻这些问题,但在树状/网状数据的处理上,不得不说关系模型有其天生的弱势。 提到数据模型的时候,很多文章(包括 Designing Data Intensive Applications)都会从追忆 IMS 时代开始,介绍关系模型的辉煌历史,介绍传说中的”Great Debate”,有兴趣的同学可以找相关资料了解一下。...

  • 分布式系统笔记(一)可靠性,可拓展性和可维护性

    最近看了一本好书:Designing Data Intensive Applications。这本书条理清晰地分析了分布式系统的设计, 各种 trade off,各种 corner case,很适合我这种初学者。 分布式系统笔记系列将会根据这本书的框架,对分布式系统的相关知识进行归纳。 要对分布式系统的不同设计进行分析,首先就要知道如何衡量两种设计哪个更好。一般从可靠性,可拓展性和可维护性三个方面来进行分析。 可靠性 可靠性指的是系统能在多大程度上容错。分布式系统考虑到的错误主要来自于硬件故障,软件错误和人为的操作失误,而恶意的网络攻击一般不在讨论范围内。 硬件故障一定程度上可以认为是随机的,不同设备没有相关性。由于大型分布式系统的节点数量往往成千上万,有机器出现硬件故障是非常常见的。IBM 曾经发表过一个利用机器学习预测硬盘故障的研究,用这种思路可以帮助运维团队及时发现并更换可能故障的设备。 软件错误就是平时说的 bug, 这种错误是系统性的,且大部分 bug 是可重现的,因此这种错误的危害可能遍及整个系统,一旦发作危害很大。预防软件错误主要靠现代软件设计的方法,比如代码审查,完整的测试,解耦等等。有时我们可以选择采用一些随机算法来提高性能,这也会引入一定的错误,需要顶层有对应的容错机制来解决。 人为的操作失误主要是开发/运维成员误操作导致的事故。有名的例子有 gitlab 删库事件。要防止这类事故,应该尽量避免运维在命令行界面操作,并进行合理的权限管理。为运维提供图形界面进行规范的管理,监控不仅可以降低失误,还能提高系统的可维护性。 提高可靠性的方法很多,除了以上的预防措施之外,最基础的是做好故障检测和数据备份,使得错误发生时能做到及时诊断,及时恢复。之后会提到数据库的 WAL 和数据备份,调度系统的心跳检测和 fail over,都体现了这种思想。 可拓展性 可拓展性是指系统应对负载增长的能力。根据应用的不同,负载有很多衡量方式,比如网游的负载可能是指在线人数的峰值,微博的负载可能是指每天的新微博数,小说网站的负载可能是指小说的总数。在负载增长后保持性能的代价,就反映了这个系统的可拓展性。 系统的性能主要通过客户端观察到的响应时间来衡量。这里有个叫做 percentile 的概念。一般我们关心的是最慢的 1%的响应时间,对应的 percentile 就是 p99。Amazon 使用的衡量标准是 p99.9,也就是最慢的 0.1%的响应时间。造成这些响应时间较长的原因有很多,可能是用户做了一个复杂的操作,网络故障,系统繁忙,结点恢复或者其他随机的原因。高 percentile 的衡量使我们的优化目标主要放在最慢的那一部分操作上,比较适合购物网站,即时通信等用户对响应时间要求较高的情况。在 OLAP 和一些批处理系统中,则会将 percentile 设的低一点,甚至直接用平均数/中位数作为衡量标准。 应对负载增长主要有两类方式,一个是纵向拓展,就是换更好的机器,一个是横向拓展,就是加更多的结点。两类方式都没法无限制的使用,硬件条件越好价格增长越快,结点数越多系统越复杂,实践中经常两类方式混合使用。 下面举两个例子说明不同业务对分布式系统架构性能优化的影响。 Twitter 的例子...

  • leancloud实习总结

    在 LeanCloud 实习两个月,写点东西记录一下这段时间的感受。 LeanCloud目前还是一家创业公司,提供的是BaaS服务,主要是在各个厂家提供的云产品的基础上进行封装、拓展,将分布式系统的细节隐藏起来, 给用户看到的是一个功能强大的“单机”数据库,从而极大地减少后端/运维的工作量甚至取而代之。 我实习期间基本上只参与了收费系统的开发,大致就是做一些统计发一些告警邮件之类的工作。 有意思的是开发用的语言是Clojure,工业环境用函数式语言最大的好处就是易维护, 至于运行效率,反正我们只是数据的搬运工,性能瓶颈不在这里:)我入职第一周就能开始写代码, 可见系统可维护性跟某些用C++写的祖传系统真的不是一个等级。 虽然做的事情听起来很简单(实际上也很简单),但我还是犯了很多错误。变量名, 接口设计的不标准在前期是家常便饭了。另外还有之前写玩具代码不怎么会考虑的问题, 比如打log,处理超时,调用失败等。最后几天我还把精度高的数据存到低精度的字段了, 写测试的时候居然没考虑到这种情况,失败。BTW,写测试测自己写的程序好像怪怪的? 都要互相review代码了感觉代码测试分开写比较好一些? 在这边最大的收获还是开拓了自己的视野。看到某些重要issue下一长串的讨论, 明显感觉同事关注的重点跟我完全不一样。我原来的视角有点像开发浅层应用的程序员, 不过算法好一点罢了。公司则是要为用户提供Baas服务,他们的视角更像是一个设计者, 一个架构师。当时正在开发一个叫LiveQuery的功能,是为了解决多点数据同步问题的。 本来一般的公司只要根据自己的业务特点,选择适当的解决方式即可,但是作为云服务的提供者, 必须要把这个功能抽象出来,在不同的实现方式之间作取舍,甚至通过定价策略引导用户改变使用方式。 除此之外,我还接触了一些软件工程的方法论。这些东西之前只在一些公众号里看到过,还看得云里雾里的。 这两个月耳濡目染,真的受益匪浅,可惜我现在能力有限,还没法把这些东西系统地写出来。 LeanCloud好处还没说全,团队内部的氛围非常好,福利也很丰富,不过这些对我这个实习生来说就显得不那么重要了。 现在来看之前在学校闭门造车,走过的弯路还是不少。能早点接触工业界的生产方式, 对我来说是最大的收获。BTW,能跟昆山这么多大神一起工作也是一段很有趣的经历。 感谢LeanCloud。

  • 初探信息论

    这篇文章是我在 Lean Cloud的内部分享。信息论是个很有意思的东西,我选择这个主题的原因 主要是为了防止某些人看到第一张 ppt 就一眼望到底,现在看来这个目的还是达到了。 其实信息论的应用主要是在通信领域,在信息学中一般就只能给个下界,还很 ideal。 去 Google 上搜 Information Theory in Computer Science 的话确实能找到那么几个学校开了这门课, 但是课的内容还是比较偏通信,压缩这几个领域的。反正这篇文章大家就当理性愉悦看着玩吧, 这大概是最水的理性愉悦了。 信息熵 信息论的核心是一个信息熵的概念。熵在物理里面反映的是一个系统的混乱程度, 在信息论里边有时候说熵反映了一个信息的度量,即事件 X 的信息熵反映的是当 X 确定之后能得到的信息量的多少,与 X 的真实值没有关系。 听起来还是很玄乎,总之对于一个随机事件 X,我们希望有这样一个量 H(X) 来反映他的某些属性: H(X) ≥0 X 的概率密度越分散,H(X) 越大 对于两个独立随机事件 X,Y,有 H(X,Y) = H(X) + H(Y) H(X Y) + H(Y) = H(X,Y)...

  • 如何愉快地写一个parser

    预告 有没有想过这样写一个 parser: 不要写 scanner 不要写 AST 生成 不要优先级,左结合右结合 不用担心左递归/右递归 最最重要的是无需设计复杂的语法 Q & A 啥时候填坑 在可预知的未来是没空了(要无限期延迟了)。 下面通过 QA 简略介绍一下这东西怎么弄。 到底怎么写 用 clojure 的一个库 instaparse。 简单的教程 在这里。 显然简单单词的 scanner 已经嵌在语法里了。 clojure 没有类,区分 token 全靠 vector 第一个元素,自然不要写 AST。 (用 pprint 把结果打出来就可以看得很清楚了) clojure 的入门教程的话,个人推荐 braveclojure。 这东西当 scanner 只能处理正则,我要搞 comment 怎么办 parse 之前先搞个 comment-parser...

  • 数据库中的数据结构

    写在前面 先推荐一下 Christophe 的 How does a relational database work, 把 DBMS 的每个部分都理了一遍,可以让你对 DBMS 有一个大体的印象,不过这篇文章有些地方说法欠妥,看的时候最好带上脑子。 B 树/B+ 树 好,现在假设你已经瞄了一眼上面那个链接(其实不瞄也没关系),并且拥有了基本的操作系统和数据结构的知识。 我们先思考一个问题:现在你手里有一堆无序的 item,每个 item 有 key 和 value 两个属性,你要支持插入、删除、 按 key 查询、查询 key 连续的一段区间,你会选择什么数据结构? 第一想法肯定是各种平衡树、线段树。 然而,我所知的大多数硬盘数据库采用的是 B 树或者 B+ 树。B 树这种数据结构由来已久,从半个世纪前的 IMS 时代就开始用来存储数据。 B+ 树是 B 树的进化版,两者结构大同小异,B+ 树在最底层把所有结点链了起来以加快区间查询的速度。 现代 DBMS 很多采用的是 B+...

  • 阿里巴巴实习总结

    去阿里实习了一个月,回来之后想总结一下这段时间的经历。可惜实习时间太短,只来得及匆匆一瞥,学到的东西可能不多。 初次体验程序员的生活,感想还是蛮多的。 阿里给我总的印象,不愧是巨头公司。阿里内部到处造轮子,技术的覆盖面看起来非常广,文档看起来也蛮丰富。之所以是看起来, 是因为实习生没权限看其他组的文档,很多项目我只知道有一个牛逼的名字和简介。我说学到的东西不多, 很大一部分原因是我只能通过跟师兄问答的方式了解一个项目。如果你不想进阿里的话,我个人是不太推荐来阿里实习的。 当然你要是只想刷个成就当我没说。 我加入的组做的是搜索引擎,平常工作很大一部分是运维,但是实习生没权限。不过这倒是帮我避开了几次加班就是了。 其实服务器没出事的话是没有加班的,再加上我们部门的结对编程制度,总的来说工作的强度还是比较低,没有外界传说的那么恐怖。 组里的同学对新人也很友好,基本上是有问必答,加上师兄经常跟我结对,要是开了权限就更好了。 因为我实习的时间比较短,所以主管给我分配了一个探索性的任务。简单来说就是我们这引擎要给用户提供一个 DSL 进行高级定制,既要隐藏引擎内部的实现,又要保证效率,看这玩意要怎么搞。我加入的时候这个项目组刚成立,三个人搞调研,走的时候 demo 刚好做完,大部分技术问题心里都有了底,也算是全始全终。当然,要是开了权限就更完美了。 最开始主要是测了 Luajit 的效率,纯 Luajit 的话数据还是蛮好看的,但是一跟 c++ 交互就惨不忍睹了。主要问题是 Luajit 内部数据结构跟 c++ 的是不一样的,转换的开销很难避免,再加上我们还有其他需求,到最后只能把 Luajit 魔改一番才可能满足用户的需求。至于其他解释型语言则更加不堪,因此我们决定试试自己实现一个编译器。这个测试过程大概持续了一周的时间, 最大的感想是师兄看文档的速度真的快,我还在一行一行的读,他已经直接跳到重点了。打不赢打不赢。 走编译的话大方向是用 LLVM 做个魔改版 JAVA 编译器。反正先做个 demo 踩踩坑,JAVA 语法特性被我们砍得七零八落。 实现起来感觉 JAVA 跟 C++ 非常像,就是多了个 GC。可能真正的生产代码还有一些利用 JVM 特性的 trick,不过我们都不用考虑。 我做的部分是 AST 生成之后,构建 Symbol Table,进行...

  • 关于阿里NASA计划的感想

    先提醒一下,这篇文章可能大部分都在胡言乱语。 题目里说的,是阿里巴巴最近提出来的 NASA,不知道的可以看这一篇报导。 大概意思就是阿里巴巴要在机器学习、芯片、物联网、操作系统、生物识别等方面砸钱搞科研了。 我最先想到的是昨天看到的王垠的一些文章,他认为 linux 的很多设计存在缺陷, 甚至想亲自出马写一个操作系统。其他方面姑且不论,在分布式计算这一方面, linux 系统是有很大的进步空间的。 linux 设计之初,是没有人想到它会在今后被用来跑高并发的分布式系统的。 当时的主要使用场合是 PC,linux 为了安全性能使用了一些效率较低的设计,比如进程不能共享内存。这个设计直接导致了上下文切换的巨大开销。 在当时看来,上下文切换的开销是可以被接受的。但是,在执行并行计算或者分布式计算任务的时候,上下文切换就成为了性能杀手。 进程/线程切换频繁,加上单独的进程/线程任务相对简单化,后果不用我说你也知到。或许这也是一种千年虫现象吧。 在分布式系统中,我们有的是办法把各种问题转移到 master 或者 client,让每台 server 全心全意当 CPU。 我们可以做到进程内存共享,消灭上下文切换,消灭进程与线程的区别。(说句题外话,消灭线程绝对是一件大快人心的事) 王垠还吐槽了一点,linux 进程交换信息的主要方式是字符串,进程间没法相互传结构性数据。文件读写也是, 我们写一个工具经常还要先写个 parser。这个东西还是一个历史遗留问题,到现在都没有一个结构性数据的统一规范给我们用。 这东西对效率有多大影响也要视具体应用而定,大部分情况影响不大。但是还有一个心情问题:如果分布式系统开发时能随意共享内存, 传递数据结构,开发者的心情肯定会很爽,效率肯定会很高。 我还要补一个方面:通过操作系统层面的函数式数据结构和垃圾回收,消灭绝大部分锁。这不是什么新鲜的事情, 只不过把原来函数式语言编译器做的事情交给操作系统去做了。与其把锁隐藏,不如把锁消灭。当然, 肯定要保留一些变量类型,这方面可以向 clojure 学习。 操作系统方面好像扯了蛮多了。其实这方面的缺陷肯定有不少人已经看到了,但是搞个新的分布式操作系统很可能是个伪需求: 多搞几个集群问题就解决的差不多了。所以分布式 OS 没见到谁搞,手机 OS 倒是搞了一个又一个。 回到那条新闻,马云的 NASA 能搞成什么样子姑且不论,这个计划起码反映了阿里在技术领域的探索欲,这不是百度之流的公司可以比的。 联系到阿里在电商领域的霸主地位,或许阿里能在树十年后成为互联网行业的超级公司。 其他几个领域我都是菜鸟,就不做评论了。