可串形化的快照隔离（Serializable Snapshot Isolation，SSI）近两年被研究，尚需在实践中证明其性能，但是它很有可能成为未来数据的标配。 悲观与乐观并发控制

两阶段枷锁（two-phase locking，2PL）是近 30 年来数据库唯一一种被广泛使用的串形化算法。 多个事务可以同时读取同一个对象，但只要出现任何写操作（修改或删除），则必须加锁以独占访问。 两阶段包括： 事务执行之前要获得锁（第一阶段） 事务结束之后要释放锁（第二阶段） 实现 2PL 用于 MySQL（InnoDB）和 SQL Server 中的“可串形化隔离”，以及 DB2 的“可重复读”。 每个对象通过一个「读写锁」隔离读写操作。 共享锁进行读取。 独占锁进行修改。 读取先获取共享锁，如果要修改则升级为独占锁。 事务获得锁之后一直持有到事务结束。 性能 慢和死锁 谓词锁 通过对区间条件加谓词锁。 索引区间锁

实际串行执行 解决并发问题最直接的方法：在一个线程上按照顺序方式每次执行一个事务。 为什么可行： 内存越来越便宜，可以将事务需要的数据都放在内存中。 OLTP 事务通常执行很快，只产生少量的读写操作。通常较长时间的分析操作通常是只读。 事务为了充分利用单线程所做的调整： 采用存储过程封装事务，Redis 采用 Lua 分区 约束 事务必须简短而高效。 事务所需数据都在内存。 写入吞吐量必须低，否则需要采用分区，最好没有跨分区事务。 要支持跨分区事务必须确保跨分区事务占比很小。 两阶段加锁 可串形化的快照隔离

即不是脏写也不会更新丢失，事务之间的写冲突并不直接，写倾斜可以视为更广义的数据丢失。 考虑急诊医生请假系统，核心逻辑是必须要有一个医生值班。两个医生同时请假，事务同时同时开始，那么两个医生都能查询到有两个医生值班，最后请假成功，导致无医生值班。

写事务并发除了需要防止更新丢失还有一些更为微妙的写冲突。 写倾斜与幻读 定义写倾斜。

读事务遇到并发写会出现脏读（读-提交和可重复读可以解决），写事务并发会带来一些冲突，最值得关注的就是更新丢失问题。 应用程序从数据库读取某些值，然后应用逻辑做出修改，然后写回新值。 原子写操作 UPDATE counters SET value=value+1 WHERE key = 'foo'; 原子操作通常采用方式： 对读取对象加独占加锁，这种技术有时被称为「游标稳定性」。 强制所有原子操作都在单线程上执行。 显式枷锁 BEGIN TRANSACTION; SELECT * FROM figures WHERE name = 'robot' AND game_id = 222 FOR UPDATE; -- 指示数据库对返回的所有结果行要加锁。 缺点：侵入应用逻辑、容易引发死锁（竞争冲突）。 自动检测更新丢失 数据库（Oracle 的串形化和 SQL Server 的快照级别隔离）可以自动检测何时发生了更新丢失，然后终止违规的那个事务。 原子比较和设置 UPDATE wiki_pages SET content = 'new_content' WHERE id = 1234 AND conetnt = 'old_content'; 冲突解决与复制 最后写入者获胜

tags: Go,Memory Model source: 更新Go内存模型 https://research.swtch.com/gomm

tags: LeetCode source: https://leetcode.com/problems/reverse-nodes-in-k-group/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { deque<ListNode*> dq; ListNode* cur = head; ListNode* top = nullptr; ListNode* tail = nullptr; bool first_k = true; while (cur != nullptr) { dq.push_front(cur); cur = cur->next; if (dq.size() == k) { // start reverse in k top = dq.front(); dq.pop_front(); // override head or connected from last k if (first_k) { head = top; first_k = false; } else { tail->next = top; } while(!dq.empty()) { top->next = dq.front(); dq.pop_front(); top = top->next; } top->next = cur; tail = top; // mark the tail of linked list } } if (!dq.empty() && tail != nullptr) { tail->next = dq.back(); } return head; } };

