本地事务的原子性和持久性是如何实现的

要实现持久性，数据库事务的修改必须要写入到磁盘中，否则，当出现数据库异常退出、系统宕机、机房断电等意外情况时，位于内存中的所有数据将会丢失。 但是，磁盘的操作又不是一个原子性行为，数据库可能在写入前、写入后、正在写等状态发生异常，这就需要我们采取一定的手段来保证事务的原子性。 目前的数据库管理系统采用的是先写日志、再写磁盘的策略来保证事务的原子性以及持久性的。本文将阐述 Commit Logging、Shadow Paging 以及 Write-Ahead Logging 三种策略。 Commit Logging Commit logging 是一种事务实现方式。在将数据修改写到磁盘之前，先把事务操作所需要的所有信息（包括修改什么数据、数据物理上位于哪个内存页和磁盘块中、从什么值改成什么值，等等）以日志的形式写到文件中。 只有日志记录全部写入到了磁盘之中后（日记文件也需要持久化到磁盘中），才会根据日志记录中记录的信息将修改写入到磁盘。 一个事务成功提交会，会在日志记录中添加上 Commit Record ，表示事务已经成功提交。在讲事务的修改成功写入到磁盘中后，还会在添加上一条 End Record 用来标识磁盘写入成功。 Commit Logging 如何保证持久性和原子性 一旦事务在日志记录中写入了 Commit Record ，那么该事务的所有修改已经全部安全落盘，那么，即便数据库在讲事务的修改写入到磁盘的过程中异常退出，在数据库系统重启恢复阶段，也能够将未完成的写入继续做完，这保证了事务的持久性。 如果 DBMS 在将一个事务的 Commit Record 安全写入到日志文件之前就异常终止，那么，只需要在 DBMS 重启恢复阶段，回滚该事务的所有变更的写入操作即可，这保证了事务的原子性，不会存在中间状态。 Commit Logging 的缺陷 Commit Logging 的缺陷在于，在事务讲修改更新操作完全写入日志记录文件之前，无法讲修改写到磁盘之中，日志文件的修改和磁盘的修改变成了同步的操作。如果在日志文件写入的同时磁盘处于空闲状态，那么将会导致磁盘资源的空置和浪费。 Shadow Paging Shadow paging 是另一个实现事务原子性以及持久性的技术。它是基于 Copy-on-Write 的方法。 Shadow paging 是这样工作的： 在事务修改一个数据页之前，将会复制一份该数据页的副本，该副本即为原数据页的影子 shadow。 所有的修改将会作用于影子页，因为影子页没有被位于磁盘中的任何数据页所引用，因此它的修改是十分安全的，不会影响一致性。 当影子页准备被持久化的时候，磁盘中所有引用原数据页的指针将被指向影子页。 最后一步的指针修改可以认为是原子性的，现在磁盘在硬件上保证了不会出现改了『半个值』的情况。 Shadow Paging 的缺点 Shadow paging 的实现要比 Commit Logging 更加简单，但只要涉及到并发锁时，Shadow Paging 所能够处理的并发事务数量将成为一个瓶颈。

本地事务的隔离性是如何实现的

