Chapter 3 Types Arrays 不支持动态开数组： // an array of 100 int32 elements, all set to 1 let mut arr1 = [1;100]; // correct let n = 100; let mur arr2 = [1;c]; // error Vectors let mut arr = vec![0,6,4,8,1]; arr.sort() // increasing order arr.sort_by(|a,b| b.cmp(a)) // decreasing order If you know the number of elements a vector will need in advance, instead of Vec::new you can call Vec::with_capacity to create a vector with a buffer large enough to hold them all, right from the start. ...

最近在写毕设项目时，总是发现有些单元测试在 VSCode 的 Testing Panel 连续运行测试时无法通过，但是单独运行时能正常通过，困扰了我好长一段时间。 有一次我发现了一个盲点： 在我写的框架中，有一个 config.go 文件： var Config = config{ LeaseTime: 1000 * time.Millisecond, MaxRecordLength: 2, IdGenerator: NewIncrementalGenerator(), Serializer: serializer.NewJSONSerializer(), LogLevel: zapcore.InfoLevel, } 当我从 Testing Panel 连续运行测试时，不同的测试都会复用 IdGenerator。 从网上查了资料后，才知道： The behavior you’re seeing is expected because Config is a global variable and it’s shared across the entire package. This means that state, such as the current ID from your NewIncrementalGenerator (), is preserved and reused across all your tests running within the same package. Go runs test functions (those starting with Test) in parallel by default, but within a single test package, they all share the same memory space. Therefore, global variables will persist their state across individual tests within that package. ...