读-未提交 读数据时，会读到未成功提交的数据（未防止“脏读”） 写数据时，只会覆盖已成功提交的数据（防止“脏写”） 读-提交 读数据时，只会读到已成功提交的数据（防止“脏读”） 写数据时，只会覆盖已成功提交的数据（防止“脏写”） 防止脏写 通常通过推迟第二个写请求（行锁），直到前面的事务完成提交（或者终止）。 防止脏读 通过行锁同样可以避免脏读，但是实际中不可行（性能太差），一般采用类似 MVCC 的方式：对于待更新的对象，数据库都会维护其旧值和当前持锁事务将要设置的新值两个版本。 事务提交之前，其他所有读操作读旧值；仅当写事务提交之后，才会切换到读取新值。 可重复读（快照级别隔离） 在同一个事务中，反复读取总能获得一致性的结果，而不会读取到其他事务提交修改的新值。总体性想法是：每个事务都从数据库的一致性快照中读取，事务一开始所看到的是最近提交的数据，即使数据随后可能被另外一个事务更改，但保证每个事务都只看到特定时间点的旧数据。 实现快照级别隔离 MVCC 串行化

原子性（Atomicity） 一致性（Consistency） 一致性并不是数据所保证的，而是程序借助数据库的原子性和隔离性（AD）来达到一致性。一致性的 C 放到 ACID 中只是为了可以更加顺畅的宣传（读）。 隔离性（Isolation） 事务隔离级别 持久性（Durability）

事务简化程序层错误处理，将多个读写捆绑成一个操作逻辑操作单元，成功则全部成功，失败则可以进行安全重试。 深入理解事务 ACID 单对象与多对象事务操作 事务操作涉及多对象和但对象。 多对象，如更新邮件未读数和未读邮件个数 单对象，如更新一个大的字段（20KB 的 JSON） 弱隔离级别 事务隔离级别中的「读-未提交」、「读-提交」和「快照级别隔离可重复读」。 防止更新丢失 写倾斜与幻读 串行化

tags: LeetCode source: https://leetcode.com/problems/reverse-linked-list-ii/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { stack<int> st; ListNode* cur = head; ListNode* prev_start = nullptr; if (left == 1) { prev_start = new ListNode(0, head); // dummy prev_start point to head } int i = 1; while(cur != nullptr) { if (i >= left && i <= right) { st.push(cur->val); } if ((i + 1) == left) { prev_start = cur; } // move ahead i++; cur = cur->next; } if (prev_start != nullptr) { cur = prev_start->next; while (st.size() > 0) { cur->val = st.top(); cur = cur->next; st.pop(); } } return head; } };

tags: Emacs 最近换到 ivy 之后 projectile 切换项目加载 Buffer 或查找文件变得巨慢，查抄一番发现问题可以通过缓存解决： ivy-rich Projectile Caching

tags: Memory Model,Java,编程语言内存模型

tags: Java 内存模型 新模型遵循 DRF-SC 方法：保证弱有序和无数据竞争（DRF）的 Java 程序以顺序一致的方式执行。 JSR-133，在 2004 年发布的 Java 5.0 中被采用。规范：The Java Memory Model, 2005。 Java 中程序员需要同步操作建立 happens-before 关系，确保一个线程不会在另一个线程读取或写入时并发的写入非原子变量。主要的同步操作有： 同步原子（volatile）和其它操作 参见：Java 同步原子（volatile）。 有数据竞争的程序语义 弱有序和无数据竞争（DRF）只保证「无数据」竞争的程序的顺序一致性行为。新的 Java 模型（和原版本一致）出于以下原因定义了「有数据」竞争程序的顺序一致性行为： 支持Java的一般安全（security）和安全保障（safety guarantee）。 让程序员更容易发现错误。 使攻击者更难利用问题，因为由于数据竞争的原因可能造成的损失更有限。 让程序员更清楚他们的程序是做什么的 新的模型不再依赖内存一致性（coherence），取而代之的复用 happens-before（已经用于决定程序是否存在竞争）来决定竞争读写的结果。 具体规则参见：Java 决定竞争读写的具体规则。使用 happens-before 并结合Java 同步原子（volatile）就可以建立新的 happen before 关系，是对原始Java内存模型的重大改进。它为程序员提供了更多有用的保证，并使大量重要的编译器优化得到了明确的允。 happens-before 不排除语无伦次（incoherence） 以前发生的事不排除无用性（acausality）

