A Note on Distributed Computinghttps://www.evernote.com/l/AATOjsjG24pA2arIYnWYGKrSSJ0bfMn40DsA Java Fork/join Calamityhttps://www.evernote.com/l/AAQtr3xjkGBMp5n7NWKGwE5n8J6C0ljdVTgOn Desgining and Deploying Internet-Scale Serviceshttps://www.evernote.com/l/AASLhmNDXjxMUJTQGNUyiSo0CYr7Cexgib0SQLAlchemy Sessionhttps://www.evernote.com/l/AASJSQGd18RG95kX5oJX96ZSqv-6UxiLaCoEtcd Clustering Guidehttps://www.evernote.com/l/AARwnSidwgRPcZ8myCJ5wCNO0M4LHoas0IIArk: A real wold consensus implementationhttps://www.evernote.com/l/AARdVmQe4OpK94Dyk7CMSz6kHzbykzQ6ibk ...继续阅读 (7)

TIME_WAIT, tcp_tw_recycle 和 tcp_tw_reusehttps://www.evernote.com/shard/s4/nl/337881/b9b9211d-cab5-419a-a159-845166a89a65/牛顿冷却公式https://www.evernote.com/shard/s4/nl/337881/272d4748-fe17-44f3-9df6-7953cca80956/威尔逊置信区间https://www.evernote.com/shard/s4/nl/337881/4a5cd92e-5ba2-4f4e-a6fb-691eb9a9d41f/贝叶斯平均https://www.evernote.com/shard/s4/nl/337881/7e296354-8561-4c26-b8e7-7d881087512f/Consensus, bridging theory and practicehttps://www.evernote.com/shard/s4/nl/337881/7a06e249-98ab-4ff3-9c6c-92cedae13266/https://www.evernote.com/shard/s4/nl/337881/42aa043b-11aa-4e0e-b33c-3a21ebf42203/https://www.evern ...继续阅读 (33)

一直很知趣地没敢看过 Paxos。首先 Paxos 本身就难理解；其次，Paxos 作为一个学术上的算法，并没有为工程实现提供指导，最终 Chubby 和 Zookeeper 都并未实现真正的 Paxos，其正确性更多要依赖线上验证，而不能得到形式化证明的可靠性。近两年新出现的 Raft 协议，针对 Paxos 的两个问题做了很大的改善：其一，协议的设计从始至终面向可理解性，使学生容易建立对算法正确性的直观认识；其二，面向工程领域的实际需求，容易在满足正确性的前提下扩展协议，比如 Membership 管理、Snapshot 等。怎样做到可理解性？Raft 的方法是将问题分解为 Leader 选举、日志同步、安全性约束 三个部分，使单独的部分容易理解；此外控制状态的数量，减少不确定性，乃至善用不确定性减少复杂性。值得一提的是，Raft 论文的叙述结构也十分清晰，非常值得一看。Leader 选举与 Paxos 的 P2P 方案不同，Raft 协议采用强 Leadership 方案，其集群中的每个节点处于三个状态之一：Leader：当前整个集群的 Leader，接受客户端的请求，通过心跳发送 AppendEntries 消息同步日志，并维持自己的 Leader 地位；Follower：被动接受来自 Leader 的日志同步；Candidate：尝试成为 Leader 的节点，它们会发送 ...继续阅读 (48)

试试把 Evernote 里长草的一些笔记搬到博客来。Redis latency problems troubleshooting:https://www.evernote.com/l/AAQRPJ7ucjVCSI1GhTh48p3lz2RiC4VbLb8Redis administration:https://www.evernote.com/l/AATks5YMaH5DKYi8jrKuQwpe_jtVBMloTKkTransparent Huge Page:https://www.evernote.com/l/AARMPokLwiZCrIEHOaoPGa3qGFSEGTvL05gEffective TLB shootdowns:https://www.evernote.com/l/AAT-2sq4x4VJVqieCYHk-aG1wDakmuxFsXcData Dependences and Hazards:https://www.evernote.com/l/AAR0LyWpNyZM64TlPbn8cKyPw4kxpN_35TEAcquire/Release Semantics:https://www.evernote.com/l/AARcIY1uhXNPrpFO-1aSc55lRVjzDkmfZ84Building Software Systems at Google and ...继续阅读 (27)

