Notes

tags: LeetCode source: https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题：会有不同顺序但是元素相同的数组，如何快速高效的进行过滤？ ...

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens-ii/ 参见：LeetCode: 51. N-Queens

tags: Algorithm,Brute Force Approach

tags: 技术概念 创业公司有：积梦智能。

tags: 技术概念

tags: 技术概念

tags: 技术 目前互联网领域里比较热门的概念和方向。

tags: 技术概念

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置，那么横轴、纵轴、对角线都不再允许放置。我们按行进行遍历，所以我们需要跟踪以下位置是否已经放置 Queue： 纵轴（Column）：cols 主对角线（Positive Diagonal）：posDiag 次对角线（Negative Diagonal）：negDiag 纵轴很好记录，但是对角线比较困难，我们先来看一下对角线的特征，假设横轴为 r 纵轴为 c ， r - c 在正对角线是一致的： 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res.push_back(track); return; } for (int c = 0; c < n; c++) { if (cols.find(c) != cols.end() || posDiag.find(r - c) != posDiag.end() || negDiag.find(r + c) != negDiag.end()) { continue; } cols.insert(c); posDiag.insert(r - c); negDiag.insert(r + c); track[r][c] = 'Q'; backtracking(r + 1, n); track[r][c] = '.'; cols.erase(c); posDiag.erase(r - c); negDiag.erase(r + c); } } }; 结果 ...

tags: 分布式共识,Paxos

tags: 分布式共识

tags: 分布式共识,分布式

tags: 共识算法，分布式共识

tags: Incomplete，分布式，共识算法

tags: 分布式,Incomplete

利用底层指令集实现比较设置等原子操作。 See also：https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2

tags: GDB,macOS macOS 下通过 GDB 调试程序会出现： Unable to find Mach task port for process-id 1375: (os/kern) failure (0x5). (please check gdb is codesigned - see taskgated(8)) 需要通过 Keychain Access Application 创建证书： code-sign-cert 需要对 gdb 进行签名，首先创建 gdb-entitlement.xml ： <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> <plist version="1.0"> <dict> <key>com.apple.security.cs.debugger</key> <true/> </dict> 运行签名 codesign --entitlements gdb-entitlement.xml -fs code-sign-cert $(which gdb) See also: PermissionsDarwin。

偏序集合（英语：Partiallyordered set，简写poset）是数学中，特别是序理论中，指配备了部分排序关系的集合。 这 See also: 偏序关系

CAP 最初作为一个经验法则提出（20 世纪 70 年代），并没有准确的定义，目的也只是帮助大家深入探讨数据库设计的权衡之道。它由 Eric Brewer 于 2000 年正式命名。 解释一 CAP 定理：不要求线性化的应用更能容忍网络故障。 只要不可靠才诶黄哦，都会发生违背线性化的风险。我们可以做如下权衡： 如果应用要求线性化，一旦发生网络分区，则必须等待网络修复，或者直接返回错误。结果为服务不可用（保证一致性或者线性化）。 如果应用不要求线性化，且每个可副本独立处理请求。此时服务可用，但结果行为不符合线性化（保证高可用）。 解释二 一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。系统只能支持两个特性。 这里的分区指网络分区（即网络故障）。 不过，这种理解存在误导性，网络分区是一种故障，不管喜欢还是不喜欢，它都可能发生，所以无法选择或逃避分区问题。 网络正常的时候，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，必须要么选择线性（一致性），要么可用性。 也就是“网络分区的情况下”是选择一致还是可用。