如果没有并发的存在，数据库所有事务总是串行执行的，那么也就不会有临界资源竞争的情况出现，但现实情况是不可能没有并发的存在。 为了保证并发的正确性，需要通过对数据库资源加锁。本文将首先介绍数据库中的锁，之后会介绍各个隔离级别及其实现方式。 锁 写锁（Write Lock，也叫作排他锁，eXclusive Lock，简写为 X-Lock）：如果数据有加写锁，就只有持有写锁的事务才能对数据进行写入操作，数据加持着写锁时，其他事务不能写入数据，也不能施加读锁。 读锁（Read Lock，也叫作共享锁，Shared Lock，简写为 S-Lock）：多个事务可以对同一个数据添加多个读锁，数据被加上读锁后就不能再被加上写锁，所以其他事务不能对该数据进行写入，但仍然可以读取。对于持有读锁的事务，如果该数据只有它自己一个事务加了读锁，允许直接将其升级为写锁，然后写入数据。 范围锁（Range Lock）：对于某个范围直接加排他锁，在这个范围内的数据不能被写入。 特别注意：写锁禁止其他事务施加读锁，而不是禁止事务读取数据。 兼容性 只有读锁和读锁是兼容的，写锁不兼容任何其他锁。 Write Lock (X) Read Lock (S) Write Lock (X) 不兼容 不兼容 Read Lock (S) 不兼容 兼容 事务隔离级别 事务的隔离性是通过锁的机制来实现的，事务的隔离性越高，并发吞吐量越低，为了让开发人员能够在吞吐量以及隔离性之前取的较好的平衡点，数据库提供了多种隔离性级别。 从本质上来说，事务在不同隔离级别下的不同表现，来源于不同隔离级别采取的加锁机制的不同。 下表是事务的 4 个隔离级别，隔离性从上到下依次递减： 隔离级别 特征 可能存在的问题 Serializability，可串行性 多个事务并发执行的效果，和串行执行的效果一致。 无 Repeatable read，可重复读 可重复度保证一个事务读取到的数据，在整个事务执行过程中不会改变。 幻读 Read committed，读已提交 不允许一个事务读取到其他事务提交的数据。 幻读、不可重复读 Read uncommitted，读未提交 允许一个事务读取到其他事务未提交的数据。 幻读、不可重复读、脏读 Serializability, 可串行性 对事务所涉及到的数据加读锁、写锁、范围锁即可实现 Serializability 所要求的隔离性。 Repeatable Read, 可重复读 可重复读 对事务所涉及的数据加读锁和写锁，且一直持有至事务结束，但不再加范围锁。这就意味着 可重复读 可能会出现幻读（Phantom reads, 可参考下文针对幻读问题的讨论）的问题，比如说：

CAP 理论和 PACELC 理论

CAP 理论 CAP 理论阐述的是，一个分布式系统不可能同时满足一致性（consistency）、可用性（availability）和分区容错性（partition tolerance）这 3 个特性，至多只能满足其中的两个，实际上要么满足 CP（一致性+分区容错性），要么满足 AP（可用性+分区容错性）。 一致性 consistency 读请求（read request）总是能得到最新的值，也就是说，在任何时间，分布式系统中所有节点对于任一一个值存储的都是相同版本。这便是一致性。 可用性 availability 可用性意思是，每一个请求都能够收到非异常返回，但并不保证请求拿到的值就是最新的值。 分区容错性 partition tolerance 分区（partition）意味着分布式系统的任意一对节点出现了通讯中断。而分区容错性则要求，即便在内部节点出现故障时，整个系统依然能够运行，部分节点之间的网络异常不会导致整个系统的失效。 分区容错的必要性 分区容错性是一个分布式系统不可或缺的特性，因为任何系统的任意节点之间都有可能出现网络故障。当一个系统出现分区，部分内部节点无法访问彼此的时候，必须要在一致性和可用性之间做出选择：是为了保障服务依然可用而损害一致性呢，又或者是保障一致性而拒绝服务？ 举个例子，考虑上图的情况，假设有两个节点 A 和 B 之间发生了分区的情况，当用户先向节点 B 给 X 变量写一个值后，从节点 A 读取 X 变量，那么系统面临着两个选择： 它可以选择其中一个请求返回失败，但这样就损害了可用性 它可以处理两个请求，但是针对读请求返回一个旧的值，但这样就破坏了一致性 因此，我们能够得出结论： 实际上，CAP 理论要求一个分布式系统在内部节点发生网络故障，分区错误发生时，要么选择保留一致性，要么选择维护可用性。 PACELC 理论 PACELC 理论是 CAP 理论的补充，以下这段文字摘抄自维基百科 PACELC theorem - Wikipedia，它指出了 PACELC 这几个字母的缩写是怎么来的： In theoretical computer science, the PACELC theorem is an extension to the CAP theorem. It states that in case of network partitioning (P) in a distributed computer system, one has to choose between availability (A) and consistency (C) (as per the CAP theorem), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and consistency (C).

LeetCode 笔记 1：Sliding Window 题目总结

什么是滑动窗口算法 先用一个简单的题目来说明什么是滑动窗口算法。 最直接的思路就是，对于每个给定的 index，计算出从该 index 开始的一个最小 subarray，其和大于 target: int minLength = Integer.MAX_VALUE; for (int i = 0; i < nums.length; ++i) { int sum = 0; for (int j = i; j < nums.length; ++j) { sum += nums[j]; if (sum > target) { minLength = Math.min(minLength, j - i + 1); } break; } } 这个算法的问题就在于，相邻的 index 之间，存在着重合的计算。 解决办法就是维护一个滑动窗口，这样就能够解决重复计算的问题了： class Solution { public int minSubArrayLen(int target, int[] nums) { int res = Integer.