// p and q may or may not point at the same object. int i = p.x; // ... maybe another thread writes p.x at this point ... int j = q.x; int k = p.x; 在这个程序中，公共子表达式消除（common subexpression elimination）会注意到 p.x 被计算了两次，并将最后一行优化为 k = i 。

tags: Java 内存模型,Java Java 是第一个试图写下多线程程序保证的主流语言。它包括： 互斥体（mutex），并定义了它们隐含的内存排序要求。 “volatile” 原子变量: volatile 变量的所有读和写都需要直接在主内存中按程序顺序执行，使得对 volatile 变量的操作以顺序一致的方式进行。 制定了（或者至少试图制定）具有数据竞争的程序的行为。 缺陷 Atomic 需要同步：volatile 原子变量是不同步的，所以它们无助于消除程序其余部分的竞争。不能用于构建新的同步原语。 一致性与编译器优化不兼容：Java 编译器公共子表达式消除（common subexpression elimination）会导致其他线程写入新值无法对消除后表达式生效。

保证了弱有序和无数据竞争（DRF）的系统会提供称为同步的特定指令，提供一种协调不同处理器（相当于硬件线程）的属性。

原子变量（atomic variable）或原子操作（tomic operation）更好的解释。

现代语言以原子变量（atomic variable）或原子操作（atomic operation）的形式提供特殊能力，允许程序同步其线程(参见硬件内存一致性模型)。 代码示例 // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); 如果使用原子变量实现 done 会产生很多效果： Thread 1 的编译代码必须确保对 x 的写入完成，并且对 done 的写入可见之前对 x 的写入对其他线程可见。 Thread 2 的编译代码必须在循环的每次迭代中（重新）读取 done 。 Thread 2 的编译代码必须在读取 done 之后才读取 x 。 编译后的代码必须做任何必要的事情来禁用可能会重新引入这些问题的硬件优化。 使 done 原子化的最终结果是程序按照我们想要的方式运行，成功地将 x 的值从 Thread 1 传递到 Thread 2 。 上面代码如果不使用原子变量会出现 Thread 1 和 Thread 2 读取 x 的同时写 x ，从而导致数据竞争（data race)。 done 使用原子变量实现后，用于同步对 x 的访问： Thread 1 现在不可能在 Thread 2 读取 x 的同时写 x，从而避免数据竞争。 这是硬件内存模型弱有序和无数据竞争（DRF）在编程语言环境的应用。 ...

弱有序是 Sarita Adve 和 Mark Hill 在他们 1990 年的论文 Weak Ordering - A New Definition (1990) 提出。 定义如下 Let a synchronization model be a set of constraints on memory accesses that specify how and when synchronization needs to be done. 同步模型是对内存访问的一组约束，这些约束指定了何时以及如何进行同步。 硬件相对于同步模型是弱有序的，当且仅当它在顺序上与遵守同步模型的所有软件一致时。 Adve和Hill提出了一种同步模型，他们称之为无数据竞争(data-race-free，DRF)。该模型假设硬件具有独立于普通内存读写的内存同步操作。普通的内存读写可以在同步操作之间重新排序，但不能在跨它们移动。(也就是说，同步操作也可用来做重新排序的内存屏障。)如果对于所有理想化的顺序一致的执行，从不同线程对同一位置的任何两个普通存储器访问要么都是读取，要么通过同步操作强制一个在另一个之前发生而分开执行，则程序被称为无数据竞争的。