tags: 分布式共识,一致性 一致性保证 分布式一致性主要针对延迟和故障等问题来协调副本之间的状态。 线性化：最强一致性模型 顺序保证：保证时间顺序，特别是因果关系和全局顺序 最终一致性：一种非常弱的保证，参见最终一致性效应 可线性化 分布式语义下对寄存器（单个对象）顺序的读写。应区别与可串行化。 可串行化针对不同事务的隔离，用来确保事务执行的结果与串形执行的结果相同 可线性化是读写寄存器（单个对象）的最新值的保证。 线性化依赖的条件 加锁与主节点选举 每个启动节点都试图获得锁，其中只有一个可以成功成为主节点。通过加锁来保证主节点选举「线性化」。 约束与唯一性保证 同一个用户名、电子邮件或系统中文件名需要唯一性的保证，也应该进行「线性化」。 跨通道的时间依赖 系统中存在其他通信渠道也需要「线性化」。 实现线性化系统 主从复制（部分支持可线性化） 共识算法（可线性化） 多主复制（不可线性化） 无主复制（可能不可线性化） 线性化与Quorum 一致性 Dynamo 风格的复制模型，读写遵从严格的 quorum 是无法支持可线性化的。 线性化的代价 多主复制和主从复制，网络中断都会导致同步暂停，从而无法保证客户端要求的线性化读写。 CAP 理论 可线性化与网络延迟 很少有系统真正满足线性化，现代多个 CPU 对同一个内存地址的读写都不能满足（参见硬件内存模型），如果需要强一致则需要内存屏障（栅栏）指令。 之所以放弃线性化的原因就是性能，而不是为了容错。由于网络延迟的不确定性，无论是否发生网络故障，线性化对性能的影响都是巨大的。 顺序保证 顺序与因果关系 顺序有助于保持因果关系。 因果顺序并非全序：因果关系是小范围集合的偏序，可线性化是一个全序操作。 可线性化强于因果一致性 捕获因果依赖关系：检测并发写 序列号排序 非因果序列发生器 适用于系统不存在唯一主节点。 每个节点都独立产生自己的一组序列号：一个奇数一个偶数，或者切入节点唯一标识符。 用足够高的分辨率的墙上时间戳附加到每个操作上。 预先分配区间范围，并及时扩容。 Lamport 时间戳 可以产生因果关系一致的序列号。Lamport 时间戳是一个值对 （计数器，节点 ID） ： 节点 ID：每个节点都有一个唯一标志符。 计数器：每个节点都有一个计数器记录各自处理的请求总数。 优点： 两个节点可能存在相同的计数器，但是时间戳中的节点 ID 可以确保每个时间戳都是唯一的。 保证全序：比较两个 Lamport 时间戳，计数器较大的时间戳越大，计数器相同则节点 ID 大的那个时间戳越大。 通过节点排序保证了全局因果关系。Lamport 不同于版本矢量： 版本矢量用以区分两个操作是并发还是因果依赖。 Lamport 时间戳主要用于确保全序关系。 时间戳依然不够 某些场景下全序关系依然不能满足需求，比如用户名唯一性要求，为了确认用户名唯一，需要获取所有节点正在进行的请求，查看有没有相同的用户名请求，才能建立全序关系。 ...

节点撒谎伪造 Fencing 令牌，或者部分节点故障、不遵从协议、干扰网络或者恶意攻击，则为「拜占庭故障」。 如果系统仍可以继续运行，那么我们称之为「拜占庭式容错系统」。

Fencing（围栏）锁，每次锁服务授予锁时，同时返回 fencing 令牌，每次客户端发送写请求，都必须包含所持有的 fencing 令牌。 fencing 令牌单调递增，如果低版本的写入后到达，发现已经有高版本的 fencing 令牌写入，则拒绝此次写入。

墙上时钟 根据某个日历返回当前的日期与时间。 Linux 上的 clock_gettime(CLOCK_REALTIME) Java 中的 System.currentTimeMills() 会返回 1970-01-01（UTC）的时间戳（秒和毫秒）。 墙上时钟会和 NTP 服务器同步产生跳跃导致一些奇怪的问题。 单调时钟 更适合测量持续时间段（时间间隔），如超时或服务的响应时间。保证总是向前（不会出现墙上时钟的回拨现象）。 Linux 上的 clock_gettime(CLOCK_MONOTONIC) Java 中的 System.nanoTime() 单调时钟多个节点的对比没有任何意义，多路 CPU 可能有单独的计时器，且不与其他 CPU 进行同步。由操作系统进行补偿它们之间的偏差。 NTP 检测到本地石英比时间服务器更快或者更慢，NTP 会调整本地石英的震动频率（摆动），最大幅度为 0.05%。 NTP 并不会直接调整单调时钟向前或回拨 。

tags: LeetCode,backtracking 视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo 在 LeetCode: 46. Permutations 的基础上增加重复的元素。感觉不能依赖于 track + map 的去重逻辑回溯。 class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; } }; 数据特征： Value: 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, Index: 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> ret; int n, i; vector<vector<int>> perms; if (nums.size() == 1) { ret.push_back(nums); return ret; } for (i = 0; i < nums.size(); i++) { n = nums.back(); nums.pop_back(); perms = permuteUnique(nums); for (auto perm : perms) { perm.push_back(n); res.insert(perm); } nums.insert(nums.begin(), n); } for (auto r : res) { ret.push_back(r); } return ret; } };

