鸽了

原文 https://www.fluentcpp.com/2021/02/05/how-stdany-works/

https://www.fluentcpp.com/2021/01/29/inheritance-without-pointers/

我加了个人的理解，大家英文好的去看原文

我感觉看不完了

另外，趁着假期，把知乎收藏夹/微博收藏夹和印象笔记都整理一下

引自 https://ericfu.me/yugabyte-db-introduction/

系统架构

逻辑上，Yugabyte 采用两层架构：查询层和存储层。不过这个架构仅仅是逻辑上的，部署结构中，这两层都位于 TServer 进程中。这一点和 TiDB 不同。

Yugabyte 的查询层支持同时 SQL 和 CQL 两种 API，其中 CQL 是兼容 Cassandra 的一种方言语法，对应于文档数据库的存储模型；而 SQL API 是直接基于 PostgresQL 魔改的，能比较好地兼容 PG 语法，据官方说这样可以更方便地跟随 PG 新特性，有没有官方说的这么美好我们就不得而知了。

Yugabyte 的存储层才是重头戏。其中 TServer 负责存储 tablet，每个 tablet 对应一个 Raft Group，分布在三个不同的节点上，以此保证高可用性。Master 负责元数据管理，除了 tablet 的位置信息，还包括表结构等信息。Master 本身也依靠 Raft 实现高可用。

基于 Tablet 的分布式存储

这一部分是 HBase/Spanner 精髓部分，Cockroach/TiDB 的做法几乎也是一模一样的。如下图所示，每张表被分成很多个 tablet，tablet 是数据分布的最小单元，通过在节点间搬运 tablet 以及 tablet 的分裂与合并，就可以实现几乎无上限的 scale out。每个 tablet 有多个副本，形成一个 Raft Group，通过 Raft 协议保证数据的高可用和持久性，Group Leader 负责处理所有的写入负载，其他 Follower 作为备份。

下图是一个例子：一张表被分成 16 个 tablet，tablet 的副本和 Raft Group leader 均匀分布在各个节点上，分别保证了数据的均衡和负载的均衡。

和其他产品一样，Master 节点会负责协调 tablet 的搬运、分裂等操作，保证集群的负载均衡。这些操作是直接基于 Raft Group 实现的。这里就不再展开了。

有趣的是，Yugabyte 采用哈希和范围结合的分区方式：可以只有哈希分区、也可以只有范围分区、也可以先按哈希再按范围分区。之所以这么设计，猜测也是因为 Cassandra 的影响。相比之下，TiDB 和 Cockroach 都只支持范围分区。

哈希分区的方式是将 key 哈希映射到 2 字节的空间中（即 0x0000 到 0xFFFF），这个空间又被划分成多个范围，比如下图的例子中被划分为 16 个范围，每个范围的 key 落在一个 tablet 中。理论上说最多可能有 64K 个 tablet，这对实际使用足够了。

哈希分区的好处是插入数据（尤其是从尾部 append 数据）时不会出现热点；坏处是对于小范围的范围扫描（例如 pk BETWEEN 1 AND 10）性能会比较吃亏。

基于 RocksDB 的本地存储

每个 TServer 节点上的本地存储称为 DocDB。和 TiDB/Cockroach 一样，Yugabyte 也用 RocksDB 来做本地存储。这一层需要将关系型 tuple 以及文档编码为 key-value 保存到 RocksDB 中，下图是对文档数据的编码方式，其中有不少是为了兼容 Cassandra 设计的，我们忽略这些，主要关注以下几个部分：

• key 中包含
• 16-bit hash：依靠这个值才能做到哈希分区
• 主键数据（对应图中 hash/range columns）
• column ID：因为每个 tuple 有多个列，每个列在这里需要用一个 key-value 来表示
• hybrid timestamp：用于 MVCC 的时间戳
• value 中包含
• column 的值

如果撇开文档模型，key-value 的设计很像 Cockroach：每个 cell （一行中的一列数据）对应一个 key-value。而 TiDB 是每个 tuple 打包成一个 key-value。个人比较偏好 TiDB 的做法。

分布式事务：2PC & MVCC

和 TiDB/Cockroach 一样，Yugabyte 也采用了 MVCC 结合 2PC 的事务实现。

