分布式系统,程序语言,算法设计

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第六节课笔记,是 Raft 论文讲解的第一部分,主要总结了容错的几种类型以及 Raft 中的 Leader 选举相关内容。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第五节课笔记,包括两部分:第一部分由一个助教讲了 lab2 中将会用到的一些 go 的源语、设计模式和实践技巧,包括内存模型、goroutine和闭包、时间库、锁、条件变量、channel、信号、并行和一些常用工具等等。第二部分是由另两个助教梳理了下 raft 中常遇到的一些 bug 和调试方法。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第四节课笔记,VM-FT。

备份——容错

失败(Failue)

如何定义?在其他电脑看来,停止对外提供服务。
通过备份/副本(Replication)
可以解决:宕机(fail-stop),比如 CPU 过热而关闭、主机或者网络断电、硬盘空间耗尽等问题。
不能解决:一些相关联(correlated,主副本机器会同时存在)的问题,比如软件 Bug、人为配置问题

前提

主从备份可以工作的一个假设是,主从机器的出错概率需要时独立的。
比如说:同一批次机器、同一个机架上的机器,出错概率就存在强正相关特性。

是否值当

需要对业务场景和所需费用考量,是否真的需要进行 Replica。比如银行数据就需要多备份,而课程网站可能并不需要。

阅读全文 »

目标

充分利用现代存储 SSD 的性能,在提供同样 API 的情况下,显著降低 LSMTree 的读写放大,以提高其性能。

背景

在传统磁盘上,顺序 IO 的性能大概是随机 IO 的 100 多倍,LSMTree 基于此,将海量 KV 的随机读写实现为内存随机读写+顺序刷盘+定期归并(compact),以提高读写性能,尤其适用于写多于读时效性比较强(最近数据最常访问)的场景。

wisckey-lsm-tree.png

阅读全文 »

博客本来用的是 github pages,但貌似由于百度爬虫太疯狂,被 github 给 ban 掉了。根据 marketmechian 的数据,在中国大陆搜索引擎界,百度还是占了半壁江山:

  • Baidu: 67.09%
  • Sogou: 18.75%
  • Shenma: 6.84%
  • Google: 2.64%
  • bing: 2.6%
  • Other: 2.08%

而作为一个中文博客,还是希望能够被更多的国内用户看到,因此一直在寻求一个使得百度爬虫自动爬取博客的方法。偶然间在浏览博客时,看到了有人在推荐 zeit.co 这个托管平台,使用了下,发现真是个非常棒的静态代码托管+CI Serverless Function 平台,在这里推荐给大家。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第三节课笔记,GFS。

概述

存储(Storage)是一个非常关键的抽象,用途广泛。

GFS 论文还提到了很多关于容错、备份和一致性的问题。

GFS 本身是 Google 内部一个很成功的实用系统,其关键点被很好的组织到一块发表成为了学术论文,从硬件到软件,涵盖了很多问题,值得我们学习。

想详细了解 GFS,也可以看我之前的 GFS 论文笔记

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第二节课笔记,RPC 和线程。

为什么用 Go

  1. 语法先进。在语言层面支持线程(goroutine)和管道(channel)。对线程间的加锁、同步支持良好。
  2. 类型安全(type safe)。内存访问安全(memory safe),很难写出像 C++ 一样内存越界访问等 bug。
  3. 支持垃圾回收(GC)。不需要用户手动管理内存,这一点在多线程编程中尤为重要,因为在多线程中你很容易引用某块内存,然后忘记了在哪引用过。
  4. 简洁直观。没 C++ 那么多复杂的语言特性,并且在报错上很友好。
阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第一节课笔记,绪论。

课程背景

构建分布式系统的原因:

  1. Parallelism,资源并行(提高效率)。
  2. Fault tolerance,容错。
  3. Physical,系统内在的物理分散。
  4. Security,不可信对端(区块链)。

分布式系统面临的挑战:

  1. Concurrency,系统构件很多,并行繁杂,交互复杂。
  2. Partial failure,存在部分失败,而不是像单机一样要么正常运行,要么完全宕机。
  3. Performance,精巧设计才能获取与机器数量线性相关的性能。
阅读全文 »

本文缘起于Lu Pan 的个人博客文章:https://blog.the-pans.com/cap/ ,是他经过 Martin Kleppmann 授权并且翻译的博文”Please stop calling databases CP or AP”中文版本。但译文中不少句子读来颇为古怪,我对照英文原文,按照自己理解,逐句校验、重译了一遍。这篇文章探讨了为什么不应该滥用 CAP定理 这个概念,旁征博引,入木三分,值得一读。更值得称道的是,Martin 文中所有关键观点都给出了来源,并在最后推荐了一些学习资料,都是不错的阅读材料。以下是正文。

在 Jeff Hodges 的精彩博文给年轻人关于分布式系统的笔记 中,他建议我们用CAP定理来评判系统。不少人听从了这个建议,将他们的系统称为”CP” (提供一致性但在网络分区时不可用),“AP”(高可用但是在网络分区时不一致) 或者干脆 “CA” (说明还没有读过Coda的五年前的文章)。

我同意 Jeff 的所有其他观点,但其关于 CAP 定理的使用建议,我不能表示赞同。CAP 定理本身太过简化而且存在广泛的误解,以至于在界定系统时不能有效的起到作用。因此我请求大家不要再引用CAP定理, 不要再讨论CAP定理。取而代之,我们应该用更精确的术语来表述我们对系统的取舍。

(当然,讽刺的是我不希望别人再讨论这个话题,自己却正在写一篇关于这个话题的文章。不过至少以后别人问我为什么不喜欢讨论CAP定理的时候,我可以把这篇文章的链接给他。还有,抱歉这篇文章会有些吐槽,但是至少这些吐槽给出了文献引用)

阅读全文 »

cap-consistency-example.png

小引

曾经在一个面试中让谈谈对 CAP 的理解,当时凭着准备面试时谷歌到的N手资料,类似于小学生背书一样,生挤出只言片语。面试官无奈的笑笑,简练的概括出他想要听到的要点,听的我心下惭愧。面试自然是挂了,后来工作时偶尔接触到这个词汇,初不得要领,后通过不同资料的多侧面理解、印证,渐渐拼凑出了一个轮廓,在这里梳理下,将影子撵到纸上,以供日后索引。

面试官大约是这么概括的:在分布式系统中,失败必然的,分区容错(P)是一定需要的,因此设计系统时需要在可用性(A)和一致性(C)间进行权衡。当时被教育印象很深,现在看来,这句概括是点出了小荷才露尖尖角的那个角。

阅读全文 »