ARM和POWER系统的概念模型是，每个处理器从其自己的完整内存副本中读取和向其写入，每个写入独立地传播到其他处理器，随着写入的传播，允许重新排序。 在这个宽松的(relaxed)模型中，我们迄今为止所看到的每一个litmus test的答案都是“yes，这真的可能发生。” Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. On ARM/POWER: yes! Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): yes! On ARM/POWER: yes! Litmus Test: Independent Reads of Independent Writes (IRIW) Can this program see r1 = 1, r2 = 0, r3 = 1, r4 = 0? (Can Threads 3 and 4 see x and y change in different orders?) // Thread 1 // Thread 2 // Thread 3 // Thread 4 x = 1 y = 1 r1 = x r3 = y r2 = y r4 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. On ARM/POWER: yes! Litmus Test: Load Buffering Can this program see r1 = 1, r2 = 1? (Can each thread's read happen after the other thread's write?) // Thread 1 // Thread 2 r1 = x r2 = y y = 1 x = 1 On sequentially consistent hardware: no. On x86 (or other TSO): no. On ARM/POWER: yes!

内存屏障（或栅栏）是非顺序一致性的硬件提供的一种显式指令，用于控制排序提供更强的内存排序，修复同步算法。 添加内存屏障，确保每个线程在开始读取之前都会刷新其先前对内存的写入： // Thread 1 // Thread 2 x = 1 y = 1 barrier barrier r1 = y r2 = x x86 总存储有序（x86-TSO) 加上内存屏障之后 r1=0, r2=0 就会变得不可能。

x86 总存储有序(x86 Total Store Order, x86-TSO)：所有处理器仍然连接到一个共享内存，但是每个处理器都将对该内存的写入(write)放入到本地写入队列中。处理器继续执行新指令，同时写操作(write)会更新到这个共享内存。一个处理器上的内存读取在查询主内存之前会查询本地写队列，但它看不到其他处理器上的写队列。其效果就是当前处理器比其他处理器会先看到自己的写操作。 重要的是： 所有处理器都保证写入（存储 store）到共享内存的（总）顺序，所以给这个模型起了个名字：总存储有序（Total Store Order，TSO）。 写队列是一个标准的先进先出队列：内存写操作总是以与处理器执行相同顺序的应用于共享内存。 基于以上下面 litmus test 的答案依然是 no ，这种情况与顺序一致性模型结果一致： Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. 但其他测试则并不一致区分与顺序一致性的常用例子: Litmus Test: Write Queue (also called Store Buffer) Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): yes! TSO 系统中，线程 1和 2 可能会将它们的写操作排队，然后任何一个写操作进入内存之前从内存中读取，这两个读操作都会看到零。但是任何顺序一致的执行中， x=1 或 y=1 必会有一个首先生效。 ...

下面这种关于样本结果的问题被称为 litmus test 。它只有两个答案：可能还是不可能？为我们提供了一种区分内存一致性模型的清晰方法：如果一个模型支持特定的执行，而另一个不支持，那么这两个模型显然不同。 litmus test 假设所有变量都初始为 0 ， rN 表示非共享变量，而是一个线程本地寄存器。 Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x 然而不幸的是，一个特定的模型对一个特定的 litmus test 给出的答案往往令人惊讶。

Leslie Lamport 1979 年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 定义： The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called sequentially consistent. ...

tags: 一致性，Memory Model 当执行给定程序时，硬件和编译器之间的契约，对编译后后的代码对存储在内存中的数据更改的可见性和一致性。 这种契约称为「内存一致性模型（Memeory Consistency Model）」或仅仅是「内存模型（Memory Model）」。 最初目标是定义程序员编写汇编代码时硬件提供的保证，后来用来定义高级编程语言（如 C++ 或 Java）对该语言编写代码的程序员提供的保证。 例如下面变量都初始为 0 的情况下，线程 1 和 2 都运行在自己专用的处理器上，都运行到完成，这个程序能打印 0 吗？ // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); Memory coherence vs consistency 内存一致性（coherence） 内存顺序一致性（sequential consistency） 硬件 顺序一致性 x86 总存储有序（x86-TSO) ARM/POWER Relaxed Memory Model 弱有序和无数据竞争（DRF） 编程语言内存模型