时间戳

时间戳是分布式事务的关键选型之一。Yugabyte 和 Cockroach 一样选择的是 Hybrid Logical Clock (HLC)。

HLC 将时间戳分成物理（高位）和逻辑（低位）两部分，物理部分对应 UNIX 时间戳，逻辑部分对应 Lamport 时钟。在同一毫秒以内，物理时钟不变，而逻辑时钟就和 Lamport 时钟一样处理——每当发生信息交换（RPC）就需要更新时间戳，从而确保操作与操作之间能够形成一个偏序关系；当下一个毫秒到来时，逻辑时钟部分归零。

不难看出，HLC 的正确性其实是由 Logical Clock 来保证的：它相比 Logical Clock 只是在每个毫秒引入了一个额外的增量，显然这不会破坏 Logical Clock 的正确性。但是，物理部分的存在将原本无意义的时间戳赋予了物理意义，提高了实用性。

个人认为，HLC 是除了 TrueTime 以外最好的时间戳实现了，唯一的缺点是不能提供真正意义上的外部一致性，仅仅能保证相关事务之间的“外部一致性”。另一种方案是引入中心授时节点（TSO），也就是 TiDB 使用的方案。TSO 方案要求所有事务必须从 TSO 获取时间戳，实现相对简单，但引入了更多的网络 RPC，而且 TSO 过于关键——短时间的不可用也是极为危险的。

HLC 的实现中有一些很 tricky 的地方，比如文档中提到的 Safe timestamp assignment for a read request。对于同一事务中的多次 read，问题还要更复杂，有兴趣的读者可以看 Cockroach 团队的这篇博客 Living Without Atomic Clocks。

事务提交

毫不惊奇，Yugabyte 的分布式事务同样是基于 2PC 的。他的做法接近 Cockroach。事务提交过程中，他会在 DocDB 存储里面写入一些临时的记录（provisional records），包括以下三种类型：

• Primary provisional records：还未提交完成的数据，多了一个事务ID，也扮演锁的角色
• Transaction metadata：事务状态所在的 tablet ID。因为事务状态表很特殊，不是按照 hash key 分片的，所以需要在这里记录一下它的位置。
• Reverse Index：所有本事务中的 primary provisional records，便于恢复使用

事务的状态信息保存在另一个 tablet 上，包括三种可能的状态：Pending、Committed 或 Aborted。事务从 Pending 状态开始，终结于 Committed 或 Aborted。

事务状态就是 Commit Point 的那个“开关”，当事务状态切换到 Commited 的一瞬间，就意味着事务的成功提交。这是保证整个事务原子性的关键。

完整的提交流程如下图所示：

另外，Yugabyte 文档中提到它除了 Snapshot Isolation 还支持 Serializable 隔离级别，但是似乎没有看到他是如何规避 Write Skew 问题的。

参考

1. Yugabyte DB
2. Yugabyte DB Documents
3. Living Without Atomic Clocks - Cockroach Labs
4. https://ericfu.me/yugabyte-db-introduction/

最近在网上看到一篇抓堆栈的脚本工具介绍

工具还挺漂亮的，但是我的问题在于

1. perl写的，还依赖魔改ag，首先我看不懂，其次部署使用稍微有点成本(我看评论区有人帮忙打包)，然后是参数费解有点学习成本
   1. 主要是我看不懂，不是我写的，我可能就只会简单的查
2. 调用细节可能不够清晰，虽然足够用了

所以有了两个想法

1. 学一下perl，改写成python的工具？搜了一圈perl2python没有工具能用

2. 能不能用clang的工具？

PS：如何导出compliation database，也就是compile_commands.json

我折腾了半天导出，但是我根本用不到，这里把折腾记录放在下面

compilation database是clang/llvm的一个功能，作为一个语言后端支持language support protocol，需要有能力导出符号

所有的标记符号可以汇总成这个compilation database (clangd就是这个功能，对解析好的compilation database进行服务化，支持IDE的查询)

背后的技术是libclang，也有很多例子，这里就不展开了，可以看这个链接

既然都能支持IDE，难道还不能支持简单的函数调用查看，调用图生成吗，我似乎找到了新方案