很久之前就想记一下关于数据库隔离级别的东西了，前几周在知乎上回答了一个相关的问题，正好整理一下。完美的数据正确性有它的代价，不同的读写场景，对隔离性的需求不同。隔离性越高，数据越安全，但性能越低。教科书上一般会写四种隔离级别，按照不同隔离级别可能出现的 "症状" 划分：Read Uncommitted：可能读到他人未 Commit 、可能被 Rollback 的脏数据，即 Dirty Read；Read Committed：不会读到他人未 Commit 的数据，但事务内重复读一条数据，可能得到不同的结果，即 Non-repeatable Read；Repeatable Read：同一事务内重复读一条数据的结果相同，但读取多个数据的时候，可能会得到不同的结果，即 Phantom Read；Serializable：完全的隔离性，在语义上相当于事务的执行没有并发一样；时至今日即使 wikipedia 上也是这四种分类，但是与现实世界已经不符合了[1]：按照 “症状” 划分的四种隔离级别，只适用于描述基于锁实现的并发控制；可是现在市面上的数据库早就都基于 MVCC 实现了，结果是各家数据库依然留着这四个隔离级别的名头，但语义有了不同：MySQL 中最低的隔离级别其实是 Read Committed，而且不会出现 Phantom Read；Repeatable Read 其实是 Snaps ...继续阅读 (43)

最近上线项目中尝试用 supervisord 监视 puma 进程。社区里教程似乎比较少，中间踩了个小坑在这里记录一下。Why Supervisord ?supervisord 是 python 社区里比较常用的工具，能够保证进程在极端情况下挂掉之后重启，使 web app 成为一个默认活着的服务。诚然 puma / unicorn 这类 App 服务器的 master 进程已经足够稳定了，但是不能排除云服务商半夜重启服务器的可能性。相比 daemontools，似乎比较容易配置；相比 systemd，兼容性更好，如果选用的镜像不是默认 systemd，这类核心的系统组件切换起来风险应该不小。Users操作 supervisord 需要 sudo 权限，而 app 要降权执行，为此准备两个用户：deploy 用户：用以存放 Web App 代码，拥有 sudo 权限，且 NOPASSWD，用以执行部署脚本、存放应用代码及依赖、控制 supervisorctl；主用户组为 deploy，可以保证部署的代码文件的用户组为 deploy；代码存放在 /home/deploy/www/myapp；app 用户：没有 sudo 权限，甚至不需要 home 目录，用以降权执行 App 代码；加入 deploy 用户组，/home/deploy/www/myapp/shared 下的 tmp 目 ...继续阅读 (36)

上周意识到知乎答错了一个问题之后，回家扫了几篇 CAP 相关的文章，重写了答案，也记录了一些笔记。CAP 很容易被误解或者模棱两可，一旦理解之后可以认为它不难，即使不理解也并不妨碍依赖它作为设计系统的指导原则，但是不能否认，CAP 理论直面了分布式系统的固有困难，可能还是写一篇 blog 总结一下对理解更加有益。单纯看网上的文章很容易走歪，我也仍不能保证这篇 blog 中没有理解错误的地方，欢迎指正、交流。Defination“Data consistency, system availability, and tolerance to network partition—only two can be achieved at any given time. ” ，即一个系统在一个特定时刻最多只能保证两条性质，进一步可以理解为：在 P 发生时，A 和 C 只能选一个；当系统没有出现 P 时，不需要做 C 与 A 的权衡。C、A、P 各自的定义是：Consistency: 关心单个数据多个副本的一致，需要注意与 ACID 的 "C" 有很大不同；属于 safety 约束，“anything bad won't happen”；Availability: 写入、读取请求最终一定可以得到结果；属于 liveness 约束，“something good eventually happen ...继续阅读 (27)