tags: Memory Model,Computer Systems Hardware Memory Models 硬件内存模型 内存模型 内存一致性模型

tags: Emacs 优化 GC 参考：LSP Mode Performance ;; Optmization ;; Sources: ;; ;; - https://www.reddit.com/r/emacs/comments/ofhket/further_boost_start_up_time_with_a_simple_tweak/ ;; - https://emacs-lsp.github.io/lsp-mode/page/performance/ ;; (setq gc-cons-threshold 32000000) ;; 32mb (setq read-process-output-max (* 1024 1024)) ;; 1mb 将启动速度优化到 3 秒左右。 Dumping Emacs Emacs WIKI: Dumping Emacs Painless Transition to Portable Dumper

为什么不用取模？ 节点数发生变化时，会导致很多关键字需要做节点数据迁移，会大大增加再平衡的成本。 固定数量的分区 创建远超实际节点数的分区数量，然后再为每个节点分配多个分区。 新加入节点 从现有的节点上匀走几个分区，直到分区再次达到平衡。 删除节点 采取和上面相反的过程。 优点 分区总数量不变，也不会改变关键字的分区映射关系。 唯一需要调整的分区与节点的映射关系。 分区和节点的映射关系调整可以逐步完成。 缺点 分区数量需要数据库创建时确定，并不能更改 动态分区 分区数据增长超过一个可配参数的阈值（HBase 10GB），它就拆分为两个分区，相反则合并相邻的分区。过程类似B-trees 的分裂操作。 每个分区总是分配一个节点，一个节点可以承载多个分区。 分区分裂 将其中的一半转移到其他节点以平衡负载。 优点 分区数量可以自动适配数据总量。 空数据库可以配置初始分区解决少量数据集就一个分区避免系统热点（HBase 和 MongoDB） 按节点比例分区 使分区数与集群节点数成正比关系（Cassandra 和 Ketama），就是每个节点具有固定数量的分区。 当节点数不变时，每个分区的大小与数据集大小保持正比增长关系。 新加入节点 随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量。 优点 较大的数据可以使每个分区的大小保持稳定。 缺点 存在不公平分裂。

对所有数据构建全局索引，为了避免瓶颈，对索引本身进行分区，比如： 将 a～r 开始的关键字放在分区 0 将 s～z 开始的关键字放在分区 1 优点 可以支持高效的区间查询 读取更为高效 缺点 写入速度慢，会引入明显的写入放大 写入逻辑复杂 难以保证索引时刻最新，需要跨多个相关分区的分布式事务支持 实践 对全局二级索引的更新往往都是异步的。

每个分区各自维护自身的二级索引，读取时需要对所有分区节点进行查询然后对结果进行合并。 这种方法虽然二级索引查询代价高，但依然广泛用于实践：MongoDB、Riak、Cassandra、ElasticSearch、SolrCloud 和 VoltDB。

可以基于关键值哈希函数的方式分区，解决基于关键字区间分区数据倾斜与热点的问题。一个好的哈希函数可以处理数据倾斜并使其均匀分布，并且不需要在加密方面很强。 优点 这种方法可以很好的将关键字均匀分配到多个分区中。 缺点 丧失良好的区间查询性能。即使关键字相邻，也会分布在不同的分区上。

为每个分区分配一段连续的关键字或者关键字区间范围。

负载倾斜会导致所有负载都集中在一个分区节点上，这种负载严重不成比例的分区即称为系统热点。 应用层解决 即使通过基于关键字哈希值分区和基于关键字区间分区等策略解决了大部分热点问题，但是极端情况下依然会出现热点，比如社交媒体的热点时间都会导致热点，只能通过应用层解决，一个简单的技术： 关键字开头或结尾添加一个随机数，两位随机数就可以将关键字的写操作分布到 100 个不同的分区上； 读取就必须从所有的 1000 个关键字中读取数据然后进行合并； 通过额外的元数据标记哪些关键字进行了特殊处理。 由于对读取造成的额外开销，所以通常只有对少量的热点关键词附加随机数才有意义。