但是这些方案都躲不开编译一遍，虽然只是简单的parser一遍，没有那么慢, 后面如果有时间，改写成python更好一些

如果编译环境是bazel，有https://github.com/grailbio/bazel-compilation-database支持

简单来说，就是改项目的BUILD和WORKSPACE

BUILD要加上

## Replace workspace_name and dir_path as per your setup.
load("@com_grail_bazel_compdb//:aspects.bzl", "compilation_database")

compilation_database(
    name = "compdb",
    targets = [
        "yourtargetname",
    ],
)

这里target写你自己的target，可以多个target分割，name随便，这里我写成compdb

然后WORKSPACE要加上

http_archive(
    name = "com_grail_bazel_compdb",
    strip_prefix = "bazel-compilation-database-master",
    urls = ["https://github.com/grailbio/bazel-compilation-database/archive/master.tar.gz"],
)

最后编译

bazel build //path/yourtargetnamedir:compdb

就生成compile_commands.json了

其他编译环境，用bear

bear本身支持macos和linux，尝试命令行安装一下，安装不上的话源码安装

如果是makefile系列的编译系统，直接

bear -- make

就可以了，这里以memcached为例子

用python解析

PS：

如果遇到报错

    raise LibclangError(msg)
clang.cindex.LibclangError: dlopen(libclang.dylib, 6): image not found. To provide a path to libclang use Config.set_library_path() or Config.set_library_file().

说明找不到libclang，需要指定一下，比如

export DYLD_LIBRARY_PATH=/usr/local/Cellar/llvm/11.0.0/lib/

这篇文章很有干货，整理一下 https://www.evanjones.ca/durability-filesystem.html

flag和函数的区别是：flag表示每次io操作都会执行，函数是在执行函数的时候触发；

O_Direct优劣势：

• 优势：直接绕过page cache/buffer cache，节省操作系统内存；使用O_DIRECT方式提示操作系统尽量使用DMA方式来进行存储设备操作，节省CPU；
• 劣势：字节对齐写（logic block size）；无法进行IO合并；读写绕过cache，小数据读写效率低；

关于函数的问题

• fsync遇到过bug ，fsync可能报错EIO，系统没把脏页刷盘，但数据库层认为刷完了，导致这段数据丢了 https://wiki.postgresql.org/wiki/Fsync_Errors
• sync_file_range这里有个原理 ,不刷元数据！rocksdb会用这个来刷盘，看这个注释，额外再用fdatasync。除非你知道你在做什么，否则不要用这个api

作者总结

• fdatasync or fsync after a write (prefer fdatasync).

• write on a file descriptor opened with O_DSYNC or O_SYNC (prefer O_DSYNC).

• pwritev2 with the RWF_DSYNC or RWF_SYNC flag (prefer RWF_DSYNC).

结论，推荐使用O_DSYNC/fdatasync()

一些关于随机(写)的性能观察

• 覆盖写比追加写快(~2-100% faster) 追加写要原子修改元数据。
• 和system call相比，用flag更省，性能更好(~5% faster)

page cache

系统对page cache的管理，在一些情况下可能有所欠缺，我们可以通过内核提供的posix_fadvise予以干预。

#include <fcntl.h>

int posix_fadvise(int fd, off_t offset, off_t len, int advice);

posix_fadvise是linux上对文件进行预取的系统调用，其中第四个参数int advice为预取的方式，主要有以下几种：

POSIX_FADV_NORMAL 无特别建议 重置预读大小为默认值 POSIX_FADV_SEQUENTIAL 将要进行顺序操作 设预读大小为默认值的2 倍 POSIX_FADV_RANDOM 将要进行随机操作 将预读大小清零（禁止预读） POSIX_FADV_NOREUSE 指定的数据将只访问一次 （暂无动作） POSIX_FADV_WILLNEED 指定的数据即将被访问 立即预读数据到page cache POSIX_FADV_DONTNEED 指定的数据近期不会被访问 立即从page cache 中丢弃数据

/proc/sys/vm/dirty_writeback_centisecs：flush检查的周期。单位为0.01秒，默认值500，即5秒。每次检查都会按照以下三个参数控制的逻辑来处理。