tags: 分布式 故障与部分失效 单节点一般是要么工作要么失效，但是分布式系统多节点面临部分失效，大大提高了分布式系统的复杂性。 单节点软件特性： 硬件正常工作时，相同的操作通常总会产生相同的结果，即确定性。 如果发生了某种内部错误，我们宁愿使计算机全部崩溃，而不是返回一个错误的结果。 云计算和超算 超算：垂直扩展的极端，设置检查点，一点节点故障则全部失效从上一个检查点重新开始（离线批处理），类似单机上内核崩溃。 云计算：水平扩展的极端 传统企业位于两个极端的中间 分布式可靠必然面临部分失效，需要依赖软件系统来提供容错机制。我们需要在不可靠的组件上构建可靠的系统。 不可靠网络 分布式无共享系统：成本低廉。 互联网以及大多数 IDC 内部网络都是异步网络：不保证发送一定到达（排队），等待响应时可能出现任何错误。 现实中的网络故障非常普遍 故障检测：HA、主从切换、保活机制（ICMP，SYN） 超时与无限期的延迟 网络拥塞与排队 网络负载过高会出现拥塞。 数据在发送的过程中分别会在发送端和接收端进行排队：等待发送和等待处理。 TCP 的拥塞控制机制。 虚拟化 CPU 核切换虚拟机 同步与异步网络 同步网络：固定电话网络，一路电话分配固定的电路、有带宽保证，规定延迟内保证完成数据包发送，不会丢弃数据包，成本高，利用率低 异步网络：数据中心网络，共享带宽，无法保证延迟和数据包发送，成本低廉，利用率高 不可靠时钟 单调时钟与墙上时钟 时间同步与准确性 计算机中的石英钟不够精确 NTP 服务器不稳定（网络、防火墙或服务本身） 虚拟机中时钟是虚拟化的。 终端设备不可控：休眠、故意设置 依赖同步的时钟 时钟陷阱： 一天可能不总是 86400 秒 回拨 多个节点上的时间完全不相同 需要精确同步的时钟： 自己监控所有节点上的时钟偏差 某个节点时钟漂移超出上限则将其宣告失效 时间戳与时间顺序 最后写入者获胜 时钟的置信区间 通过直接安装 GPS 接收器或原子（铯）时钟，它的误差范围通常可以查询制造商手册。 全局快照的同步时钟 Google Spanner 根据部署了 GPS 接收器或者原子时钟的 TrueTime API 返回的时钟置信区间。确保读事务足够晚发生，避免与先前事务的置信区间产生重叠。 进程暂停 垃圾回收 虚拟化暂停虚拟机 磁盘 I/O 内存交换分区 手动暂停进程（SIGSTOP/SIGCONT） 响应时间保证 RTOS 系统 调整垃圾回收的影响 知识，真相与谎言 真相由多数决定：Quorum 一致性 主节点与锁 Fencing 令牌 拜占庭故障 理论系统模型与现实 计时方面 ...

tags: LeetCode,backtracking Keywords backtrack 回溯算法 图解 举例： [1, 2, 3] ，顺着叶子节点和删除的节点就可以还原成全排列。 从上面图可以看出来，叶子节点加上回溯路径上被移除的节点就是结果的一项，从左到右依次是： [3,R:2,R:1] -> [3,2,1] [2,R:3,R:1] -> [2,3,1] … class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> track; backtrack(res, track, nums); return res; } void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); i++) { if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) { continue; } track.push_back(nums[i]); visited[nums[i]] = true; // go into next level backtrack(res, track, nums); visited[nums[i]] = false; track.pop_back(); } } private: map<int, bool> visited; }; 根据视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo ...

tags: 编程语言内存模型,JavaScript litmus test Litmus Test: ES2017 racy reads on ARMv8 Can this program (using atomics) see r1 = 0, r2 = 1? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y x = 2 (non-atomic) r2 = x C++: yes (data race, can do anything at all). Java: the program cannot be written. ARMv8 using ldar/stlr: yes. ES2017: no! (contradicting ARMv8)

tags: Rust,Swift,编程语言内存模型 都采用C++11 内存模型。

tags: C++11 内存模型,C/C++ C++ 还添加了较弱的原子，可以使用 atomic_store_explicit 和 atomic_load_explicit 以及附加的n内存排序参数来访问这些原子。使用 memory_order_seq_cst 使显式调用等效于C++ 同步原子（atomic）较短的调用。 较弱的原子称为 acquire/release 原子，一个 release 如果被后来的 acquire 观察到，那么就创建了一个 happen-before 的关系(从 release 到 acquire)。这个术语意在唤起 mutex:release 就像 unlock mutex ， acquire 就像锁定同一个 mutex 。release 之前执行的写入必须对后续 acquire 之后执行的读取可见，就像解锁 mutex 之前执行的写入必须对后解锁 mutex 之后执行的读取可见一样。 atomic<int> done; // Thread 1 // Thread 2 atomic_store(&done, 1, memory_order_release); while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ } acquire/release 原子只对单个内存位置的操作进行顺序一致的交替执行，所以属于内存一致性（coherence）而非顺序一致性。 来看下面 litmus test： 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! On Java (using volatiles): no. On C++11 (sequentially consistent atomics): no. On C++11 (acquire/release atomics): yes!