最近用 Evernote 明显多于纸质笔记和 blog，有些笔记就留在了里面长草，没有进一步整理。放假在家正好整理一下前段时间看 BigTable 论文的笔记。传统关系式数据库很难做到水平扩展，BigTable 是 Google 三大件之一的海量数据库方案。它基于 GFS 之上，在 GFS 的海量存储之上提供结构化的表存储。然而相对于面向高吞吐优化的 GFS，BigTable 的应用场景更加广泛，既适用于高吞吐的数据分析应用，也适用于面向用户的低延时应用。论文中对 BigTable 的定义为： "A sparse, distributed, persistent multi dimension sorted map"。此 map 基于行键、列键和时间戳进行索引，其中的键与值为裸的字节序列。为了方便讲解，论文中将 WebTable 作为例子，假定为爬虫爬来的网页数据表：行与 TabletBigTable 不支持跨行事务，但是每行的数据读写是原子的，因而得以安全高效地基于行做数据分割。每个行键对应一行数据，行键按字典序排列。每张表按一定行键的范围划分为 Tablet，Tablet 也正是数据分割与负载均衡的基本单位。每张 Tablet 大约为 100mb，当数据增大会自动分裂；当一台节点上的 Tablet 数量增多时，会尝试将 Tablet 的所有权 [1] 迁移到其它节点上。基于行键 ...继续阅读 (25)

flashcache 是 facebook 开源的 ssd 存储产品，它基于内核的 devicemapper 机制，允许将 ssd 设备映射为机械存储设备的缓存，堆叠成为一个虚拟设备供用户读写，从而在一定程度上兼顾 ssd 的高速与机械存储设备的高容量，更加经济高效地支撑线上业务。flashcache 支持三种缓存策略：回写(Write Back)：修改内容之后，并不立即写入后端设备写透(Write Through): 修改内容时写入后端设备，同时也更新前端设备中的缓存块环写(Write Around): 修改内容时，先写入后端设备，同时使前端设备中对应的缓存块失效为便于分析，先只看下仅支持写透缓存的一个“分支”：flashcache-wt。它最简单、安全，但整体效率相对而言偏低，它也是一种易失性缓存，在重启机器、卸载设备之后缓存的内容会全部失效。基本使用确保内核已启用 DeviceMapper，编译内核模块并安装之后：创建缓存设备:flashcache_wt_create /dev/cachedev /dev/sda1 /dev/hda1删除缓存设备:dmsetup remove cachedev使用者需要注意建立缓存设备之后，就不应该再对 /dev/sda1 和 /dev/hda1 两个设备直接读写了。缓存的组织虽然数据会被写入 ssd 设备，但缓存的组织信息一律保存在内存中， ...继续阅读 (36)