/proc/sys/vm/dirty_expire_centisecs：如果page cache中的页被标记为dirty的时间超过了这个值，就会被直接刷到磁盘。单位为0.01秒。默认值3000，即半分钟。

/proc/sys/vm/dirty_background_ratio：如果dirty page的总大小占空闲内存量的比例超过了该值，就会在后台调度flusher线程异步写磁盘，不会阻塞当前的write()操作。默认值为10%。

/proc/sys/vm/dirty_ratio：如果dirty page的总大小占总内存量的比例超过了该值，就会阻塞所有进程的write()操作，并且强制每个进程将自己的文件写入磁盘。默认值为20%。

ref

• linux IOhttps://www.scylladb.com/2017/10/05/io-access-methods-scylla/ 这几个图画的还行。不过原理也比较简单。不多说
• page cache https://www.jianshu.com/p/92f33aa0ff52

整理自 https://wolchok.org/posts/inlining-and-compiler-optimizations/

文章串起来了一些知识，读一读，增加一下见解。当然，学习一下clang/llvm更直接一些，这些都是二手复读

看到网友推荐这篇博客，整理归纳一下 https://martinfowler.com/articles/patterns-of-distributed-systems/

我发现有人翻译了，但是翻译的不全。 https://xie.infoq.cn/article/f4d27dd3aa85803841d050825

这里的分布式系统是指所有的系统，共性问题

面临的共性问题

• 进程崩溃
  • 配置文件修改导致的暂时下线（大公司已经出过很多起了）
  • 异常场景没处理，比如磁盘满
  • 云场景下的其他影响的场景

这些场景下如何处理数据丢失？解决方案：WAL

• 网络延迟问题
  • 不知道其他进程的状态是否正常 解决方案： 心跳
  • 脑裂导致的数据冲突 解决方案 Quorum

• 另一种异常，进程暂停，可能是内部在忙，没有及时响应，可能是gc引起的延迟等等

• Generation Clock 我的理解就是term 推进，老master检测自己不是最新的index，就自动降低身份 也就是Lamport’s timestamp

• 时间同步问题，ntp是不准的甚至是会出错的，有原子钟方案，也有lamport逻辑时钟方案

  （其实原子钟方案比较简单，一个gps原子钟七八万，我之前的老项目用过，这个成本对于互联网公司还好吧，为啥都不用呢，不方便部署么）

一个整合方案，以及涉及到具体的设计细节

WAL

首先是WAL 也就是commit log commit log要保证持久性

每个日志要有独立的标记，依此来分段整理，方便写，但是不能无限长，所以要有个Low-Water-Mark标记，其实就是后台线程定期删日志

日志更新就相当于队列追加写了，为了吞吐可能要异步一些

考虑如何实现这样一个kv；

首先kv得能序列化成log，并且能从log恢复

需要支持指定snapshot/timestap恢复，这两种是淘汰判定的标准，也就是一个unit

Low-Water-Mark实现方案

• 基于快照snapshot，每次成功的写入index都是一次快照，快照落盘就过期，可以删掉 有点像生产消费

zookeeper etcd都是这个方案，代码类似下面

public SnapShot takeSnapshot() {
    Long snapShotTakenAtLogIndex = wal.getLastLogEntryId();
    return new SnapShot(serializeState(kv), snapShotTakenAtLogIndex);
}

//Once a snapshot is successfully persisted on the disk, the log manager is given the low water mark to discard the older logs.

List<WALSegment> getSegmentsBefore(Long snapshotIndex) {
    List<WALSegment> markedForDeletion = new ArrayList<>();
    List<WALSegment> sortedSavedSegments = wal.sortedSavedSegments;
    for (WALSegment sortedSavedSegment : sortedSavedSegments) {
        if (sortedSavedSegment.getLastLogEntryId() < snapshotIndex) {
            markedForDeletion.add(sortedSavedSegment);
        }
    }
    return markedForDeletion;
}

• 基于时间，有点像日志轮转

kafka就是这种方案

private List<WALSegment> getSegmentsPast(Long logMaxDurationMs) {
    long now = System.currentTimeMillis();
    List<WALSegment> markedForDeletion = new ArrayList<>();
    List<WALSegment> sortedSavedSegments = wal.sortedSavedSegments;
    for (WALSegment sortedSavedSegment : sortedSavedSegments) {
        if (timeElaspedSince(now, sortedSavedSegment.getLastLogEntryTimestamp()) > logMaxDurationMs) {
            markedForDeletion.add(sortedSavedSegment);
        }
    }
    return markedForDeletion;
}