tags: C++11 内存模型,C/C++ C++ 并没有仅仅停留在内存一致性（coherence）的C++ 弱同步原子（acquire/release atomic）。它还引入了非同步原子，称为 relaxed 原子（memory_order_relaxed）。这些原子根本没有同步效果——它们没有创建先发生的边——并且它们根本没有排序保证。事实上，宽松原子读_写和普通读_写没有区别，除了宽松原子上的竞争不被认为是竞争， 不能着火 。

tags: C++11 内存模型 C++ 采用了顺序一致的原子变量，很像Java 同步原子（volatile）(与 C++ volatile 没有关系）。 atomic<int> done; // Thread 1 // Thread 2 atomic_store(&done, 1); while(atomic_load(&done) == 0) { /* loop */ } C++ 弱同步原子（acquire/release atomic）

tags: C++11 内存模型 与 Java 不同，C++ 没有给有竞争的程序任何保证。任何有竞争的程序都属于“未定义的行为”。允许在程序执行的最初几微秒内进行竞争访问，从而在几小时或几天后导致任意的错误行为。这通常被称为“DRF-SC或着火”：如果程序没有数据竞争，它以顺序一致的方式运行，如果有数据竞争，它可以做任何事情，包括着火。

tags: C/C++,Memory Model,编程语言内存模型 受新的 Java 内存模型（2004）许多同样的人开始为 C++ 定义一个类似的内存模型，最终在 C++11 中采用。 两个重要方便的差异： C++ 对具有数据竞争的程序不做任何保证 C++ 提供了三种原子性：强同步（顺序一致性），弱同步（内存一致性（coherence））和无同步（“relaxed”，用于隐藏竞争）。 第一点尝试消除对 Java 模型的复杂性需求，“relaxed” 的原子性重新引入 Java 关于定义什么是竞争程序的所有复杂性。结果是C++模型比Java更复杂，但对程序员的帮助更小。

线程的创建前置于（happens bofere）线程的第一个动作。 互斥体 m 的解锁前置于（happens before）任何 后续（subsequent） 对互斥体 m 的锁定。 volatile 变量 v 的写入前置于（happens bofere）任何 后续（subsequent） 对变量 v 的读取。 “后续（subsequent）” 意味着什么？Java 定义了所有锁定、解锁和 volatile 变量访问的行为，给出了整个程序中所有这些操作的总顺序，就像它们发生在某个顺序一致的交错中一样。“后续（subsequent）”指在总顺序中较晚执行。也就是说：锁定、解锁和 volatile 变量的访问的“总顺序”定义了“后续”的含义，“后续”定义了由特定执行创建的“前置于（happens before）”关系，最终“前置于（happens before）”关系定义了该特定执行是否存在数据竞争。如果没有数据竞争，那么执行就会以顺序一致的方式进行。 事实上， volatile 访问必须表现得像在某种总排序一样，意味这在下面 litmus test 中，不能出现 r1=0 和 r2=0 的结果: 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! On Java using volatiles: no. Java 中对 volatile 变量 x 和 y 的读写不能被重新排序：一个线程的写入一定会同步到第二个，紧随着第二个的写入的读取就一定能看到第一个写入。

对于小于等于 word 大小的变量，对变量（或字段） x 的读取必须看到对 x 的某一次写入所存储的值。 如果读取 r 观察到对 x 的写入 w ，那么 r 不发生在 w 之前。 也就是说 r 可以观察发生在 r 之前的所有写入，并且可以观察与 r 竞争的写入。

See also: 顺序一致性。

tags: Memory Model，一致性 FROM 硬件内存模型： threads in the system must agree about a total order for the writes to a single memory location. That is, threads must agree which writes overwrite other writes. This property is called called coherence. 内存一致性的系统都所有线程都必须接受对一个内存地址所有写入的总顺序。换句话说，所有线程必须同意哪些写入可以覆盖另外的一些写入。

Coherence deals with maintaining a global order in which writes to a single location or single variable are seen by all processors. Consistency deals with the ordering of operations to multiple locations with respect to all processors. Memory coherence: a memory system is coherent if any read of a data item returns the most recently written value of that data item (what values can be returned by a read). Memory consistency: A memory consistency model for a shared address space specifies constraints on the order in which memory operations must appear to be performed (i.e. to become visible to the processors) with respect to one another.(when a written value will be returned/seen by a read). ...

悲观并发控制 两阶段加锁是一个典型的悲观并发控制。设计原则：如果某些操作可能出错，则直接放弃等待直到安全。 乐观并发控制 如果可能发生潜在冲突，事务会继续执行而不是终止，寄希望与相安无事；而当事务提交时，数据库会检查是否发生了冲突，如果是的话，中止事务并接下来重试。 对比 如果冲突很多则性能不佳，如果性能良好，且事务之间的竞争不大，乐观并发控制会比悲观方式性能高很多。

可串形化的快照隔离（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）