Background 最近在看分布式事务相关的论文，很多论文设计的系统中都实现的是快照隔离这一层次的机制，其中 Epoxy 最为典型，直接把 Postgres 的快照隔离机制在中间层重新实现了一遍。 之前看关于 Postgres 快照隔离机制的文章，找到了这个：PostgreSQL并发控制，讲得非常好，逻辑非常清晰，理论和实际例子相结合。 这篇文章中关于 Visibility Check Rules 的部分讲的非常详细，但是没啥规律，可归纳性不强，我时不时就会回来看看这一段，但每次看的时候好像都要从头再重新理解一遍，于是最近我整理了一下这十条规则，力求达到清晰有序。 Rules 我先把原文中提到的十条规则列出来，方便下文做参考。 可以把这些规则简单地按照 t_xmin 的状态分为三部分： Status of t_xmin is ABORTED: Rule 1: If Status (t_xmin) = ABORTED ⇒ Invisible Status of t_xmin is IN_PROGRESS: Rule 2: If Status (t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax = INVAILD ⇒ Visible Rule 3: If Status (t_xmin) = IN_PROGRESS ∧ t_xmin = current_txid ∧ t_xmax ≠ INVAILD ⇒ Invisible Rule 4: If Status (t_xmin) = IN_PROGRESS ∧ t_xmin ≠ current_txid ⇒ Invisible Status of t_xmin is COMMITTED: ...

原理 ThreadLocal 是一种线程局部变量，它为每个线程提供了一个独立的变量副本，所以每个线程都可以拥有自己的局部变量，互不影响。 ThreadLocal 可以做到线程隔离的原因在于，每次创建 ThreadLocal 的时候，都会创建一个新的线程局部存储区，这个存储区只存在于当前线程中，其他线程无法访问到。这样就实现了线程之间的隔离，每个线程都可以在自己的线程局部存储区中保存自己的数据，互不影响。 使用方法 管理 Connection ThreadLocal 的相关知识我查过多次，一直不理解为什么使用 ThreadLocal 可以起到“管理 Connection”的作用，我之前的疑问是这样的： 数据库连接在同一时间只能被一个线程所持有，线程在申请数据库连接时也是线程安全的。Java 多线程访问同一个 java.Sql.Connection 会导致事务错乱。如果 ThreadLocal 的作用是“提供副本”的话，那么多个线程拿到的不就是同一个 Connection 了？ 其实是这样的： 如果不使用 ThreadLocal，你当然可以用局部变量的方式来保证线程封闭（Thread Confinement），即在一个函数中先从连接池中获取连接，执行完逻辑后再归还连接。但如果说你必须要使用到一个全局变量的 Connection 呢？ 如果不使用 ThreadLocal，就会出现不同的线程使用同一个全局变量的问题，自然不满足“一个数据库连接在同一时间只能被一个线程所持有”的限制。 每当一个线程需要数据库连接时，它就从数据库连接池中取出一个连接，存到 ThreadLocal 中，这样虽然不同线程的数据库连接都叫 dbConn,但都是独立的 Connection。 在 Spring 的 Web 项目中，我们通常会将业务分为 Controller 层，Service 层，Dao 层，我们都知道@Autowired 注解默认使用单例模式，那么不同请求线程进来之后，由于 Dao 层使用单例，那么负责数据库连接的 Connection 也只有一个，如果每个请求线程都去连接数据库，那么就会造成线程不安全的问题，Spring 是如何解决这个问题的呢？ 在 Spring 项目中 Dao 层中装配的 Connection 肯定是线程安全的，其解决方案就是采用 ThreadLocal 方法，当每个请求线程使用 Connection 的时候，都会从 ThreadLocal 获取一次，如果为 null，说明没有进行过数据库连接，连接后存入 ThreadLocal 中，如此一来，每一个请求线程都保存有一份自己的 Connection，于是便解决了线程安全问题。 public class DatabaseUtil { private static DataSource dataSource = ...; // 数据库连接池 private static final ThreadLocal<Connection> connectionHolder = new ThreadLocal<>(); public static Connection getConnection() throws SQLException { Connection conn = connectionHolder.get(); if (conn == null) { conn = dataSource.getConnection(); connectionHolder.set(conn); } return conn; } public static void closeConnection() throws SQLException { Connection conn = connectionHolder.get(); if (conn != null) { conn.close(); connectionHolder.remove(); } } } public class MyServlet extends HttpServlet { @Override protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException { Connection conn = null; try { conn = DatabaseUtil.getConnection(); // do something with the database connection // ... } catch (SQLException e) { // handle exception } finally { if (conn != null) { try { DatabaseUtil.closeConnection(); } catch (SQLException e) { // handle exception } } } } } 在这个示例中，DatabaseUtil 类通过 ThreadLocal 来存储数据库连接。每个请求线程从连接池获取连接时，会先检查 ThreadLocal 中是否已经存在了一个连接，如果没有就创建一个新连接并将其存储到 ThreadLocal 中，否则直接从 ThreadLocal 中获取已有的连接。在请求处理完毕后，关闭连接并从 ThreadLocal 中删除对象引用，以便及时释放资源和避免内存泄漏。 ...

Background 前段时间看到了 Windows Subsystem for Linux September 2023 update - Windows Command Line 这篇文章后，发现了 WSL 2 的新网络模式挺有意思的： Networking improvements are a consistent top ask for WSL, and this feature aims to improve the networking experience in WSL! This is a complete overhaul on the traditional NAT networking architecture of WSL, to an entirely new networking mode called “Mirrored”. The goal of this mode is to mirror the network interfaces that you have on Windows into Linux, to add new networking features and improve compatibility. ...

本章是这本书最酣畅淋漓的一章，涉及到了一致性和共识问题的方方面面，知识点多而不失条理。第一部分先讲了 Linearizability, 为后面的知识点做铺垫。到了 “Ordering Guarantees” 这一小节，从因果关系的带来的 “Happened Before” 的关系开始讲起，讲到了序列号和 Lamport Timestamp，提出来 Lamport Timestamp 的一个缺点：无法在某事件发生时判断是否有冲突，然后引出了全序关系广播，在全序关系广播中又讲到了和 Linearizable 之间的等价关系，最后引出共识算法。太精彩了，值得反复阅读！ Consistency Guarantees Most replicated databases provide at least eventual consistency, which means that if you stop writing to the database and wait for some unspecified length of time, then eventually all read requests will return the same value. A better name for eventual consistency may be convergence, as we expect all replicas to eventually converge to the same value. ...

写这篇文章的原因是之前在测试 6.824 Lab2B 时总是会出现几个错误，去提了 issue 后也没有得到令人信服的结果，自己有一点头绪但是没验证，这事就这么放着了。 然后最近有个同样做 6.824 的同学给我发了邮件，说他也遇到了同样的问题，重新分析了一下后，本来想简单回复一下的，结果回复的内容越写越多，就干脆直接整理为一篇文章，供大家参考。 异常情况 我之前在对 Lab2B 进行测试时，总是有几个简单的测试点过不了，仿佛代码即使正确，也总是可能出错。我经过分析后发现，都遵循以下这种错误模式： Leader 接收了来自上层的请求，还未提交该日志或者只有他提交了日志（该日志已经被 major 收到）时，就因为收到了其他 peer 的 RequestVote RPC 重新变回了 Follower。 重新选举后再次成为 Leader 后，由于旧任期的 Log 不能被新任期的 Leader 提交，所以之前的日志无法提交。 没有新的请求进来，导致该日志一致无法提交，然后 2 秒后超时，测试无法通过。 错误提示都是 one(xxx) failed to reach agreement。 为什么会出现 在 Lab2B 最开始的几个测试中，测试的编写者为了简化测试，测试代码中提交 command 的操作均为 cfg.one(cmd, servers, false)，这个函数的第三个参数名为 retry，控制的是对于一个请求，是否需要在超时后重新提交。 这里 retry 被设置为了 false，也就是说整个执行过程中只会调用 rf.Start() 一次，如果遇见了上文说的异常情况，就会被卡住，最后出现超时报错的情况。 也就是说，所谓的异常情况就是恰好遇见了一个 timing 加上 Lab2B 前面的几个测试有“缺陷”造成的。 no-op 机制 Raft 协议中本身是没有这个问题的，在论文第 13 页中说明了一个节点在当选 Leader 后会发送一个 no-op 的日志，这样新 Leader 就能把 no-op 以及它之前未提交的日志一起提交，就不会卡住了。 ...

ACID 中的一致性 我们现在关注的是其中的 C，即一致性 Consistency。它是什么意思呢？通俗地说，它指的是任何一个数据库事务的执行，都应该让整个数据库保持在「一致」的状态： ACID 中的「一致性」，是对于整个数据库的「一致」状态的维持。抽象来看，对数据库每进行一次事务操作，它的状态就发生一次变化。这相当于把数据库看成了状态机，只要数据库的起始状态是「一致」的，并且每次事务操作都能保持「一致性」，那么数据库就能始终保持在「一致」的状态上 (Consistency Preservation)。 所谓状态是不是「一致」，其实是由业务层规定的。比如转账的例子，“转账前后账户总额保持不变”，这个规定只对于「转账」这个特定的业务场景有效。如果换一个业务场景，「一致」的概念就不是这样规定了。所以说，ACID 中的「一致性」，其实是体现了业务逻辑上的合理性，并不是由数据库本身的技术特性所决定的。 为了让事务总是能保持 ACID 的一致性，我们需要在实现上考虑哪些因素呢？ 出错情况 (failure/error) 事务本身的实现逻辑可能存在错误，这需要应用层进行恰当的编码来保证。 需要 ACID 中的 A（原子性）来保障。简言之，原子性保障了事务的执行要么全部成功，要么全部失败，而不允许出现“只执行了一半”这种“部分成功”的情况。 并发行为 需要 ACID 中的 I（隔离性）来保障了。什么是隔离性呢？它对于并发执行的多个事务进行合理的排序，保障了不同事务的执行互不干扰。换言之，隔离性这种特性，能够让并发执行的多个事务就好像是按照「先后顺序」执行的一样。 Summary ACID 中的一致性，是个很偏应用层的概念。这跟 ACID 中的原子性、隔离性和持久性有很大的不同。原子性、隔离性和持久性，都是数据库本身所提供的技术特性；而一致性，则是由特定的业务场景规定的。 要真正做到 ACID 中的一致性，它是要依赖数据库的原子性和隔离性的（应对错误和并发）。 最后，ACID 中的一致性，甚至跟分布式都没什么直接关系。它跟分布式的唯一关联在于，在分布式环境下，它所依赖的数据库原子性和隔离性更难实现。 总之，ACID中的一致性，是一个非常特殊的概念。除了数据库事务处理，它很难扩展到其它场景，也跟分布式理论中的其它「一致性」概念没有什么关系。 分布式事务与共识算法的关系 共识问题 (consensus problem)。这是分布式系统中的一个十分基础而核心的问题，它表示如何在分布式系统中的多个节点之间就某事达成共识。 网上通常提到的「分布式一致性协议」，或者「分布式一致性算法」，一般来说就是解决这里的共识问题的算法。 这些算法或协议，经常包含 Paxos 之类，但也可能包括两阶段提交协议 (2 PC)或三阶段提交协议 (3 PC)。 ACID 中的原子性，要求事务的执行要么全部成功，要么全部失败，而不允许出现“部分成功”的情况。在分布式事务中，这要求参与事务的所有节点，要么全部执行 Commit 操作，要么全部执行 Abort 操作。换句话说，参与事务的所有节点，需要在“执行 Commit 还是 Abort”这一点上达成一致（其实就是共识）。这个问题在学术界被称为原子提交问题（Atomic Commitment Problem），而能够解决原子提交问题的算法，则被称为原子提交协议（Atomic Commitment Protocal，简称ACP）。2PC 和3PC，属于原子提交协议两种不同的具体实现。 我们可以发现原子提交问题和共识问题的关联： 共识问题，解决的是如何在分布式系统中的多个节点之间就某个提议达成共识。 原子提交问题，解决的是参与分布式事务的所有节点在“执行 Commit 还是 Abort”这一点上达成共识。 所以，原子提交问题是共识问题的一个特例。（？） 一些细节的不同，可能导致非常大的差异。当我们描述共识问题的时候，我们说的是在多个节点之间达成共识；而当我们描述原子提交问题的时候，我们说的是在所有节点之间达成共识。这个细微的差别，让这两类问题，几乎变成了完全不同的问题（谁也替代不了谁）： ...