private long timeElaspedSince(long now, long lastLogEntryTimestamp) {
    return now - lastLogEntryTimestamp;
}

读取？一致性方案 quorum

读大多数 判定数据

写WAL - 复制组

复制组要保证高可用性 心跳检查，节点间心跳以及自身心跳处理，如果自身僵住需要退位

复制组有主从，涉及到选举算法 zab raft之类

arangodb也是多模数据库，支持文档和图两种，支持mongodb式的操作json语法，也支持类似sql的方法

简单体验一下

在macos上非常好体验，直接brew就能安装

brew install arangodb
brew serivces start arangodb
brew services stop arangodb

注意是有密码的，我这里直接把密码关掉了，参考这个文档, 修改arangodb.conf 把authentication改成false重启就可以了

可以网页访问 http://localhost:8529/_db/_system/_admin/aardvark/index.html#collections

arangodb也提供了命令行 arangosh

备份 https://www.arangodb.com/docs/stable/backup-restore.html

replication appler是什么概念？https://www.arangodb.com/docs/stable/http/replications-replication-applier.html

经典图

• Unavailable: 当出现网络隔离等问题的时候，为了保证数据的一致性，不提供服务。熟悉 CAP 理论的同学应该清楚，这就是典型的 CP 系统了。
• Sticky Available: 即使一些节点出现问题，在一些还没出现故障的节点，仍然保证可用，但需要保证 client 不能更换节点。
• Highly Available: 就是网络全挂掉，在没有出现问题的节点上面，仍然可用。

并发事务在没有隔离性保证时会导致哪些问题：

• Dirty Write 脏写 - 一个事务覆盖了另一个事务还没提交的中间状态
• Dirty Read 脏读 - 一个事务读到了另一个事务还没提交的中间值
• Non-Repeatable Read 不可重复读 - 一个事务中连续读取同一个值时返回结果不一样（中途被其他事务更改了）
• Phantom 幻读 - 当一个事务按照条件C检索出一批数据，还未结束。另外的事务写入了一个新的满足条件C的数据，使得前一个事务检索的数据集不准确。
• Lost Update 写丢失 - 先完成提交的事务的改动被后完成提交的事务覆盖了，导致前一个事务的更新丢失了。
• Cursor Lost Update - Lost Update的变种，和Cursor操作相关。
• Read Skew 偏读 - 事务在执行a+b期间，a，b值被其他事务更改了，导致a读到旧值，b读到新值
• Write Skew 偏写 - 事务连续执行if(a) then write(b) 时， a值被其他事务改了，类似超卖。

可以看到，由于隔离型相关的问题其实都是并发竞争导致的，所以和「多线程安全」问题非常相像，思路和方案也是共通的。 现代数据库系统已经将并发竞争问题抽象为隔离级别（Isolation level）来处理 ，也就是 ACID中的I。接下来我们看一下常见的隔离级别，以及能提供的保证：

• Read Uncommitted - 能读到另外事务未提交的修改。
• Read Committed - 能读到另外事务已经提交的修改。
• Cursor Stability - 使用 cursor 在事务里面引用特定的数据，当一个事务用 cursor 来读取某个数据的时候，这个数据不可能被其他事务更改，除非 cursor 被释放，或者事务提交。
• Monotonic Atomic View - 这个级别是 read committed 的增强，提供了一个原子性的约束，当一个在 T1 里面的 write 被另外事务 T2 观察到的时候，T1 里面所有的修改都会被 T2 给观察到。
• Repeatable Read - 可重复读，也就是对于某一个数据，即使另外的事务有修改，也会读取到一样的值。
• Snapshot - 每个事务都会在各自独立，一致的 snapshot 上面对数据库进行操作。所有修改只有在提交的时候才会对外可见。如果 T1 修改了某个数据，在提交之前另外的事务 T2 修改并提交了，那么 T1 会回滚。
• Serializable - 事务完全按照顺序依次执行，相当于强锁。