分区不均匀时出现某些分区节点比其他分区承担更多的数据量和查询负载。倾斜会导致分区效率严重下降。

每一条数据都属于特定的分区，每个分区都是一个小型数据库。 目的 提高扩展性，分散大的数据集和查询负载。 目标 将数据和查询负载均匀的分步在所有节点上。如果分布不均匀会出现负载倾斜和系统热点。 数据分区与数据复制 结合数据复制每个分区在多个节点都有副本，进行冗余提高可用性。 键-值数据的分区 避免系统热点最简单的方法是将记录随机分配给所有节点上，缺点是：没办法知道数据保存在哪个节点上，所以读取时需要查询所有节点。 基于关键字区间分区 基于关键字哈希值分区 负载倾斜与系统热点 分区与二级索引 二级索引不能唯一标识一条记录，比如查询颜色为红色的汽车。二级索引带来的主要挑战是它们不能规整的映射到分区中。 有两种方法来支持对二级索引进行分区： 基于文档分区的二级索引 基于词条的二级索引分区 分区再平衡 动态再平衡策略 自动与手动再平衡操作 请求路由 策略 客户端可以连接任意节点，并由节点做转发不在当前节点的分区请求。 由路由层来充当分区感知的负载均衡器。 客户端直接感知分区和节点分配关系，客户端直连目标节点。 做出路由决策的组件 Zookeeper gossip 协议

syn::Span 代码位置

