木鸟杂记

概览

Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能，Dynamo 采用了最终一致性模型，它对开发人员提供一种新型 API，使用了版本机制，并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务，同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构，因此对微服务状态的存储系统的可用性要求尤其高。

S3 （Simple Storage Service）是 Amazon 另一款有名的存储服务，虽然也可以理解为 KV 存储，但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务，主要存储二进制文件，不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务，主要存储结构化数据（如 json），并且可以对数据设置索引，且支持跨数据条目的事务。

相对于传统的关系型数据库，Dynamo 可以认为是只提供主键索引，从而获取更高的性能和更好的扩展性。

为了实现可扩展性和高可用性，并保证最终一致性，Dynamo 综合使用了以下技术：

1. 使用一致性哈希对数据进行分片（partition）和备份（replicate）。
2. 使用版本号机制（Vector Clock）处理数据一致性问题。
3. 使用多数票（Quorum）和去中心化同步协议来维持副本间的一致性（Merkle Tree）。
4. 基于 Gossip Protocol 进行失败检测和副本维持。

实现上来说，Dynamo 有以下特点：

1. 完全去中心化，没有中心节点，所有节点关系对等。
2. 采用最终一致性，使用版本号解决冲突，甚至要求用户参与解决冲突。
3. 使用哈希值进行数据分片，组织数据分布，均衡数据负载。

儿时初学“让我们荡起双桨”，只感觉旋律朗朗；年岁稍长，偶尔哼起，三言两语，味出千万意境；后来，求学帝都，游北海，正是“湖面倒映着美丽的白塔，四周环绕着绿树红墙”，光阴荏苒，不变的是文字的生命力。

歌词为乔羽先生所做，很多脍炙人口的名作皆出自其手：《我的祖国》、《难忘今宵》、《爱我中华》。词分三段，层层递进。第一段写划船之景，寥寥几句，首尾勾连、推近及远、勾勒出四合景象。第二段写欢快之情，童真昂扬，心情轻快，描绘出饱满的童趣。第三段继而升华，设问如此美景、如此生活、如此时代，如何得来？尔后戛然而止，语已尽而意无穷。

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

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

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

备份——容错

失败（Failue）

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

前提

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

是否值当

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

目标

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

背景

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

博客本来用的是 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 平台，在这里推荐给大家。

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

概述

存储（Storage）是一个非常关键的抽象，用途广泛。

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

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

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

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

为什么用 Go

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

MIT 今年终于主动在 Youtube 上放出了随堂视频资料，之前跟过一半这门课，今年打算刷一下视频，写写随堂笔记。该课程以分布式基础理论：容错、备份、一致性为脉络，以精选的工业级系统论文为主线，再填充上翔实的阅读材料和精到的课程实验，贯通学术理论和工业实践，实在是一门不可多得的分布式系统佳课。课程视频: Youtube，B站。课程资料：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 的理解，当时凭着准备面试时谷歌到的N手资料，类似于小学生背书一样，生挤出只言片语。面试官无奈的笑笑，简练的概括出他想要听到的要点，听的我心下惭愧。面试自然是挂了，后来工作时偶尔接触到这个词汇，初不得要领，后通过不同资料的多侧面理解、印证，渐渐拼凑出了一个轮廓，在这里梳理下，将影子撵到纸上，以供日后索引。

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