这是那个经典论文描述的场景 图片介绍。另外知乎有篇验证文章

一致性面临的问题

server端视角

• 线性一致性（Linearizability）- 最强的单对象一致性模型，要求任何写操作都能立刻同步到其他所有进程，任何读操作都能读取到最新的修改。简单说就是实现进程间的 Java volatile 语义。这是一种对顺序和实时性都要求很高的模型。要实现这一点，要求将所有读写操作进行全局排序。
• 顺序一致性（Sequential Consistency）：在线性一致性上放松了对实时性的要求。所有的进程以相同的顺序看到所有的修改，读操作未必能及时得到此前其他进程对同一数据的写更新。
• 因果一致性（Causal Consistency）：进一步放松了顺序要求，提高了可用性。读操作有可能看到和写入不同的顺序 。只对附加了因果关系的写入操作的顺序保证顺序性。“逻辑时钟”常用来为操作附加这种因果关系。
• PRAM一致性(Pipeline Random Access Memory) ：多进程间顺序的完全放松，只为单个进程内的写操作保证顺序，但不保证不同的写进程之间的顺序。这种放松可以大幅提高并发处理能力。例如Kafka保证在一个分区内读操作可以看到写操作的顺序 ，但是不同分区间没有任何顺序保证。

client端视角

• 单调读一致性（Monotonic-read Consistency），如果一个客户端读到了数据的某个版本n，那么之后它读到的版本必须大于等于n。
• 单调写一致性（Monotonic-write Consistency），保证同一个客户端的两个不同写操作，在所有副本上都以他们到达存储系统的相同的顺序执行。单调写可以避免写操作被丢失。
• 写后读一致性、读己之写一致性（Read-your-writes Consistency），如果一个客户端写了某个数据的版本n，那么它之后的读操作必须读到大于等于版本n的数据。
• 读后写一致性（Writes-follow-reads Consistency）保证一个客户端读到版本n数据后（可能是其他客户端写入的），随后的写操作必须要在版本号大于等于n的副本上执行。

PRAM一致性(Pipeline Random Access Memory)完全等同于读你的写、单调写和单调读。如果要追求读后写一致性，只能选择因果一致性。如果你需要完全的可用性，可以考虑牺牲阅读你的写，选择单调读 + 单调写。

分布式系统中的时间和顺序 Time and order

• 时间和顺序
  • 像单机系统一样有同样的执行顺序
• 全局有序和偏序
• 什么是时间
• 分布式节点的时间相同吗
  • 全局时钟
  • 本地时钟
  • 无时钟
• 时间在分布式系统中的作用
  • 定义系统中的顺序
    • 系统的正确性取决于正确的顺序
    • 冲突协调需要顺序作为评判标准
  • 定义边界条件（故障检测器）
• 矢量时钟（计数器+通信）
  • Lamport Clock
  • Vector Clock
• 故障检测（心跳+定时器）
• 时间，顺序和性能
  • 分布式系统天生是偏序的
  • 全局有序需要额外的通信
  • 利用Single Node 可降低顺序保证难度（将需要有序的操作部分放在单个节点上同步执行）

复制：强一致性模型

• 复制
  • 复制要解决的是一组通信问题
    • 什么样的通信模式可以提供所需的性能和可用性？
    • 当网络分区或节点崩溃，如何保证容错性、持久性和一致性？
  • 复制的四个阶段
    • 客户端发送请求
    • 复制中的同步部分执行
    • 向客户端返回答复
    • 复制中的异步部分执行
• 同步复制
  • 是一种悲观复制
  • 性能取决于最慢的一个节点(N of N)
  • 提供很好的持久性和一致性保证
• 异步复制
  • 是一种乐观复制
  • 性能很快 (1 of N)
  • 提供很弱的持久性和一致性保证
• 主要复制方法
  • 防止分歧的 Single-Copy Systems
  • 允许分歧的 Multi-Master Systems
• Primay-Backup 主备复制协议
  • 异步主备复制（只需要一条信息 ：更新）
  • 同步主备复制（需要两条信息：更新+确认收到）
    • 仍然需要额外的协调来应对故障，保证持久性（主节点在任意时间可能失效）
    • 需要日志和2pc来做额外保证（失败回滚）
