1月待读

我感觉看不完了

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

Read More

yogabytedb调研

引自 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 实现高可用。

img

基于 Tablet 的分布式存储

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

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

img

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

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

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

img

哈希分区的好处是插入数据(尤其是从尾部 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 的值

img

如果撇开文档模型,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,便于恢复使用

img

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

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

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

img

另外,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/

Read More

一个查看函数调用的新方案-操作compliation database

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

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

  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/

Read More

(译)关于Linux IO 持久性的讨论,以及page cache

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

flag\action page cache buffer cache inode cache directory cache
O_DIRECT write bypass write bypass write & no flush write & no flush
O_DSYNC/fdatasync() write & flush write & flush write & no flush write & no flush
O_SYNC/fsync() write & flush write & flush write & flush write & flush
sync_file_range() write & flush write & flush no write no write

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

Read More


(译)分布式系统的模式

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

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

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

Type of platform/framework Example
Databases数据库 Cassandra, HBase, Riak
Message Brokers消息队列 Kafka, Pulsar
Infrastructure基础架构元信息管理 Kubernetes, Mesos, Zookeeper, etcd, Consul
In Memory Data/Compute Grids网格 Hazelcast, Pivotal Gemfire
Stateful Microservices微服务 Akka Actors, Axon
File Systems文件系统 HDFS, Ceph

面临的共性问题

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

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

  • 网络延迟问题
    • 不知道其他进程的状态是否正常 解决方案: 心跳
    • 脑裂导致的数据冲突 解决方案 Quorum
  • 另一种异常,进程暂停,可能是内部在忙,没有及时响应,可能是gc引起的延迟等等

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

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

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

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

WAL

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

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

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

img

考虑如何实现这样一个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之类


Read More

arangodb初体验

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


Read More

分布式系统中的一致性模型,以及事务

经典图

  • 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

Read More

^