循环展开 let fields = vec![ syn::Ident::new("foo", syn::Span::call_site()), syn::Ident::new("bar", syn::Span::call_site()), ]; let token = quote!{ #(#fields),* }; // -> foo,bar

准备 解析宏通过两个 crate 进行： quote = “1.0” syn = “1.0” Derive 属性宏 探讨 Rust 宏系统中带属性（Attributes）的 Derive 宏的几种变体，以及如何进行解析。 属性宏的变体 函数调用 #[derive(Custom)] struct Demo { #[attr(arg)] a: i8, } 关键字参数调用 #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 直接赋值 #[derive(Custom)] struct Demo { #[meta = "val"] c: i8, } 函数调用 关键字参数调用 可以从 Struct 解析出各个字段，通过解析各个字段的 attrs 属性，并对 attrs 进行遍历，使用 attr.parse_args()? 即可解析出对应的关键字参数，咱们以前面的代码为例: #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 对应的解析代码为： ...

确定前后关系 服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，并将新版本号与写入值一起保存。 当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写入之前，客户端必须先发送读请求。 客户端写主键，写请求必须包含之前读到的版本号，读到的值和新值合并后的集合。写请求的响应可以像读操作一样，会返回所有当前值，这样可以一步步链接起多个写入的值。 当服务器收到带有特定版本号的写入时，覆盖该版本号或者更低版本的所有值，但必须保存更高版本号所有值。 当写请求包含了前一次读取的版本号时，意味着修改时基于以前的状态。否则它将与所有的其他写入同时进行，不会覆盖任何已有值，其传入的值将包含在后续读请求的返回值列表中。 合并同时写入的值 上面算法不会导致数据丢失，但是客户端需要做一些额外的工作：如果多个操作并发发生，则客户端必须通过合并并发写入的值来继承旧值。同时删除需要特殊的墓碑标记，防止被合并回去。 版本矢量 每个副本和每个主键均定义一个版本号，每个副本在处理时增加自己的版本号，并跟踪从其他副本看到的版本号。通过这些信息来指示要覆盖那些值，该保留那些并发值。 所有的版本号集合称为版本矢量。

LWW：最后写入者获胜 Happens-before 关系和并发

当节点不能满足 \(w + r > n\) 时将写请求暂时写入一些可访问的临时节点中，一旦网络问题得到交接，临时节点需要把接收的写入全部发送到原始主节点上。这就是所谓的数据回传（或者暗示移交）。

tags: 一致性 确定读写成功 确定读写节点在多少节点成功才可以认为写入成功：需要保证读取时至少一个包含新值。 n 个副本的情况下，写入需要 \(w\) 个节点确认，读取必须至少查询 \(r\) 个节点，则只要 \(w + r > n\) ，读取的节点中一定会包含最新值。 \(w\) 仲裁写（法定票数写） \(r\) 仲裁读（法定票说读） 一般 \(n\) 设置为奇数： \(w=r=(n+1)/2\) （向上取整）。 可容忍的失效节点数 仲裁条件 \(w+r>n\) 定义了系统可容忍的失效节点数。 \(w<n\) ，如果一个节点不可用，仍然可以处理写入。 \(r<n\) ，如果一个节点不可用，仍然可以处理读取。 \(n=3\),\(w=2\),\(r=2\)，则可以容忍一个节点不可用 \(n=5\),\(w=3\),\(r=3\), 则可以容忍两个节点不可用 局限性 如果采用了 sloppy quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证写请求一定存在重叠的节点。 并发无法明确顺序，需要进行合并并发写入。如最后写入者获胜。 同时读写，写操作在一部分节点上完成，则读取新值还是旧值存在不确定性。 部分节点写入成功，但是最终写入失败无法回滚。 新值的节点失效，但恢复数据来自某个旧值，则总的新值节点数低于 w 边界情况

没有主节点，允许任何节点接受来自客户端的写请求。 实现方式 客户端直接将其写请求发送到多节点 一个协调者代表客户端进行写入，与主节点的数据库不同，协调者并不负责写入顺序的维护。 节点失效时写入数据库 客户端将写请求并行发送给三个节点，两个可用节点接受写请求，而不可用副本则无法处理该请求。 现在失效的节点重新上线，客户端可能会读取到旧的值。 为了解决这个问题客户端并行的向多个节点发送读请求，并通过版本号来确定哪个值更新。 读修复与反熵 读修复；客户端并行读取多个节点，检测到过期的返回值，然后用新的返回值写入到返回旧值的副本。 反熵过程：后台不断查找副本之间的差异，将任何缺少的数据从一个节点复制到另一个节点。不保证特定顺序的复制写入，并且会引入明显的复制滞后问题。 Quorum 一致性 检测并发写

最常见的拓扑结构，提供更好的容错。每个节点从其他所有节点同步写入。

通过指定一个根节点，根结点将所有的写操作转发给其他所有节点。

每个节点接收来自前序节点的写入，并将这些写入（加上字节的写入）转发后后序节点。同时通过唯一 ID 防止无限循环。

每个副本总是保存最新值，允许覆盖并丢弃旧值。假定每个写请求都最终同步到所有副本，只要我们有一个明确的方法来确定哪个写入时最新的，则副本可以最终收敛到相同的值。 通过每个请求附加一个时间戳，选择最新即最大的时间戳，丢弃较早的写入。则为最后写入着获胜（last write wins，LWW）。 缺点 会造成数据丢失。 适用场景 缓存系统。 确保安全无副作用 唯一方法是只写入一次然后写入值视为不可变，这样旧避免对同一个主键的并发（覆盖）写。

多个主节点看到的执行顺序不一致，病了同时按照各自看到的写入顺序执行，那么数据库最终将处于不一致状态。 数据库必须以一种趋同的方式来解决冲突。 可能的解决方式 给每个写入分配唯一的 ID，如基于时间戳的最后写入者获胜。 为每个主节点分配一个唯一 ID，序列号高的优先于序列号低的主节点，可能导致数据丢失 以某种方式合并值，如按照字母顺序拼接在一起 利用预定义号的格式记录，然后依靠应用层逻辑，事后解决冲突（可能会提示用户）