• 2PC 两阶段提交协议
  • 主要是允许失败回滚，防止故障导致的分歧
  • 无法做到分区容忍(N of N复制)
• 分区容忍一致性复制协议
  • 什么是网络分区
    • 无法区分远程节点崩溃还是网络故障
  • 大多数仲裁 Quorums
    • 获得大多数投票即可进行(N/2+1 of N)
    • 通过奇数节点保证分区时只有一个集群是活跃的
    • 允许少数派数据不一致，但少数派的数据会被放弃来保证一致性。（放弃活跃性保证安全性）
  • 节点区分角色
    • 一个Leader角色和多个Follower角色
  • 为选举区分纪元 Term
    • 充当逻辑时钟用于识别出已经过期的选票和Leader角色
  • Leader 变更机制
    • 要保证一旦做出一个决策，即使因为崩溃而更换Leader也不能丢失这个决策
  • 将纪元内的提案编号
    • 要保证一旦做出一个决策，即使因为崩溃或分区也不能丢失这个决策
  • 通常的操作流程
• 分区容忍一致性算法的代表：Paxos、Raft、ZAB
• 总结：具有强一致性的复制方法
  • Primay-Backup 主备模型(MySQL)
    • 基于日志的复制，从节点只读
    • 有复制延迟
    • 有单一且静态指定的主
    • 无法容错
  • 2PC
    • 一致表决
    • 无复制延迟
    • 静态主
    • 无法容错
  • Paxos类
    • 大多数机制
    • 动态指定主
    • 允许一部分节点失败或分区

复制：弱一致性模型

• 接受分歧
  • 允许暂时的分歧，找到某种处理分歧的方法，并最终返回一致可用的结果
  • 两种最终一致模型：
    • 概率最终一致
    • 保证最终一致
• 协调不同操作的顺序
  • 分区时允许多个副本被不同客户端写入不同的值(AP)
  • 利用协调协议处理写入冲突并收敛成一个可用的值
• Amazon’s Dynamo
  • 数据分布技术：一致性哈希
  • 一致性保证技术：部分大多数仲裁 Partial Quorums (R+W>N)
  • R+W>N 是强一致性吗
  • 冲突检测和Read-Repair
    • 允许副本分歧的系统必须有办法最终协调两个不同的值
    • 这种协调方法必须依赖一些元数据
      • 没有元数据：Last Write Win
      • 依赖时间戳: Global Clock
      • 依赖版本号：Lamport Clock
      • 依赖向量时钟：Vector Clock (准确跟踪因果关系的最小实现）
    • 读取修复依然可能会返回多个值
  • 副本同步技术：Gossip 协议和 Merkle Tree
• 无序编程
  • 一些数据类型在任意操作顺序下都会收敛为同一个值
• CRDT : Conflict-free replicated data types
  • CRDT的三律
    • 交换律、组合率、幂等律
  • 常见的CRDT结构
    • Counter
    • Register
    • Set / PN Set
• CALM定理
• 非单调性有什么好处

线性一致性

我们可以利用线性一致性的原子性约束来安全地修改状态。我们定义一个类似CAS（compare-and-set）的操作，当且仅当寄存器持有某个值的时候，我们可以往它写入新值。 CAS操作可以作为互斥量，信号量，通道，计数器，列表，集合，映射，树等等的实现基础，使得这些共享数据结构变得可用。线性一致性保证了变更的安全交错。

顺序一致性，强调顺序，不是必须发生，但保持顺序发生

因果一致性，保证因果顺序，顺序一致性的子集

串行一致性，有条件必严格

最终一致性以及CRDTs数据结构

ref

• https://zhuanlan.zhihu.com/p/48782892
• “分布式一致性模型” 导论http://yuezhang.org/2019/05/17/consistency-model.html 解释了经典论文
• 从复制的视角看一致性 http://yuezhang.org/2018/03/29/distributed-systems-for-fun-and-profit-note.html
• 时间戳相关的问题 https://zhuanlan.zhihu.com/p/333471336
• https://zhuanlan.zhihu.com/p/333471336
• https://zhuanlan.zhihu.com/p/90996685
• 经典论文 https://nan01ab.github.io/2017/08/ANSI-SQL-Isolation-Levels.html