在前面一些预备内容之后，任务执行的悬念其实已经不大了。DAGScheduler 会在 runJob 中多次调用 submitTasks，由调度器后端负责具体的执行，随后调度器后端调用 taskEnded 向 DAGScheduler 反馈任务的进展。LocalScheduler先看最简单的 LocalScheduler，它将任务安排在本地单线程执行，代码非常直接，几乎没有注释的必要。 它代表了调度器后端的最简实现。def run_task(task, aid): logger.debug("Running task %r", task) try: Accumulator.clear() result = task.run(aid) accumUpdates = Accumulator.values() return (task.id, Success(), result, accumUpdates) except Exception, e: logger.error("error in task %s", task) import traceback traceback.print_exc() return (task.id, Ot ...继续阅读 (25)

为生产环境设计的 dpark 虽然构建于 Mesos，然而它并非完全绑定于 Mesos。除了 Mesos ，dpark 也提供了多线程与多进程作为后端。这样做很有意义，最起码使代码更加容易测试。dpark 与 Mesos 交互的逻辑比较复杂，不如放到下一篇单独记录。在这篇 blog 里，只简单记录一下 dpark 与 Mesos 无关的部分。RDDRDD 可以说是 spark 那篇论文的主题。Hadoop 总是将有依赖关系的计算之间的临时数据存储于分布式文件系统，利用文件系统的 Replication 提高数据的可靠性。然而分布式文件系统是一个共享内存模型，较强的一致性使得同步成本也相对更大。对此 spark 提供了更加讨巧的设计：会丢数据是既成事实，但是我们对数据的计算规则一清二楚，当丢数据时，只消重新计算再传一遍就好了，没必要维护临时数据的一致性。效果惊人的好。[^1]对应的实现就是 RDD (Resilient Distributed Datasets)。dpark 官方文档的描述非常好，就直接贴过来吧：有两种方式可以产生 RDD，通过特定函数从存储设备（内存或硬盘）创建，或者由其他 RDD 生成RDD 带有它所依赖的其他 RDD 的信息，以备计算失败的时候能够重新计算RDD 是只读的，这样从拓扑中恢复这个 RDD 的工作就能简单很多RDD 可以被重复使用一个 RDD 由多个 ...继续阅读 (138)

终于花一周时间理了一遍 dpark 的逻辑，原始的笔记放在了evernote，刚刚放下一天就不忍直视了，在这里尝试提炼一下。目测把内容堆到一篇 blog 里有些吃力，还是计划分成三篇然后祈祷不要坑掉好了。dpark 在项目开始之初的定位为 spark 的 python 版实现，思路基本一致，读代码时可以相互参考。尤其是刚刚开始阅读代码时，对各逻辑结构心里没底，spark 代码中的类型签名能够起到很棒的引导作用。然而毕竟 spark 的代码规模更大一些， 总体而言仍是 dpark 更容易读完。spark 将设计构建于 mesos 平台之上，很多代码都是围绕着 Mesos 的接口展开，在这里先简单记录一下 Mesos 的基础概念和基本的接口，在此暂且无意深究 Mesos 的内部实现。BackgroundMesos 是一个专门为集群计算框架设计的基础设施，就像虚拟化允许大家在一个物理机器上运行多个操作系统， Mesos 允许我们在同一个集群中执行多个计算框架，比如 Hadoop,MPI,Spark,Storm 等等，把它们放在各自的 cgroup 里，实现资源的隔离。在同一个集群中跑这么多不同的框架有什么用处？比较直接的一个回答是，Map Reduce 其实是个很受限制的计算模型，对于一些特定的情景，可能其它的某些计算模型更为适用，一个例子就是为高实时的流式计算而设计的 Storm。如果 ...继续阅读 (37)

前段时间看了一遍 mruby GC，基本把逻辑理清楚了，发补丁补了一些注释之余这里简单记一下。三色 GC搞过 rails 的同学会有印象，传统 Mark-Sweep 的主要问题是收集时间的不可控 [1]，不幸赶上 GC 的话，页面延迟会比较大。mruby 像 lua 一样将目标设定为可嵌入的解释器，对此很自然的考虑是令 GC 分阶段渐进执行，而三色 GC 也是最简单、最正确的渐进式 GC 的实现方式。三色 GC 的思路来自 Knuth 的三色图遍历算法 [2]，对象分为黑、灰、白三种颜色，分别维护在不同的集合里。一轮 GC 的流程很简单：在一开始，所有对象都是白色，从根对象开始遍历，标记为灰色随后只要灰色队列中还存在对象，便从中取一个对象，将它标记为黑色，并将它直接引用的对象标记为灰色，然后就允许暂停了 (当然继续跑下去也不碍事，GC 的暂停与否，一般看某些阙值的设定)待所有灰色对象消失之后，白色对象就是可回收的死对象了。为了让 Sweep 阶段渐进化，仍可以引入另一种白色，放到单独的集合里。到下一轮 GC 开始之后，新申请的对象会被标记为这种新的白色，至于旧的白色对象，则在理论上可以随时收集，不会受到新申请的白色对象的干扰。也就是说，mruby GC 在 Sweep 阶段回收的永远是上一轮 GC 留下的死对象。此外一条铁律是：黑色对象不可以引用白色对象。然而在一轮 GC 期间对象 ...继续阅读 (29)

很庆幸在学校里养成了记笔记的习惯，对于我这种理解力与记忆力都很差又懒于动手实践 [1] 的人而言，如果不试着记录一点东西，学习就全无进展可言了。当时几乎旷掉了所有的课去图书馆看书，捎一本笔记一把尺子，随着看书划下重要的句子，随着记录一部分划下的句子。有买过几本大的本子用来尝试系统地记录笔记，操作系统一本、计算机网络一本、编译一本，尽量工整地记录。然而在开始记录时就意识到了这个事实：这些本子以后是不会怎么看的。意识到这点之后，仍在这些本子上写了不少东西。即使以后不看，我依然相信记录在纸质的介质上仍有好处：眼睛阅读的速度远大于大脑理解的速度，用笔记录可以放慢阅读的速度，同时作为一种输出，确保真正读下了这段句子。甚至大脑理解的速度仍要远大于用笔记录的速度，在成本上其实很容易接受。然而，组织笔记的结构却成了一个头痛的问题。再者，尽量保持笔记的工整，导致了许多不必要的工作量。目的终究是看书，不是写笔记。慢慢地越发倾向于抛弃笔记的结构，直接将重要的句子提炼出来，按照平坦的结构记录到小本子上。到现在已经快写完了两本小本子，效果特别好，每当想温习功课时，都能够很快地翻完。笔记的阅读速度既然远远大于记录的速度，那么应当优先考虑写优化，就像 Log Structured FS 那样。工作之后没有那么多时间来看书了，也越发的感觉到一个瓶颈，原先的学习方式仅面向书本而已，进入工程领域，字面上的知识终究是虚 ...继续阅读 (20)

有关 Shadow Page Table 的一些设定困惑了很长时间，毕竟没有硬件的支持，放出来特别多黑魔法眼花缭乱的坑爹感，印象十分深刻。昨天把书从旧居搬了过来，躺床上翻 《支撑处理器的技术》 无意翻到影子页表这一节，对这两段颇为疑惑：200页, 影子页表 -- x86的 Hardware Table Walk 设施:此外， Guest OS 更改页表项目时，也必须修改与之对应的影子页表。为解决这个问题，VMM 首先将保存 Guest OS 页表的内存区域设置为只读。202页，虚拟TLB -- 更好的影子页表:虚拟 TLB 方式中， Guest OS 可以随意改变页表内容， 例如， Guest OS 可以改变某个页面对应的虚拟物理内存地址，而不会通知 VMM，这样就与虚拟 TLB 的内容产生矛盾。但是，即使没有虚拟化，操作系统像这样改变页表的内容，也会导致硬件的 TLB 内容和被改变的页表内容之间的矛盾， 因此必须清空 TLB 的内容。在虚拟化环境中， 清空 TLB 的特权指令执行时会产生异常，从而控制转移到 VMM，这样就能将 Guest OS 对页表的改变反映到虚拟 TLB 中。那么既然 Guest OS 会使用 invlpg 同步页表项的改动，那么还为什么必须给 Guest OS 页表的内存区域写保护？带着这个问题 google 了一番，几处资料给出的解释都不大一样，但都是很 ...继续阅读 (34)

强扣教科书的字眼的话，nginx中的radix tree似乎更像bitwise trie。bitwise trie的性质不难理解：从key的二进制最高位起，按位区分左子树还是右子树数据只保存于叶节点因此:特定key的查找路径总是固定的树的高度等于key的位数nginx中默认的模块中，只有http/modules/ngx_http_geo_module.c用到了radix_tree。它可以依据ip的范围划定出地理区域。这里记一下nginx的实现中有趣的地方，为了与教科书上的Radix Tree区分，这里统称为radix_tree。Code Notesngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)关于preallocation参数有一大段注释：/* * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc. * increases TLB hits even if for first lookup iterations. * On 32-bit platforms the 7 preallocated bits takes continuous 4K, * 8 - 8K, 9 - 16K, etc. On 64-bit platf ...继续阅读 (25)