Time-Stamp Based Protocols

Suppose transaction Ti issues read(Q):

• If TS(Ti) < W-TimeStamp(Q), then Ti needs to read the value of Q which was already overwritten. Hence the read request is rejected and Ti is rolled back.
• If TS(Ti) >= W-TimeStamp(Q), then the read operation is executed and the R-timeStamp(Q) is set to the maximum of R-TimeStamp(Q) and TS(Ti).

Suppose transaction Ti issues write(Q):

• If TS(Ti) < R-TimeStamp(Q), then this implies that some transaction has already consumed the value of Q and Ti should have produced a value before that transaction read it. Thus, the write request is rejected and Ti is rolled back.
• If TS(Ti) < W-TimeStamp(Q), then Ti is trying to write an obsolete value of Q. Hence reject Ti’s request and roll it back. / Ignore this write operation. (Tomas’s Write Rule)
• Otherwise, execute the write(Q) operation and update W-TimeStamp(Q) to TS(Ti).

OCC

Each transaction Ti has three phases:

• Read phase: reads the value of data items and copies its contents to variables local to Ti. All writes are performed on the temporary local variables.
• Validation phase: Ti determines whether the local variables whose values have been overwritten can be copied to the database. If not, then abort. Otherwise, proceed to Write phase.
• • When validating transaction Tj, for all transactions Ti with TS(Ti) < TS(Tj), one of the following must hold:
  • • Finish(Ti) < Start(Tj), OR
    • Set of data items written by Ti does not intersect with the set of data items read by Tj, and Ti completes its write phase before Tj starts its validation phase.
• Write phase: The values stored in local variables overwrite the value of the data items in the database.

A transaction has three time stamps:

• Start(Ti): When Ti started its execution.
• Validation(Ti): When Ti finished its read phase and started its validation.
• Finish(Ti): Done with the write phase.

MVCC

Assume that transaction Ti issues either a read(Q) or a write(Q) operation.

Let Qk denote the version of Q whose write timestamp is the largest write timestamp less than TS(Ti), i.e., W-TimeStamp(Qk) < TS(Ti).

• If Ti issues a Read(Q), then return the value of Qk.
• If Ti issues a write(Q), and TS(Ti) < R-TimeStamp(Qk), then Ti is rolled back.
• Otherwise, a new version of Qk is created.

在阐述 SQL 的优化方案之前，我们需要先了解 SQL 的执行流程，如下：

1. 客户端发送 SQL 语句给 MySQL 服务器。

2. 如果查询缓存打开则会优先查询缓存，如果缓存中有对应的结果，直接返回给客户端。不过，MySQL 8.0 版本已经移除了查询缓存。

3. 分析器对 SQL 语句进行语法分析，判断是否有语法错误。

4. 明确 SQL 语句的目的后，MySQL 通过优化器生成执行计划。优化器通过成本计算预估出执行效率最高的方式，基本的预估维度为：

5. IO 成本：

   1. 数据量越大，IO 成本越高，所以要避免 select *；尽量分页查询。
   2. 尽量通过索引加快查询。

6. CPU 成本：

   1. 尽量避免复杂的查询条件，如有必要，考虑对子查询结果进行过滤。
   2. 尽量缩减计算成本，比如说为排序字段加上索引，提高排序效率；比如说使用 union all 替代 union，减少去重处理。

7. 执行器调用存储引擎的接口，执行 SQL 语句。

SQL 性能分析工具

如果要查询某一类 SQL 语句的执行频率，比如查看当前数据库的增删改查操作的访问频次，我们可以使用如下命令：

1

SHOW [GLOBAL | SESSION] STATUS LIKE 'Com_%';

慢查询日志记录了执行时间超过指定参数（long_query_time，单位：秒，默认 10 秒）的所有 SQL 语句。

慢查询日志默认不开启，所以我们需要在配置文件 /etc/my.cnf 中配置如下信息来启动慢查询日志：

1
2
3

slow_query_log = 1

long_query_time = 2 # 执行时间超过 2s 的操作被记录到慢查询日志当中

profile 详情（默认关闭），该功能可以帮助了解 SQL 语句耗时的部分。比如：

• 查看每一条 SQL 的耗时基本情况：SHOW PROFILES;
• 查看指定 query_id 的 SQL 语句各个阶段的耗时情况（或CPU 使用情况）：show profile [cpu] for query query_id;
• 查看是否支持 profile 操作：SELECT @@have_profiling;

如果需要开启 profile 操作，我们可以设置：SET profiling = 1;

EXPLAIN SELECT SQL语句; 可以获取 MySQL 如何执行 SELECT 语句的信息，包括 SELECT 语句执行过程中表如何连接和连接的顺序，也就是该 SQL 语句的执行计划的细节。

上图展示了 explain 语句的结果中的各个字段，这些字段的含义如下表：

示例：

通过 explain 命令，我们能分析出一些慢 SQL 的常见原因：

首先是索引使用问题，我们可通过 possible_keys(预计使用的索引) 和 key(实际使用的索引) 两个字段查看 InnoDB 有没有使用索引，优化器是否选择了错误索引，以及有没有实现覆盖索引。

接着是 I/O 开销问题，通过 rows(执行当前查询要遍历的行数) 和 filtered(有效行数/扫描行数比值) 字段来查看，是否扫描的行数过多，是否返回无用列且无用列有明显 I/O 性能开销(比如text、blob、json 等类型）。

optimizer_trace 可用于跟踪执行语句的解析、优化、执行的全过程。

使用步骤：

• 查看系统变量信息：show variables like '%optimizer_trace%';
• 打开 optimizer trace 开关：set optimizer_trace="enabled=on";
• 执行 SQL 语句。
• 查看 INFORMATION_SCHEMA.OPTIMIZER_TRACE 表中跟踪结果：select * from INFORMATION_SCHEMA.OPTIMIZER_TRACE;，并分析执行树：
  • join_preparation：准备阶段；
  • join_optimization：分析阶段；
  • join_execution：执行阶段。

关闭该功能：set optimizer_trace="enabled=off";

定位慢 SQL

定位和优化慢 SQL 是提升 MySQL 性能的关键环节。通常可通过以下四大步骤完成：

1. 慢查询日志：记录所有执行时间超过阈值的 SQL，并借助 mysqldumpslow 汇总分析；
2. 服务监控：在应用层面通过字节码插桩、连接池或 ORM 拦截对慢 SQL 进行实时监控与告警；
3. SHOW PROCESSLIST：在数据库层面查看当前运行的会话及其执行时间，快速锁定长时间运行的语句；
4. EXPLAIN：对疑似慢 SQL 执行 EXPLAIN，洞察查询执行计划，从而发现索引缺失、全表扫描等根本原因。

索引优化

覆盖索引指的是当查询所需字段全部存在于索引叶节点时，数据库可以仅依赖索引而无需回表读取，显著降低 I/O 开销。因此我们需要避免不必要的列，只查询需要的列。

创建联合索引能使多个查询字段同时被索引覆盖，从而避免回表和索引合并操作，且应遵循最左前缀规则以确保索引被有效利用。

为了保持索引的可用性，应避免使用 !=、<> 等非等值算符以及在索引列上应用函数，因为这些写法会导致索引失效，全表扫描或全索引扫描，从而影响性能。

当对较长字符串字段建立前缀索引时，可节省存储空间，但由于前缀索引无法存储完整值，MySQL 无法利用其实现排序或分组操作，依然可能触发 filesort 或临时表。

此外，InnoDB 默认启用索引下推技术（ICP），能将部分过滤条件下放至存储引擎层，仅在满足索引列过滤的记录上执行回表，从而减少数据传输量与回表次数，进一步提升查询效率。

假设我要执行如下命令：

1

SELECT * FROM users WHERE age > 30 AND city = 'Los Angeles';

在未启用索引下推时，InnoDB 存储引擎仅依据 age > 30 的索引范围扫描收集所有符合该条件的行，并将它们一股脑儿地返回给 MySQL 服务器层，由服务器再对 city = 'Los Angeles' 条件逐行筛选；而启用索引下推后，存储引擎会在索引扫描阶段同时评估 age > 30 与 city = 'Los Angeles' 两个条件，只有同时满足的行才会被送到服务器层，从而避免了无谓的行回表和服务器级过滤，显著减少了 I/O 操作并提升了查询性能。实际执行时，若在 EXPLAIN 的 Extra 列中看到 Using index condition 即表示已启用这一优化。

join 优化

在实际生产环境中，为了避免子查询带来的性能瓶颈，我们通常将其改写为等价的 JOIN 操作，并让行数较少的小表首先驱动行数庞大的大表，从而缩小中间结果集，减少随机 I/O；同时可以在业务表中适当增加冗余字段，将频繁关联的维度信息直接存储在事实表中，以降低 JOIN 次数；为控制单次查询的复杂度，通常不超过三张表联合查询，如若业务允许，还可将逻辑复杂的多表 JOIN 拆分为多个简单查询，再在应用层按需合并结果，以实现更稳定高效的查询性能。

insert 优化

在大规模数据写入场景下，将多条记录合并到单条 INSERT 语句中（例如一次提交 500–1000 条）能显著减少网络往返与语句解析开销，性能远超逐行插入；同时，关闭 AUTOCOMMIT 并使用 START TRANSACTION…COMMIT 手动提交事务，可以将多次写操作合并在一次事务中，避免频繁的事务开启与提交，从而进一步提升吞吐量；对于尤其庞大的数据集，采用 LOAD DATA LOCAL INFILE 命令从客户端文件批量导入，可利用服务器端的高速流式加载机制，其速度通常比批量 INSERT 快一个数量级以上；最后，确保插入数据按照主键单调递增的顺序写入 InnoDB 表，可减少聚簇索引中的页分裂与随机 I/O，获得优于乱序插入的最佳写入性能。

主键优化

选择简短且固定长度的整型主键：主键长度越短，聚簇索引和二级索引的存储和缓存开销越小；建议使用 INT 或 BIGINT 类型，并尽量避免使用 UUID 等无序且长度较长的值。

采用自增（AUTO_INCREMENT）主键：自增主键保证插入顺序与唯一性，能够最大化页的填充率并避免频繁的页分裂；只要满足业务需求，应优先使用自增主键而非自然主键（如身份证号）。

避免修改主键值：主键一旦更新，InnoDB 必须删除旧记录并插入新记录，等同于一次删除加一次插入，极易导致页分裂和 B+ 树重组，严重影响写入性能和存储布局。

显式定义主键：即使表中已有唯一索引，仍应显式声明主键列；若未定义主键，InnoDB 会隐式创建一个隐藏的聚簇索引，增加不确定性，且可能浪费空间和管理成本。

order by 优化

在 MySQL 中，任何无法直接利用索引有序性完成的 ORDER BY 操作都会触发 filesort：存储引擎先全表（或范围）扫描读取所有匹配行，将它们放入排序缓冲区（sort_buffer）中完成内存（或磁盘）排序后再返回结果；而如果能建立一个正好覆盖排序字段并且包含查询所需列的索引（Using index），MySQL 则可通过顺序扫描该索引直接输出有序结果，无需额外排序，效率更高。例如：

1
2
3

SELECT age, phone 
FROM table_name 
ORDER BY age ASC, phone DESC;

若事先创建：

1
2

CREATE INDEX idx_user_age_pho_ad 
ON table_name(age ASC, phone DESC);

则该查询可通过索引顺序扫描直接返回，避免 filesort 和回表查询；否则，MySQL 在执行时仍需先回表取出 phone 字段，再对 age、phone 结果集进行 filesort，才能满足排序要求。对于多列排序，除了要遵循最左前缀原则以保证索引可用，还需在建索引时指定正确的 ASC/DESC 顺序；当无法避免 filesort 时，可通过增大 sort_buffer_size（默认为 256 KB）来提升大数据量场景下的排序性能。

group by 优化

在 MySQL 中，如果将用于 GROUP BY 的列定义在符合最左前缀规则的复合 B+Tree 索引上，服务器就可以直接沿着索引的有序叶节点执行分组操作，而无需使用临时表或 filesort，从而显著提高聚合查询性能；例如对于 GROUP BY(a, b) 的场景，只要存在 (a, b, …) 这样的复合索引，MySQL 就能利用该索引在扫描叶节点时即完成对 (a,b) 键值的分组，而不是先拉取所有行再在服务器层排序和分组。

limit 优化

在面对海量数据分页时，传统的 LIMIT … OFFSET 会因数据库必须扫描并丢弃前 OFFSET 行而导致深度分页速度骤降；为此，可采用延迟关联（Deferred Join）技术——先在子查询中仅基于主键索引完成分页，再与主表 JOIN 获取完整行，以大幅缩减扫描量并保持深度分页的稳定性能；另一种常见做法是书签或键集分页（Keyset Pagination），即在每页结果中记录最后一行的排序键，下次查询以 WHERE key > last_key LIMIT N 的方式继续，既避免了昂贵的 OFFSET 跳过开销，又能直接利用索引顺序扫描；总之，通过延迟关联减少笛卡尔积运算并使用游标式或书签式分页策略，可在保持简洁 SQL 的同时显著提升大数据量分页查询的执行效率。

count 优化

在 MySQL 中，COUNT(column) 最慢，因为引擎要逐行取出指定列的值并判断是否为 NULL，只有非空值才累加；COUNT(primary_key) 略快一些，因为主键列本身有 NOT NULL 约束，无需判断空值即可累加；COUNT(1) 与 COUNT(*) 在现代 MySQL 中被优化为等价操作，它们都不实际读取任何列值，而是在服务层对每行隐式累加一个常量，性能十分接近，通常是最快的计数方式。

大多数权威测试与官方文档都表明，COUNT(1) 与 COUNT(*) 在 MySQL/InnoDB 上几乎没有性能差异，且二者优于其他形式的 COUNT（例如 COUNT(column)）。

[!NOTE]

如果我们需要在大数据量下统计唯一值，同时对处理速度要求很高，但是允许出现小幅度误差，这个时候我们可以使用 HyperLogLog 算法。

HyperLogLog 是一种概率算法，通过统计哈希值中最长前导零长度来估算数据基数，误差一般在 1–2% 范围内。

具体论文，可参考：https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

update 优化

InnoDB 的行锁实际上是对索引记录（index record）加锁，而非对物理存储行本身加锁：当执行带有 WHERE 条件的 UPDATE、DELETE 或 SELECT … FOR UPDATE 时，InnoDB 会在匹配条件的索引叶节点上设置记录锁和必要的间隙锁，从而实现行级并发控制；但如果查询条件无法利用任何合适的索引，InnoDB 就必须扫描整个表并在聚簇索引（或隐式主键索引）上对所有记录加锁，这时就会退化为表级锁，阻塞全表写操作；同样地，若使用的索引失效（例如对非索引列做范围扫描或函数运算），也会触发锁粒度升级为表锁，导致并发性能急剧下降。因此，为了保持细粒度的行锁并避免意外的表锁锁阻塞，务必为常用的查询条件列创建合适且选择性高的索引。

union 优化

在使用 UNION 语句时，为了让优化器更高效地执行查询，应将共同的过滤条件（如 WHERE）和分页限制（如 LIMIT）尽可能下推到各个子查询中，这样每个子查询只需处理满足自身子集条件的行，并在各自范围内完成截取与过滤，避免先将所有子查询结果合并后再做统一筛选，从而减少中间结果集的大小、降低 I/O 与内存开销，并加快整体查询响应速度。

MySQL 数据库 cpu 飙升的话，要怎么处理呢？

在 MySQL 出现 CPU 飙升时，首先可借助操作系统工具（如 top 或 htop）确认是 mysqld 进程占用过高，接着在数据库层面执行 SHOW PROCESSLIST 或查询 information_schema.processlist，快速定位执行时间或状态异常的会话，并对最耗资源的 SQL 做 EXPLAIN 分析，检查是否缺失索引或数据量过大；发现可疑线程后，可使用 KILL 语句终止它们，同时观察 CPU 是否回落，然后针对性地优化（如新增索引、重写慢查询、调整内存参数等）并重新执行这些 SQL；此外，如果是大量会话瞬间涌入导致 CPU 突增，则需与应用方协同排查连接激增的原因，并可考虑设置最大连接数或在业务层做限流，以防过多并发请求压垮数据库服务器。

有一个查询需求，MySQL 中有两个表，一个表 1000W 数据，另一个表只有几千数据，要做一个关联查询，如何优化？

如果 orders 表是大表（比如 1000 万条记录），而 users 表是相对较小的表（比如几千条记录）。

1. 为关联字段建立索引，确保两个表中用于 JOIN 操作的字段都有索引。这是最基本的优化策略，避免数据库进行全表扫描，可以大幅度减少查找匹配行的时间。

   1 2	CREATE INDEX idx_user_id ON users(user_id); CREATE INDEX idx_user_id ON orders(user_id);

2. 小表驱动大表，在执行 JOIN 操作时，先过滤小表中的数据，这样可以减少后续与大表进行 JOIN 时需要处理的数据量，从而提高查询效率。

   1 2 3 4 5 6 7 8

   SELECT u.*, o.* FROM ( SELECT user_id FROM users WHERE some_condition -- 这里是对小表进行过滤的条件 ) AS filtered_users JOIN orders o ON filtered_users.user_id = o.user_id WHERE o.some_order_condition; -- 如果需要，可以进一步过滤大表

如何解决慢查询问题？

首先，开启慢查询日志，用于记录执行时间超过阈值的查询，帮助定位慢查询的 SQL 语句。

开启方法如下：

1
2
3
4
5

SET GLOBAL slow_query_log = 1;

SET GLOBAL long_query_time = 1; -- 设置慢查询的阈值为1秒

SHOW VARIABLES LIKE 'slow_query_log%'; -- 确认是否启用

之后检查慢查询日志文件，定位耗时较长的 SQL 语句，并使用 EXPLAIN 分析 SQL 的执行计划，判断是否使用了索引或是否存在全表扫描等问题。

比如说：EXPLAIN SELECT * FROM table_name WHERE column_name = 'value';，该命令中的关键字段解释如下：

1. type：查询类型，优化目标是避免 ALL（全表扫描），优先选择 index、range。
2. key：实际使用的索引。
3. rows：扫描的行数，值越小越好。
4. extra：留意 Using temporary 或 Using filesort，这些会影响性能。

如果缺少索引，那么我们需要为查询条件中的字段添加索引，特别是 WHERE、JOIN、GROUP BY、ORDER BY 中涉及的字段。
比如说：CREATE INDEX idx_column ON table_name (column_name);

如果大量数据出现回表操作，那么需要改成覆盖索引，减少回表操作。
比如说：CREATE INDEX idx_multi_column ON table_name (column1, column2);

同时，还要判断是否出现索引失效。对此，我们可以避免对索引列使用函数或表达式，避免隐式类型转换（如字符串与数字比较）。

然后，我们可以重构查询语句，比如说使用 LIMIT 分页来避免返回大量数据：SELECT * FROM table_name WHERE condition LIMIT 100;，或者可以明确查询字段：SELECT column1, column2 FROM table_name WHERE condition;，避免运行 SELECT *;，再者可以在 JOIN 字段上设置索引，并尽量减少复杂的嵌套查询。

最后，我们可以进行表结构优化。

比如说可以使用分区表，也就是如果查询条件中经常使用时间或地理区域，可以将表按这些字段分区，减少扫描范围：

1
2
3
4
5
6
7

CREATE TABLE table_name (
  id BIGINT NOT NULL,
  created_at DATE NOT NULL
) PARTITION BY RANGE (YEAR(created_at)) (
  PARTITION p2023 VALUES LESS THAN (2024),
  PARTITION p2024 VALUES LESS THAN (2025)
);

或者如果单表数据量仍然过大，还可以按特定规则（如用户 ID）将表拆分为多个子表，降低单表数据量。

存储引擎是存储、更新或查询数据、以及建立索引等技术的实现方式。存储引擎是基于表的，而不是基于库的，因此存储引擎也可被称为表类型。

指定存储引擎：

1
2
3

CREATE TABLE 表名 (
	...
) ENGINE = INNODB ...;

查看当前数据库支持的存储引擎：SHOW ENGINES;

存储引擎特点

InnoDB

它是一个兼顾高可靠性和高性能的通用存储引擎。

特点

• DML 操作遵循 ACID 模型，支持事务。
• 行级锁提高并发访问性能。
• 支持外键 FOREIGN KEY 约束，保证数据的完整性和正确性。
• 支持非锁定读，即默认读取操作不会产生锁。

InnoDB 引擎中有多个内存块，这些内存块组成了一个大的内存池，负责如下工作：

1. 维护所有进程或线程需要访问的多个内部数据结构。
2. 缓存磁盘上的数据，方便快速读取，同时再对磁盘文件的数据修改之前在这里缓存。
3. Redo 日志缓冲。
4. …

上图中，后台线程的主要作用是刷新内存中的数据，保证缓冲池中缓存的是最新的数据，此外将已修改的数据文件刷新到磁盘，同时保证在数据库发生异常的情况下 InnoDB 能恢复到正常运行状态。

后台线程

InnoDB 存储引擎是多线程模型，因此有多个不同的后台线程，负责不同的任务：

1. Master Thread

   Master Thread 是一个非常核心的后台线程，主要负责将缓冲池中的数据异步刷新到磁盘，保证一致性，包括脏页的刷新、合并更改缓冲区、回收 Undo 页等。

2. IO Thread

   InnoDB 中大量使用了 AIO 来处理写 IO 请求，这样可以极大提高数据库的性能。而 IO Thread 主要负责这些 IO 请求的回调处理。

3. Purge Thread

   事务被提交后，其所使用的 Undo 日志可能不再被需要，因此引入 Purge Thread 来回收已经使用并被分配的 Undo 页。

4. Page Cleaner Thread

   作用是将之前版本中脏页的刷新操作都放入到单独的线程中来完成，用于减轻元 Master Thread 的工作以及对于用户查询线程的阻塞。

Checkpoint

缓冲池的设计目的是为了协调 CPU 速度和磁盘速度的鸿沟。但是如果每次一个页只要的发生变化，都要将脏页刷新到磁盘的话，那开销将非常大。而且如果从缓冲池刷新页到磁盘的磁盘过程中发生了宕机，那么数据无法恢复，因此 InnoDB 采用了 Write Ahead Log 策略，也就是当事务提交时，先写 Redo 日志再修改页。

如果 Redo 日志可以无限增大，并且缓冲池也足够大。那么我们无需将缓冲池中的脏页刷回磁盘。但是我们做不到，因为大容量内存很少见，而且维护人员需要时刻监测 Redo 日志的积累量是否超过磁盘空间阈值，此外宕机之后大量 Redo 日志的重放非常耗时，因此我们需要 Checkpoint 解决这些问题：

1. 缩短数据库的恢复时间；
2. 缓冲池不够用时，将脏页刷回磁盘；
3. Redo 日志不可用时，刷新脏页。

因此，当数据库发⽣宕机时， 数据库不需要重做所有的⽇志，因为 Checkpoint 之前的页都已经刷新回磁盘。故数据库只需对 Checkpoint 后的重做⽇志进⾏恢复。这样就⼤⼤缩短了恢复的时间。

此外，当缓冲池不够⽤时，根据 LRU 算法会淘汰最近最少使⽤的页，若此页为脏页，那么需要强制执⾏ Checkpoint，将脏页刷回磁盘。

重做日志出现不可用的情况是因为当前事务数据库系统对重做日志的设计都是循环使用的，并不是让其无限增大的。重做日志可以被重用的部分是指这些重做日志已经不再需要，即当数据库发生宕机时，数据库恢复操作不需要这部分的重做日志，因此这部分就可以被覆盖重用。若此时重做日志还需要继续使用不可被覆盖的部分，那么必须强制产生 Checkpoint，将缓冲池中的页至少刷新到当前重做日志的位置。

InnoDB 是通过 LSN（Log Sequence Number）来标记版本的，而 LSN 是 8 字节的数字。每个页有 LSN，重做日志中也有 LSN，Checkpoint 也有 LSN。

InnoDB 存储引擎内部，有两种 Checkpoint：

1. Sharp Checkpoint；
2. Fuzzy Checkpoint。

Sharp Checkpoint 发生在数据库关闭时将所有的脏页都刷新回磁盘，这是默认的工作方式。

但是若数据库在运行时也使用 Sharp Checkpoint，那么数据库的可用性就会受到大大影响，故在 InnoDB 存储引擎内部常使用 Fuzzy Checkpoint 进行页的刷新，即只刷新一部分脏页，而不是刷新所有的脏页回磁盘。

InnoDB 存储引擎中可能会生成如下几种情况的 Fuzzy Checkpoint：

• Master Thread Checkpoint；
• FLUSH_LRU_LIST Checkpoint；
• Async/Sync Flush Checkpoint；
• Dirty Page too much Checkpoint。

Master Thread 中发生的 Checkpoint，差不多以每秒或每十秒的速度从缓冲池的脏页列表中刷新一定比例的页回磁盘。这个过程是异步的，即此时 InnoDB 存储引擎可以进行其他的操作，用户查询线程不会阻塞。

FLUSH_LRU_LIST Checkpoint 是因为 InnoDB 存储引擎要保证 LRU 列表中需要有不多于 100 个空闲页可供使用。倘若没有 100 个可用空闲页，那么 InnoDB 会将 LRU 列表尾端的页移除。如果这些页中有脏页，那么需要进行 Checkpoint，而这些页是来自 LRU 列表的，因此称为 FLUSH_LRU_LIST Checkpoint。之后，这些检查被放在了一个单独的 Page Cleaner 线程中进行。

Async/Sync Flush Checkpoint 指的是重做日志文件不可用的情况，这时需要强制将一些页刷新回磁盘，而此时脏页是从脏页列表中选取的。

若将已经写到重做日志的 LSN 记为 redo_lsn，将已经刷新回磁盘最新页的 LSN 记为 checkpoint_lsn，则可定义：

$$checkpoint_age = redo_lsn - checkpoint_lsn$$

再定义以下的变量：

$$async_water_mark = 75% * total_redo_log_file_size$$

$$sync_water_mark = 90% * total_redo_log_file_size$$

若每个重做日志文件的大小为 1GB，并且定义了两个重做日志文件，则重做日志文件的总大小为 2GB。那么 async_water_mark=1.5GB，sync_water_mark=1.8GB，则：

• 当 checkpoint_age < async_water_mark 时，不需要刷新任何脏页到磁盘；
• 当 async_water_mark < checkpoint_age < sync_water_mark 时触发 Async Flush，从 Flush 列表中刷新足够的脏页回磁盘，使得刷新后满足 checkpoint_age < async_water_mark；
• checkpoint_age > sync_water_mark 这种情况一般很少发生，除非设置的重做日志文件大小小，并且在进行类似 LOAD DATA 或 BULK INSERT 操作。此时触发 Sync Flush 操作，从 Flush 列表中刷新足够的脏页回磁盘，使得刷新后满足 checkpoint_age < async_water_mark。

之后，这部分刷新操作同样被放入到 Page Cleaner 线程中，所以再也不会阻塞用户查询线程。

最后一种 Checkpoint 的情况是 Dirty Page too much，即脏页的数量太多，导致 InnoDB 存储引擎强制进行 Checkpoint。其目的的总结来说是为了保证缓冲池中有足够可用的页。其可由参数 innodb_max_dirty_pages_pct 控制，innodb_max_dirty_pages_pct 值为 75 表示，当缓冲池中脏页的数量占比 75% 时，强制进行 Checkpoint，刷新一部分的脏页到磁盘。

Master Thread

InnoDB 存储引擎的主要工作都是在一个单独的后台线程 Master Thread 中完成的。具体的演化过程请参考 MySQL 技术内幕的 36-45 页。

关键底层特性

• 插入缓冲
• 两次写
• 自适应哈希索引
• 异步 IO
• 刷新临接页

插入缓冲

InnoDB 中，主键是行唯一的标识符，通常应用程序中行记录的插入是按照主键递增的顺序来进行的（AUTO_INCREMENT），因此插入聚集索引一般是顺序的，无需磁盘随机读取。但是，一张表上可能存在多个非聚集切非唯一的二级索引，再进行插入操作的时候，数据页的存放还是按照主键顺序存放的，但是对于非聚集非唯一的索引而言，叶子节点的插入一般来说就不再是顺序的了，也就是会出现随机访问，除了日期之类的递增列的索引。

因此 InnoDB 中设计了插入缓冲：对于非狙击索引的插入和更新操作，不是每一次直接插入到索引页中，而是先判断插入的非聚集索引页是否在缓冲池中，若在，则直接插入，若不在，则先放入到一个插入缓冲中，然后再以一定频率和情况进行插入缓冲和二级索引页的合并操作，这时通常能将多个插入操作合并到一个操作中，极大提高了对于非聚集索引插入的性能。

为什么插入缓冲不操作唯一索引？

因为如果要对唯一索引进行操作，不论是插入、删除还是更新，都需要到索引页中判断要操作的记录的唯一性，这又会导致随机访问的发生，从而导致插入缓冲失去意义。

插入缓冲是一棵 B+ 树，并且该树数据库全局中只有一棵，负责对所有表的二级索引进行插入操作的缓存。该树被放在共享表空间中，即 ibdata1 中。 因此，试图通过独⽴表空间 ibd ⽂件恢复表中数据时，往往会导致 CHECK TABLE 失败。这是因为表的辅助索引中的数据可能还在 InsertBuffer 中，也就是共享表空间中，所以通过 ibd ⽂件进⾏恢复后，还需要进⾏ REPAIR TABLE 操作来重建表上所有的辅助索引。

该树中的非叶子节点存放的是查询的 search key，也就是索引键（在 Insert Buffer B + 树中，二级索引页根据（ space, offset ）都已排序好），其结构如下：

searchkey ⼀共占⽤ 9 个字节，其中 space 表⽰待插⼈记录所在表的表空间 id，在 InnoDB 存储引擎中，每个表有⼀个唯⼀的 spaceid，可以通过 spaceid 查询得知是哪张表。space 占⽤ 4 字节。marker 占⽤ 1 字节，它是⽤来兼容⽼版本的 Insert Buffer。offset 表⽰页所在的偏移量，占⽤ 4 字节。

当⼀个辅助索引要插入到页（ space, offset ）时，如果这个页不在缓冲池中，那么 InnoDB ⾸先根据上述规则构造⼀个 searchkey，接下来查询 InsertBuffer 这棵 B+树，然后再将这条记录插⼊到 Insert Buffer 的叶⼦节点中。

对于插⼊到 Insert Buffer 叶⼦节点的记录，并不是直接将待插入的记录插入，⽽是需要根据如下规则进⾏构造：

上图是 Insert Buffer 叶子节点中的记录结构，其中 space、marker、offset 字段和之前的含义一致，一共 9 字节。metadata 占用 4 字节，其存储内容如下：

IBUF_REC_OFFSET_COUNT 记录进入 Insert Buffer 的顺序，并且通过这个顺序才能得到正确的值。

从第 5 个字段开始，就是实际插入记录的各个字段，因此较原插入记录，Insert Buffer 中的叶子节点中的记录需要额外 13 字节的开销。

当启用 Change Buffer（Insert Buffer 升级）后，InnoDB 不会立即将对非聚集索引页的修改（插入、删除、更新）同步到该页上，而是将修改记录缓存到一个 Insert Buffer 中。这种做法虽然减少了大量随机 I/O，但带来两个问题：

1. 何时合并？ 合并时要把哪些缓冲修改应用到目标页？
2. 是否还有可用空间？ 只有当目标页有足够剩余空间时，才允许新的修改进入缓冲，否则要避免膨胀页大小。

为此，引入了 bitmap 页面来快速回答这两类问题，而无需读取整个索引页。

每个 bitmap 页描述一组连续的二级索引页。在常见的 16 KB 页大小下，一个 bitmap 页能跟踪 16 384 个索引页（即 256 个区）。每个 Insert Buffer Bitmap 页是 16384 个页中的第⼆个页。每个被跟踪的索引页对应 4 位信息，如下：

Merge Insert Buffer 的操作可能发⽣在以下⼏种情况下：

1. 当某个二级索引页被读取到缓冲池时，立即应用该页所有挂起的缓冲修改；
2. 当 Insert Buffer Bitmap 检测到某页可用空间不足，必须先合并才能继续缓冲新的修改；
3. Master Thread 循环检测并执行各种维护任务，包括 Change Buffer 的合并操作。

对第二点进行补充：若 Bitmap 显示该页剩余可用空间 ≥ 阈值（默认为页大小的 1/32），则直接将修改写入 Change Buffer；否则，视为可用空间不足，需要先合并该页在 Change Buffer 中的所有挂起修改，再重新计算空间后才能缓冲。

在 Master Thread 中，执行 merge 操作的不止是一个页，而是根据 srv_innodb_io_capacity 的百分比来决定真正要合并多少个辅助索引页。但 InnoDB 存储引擎又是根据怎样的算法来得知需要合并的辅助索引页？

解决方案是随机选页策略：

• 随机起点：Master Thread 在 Change Buffer 树中随机挑选一个页（或一个树节点），然后从该页开始，按内部顺序（通常是树结构中后继页）依次读取所需数量的页来合并。
• 保证覆盖全树：通过每次随机的起点，随着时间推移，整个 B+ 树中的所有页都会被均匀地触及，避免固定区段被长时间忽略。
• 批量合并：从选中的起点开始，连续取出 N 页（N 由 I/O 预算决定）进行条目合并和写回。

在 merge 时，如果要进行 merge 的条目已经被删除，此时可以直接丢弃已被 Insert/Change Buffer 存储的对应数据记录。

为什么不按顺序选页？

按 (space, offset) 排序：理论上可以从最小的表空间 ID（space）和页号（offset）开始，按顺序扫描整个 B+ 树。

公平性问题：如果总是从头开始，前面页的挂起修改会被反复优先处理，而后面页可能长时间得不到合并。

更改缓冲

更改缓冲是插入缓冲的升级版，因为它可以对 DML 操作（增删改）进行缓冲。更改缓冲的适用对象仍然是非唯一的二级索引。

innodb_change_buffering 控制 Change Buffer 的行为，默认值为 all，表示所有类型的插入、更新和删除操作都会使用 Change Buffer。可选值包括：

• none：禁用 Change Buffer。
• inserts：仅缓存插入操作。
• deletes：仅缓存删除操作。
• changes：缓存插入和删除操作。
• all：缓存所有支持的操作。

双写

双写为 InnoDB 带来了数据页写磁盘的可靠性。

当发生数据库宕机时，可能 InnoDB 存储引擎正在写入某个页到表中，而这个页只写了一部分，比如 16 KB 的页，只写了前 4 KB，之后就发生了宕机，这种情况被称为部分写失效（partial page write）。在 InnoDB 存储引擎未使用 doublewrite 技术前，曾经出现过因为部分写失效而导致数据丢失的情况。

有人会想，如果发生写失效，可以通过重做日志进行恢复。这是一个办法。但是必须清楚地认识到，重做日志中记录的是对页的物理操作，比如偏移量 800，写入 aaaa 记录。如果这个页本身已经发生了损坏，再对其进行重做是没有意义的。这就是说，在应用重做日志前，用户需要一个页的副本，当页写失效时，先通过页的副本来还原该页，再进行重做，这就是 doublewrite。

当 InnoDB 将脏页写回磁盘时，如果发生意外宕机（如断电、进程被杀），可能只写入了页面的一部分字节，这称为部分写失效（partial page write）。此时磁盘上的原始页已损坏，内部结构（例如记录边界、checksum、LSN 等）不再正确。InnoDB 的 Redo Log 仅记录对特定行或特定偏移的修改差分，并不包含整页的镜像。因此，如果缺少干净的起始页，应用这些差分时就无从下手——就像没有原图就没法正确贴修补片一样。

doublewrite 由两部分组成：一部分是内存中的 doublewrite buffer，大小为 2 MB；另一部分是物理磁盘上共享表空间中连续的 128 个页，即 2 个区（extent），大小同样为 2 MB。

在后台线程对缓冲池的脏页进行刷回磁盘的时候，并不是直接写入表空间文件，而是先通过 memcpy 将数据页复制到内存中的 doublewrite buffer，它被划分为两段，每段约 1 MB，InnoDB 按连续顺序调用 write() 将第一段写入 OS 页缓存，再调用 fsync() 强制落盘，然后对第二段重复相同操作。在这个过程中，由于 doublewrite 页面在磁盘上是连续存放的，因此写入是顺序 I/O，性能损耗也相对可控。在完成 doublewrite 页的安全落盘之后，再将磁盘的 doublewrite 中的页面按各自原始逻辑位置分散写入 .ibd 或共享表空间文件；这一步 I/O 是随机分布的。

fsync 是一个 POSIX 系统调用，用于强制操作系统将指定文件的所有已修改数据块及其元数据，从内核缓冲区刷写（flush）到物理存储设备，并在返回之前阻塞直到存储设备确认写入完成。

如果操作系统在将页写入磁盘的过程中发生了崩溃，在恢复过程中，InnoDB 可从共享表空间中的 doublewrite 中找到该页的一个副本，将其复制到表空间文件并应用 Redo 日志。

注意：有些文件系统如 AFS 提供了部分写失效的防范机制，因此在这种情况下，无需启动 doublewrite。

为什么数据页会被先写入双写缓冲，而不是直接被写入数据文件？

直接写入数据文件时，部分写失效问题更加严重，因为数据文件中的数据页分布是随机的，不同的数据页可能在磁盘的不同区域，而不是连续存放。因此，直接写入这些随机分布的页时，我们需要花费更多的时间，发生部分写失效的风险更高。而双写缓冲区是一个专门设计的区域，确保每次写入是连续的、顺序的，它使得内存中的数据能在最短的时间内被写入磁盘，从而大大减少了部分写失效的风险。

自适应哈希索引

哈希（hash）是一种非常快的查找方法，在一般情况下这种查找的时间复杂度为 O(1)，即一般仅需一次查找就能定位数据。而 B+ 树的查找次数，取决于 B+ 树的高度，在生产环境中， B+ 树的高度一般为 3 ～ 4 层，故需要 3 ～ 4 次的查询。

InnoDB 存储引擎会监控对表上各索引页的查询。如果观察到建立哈希索引可以带来速度提升，则建立哈希索引，称之为自适应哈希索引（Adaptive Hash Index，AHI）。AHI 是通过缓冲池的 B+ 树页构造而来，因此建立的速度很快，而且不需要对整张表构建哈希索引。InnoDB 存储引擎会自动根据访问的频率和模式来自动地为某些热点页建立哈希索引。

AHI 有一个要求，即对这个页的连续访问模式必须是一样的。例如对于 (a, b) 这样的联合索引页，其访问模式可以是以下情况：

1
2
3

WHERE a=xxx
-- 或者
WHERE a=xxx and b=xxx

访问模式一样指的是查询的条件一样，若交替进行上述两种查询，那么 InnoDB 存储引擎不会对该页构造 AHI。此外 AHI 还有如下的要求：

• 以该模式访问了 100 次；
• 页通过该模式访问了 N 次，其中 N = 页中记录 * 1/16。

仅当上述两项同时满足，且访问模式一致时，才会触发 AHI 的构建。同一模式访问次数 ≥ 100：保证该模式不是偶发的短时热点。页访问次数 ≥ R / 16：保证该模式命中足够多的行数，是真正的页级热点。

当你交替执行两种不同的访问模式（WHERE a=xxx 和 WHERE a=xxx AND b=xxx），即使每种模式单独都达到了 100 次，也仍然不会触发 AHI 的构建。

异步 IO

同步 I/O：每次调用 read()/write() 后，调用线程必须阻塞等待 I/O 完成，才能继续下一步操作。

异步 I/O (AIO)：调用线程可连续调用多次 io_submit()，将多个 I/O 请求并行提交给内核，而不必等待每次完成。内核或专门的 I/O 线程池负责实际读写，完成后通过回调或事件 (io_getevents) 通知应用。

AIO 的另一个优势是可以进行 IO Merge 操作，也就是将多个 IO 合并为 1 个 IO，这样可以提高 IOPS 的性能。例如用户需要访问页的 (space, page_no) 为：(8, 6), (8, 7), (8, 8)。每个页的大小为 16KB，那么同步 IO 需要进行 3 次 IO 操作。而 AIO 会判断到这三个页是连续的（显然可以通过 (space, page_no) 得知）。因此 AIO 底层会发送一个 IO 请求，从 (8, 6) 开始，读取 48KB 的页。

刷新邻接页

在刷新某个脏页时，同时检查并一起刷新该页所在区（extent）中的所有其它脏页，从而通过 AIO（异步 I/O）将多个小的写操作合并成一次较大的顺序 I/O。

为什么要刷新邻接页？

• 顺序 I/O 合并：在刷新单页时，如果只发出一个 16 KB 的写请求，操作系统与硬盘可能会进行一次小随机写；若同时将同一区中其他脏页一起刷新，就能将多次 16 KB 的写请求合并为一次大块的顺序写，从而利用顺序带宽、减少磁盘的寻道开销。
• AIO 效果：配合异步 I/O（AIO）提交这些写请求后，硬件/内核会自动合并相邻请求为更大块，有效提升 IOPS 和吞吐。

如果禁用该功能，则每次仅写出单页，虽然避免了写入无关脏页，但会频繁发生随机写，导致 I/O 延迟和写入抖动增大。

示例：在同一个 extent（假设包含页号 0–63）内，页 10、页 12、页 14 已被修改，成为脏页。

禁用刷新邻接页：每次只写出目标脏页本身，不管同一 extent 内是否还有其他脏页。仅页 12 刷入磁盘；页 10 和页 14 保持在缓冲池中，等待下次单独刷新或达到阈值才写入。

启用刷新邻接页：在同一 extent（页 0–63）内，发现目标页 12 后，会顺带把所有脏页（页 10 和页 14）一并写入一次 I/O。单次 I/O 写出页 10、12、14（共 3 × 16 KB），仅一次寻道即可完成，减少 HDD （硬盘驱动器）随机写的开销。

MyISAM

它是 MySQL 早期默认的存储引擎。

特点

• 不支持事务和外键。

• 支持表锁，不支持行锁。

• 访问速度快。

• 缓冲池只缓存索引文件，而不缓存数据文件。

MyISAM 和 InnoDB 的比较如下表：

Memory

该存储引擎的表数据存储在内存中，因此为避免受到硬件问题或断电问题的影响，我们只能将这些表作为临时表或缓存使用。

特点

• 内存存储，访问速度快。

• 默认使用 hash 索引。

以上三种存储引擎的对比如下图：

存储引擎选择

• InnoDB：支持事务、外键、行级锁。如果应用对事务的完整性有比较高的要求，在并发条件下要求数据的一致性，数据操作包含大量的增删改查，那么 InnoDB 存储引擎是比较合适的选择。
• MyISAM：如果应用以读操作和插入操作为主，只有很少的更新和删除操作，并且对事务的完整性、并发性要求不是很高，那么 MyISAM 是非常合适的（更好的选择是使用 MongoDB）。
• Memory：将所有数据保存在内存中，访问速度快，通常用于临时表及缓存。缺陷是对表的大小有限制，太大的表无法缓存在内存中，而且无法保障数据的安全性（更好的选择是使用 Redis）。

除了以上三种引擎，MySQL 还内置了 Archive 和 Federated 等存储引擎。

MySQL 的体系结构如下：

• 连接层：负责网络协议解析、用户认证及会话管理，为每个客户端分配线程或线程池。
• 服务层：包含 SQL 解析、优化与执行模块，并实现跨引擎功能，如存储过程、触发器和视图等。
• 引擎层：通过统一的 Handler API 与各存储引擎（如 InnoDB、MyISAM）通信，负责数据的存储、检索及索引管理。
• 存储层：基于操作系统文件系统执行物理 I/O，管理表空间、日志文件并支持异步或直通 I/O 优化。

Amazon DynamoDB 将 Dynamo 的增量扩展能力和可预测的高性能与 SimpleDB 的易用表模型和强一致性相结合，既避免了自建大型数据库系统所带来的运维复杂性，又突破了 SimpleDB 在存储容量、请求吞吐和查询／写入延迟方面的局限；同时，DynamoDB 作为一款无服务器、全托管的 NoSQL 服务，内置自动扩缩容、安全加固和多区域复制，让开发者能够专注于业务逻辑，而无需管理底层基础设施。

架构

一个 DynamoDB 表是多个条目的集合，或者具体来说是 KV 存储，每个条目由多个属性组成并且通过主键唯一标识。主键的模式在创建表时指定，主键模式包含分区键，或者分区键和排序键一起（也就是复合主键）。分区键的值总是作为内部哈希函数的输入，该哈希函数的输出和排序键的值（如果存在）共同决定该条目的存储位置（分区）。在具有复合主键的表中，多个条目可以具有相同的分区键值，但这些项目必须具有不同的排序键值。

DynamoDB 支持二级索引，一个表可以拥有一个或多个二级索引。二级索引允许使用除主键之外的备用键来查询表中的数据，这个备用键说白了就是二级索引键。

假设我们有一个游戏得分表 GameScores，记录玩家在不同游戏中的最高得分，表结构定义如下：

主表的表名是 GameScores，主键的设置如下：

• 分区键：UserId (String)；
• 排序键：GameId (String)。

在这种设计下，针对单个用户查询他们在某个游戏里的得分非常高效，但如果我们想要按 游戏名称（GameTitle）或 得分排名（TopScore）来查询所有玩家的成绩，就无法直接使用主键查询。

为满足上述查询需求，我们可以在表中添加一个全局二级索引 GameTitleIndex，其备用键（索引键）定义如下：

• 索引名：GameTitleIndex；
• 分区键：GameTitle (String)；
• 排序键：TopScore (Number)。

上表列出了客户端在 DynamoDB 表中读取和写入项目时可用的主要操作。任何插入、更新或删除项目的操作都可以带有一个条件，只有在该条件满足时操作才会成功。该条件判断在高并发场景中可避免多个客户端对同一项条目进行冲突性写入，例如只在某属性值符合预期时才更新。

此外，DynamoDB 支持 ACID 事务，使应用程序能够在更新多个项目时保证原子性、一致性、隔离性和持久性（ACID），而不会影响 DynamoDB 表的可扩展性、可用性和性能特性。

之前提到过，DynamoDB 表被拆分为多个分区，以满足表的吞吐量和存储需求。每个分区承载表键值范围中不重叠的一个连续区段，并在不同可用区分布多个副本，以实现高可用性和持久性。这些副本组成一个复制组，采用 Multi-Paxos 协议进行领导者选举与一致性达成。任一副本都可以发起选举，成为领导者后需定期续租，唯有领导者副本可处理写请求和强一致性读取。领导者在接收到写请求时，会生成预写日志并分发给其他副本，当多数副本将日志持久化后，才向客户端确认写入成功。DynamoDB 支持强一致性和最终一致性读取，其中任何副本都能提供最终一致性读取。若领导者被检测为失败或下线，其它副本可再次发起选举，新领导者在前领导者租约到期前不会处理写入或强一致性读取。复制组包含预写日志和以 B 树形式存储键值数据的存储副本。同时为了进一步提升可用性与持久性，复制组中还可包含仅持久化最近预写日志的日志副本，它们类似 Paxos 中的接受者，但不存储键值数据。也就是说，DynamoDB 的复制组中包含多个数据副本和多个日志副本。

DynamoDB 是由数十个微服务组成的，其中一些核心服务包括元数据服务、请求路由器服务、存储节点和自动管理服务。元数据服务存储有关表、索引以及给定表或索引的分区复制组的路由信息。请求路由器服务负责对每个请求进行授权、身份验证，并将其路由到相应的服务器。

所有的读取和更新请求都会被路由到承载客户数据的存储节点。请求路由器会从元数据服务中查询路由信息。所有资源创建、更新和数据定义请求则会被路由到自动管理服务。存储服务负责在一组存储节点上保存客户数据，每个存储节点会承载多个不同分区的副本。

在上图中，请求首先通过网络到达请求路由器（Request Router）服务，该服务依次调用认证系统进行 IAM 权限校验、查询分区元数据系统获取路由信息，并与全局准入控制（GAC）系统协作对表级吞吐进行限流，最后将请求转发至目标存储节点（Storage Node）进行数据读写操作。存储节点分布在多个可用区（AZ），采用 SSD 存储并在三个副本间使用 Paxos 算法选举主节点以提供写入一致性和读扩展能力，同时依靠副本复制实现高可用与持久性。认证系统通过 AWS IAM 服务简化身份验证与授权管理，分区元数据系统维护分区与存储节点的映射关系，而 GAC 则作为分布式令牌桶机制确保吞吐的可预测性与表级隔离。

这里需要强调的是，自动管理服务被构建为 DynamoDB 的中枢神经系统，它负责集群健康、分区健康、表的弹性扩缩以及所有控制平面请求的执行。该服务会持续监控所有分区的状态，并替换任何被判定为不健康（响应缓慢、无响应或运行在故障硬件上）的副本。它还会对 DynamoDB 的所有核心组件进行健康检查，并替换任何正在出现故障或已故障的硬件。例如，如果自动管理服务检测到某个存储节点不健康，它会启动恢复流程，把此前托管在该节点上的数据副本迁移或重建到其他健康的节点，以确保整个系统的复制组能够再次达到预期的副本数和健康状态。

[!NOTE]

普遍意义上，控制平面是系统或网络中的大脑或指挥中心，负责管理、配置和决策，决定资源如何被创建、更新、删除以及如何路由请求；而实际的数据转发、存储和处理则由数据平面执行。控制平面通过一系列管理 API 与底层组件通信，实现对系统状态的监控、调度和恢复，从而保证整体的可用性、一致性和可扩展性。

因此，在 DynamoDB 中，控制平面并不仅仅指自动管理服务，而是由多种后台管理组件和它们所提供的管理 API 共同构成的一套系统。

从预配置到弹性伸缩

在最初的 DynamoDB 版本中，开发者引入了分区的概念，以便能够动态地扩展表的容量和性能。系统最开始会将一张表切分为多个分区，使其内容能够分布到多台存储节点上，并且与这些节点的可用空间和性能相映射。当表的规模增大或访问负载上升时，系统可以进一步拆分分区并将其迁移，以实现弹性扩展。分区这一抽象证明了其极高的价值，并一直是 DynamoDB 设计的核心。

用户需要以读取吞吐量单位（RCU）和写入吞吐量单位（WCU）的形式，显式地指定一个表所需的吞吐量（预配置吞吐量）。对于不超过 4 KB 的条目，1 个 RCU 可每秒执行 1 次强一致性读取请求；对于不超过 1 KB 的条目，1 个 WCU 可每秒执行 1 次标准写入请求。

显然，早期版本将容量与性能的分配紧密耦合到各个分区，导致了若干挑战。DynamoDB 使用准入控制来确保存储节点不会过载，避免同机房中不同表的分区相互干扰，并强制执行客户所请求的吞吐量限制。

最初，一个表的所有存储节点共同承担准入控制的责任。每个存储节点会根据其本地所存放的分区的分配情况，独立地执行准入控制。由于一个节点通常会承载多个表的分区，系统便利用各分区的分配吞吐量来隔离不同表的工作负载。DynamoDB 会对单个分区可分配的最大吞吐量进行上限限制，同时确保某节点上所有分区的总吞吐量不超过由其存储介质物理特性所决定的该节点最大允许吞吐量。当表的整体吞吐量发生变化或分区被拆分时，系统会相应地调整各分区的分配吞吐量。若因表容量增长而拆分分区，子分区会从父分区继承并平均分配吞吐量；若因吞吐量需求增长而拆分分区，则新分区会按照表的预配置吞吐量进行分配。例如，假设某分区最大可承载 1000 WCU。创建一个具有 3200 WCU 的表时，DynamoDB 会生成 4 个分区，每个分区分配到 800 WCU；若将表的吞吐量提升至 3600 WCU，则每个分区可用吞吐量自动增至 900 WCU；若进一步提升至 6000 WCU，系统会拆分出 8 个子分区，每个分区分配到 750 WCU；若将吞吐量下调至 5000 WCU，则每个分区的吞吐量相应降至 675 WCU。

以上这种对各分区进行均匀吞吐量分配的做法基于如下假设：应用会均匀地访问表中各个键，且按容量拆分分区也会等比地拆分性能。但开发者发现，应用在不同时间和键范围上的访问模式常常并不均匀。当表内请求速率分布不均匀时，将分区拆分并按比例分配吞吐量，往往会导致热点区域拆分后可用性能反而低于拆分前的水平。由于吞吐量在分区层面上被静态分配和强制执行，这类非均匀工作负载偶尔会引发应用的读写请求被拒绝（即“限流”），即使整表的预配置吞吐量充足，也无法满足集中在少数键的高并发访问。

在这种配置下，最常遇到的两个挑战是：热点分区（hot partitions）和吞吐量稀释（throughput dilution）。热点分区指的是访问始终集中在某些表项上的场景，这些热点可能稳定地落在某几个分区内，也可能随着时间在不同分区间跳动。吞吐量稀释则常出现在因扩容而按大小拆分分区的场景：拆分后，父分区的吞吐量被平均分配到新分区，使得每个分区的可用吞吐量降低。

从用户角度看，这两种情况都会导致资源被限流，使其应用在某些时段出现不可用。遭遇限流的用户往往会通过人为过度提升表的预配置吞吐量来规避问题，但这导致资源浪费、成本上升，并且难以准确估算所需性能。

因此，DynamoDB 在发布后不久就推出了两项改进，即突发容量和自适应容量，以解决这些问题。

突发容量

当开发者注意到各分区的访问模式并不均匀后，又发现并非所有分区在同一时刻都会耗尽为其分配的吞吐量。因此，为了在分区层面应对短时的工作负载高峰，DynamoDB 引入了突发（bursting）机制，其核心思想是在分区级别让应用可以按尽最大努力使用未被实时消耗的容量，以吸收短暂的访问激增。DynamoDB 会保留每个分区多达 300 秒的未使用容量，用于后续的突发性吞吐需求，这部分未用容量即称为突发容量（burst capacity）。

此外，为了仍然保证工作负载的隔离性，DynamoDB 要求分区只有在所在节点整体存在未用吞吐量时才能突发。系统在存储节点层面通过多组令牌桶来管理容量：每个分区对应两组桶（一个分配桶 allocated、一个突发桶 burst），整个节点还有一组节点桶 node。它们共同构成了准入控制的机制。

每当读或写请求到达存储节点时，系统首先检查对应分区的“分配桶”是否有剩余令牌。若有，则请求被接纳，并同时从该分区与节点级令牌桶中各扣减相应令牌。当分区分配桶中的令牌耗尽后，系统仅在分区突发桶和节点级桶均有可用令牌时，才允许继续处理（突发）请求。

而且，完全依据本地（本节点）令牌桶完成校验，无需跨副本通信。写请求除了检查本地突发桶和节点桶外，还需额外验证该分区其他副本所在节点的节点级令牌桶是否有余量，以保证跨副本一致性与可用性。为支持写请求的额外校验，分区的主副本会定期从各成员副本节点收集节点级令牌余量信息，并据此决定是否允许写请求突发。

自适应容量

DynamoDB 推出了自适应容量（Adaptive Capacity）机制，专门用来应对那些持续时间比较长、突发容量救急不了的高峰期。自适应容量会持续监控所有表的预配置吞吐量和实际消耗情况；当表级别发生节流但整张表的吞吐量仍在预配置范围内时，系统会自动按比例控制算法动态提升该表中热点分区的分配吞吐量。如果表的总消耗超过预配置容量，则会相应地降低刚刚那些已接受提升的分区容量，以避免资源过度使用。自动管理服务等控制平面确保获得加速的分区被迁移到具备足够剩余能力的合适节点上，以保证性能提升能够得到支撑。与突发机制一样，自适应容量也是尽力而为的，但它能消除因访问倾斜导致的 99.99% 以上因为某几个热键访问量太高而被限流的尴尬，从而让应用跑得更稳，也更省钱。

全局准入控制

虽然 DynamoDB 通过突发和自适应容量在很大程度上缓解了非均匀访问带来的吞吐量问题，但这两种方案各有局限。突发机制仅能应对短时的流量峰值，并且依赖于节点本身还有剩余容量；自适应容量则属于被动响应，仅在检测到限流发生后才会启动，这意味着应用在此之前已经经历了短暂的不可用。两者的关键问题是：我们将分区级的容量管理紧密地和准入控制耦合起来了，而准入控制是分散在各个分区中执行的。换句话说，当用户往某个分区发请求时，这个分区自己就决定放行还是拒绝该请求。这种分区粒度的准入控制无法处理非均匀访问模式导致的热点，往往在整体容量闲置的情况下依然出现局部节流，因为每个分区的准入控制只能感知自身的吞吐量和资源使用情况。因此如果能够将准入控制从分区中剥离出来，让分区始终保持可 burst，同时又能保证不同工作负载之间的隔离，将更为高效。

为此，DynamoDB 用全局准入控制（Global Admission Control，GAC）取代了原有的自适应容量。GAC 依然基于令牌桶思想运行：一个中央服务持续监控全表范围内的令牌消耗情况，每个请求路由器在本地维护一个令牌桶；当应用请求到达时，先尝试从本地令牌桶中扣除令牌；当本地令牌不足时，再向 GAC 请求新的令牌。GAC 根据各路由器提交的消耗信息，动态计算并分发下一时间窗口内可用的全局令牌份额，确保即便流量集中在表中某些键上，也不会超过单个分区的最大处理能力。

与此同时，为了多层防护，DynamoDB 保留了分区级的令牌桶，并对其容量进行了上限限制，以防某个应用独占节点资源或过度消耗其存储节点上的吞吐量。这样，GAC 实现了跨分区的全局流量调度，而分区级令牌桶则继续在最底层保障多租户隔离。

平衡消耗的容量

让分区始终保持突发（bursting）能力，就需要 DynamoDB 对突发容量进行有效管理。DynamoDB 在多种硬件实例类型上运行，这些实例在吞吐量和存储能力上各不相同。最新一代的存储节点上往往承载着数千个分区副本，这些分区可能完全无关联，属于不同表，甚至不同客户，而各表的访问模式也千差万别。要将这些副本安全地部署在同一节点上，又能保证可用性、稳定的性能、安全性和弹性，就必须设计出合理的分配方案。

如果只用预配置吞吐量，那很好办：分区数固定，按容量找机器，根本不用担心某个分区会多吃流量。但有了突发和自适应后，分区可能随时超出预设容量使用突发资源，这就意味着某些节点在短时内可能会超载，导致把多个数据分区放到同一台机器上变得棘手。

因此，为了在不牺牲可用性的前提下，提高节点利用率，DynamoDB 实现了一套主动均衡系统：每个存储节点独立监控其上所有分区副本的吞吐量和数据大小，一旦发现总吞吐量超过节点最大容量的阈值，就会向自动管理服务报告一批候选迁移分区。自动管理服务再为这些分区寻找新的存储节点（可在同可用区或跨可用区），确保新节点上尚未存在该分区的副本，从而将它们安全地搬迁出去，降低过度紧凑部署带来的可用性风险。

拆分消费

DynamoDB 在引入全局准入控制和始终可突发能力后，发现当流量高度集中在某些键上时，仍可能出现节流。为此，它会根据分区的实际吞吐量自动扩展：当某个分区的消耗超过阈值时，系统会根据该分区的访问分布（而不是简单地把键范围对半拆分）选择最佳拆分点，将其分成两个子分区。这样可以更精准地将热点区域隔离出来，不过对于只针对单个键或按顺序访问整个键范围的场景，此方法并无优势；对此，DynamoDB 会自动识别并避免执行拆分操作。

按需配置

DynamoDB 还推出了按需表（On-Demand Tables）模式，帮助之前在本地或自建数据库上运行、需要手动配置服务器的应用解放运维负担，是一种无需用户预先规划吞吐量即可弹性扩缩的无服务器模式。按需表通过读写容量单位（RCU/WCU）来自动弹性扩缩，系统会实时监控实际的读写请求量，并能瞬间承载到达表上的流量峰值的两倍。如果后续流量超过此前最大峰值的两倍，DynamoDB 会不断新增分区并按流量情况拆分，以保证应用不会因超出配额而被限流。全局准入控制则负责从整体上监控并保护系统，防止单个应用抢占所有资源；加上基于消耗量的智能分区调度，按需表能够高效利用节点资源，避免触及节点级别的容量上限，让应用在任何突发流量下都能平稳运行。

持久性和正确性

硬件失败

DynamoDB 将预写日志存储在一个分区的所有三个副本中。为了获得更高的持久性，这些预写日志会定期归档到 S3——一个设计上可提供 99.999999999% 持久性的对象存储服务。每个副本仍保留最接近归档时间的日志，这些未归档的日志通常只有几百兆字节大小。

在大型服务中，内存或磁盘等硬件故障时有发生。一旦某个节点发生故障，该节点上承载的所有复制组就会降至两份副本。修复存储副本的过程可能需要数分钟，因为此过程不仅要复制 B 树结构，还要复制预写日志。为快速恢复，当领导副本检测到某个存储副本不健康时，它会立即添加一个日志副本，以确保持久性不受影响。添加日志副本只需几秒钟，因为系统只需从健康副本拷贝最近的预写日志，而无需复制 B 树结构。通过这种仅复制日志的快速修复方式，DynamoDB 能够在绝大多数情况下，保证最近写入操作的高持久性和系统的持续可用性。

静默数据错误

静默数据错误是指在数据存储或传输过程中发生的错误，但并未被系统的常规检测机制（如硬盘固件、操作系统或内存 ECC）发现，从而导致数据不正确却依然被认为是正确的现象。

静默数据错误的来源多种多样，通常与硬件缺陷或环境因素有关：

• 存储介质固件或驱动中的漏洞可能在擦写或读取过程中引入错误；
• 内存中的软错误，如宇宙射线或电磁干扰引起的单比特反转，若未使用 ECC 内存，则无法检测和纠正；
• 网络传输过程中，数据包在多层转换或路由中也可能被篡改而未被底层校验机制捕获；
• CPU 自身的硬件缺陷或老化也可能导致运算结果错误，如计算 1+1=3，却不会被硬件纠错方案发现。

在 DynamoDB 的实践中，某些硬件故障可能导致存储介质、CPU 或内存中出现错误，进而引发数据不正确的情况。由于这些错误往往是隐蔽的、随机出现且难以检测，DynamoDB 广泛使用校验和机制来发现静默错误。在每一条日志记录、消息以及日志文件内部都维护有校验和，用于在节点间的每次数据传输时验证数据完整性。这些校验和如同护栏，能够在各个层面防止错误蔓延。例如，在节点或组件之间传递的每条消息都会计算并校验校验和，因为消息在到达目的地之前可能会经过多层转换，任何一层都可能引入隐性错误。

每个归档到 S3 的日志文件都配有一个清单，其中记录了该日志所属的表、分区，以及日志文件中数据的起止标记。负责将日志文件归档到 S3 的代理在上传数据前会执行多项校验，包括但不限于：验证每条日志记录是否属于正确的表和分区；校验每条记录的校验和以发现任何静默错误；检查日志文件的序列号是否连续无缺。只有在所有校验通过之后，日志文件及其清单才会被归档。归档代理在复制组的三个副本上均运行；如果某个代理发现日志文件已被归档，它会下载该文件并与本地的预写日志进行比对，以再次验证数据完整性。此外，每个日志文件和清单文件在上传到 S3 时都带有内容校验和，S3 在执行上传操作时会核对该校验和，从而防范数据在传输过程中的任何损坏。

连续性校验

DynamoDB 会持续对静态存储中的数据进行校验，以期发现任何未被预见的静默数据错误或比特衰变。

一种典型的连续校验机制是擦洗，该流程的目标有两点：

• 一是验证复制组中三份副本的数据是否完全一致；
• 二是将在线副本的数据与通过归档的预写日志条目离线重建的副本进行比对。

离线重建流程详见下一小节。验证时，系统会计算在线副本的校验和，并将其与从 S3 中归档日志条目生成的快照校验和进行比对。

擦洗机制作为多层防护的一环，用于检测在线存储副本与基于日志历史重建副本之间的任何不一致性。这些全面的校验手段极大地增强了对运行中系统的信心。同时，全局表副本也采用了类似的连续校验技术。开发者发现，对静态存储数据进行持续校验，是防范硬件故障、静默数据损坏乃至软件缺陷的最可靠方法。

备份和恢复

除了防范物理介质损坏之外，DynamoDB 还支持备份与恢复机制，以防止客户应用程序中的逻辑错误造成的数据损坏。备份和恢复操作不会影响表的性能或可用性，因为它们是基于已归档至 S3 的预写日志构建的。这些备份在多分区范围内可达最接近秒级的一致性，而且它们都是 DynamoDB 表的完整副本，存储于 Amazon S3 存储桶中，用户可随时将备份数据恢复到新的 DynamoDB 表中。

此外，DynamoDB 支持按时间点恢复（Point-in-Time Restore，PITR）。通过 PITR，用户可以将表在过去 35 天内任意时间点的内容恢复到同一区域内的另一张表中。对于启用了按时间点恢复功能的表，DynamoDB 会定期对该表所属的分区进行快照并上传至 S3，快照的生成频率由该分区累积的预写日志量决定。也就是说，DynamoDB 通过快照与预写日志的配合使用，来实现按时间点恢复。当用户发起恢复请求时，DynamoDB 会为表的各个分区选取最接近请求时间的快照，应用至该时间点的预写日志，生成恢复用的表快照，并完成恢复操作。

高可用性

为实现高可用性，DynamoDB 表在一个区域内跨多个可用区进行分布和复制，并定期通过模拟真实流量的断电测试来验证对节点、机架及可用区故障的容灾能力。测试过程中，调度器会随机切断部分节点电源，随后工具会检查数据库中的数据在逻辑上保持完整且无损坏，从而确保系统在经历多种故障场景后仍能持续提供高度可靠的存储服务。

写和一致性读的可用性

写入能不能继续，关键就在于有没有领导者副本（leader）在正常工作，以及能不能凑齐足够的投票副本（write quorum）来同意这次写操作。在 DynamoDB 里，三个可用区（AZ）里各有一份数据，只要其中任意两份还能正常响应，就能完成写入。要是某个副本突然挂了，leader 会立刻再拉来一个日志副本（log replica）顶替它，这样写操作就不会因为缺少投票而被卡住。

[!NOTE]

在 DynamoDB 的 Multi-Paxos 共识中，日志副本 与普通数据副本具有相同的投票权重：当 leader 发起写入时，它会在 Phase 1（Prepare）和 Phase 2（Accept）中向所有活跃副本，包括日志副本，发送 Paxos 消息，日志副本在本地持久化写前日志后，会对 Accept 请求投下赞成票，以满足多数要求，从而使写操作被确认并返回给客户端。日志副本由于只存储日志记录，无需同步完整数据结构，能快速上线并参与投票，大幅缩短恢复时间，确保写入可用性不被中断。

至于一致性读取（consistent read），只有 leader 能给用户最新、最靠谱的数据；而最终一致性读取（eventual consistent read）则可由任意副本响应，哪怕数据还没完全同步。要是 leader 出问题，其他副本会迅速发现，并自动推举出一个新的 leader，这样读写服务就能尽快恢复，不会大面积中断。

失败检测

新的 leader 当选后，必须等待旧 leader 的租约到期才能开始提供写入和强一致性读取服务，这一过程虽然只需数秒，却会在这段时间内阻断新写入和一致性读取，影响可用性。为了尽快发现 leader 故障并将此窗口期降至最低，DynamoDB 采用了快速且可靠的故障检测机制：当某个副本长时间未收到 leader 的心跳时，它会向同组的其他副本询问它们是否仍能与 leader 通信；若其他副本反馈 leader 健康，则放弃发起选举，从而避免因灰度网络故障，如节点与 leader 间的单向通信中断或路由故障，导致的误判与不必要的 leader 选举。该改进显著减少了系统中因误判而触发的冗余选举，提升了整体高可用性。

测量可用性

DynamoDB 针对全局表（Global Tables）和区域表（Regional Tables）分别设计了 99.999% 和 99.99% 的可用性目标；可用性按每 5 分钟区间内成功处理请求的比例来计算。为确保达标，DynamoDB 在服务级别和表级别持续监控可用性指标，实时跟踪并在错误率超过阈值时触发面向用户的告警，以便自动或人工干预；同时，每日汇总各用户的可用性数据并上传至 S3，供后续趋势分析。此外，DynamoDB 还通过两类客户端监测用户侧感知可用性：一是使用 DynamoDB 作为数据存储的内部亚马逊服务，二是部署在各可用区并通过所有公网端点访问的金丝雀应用（Canary Applications）。真实流量和灰度故障检测能帮助 DynamoDB 全面评估并优化客户实际体验到的可用性与延迟。

[!NOTE]

金丝雀应用是一种合成监控和灰度测试手段，通过在生产环境中运行专门的轻量级客户端或小规模流量，持续地向系统发起真实或模拟请求，以监测系统在不同地理区域、不同网络路径和不同服务端点下的可用性和性能表现。这些应用通常分布在各可用区内，通过定期及实时的请求和心跳检测，帮助团队提前发现灰度网络故障、API 错误或性能退化，及时触发告警并辅助故障排查，从而确保用户侧感知到的可用性和延迟符合服务级别目标。

部署

与传统关系型数据库不同，DynamoDB 在部署过程中无需停机维护窗口，也不会影响客户体验到的性能和可用性。软件部署通常用于引入新功能、修复缺陷和优化性能，往往涉及对多个服务的更新。DynamoDB 以固定节奏推送软件更新，将系统从一种状态切换到另一种状态。新版本的软件在部署前会经历完整的开发和测试流程，以确保代码的正确性。多年来，在多次部署实践中，开发者认识到不仅要关注初始状态和目标状态，还需考虑在某些情况下新版本可能无法正常工作，需回滚至先前版本，而回滚后的状态往往与最初的版本并不完全相同。回滚流程如果在测试中被忽略，可能会对客户造成影响。为此，DynamoDB 在每次部署前都会在组件级别运行一整套升级和降级测试，主动执行回滚操作并运行功能测试，以便及早发现那些仅在回滚时才会显现的问题。

在分布式系统中，将软件部署到单个节点与部署到多个节点存在本质差异。部署操作并非原子性的；在部署过程中，集群中始终会有部分节点运行旧版本代码，另一些节点运行新版本代码。更复杂之处在于，新版本可能引入新的消息格式或修改协议，使得旧版本节点无法解析。DynamoDB 通过先读后写（read-write）部署模式来应对这类变更。该流程分为多个步骤：首先部署能够识别新消息格式或协议的版本，确保所有节点都能读取新消息；然后再启用新消息的发送功能。通过此种方式，新旧消息可在系统中并存，即使在回滚的情况下，系统仍能识别两种消息格式。

所有更新都会先在少量节点上进行灰度发布，以降低因部署故障带来的潜在风险。同时，DynamoDB 会对可用性指标设定告警阈值：若部署过程中错误率或延迟超出阈值，则自动触发回滚，将系统迅速恢复到上一个稳定版本。针对存储节点的软件部署，系统还会触发领导者副本切换：旧领导者主动放弃领导权，新领导者在无需等待旧领导者租约过期的情况下立即接手，从而保证可用性不受影响。

依赖外部服务

为了确保高可用性，DynamoDB 在请求路径中所依赖的所有服务，其可用性都应优于 DynamoDB；或者在这些依赖服务性能受损时，DynamoDB 仍能继续运行。DynamoDB 在请求路径中所依赖的服务示例包括用于身份验证的 AWS 身份与访问管理服务（IAM），以及对使用客户主密钥加密的表进行加密/解密的 AWS 密钥管理服务（KMS）。DynamoDB 利用 IAM 和 AWS KMS 对每一次客户请求进行身份验证。尽管这些服务本身具有很高的可用性，DynamoDB 的设计目标是：即使它们暂时不可用，也不影响 DynamoDB 的正常运行，并保持相同的安全保障。

对于 IAM 和 AWS KMS，DynamoDB 采用了一种静态稳定（statically stable）设计，即当某个依赖出现故障时，系统仍能保持运行。虽然可能无法获取该依赖在故障后才会更新的信息，但在故障发生之前已经获得的信息仍可继续使用，确保系统功能不受影响。具体而言，DynamoDB 会在执行请求认证的路由器上缓存来自 IAM 和 AWS KMS 的验证结果，并以异步方式定期刷新这些缓存。如果 IAM 或 KMS 服务出现不可用情况，路由器仍能在预定的延长时间内继续使用缓存结果。只有当客户端的请求被路由到那些尚未缓存相关结果的路由器时，才会受到影响；但在实际运行中，即便 IAM 或 KMS 性能受损，对整体服务的影响也极为有限。此外，通过本地缓存验证结果，还能在系统高负载时减少对外部调用次数，从而加快响应速度并提升系统吞吐性能。

元数据可用性

请求路由器所需的最重要的元数据之一是表的主键与存储节点之间的映射关系。DynamoDB 最初将这些路由信息存储在 DynamoDB 表自身中，该路由信息包括表的所有分区、每个分区的键范围，以及托管该分区的存储节点。当路由器接收到一个之前未见过的表的请求时，它会下载该表的全部路由信息并本地缓存。由于分区副本的配置信息很少变化，缓存命中率约为 99.75%。然而，这种缓存机制也带来了双峰性能表现的问题：在冷启动（缓存为空）时，路由器对每个请求都需要进行一次元数据查询，导致元数据服务的流量骤增，最高曾占到路由器总请求的 75%，从而影响系统性能并可能导致不稳定。此外，当缓存失效时，过多的直接查询压力还可能引发级联故障。

为了解决这一问题，DynamoDB 构建了一个名为 MemDS 的分布式内存存储系统，用以存放所有元数据并在 MemDS 集群中复制。MemDS 支持水平扩展，可处理 DynamoDB 的全部入站请求流量；其内部采用 Perkle 数据结构（Patricia 树与 Merkle 树的混合体），既可通过完整键或键前缀进行查找，也支持小于、大于和区间等范围查询，以及特殊的 floor（不大于指定键的最大键）和 ceiling（不小于指定键的最小键）两种操作。

在每台请求路由器上部署了新的分区映射缓存，替代原有的冷启动式本地缓存。新的缓存策略是：无论命中与否，都会异步向 MemDS 发起刷新请求，以确保 MemDS 集群持续承接稳定的流量。虽然这会增大元数据集群的负载，但可防止当缓存失效时对系统其他部分造成级联压力。

值得注意的是，DynamoDB 存储节点才是分区成员信息的权威来源。存储节点会将分区成员的更新推送至 MemDS，并同步到所有 MemDS 节点。如果路由器从 MemDS 获取到的成员信息已过期，则它会尝试联系该分区所在的存储节点：存储节点要么返回最新成员信息，要么返回错误码，触发路由器再次向 MemDS 查询，从而保证请求始终能被正确路由。

地理区域失败

AWS 在全球设立了多个大型地理区域（如 us-east-1、ap-southeast-1），每个区域由多个物理数据中心组成。那现在假设某个应用部署在 us-east-1 读写 DynamoDB 表，但某天该 Region 遭遇网络中断、数据中心宕机或 KMS 密钥失效，导致服务不可用。此时，所有对该表的读/写请求将失败，影响业务可用性。所以，开发者需要保障即使某 Region 宕机，也能无缝提供服务，同时保证不同地区的用户可以就近访问数据。那么这就是 DynamoDB 全局表的用武之地。

为 DynamoDB 表启用全局表，会在多个 Region 如 us-east-1, eu-west-1, ap-northeast-1 等生成完全对等的副本，并实现数据自动同步。所有副本都支持读写请求，允许客户端按需选择 Region，你同样可以选择“任一区域写入”模式，根据数据幂等性控制冲突。更新是异步的，多个 Region 可能产生延迟；若同一个条目（数据）在不同 Region 同时写入，DynamoDB 内置机制根据时间戳采用 “Last‑Writer‑Wins” 规则解决冲突。

上图中，每个区域既可本地读写，又会异步将写操作通过 DynamoDB Streams 复制到其它区域；当同一条记录在不同区域近乎同时发生更新时，Global Tables 会基于写入时间戳择优保留“最新”版本，确保最后全局一致。

如果某个 Region 宕机，全局表继续在其他 Region 上读写，不受影响。宕机区域恢复后，会自动同步补全所有挂起写入数据，无需人工干预。

假设有两个区域 A 和 B，那么两者的服务都可用时的流程如下：

客户端（App A）向 Region A 的 DynamoDB 表写入数据,写操作一旦在 Region A 达到持久化，立即返回成功给 App A，保证写入延迟最低（最终一致性或强一致性均可选）。DynamoDB 利用 Global Tables 机制，通过内部的 DynamoDB Streams 将写操作异步推送到 Region B 的副本表，在平时可让 Region B 的应用（App B）直接从 Region A 读取最新数据。副本表会在通常 1 秒内同步到最新写入项，Get 操作返回数据给 App B。

如果完成上图的第五步之后，Region A 的数据存储宕机，那么 DynamoDB 基于全局表的故障回复和切换如下：

通过 DNS 或客户端配置，将写流量切换到 Region B。切换后，App B 向 Region B 写入新数据，Region B 本地确认写入成功。当 Region A 恢复后，全局表会将 Region B 的变更异步推回 Region A。

复制

Region 内复制

多个可用区（AZ1、AZ2、AZ3）通过高速专有网络互联，数据同步延迟通常在毫秒级。每个 AZ 内都有一份完整数据副本，读写请求可路由至任一 AZ，以提升性能和可用性。

在同一区域内部署的分布式存储通常通过同步复制协议（如 Paxos、Raft）保证写操作在所有 AZ 同步完成后再返回成功，从而确保读写顺序严格一致。

单个 AZ 故障时，流量可自动切换到其他 AZ，减少服务中断，满足 99.99% 甚至 99.999% 的 SLA 要求。每份数据至少存储在三个物理位置，具备抗硬件损坏和局部灾难的能力，典型耐久性可达 11 个 9（99.999999999%）。

跨 Region 复制

数据从主区域（Region A）异步复制到一个或多个目标区域（Region B、Region C）。跨区域复制常用于灾备、合规和全球用户读写场景。

主要关注点

• 写入性能：跨区域的往返时延通常在数十至数百毫秒之间，远高于区域内几十毫秒的延迟，影响写操作的吞吐量和响应时间。为了避免同步复制带来的高延迟，多数场景采取异步复制，但这会牺牲一致性和可能造成数据丢失。
• 故障爆炸半径：一旦主区域出现故障，异步复制可能无法及时到达目标区域，导致大量未复制的数据面临丢失风险，同时故障影响范围横跨多个地理区域。因此需设计分片或多活策略，将流量和数据分散，以尽量缩小单点故障影响范围。
• 算法超时：跨区域通信更易遭遇丢包和波动，可能导致复制协议中同步或心跳消息超时。需要在复制算法中引入指数退避、幂等操作和批量确认等机制，以避免超时重试带来的性能降级。

DynamoDB Streams 是 DynamoDB 提供的变更数据捕获机制，它记录表中每次写操作的顺序日志并保留 24 小时，供下游应用实时消费。

跨区域的复制流程具体如下：源区域（Region A）通过 DynamoDB Streams 将写操作的变更记录捕获到一个持久化日志中（Stream），然后由一组可横向扩展的 RepOut 进程并行地消费这些变更，打包成包含主键、属性和时间戳的写入请求（Put(k, v, ts)），并异步发送到目标区域（Region B）。目标区域由一组 RepIn 进程并行接收这些请求，并在写入本地表前，基于附带的时间戳与本地存储的版本进行比较，仅当本地版本更旧时才执行写入，以实现幂等性和冲突解决。通过在 RepOut/RepIn 层面使用多进程或无服务器函数（如 Lambda）对不同 Stream 分片或写请求进行分片处理，并结合批量提交与并发控制，就能在线性扩展吞吐的同时保证同分区写入的顺序性和最终一致性。

Recovery Point Objective（RPO）是灾难恢复和业务连续性规划中的关键指标，定义了在发生故障或灾难时，允许丢失数据的最长时间窗口。它决定了需要多频繁地进行备份或数据复制，以保证在灾难发生后仍能接受的数据损失范围。

若主站在此窗口内发生故障，流式日志中未传输的更新就会丢失，造成 “Lost Updates” 问题。具体流程如下：

1. 应用在区域 A 执行 Put(k, v1)，本地存储和流式层记录 k, v1, ts1，立即返回成功。
2. 在 RepOut 将 k, v1, ts1 发送到区域 B 前，区域 A 突发故障（网络中断或宕机），流式层中尚未传输的 v1 列入 RPO 窗口，随故障一起丢失。
3. 故障切换后，应用在区域 B 执行 Get(k) 得到旧值 v0，再执行 Put(k, v2 = v0 + 1)。
4. 新写入 v2 覆盖了原本应该是 v1 的内容，导致先前区域 A 的更新完全丢失，即 “Lost Update”。

为有效防范 “Lost Updates” 在故障切换时的发生，首先应尽量缩短 RPO 窗口，即将异步复制升级为半同步或全同步复制，确保主库在确认写入时也等待至少一个备库的持久化 ACK，从而将未复制数据丢失的概率降至最低；与此同时，可为敏感或高价值的写操作采用混合复制策略，仅对关键数据启用同步复制，其余业务继续使用异步复制以兼顾性能与成本。其次，优化网络与资源配置，提升 RepOut/RepIn 通道的带宽和优先级，减少复制积压，并结合近连续数据保护或实时流式复制技术，将数据写入与传输延迟控制在秒级以内，以实现接近零 RPO。最后，强化应用层幂等与冲突检测，通过在写操作中引入版本号、幂等键或乐观并发控制策略，在 RepIn 应用更新时比对版本号而非仅凭时间戳判断新旧，或采用 CRDT 等机制进行多副本冲突合并，以保证即便出现复制延迟也不会因时间戳“后写胜出”而丢掉任何有效更新。

编程接口

读写操作

由于 DynamoDB 是一个键值存储，应用程序最常用的操作包括：

• 读取项（GetItem）
• 插入项（PutItem）
• 更新项（UpdateItem）
• 删除项（DeleteItem）

这其中，插入、更新和删除操作统称为写操作（writes）。写操作可以可选地指定一个条件，只有当该条件得到满足时，操作才会成功执行。

事务操作

DynamoDB 提供了两种事务操作：

• TransactGetItems（读取事务）
• TransactWriteItems（写入事务）

这些操作是以单次请求提交的，要么全部成功，要么立即失败，不会阻塞。TransactGetItems 和 TransactWriteItems 相对于其他 DynamoDB 操作按可串行化顺序执行。

TransactGetItems 会从一个或多个表中检索最新版本的项，并在同一时间点读取它们，返回的是一致快照。如果有其他冲突操作正在修改任一读取项，请求将被拒绝。

TransactWriteItems 是同步且幂等的写入事务操作，可原子性地在一个或多个表中执行多个项的创建、更新或删除操作。它使用客户端请求令牌来保证幂等性，并可附带对当前项值的预先条件校验。只要任一个预条件不成立，请求即被拒绝。

假设我们有一个在线市场应用，涉及客户（Customers）、产品（Products）和订单（Orders）三张表：

• Customers 表以客户 ID 为主键，存储客户信息及地址；
• Products 表以产品 ID 为主键，存储产品价格和库存状态；
• Orders 表以订单 ID 为主键，存储完整订单记录。

在处理一次订单时，需要确保：

1. 客户账户已通过验证；
2. 产品处于可用状态并更新为已售出；
3. 订单条目已创建。

这些操作应当作为一个事务执行，否则可能造成数据不一致。

例如，在购买一本书的事务中：

• 使用 ConditionCheck：在 Customers 表验证客户存在，但不修改任何数据；
• 使用 UpdateItem：在 Products 表确认书籍库存并将其标记为已售；
• 使用 PutItem：在 Orders 表创建订单记录。

整个过程在一个 TransactWriteItems 请求中完成，确保步骤要么全部成功，要么全部失败，保持数据一致。

该事务写入的具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// Check if customer exists
Check checkItem = new Check()
  .withTableName("Customers")
  .withKey(Collections.singletonMap("CustomerId", new AttributeValue("CustomerUniqueId")))
  .withConditionExpression("attribute_exists(CustomerId)");

// Update status of the item in Products
Update updateItem = new Update()
  .withTableName("Products")
  .withKey(Collections.singletonMap("ProductId", new AttributeValue("BookUniqueId")))
  .withConditionExpression("expected_status = :expected")
  .withUpdateExpression("SET ProductStatus = :newStatus")
  .withExpressionAttributeValues(Map.of(
    ":expected", new AttributeValue("IN_STOCK"),
    ":newStatus", new AttributeValue("SOLD")
  ));

// Insert the order item in the Orders table
Put putItem = new Put()
  .withTableName("Orders")
  .withItem(Map.of(
    "OrderId", new AttributeValue("OrderUniqueId"),
    "ProductId", new AttributeValue("BookUniqueId"),
    "CustomerId", new AttributeValue("CustomerUniqueId"),
    "OrderStatus", new AttributeValue("CONFIRMED"),
    "OrderCost", new AttributeValue().withN("100")
  ))
  .withConditionExpression("attribute_not_exists(OrderId)");

// Assemble the transaction request
TransactWriteItemsRequest twiReq = new TransactWriteItemsRequest()
  .withTransactItems(
  new TransactWriteItem().withCheck(checkItem),
  new TransactWriteItem().withUpdate(updateItem),
  new TransactWriteItem().withPut(putItem)
);

// Single transaction call to DynamoDB
AmazonDynamoDB client = AmazonDynamoDBClientBuilder.defaultClient();
client.transactWriteItems(twiReq);

事务执行

事务路由

所有发送到 DynamoDB 的操作都会先到达一组称为请求路由器的前端主机。请求路由器负责对每个请求进行认证并根据访问的键，将请求路由到相应的存储节点。键范围（key‑range）与存储节点的映射关系由元数据子系统管理。

与非事务请求类似，每个事务操作也首先由请求路由器接收。路由器会进行必要的请求身份验证和权限授权，然后将请求转发给一组事务协调器。事务协调器集群中的任意一个实例都可以接管任意事务。

事务协调器将事务分解为针对各个条目的子操作，并启动一套分布式协议，由这些数据项所在的存储节点参与执行。上图展示了执行一笔事务时，所涉及的各组件的高层架构图。

时间戳顺序

DynamoDB 使用时间戳排序（Timestamp Ordering）机制来定义事务的逻辑执行顺序。当收到事务请求后，事务协调器会使用其当前时钟的值为该事务分配一个时间戳。

为了应对大规模的事务负载，系统中运行着大量并行工作的事务协调器，不同的协调器会为不同的事务分配时间戳。只要事务的执行顺序与其分配的时间戳一致，就可以确保可串行性。

一旦时间戳分配完成并通过了预检查，参与该事务的存储节点就可以独立执行各自负责的操作，无需进一步协调。每个存储节点各自负责保证涉及其数据项的请求按正确顺序执行，并拒绝那些无法正确排序的冲突事务。

即便事务协调器之间的时钟未严格同步，只要维持事务在时间戳上的一致性，也可以保证可串行性。但若协调器的时钟越精确，成功事务的比例就越高，而且得到的事务序列越贴近真实时间顺序。

DynamoDB 的事务协调器从 AWS 提供的时间同步服务（AWS Time Sync Service）获取时间，因此多个协调器之间的时钟能维持在微秒级别的同步。

然而，即使所有时钟完全同步，事务在传输过程中仍可能因为网络延迟、事务协调器的故障与恢复等问题，导致事务在存储节点上的到达顺序不一致。为了解决这一问题，存储节点会使用存储的时间戳信息来处理任意顺序到达的事务请求。

每个事务在进入存储节点前，都会带上事务协调器分配的时间戳 T。存储节点为每个条目维护了一个记录该项最后执行事务的最大时间戳（lastCommittedTimestamp）。当节点收到一个事务请求时，它会：

1. 检查 T 是否 ≥ lastCommittedTimestamp；
2. 如果满足，则执行这个事务，并将 lastCommittedTimestamp 更新为 T；
3. 否则（即 T 比已有时间戳小），说明该事务时间在线谱中落在历史里，节点会拒绝该请求，避免生成不符合时间戳顺序的写入。

写事务的二阶段提交协议

两阶段协议确保事务中的所有写入操作都能原子性执行并保持正确顺序。为实现原子性，事务协调器首先在第一阶段对所有待写入项执行准备（prepare）。如果所有存储节点都接受该事务，则第二阶段协调器发出提交（commit）指令以执行写操作；若有任一节点无法接受，则协调器会取消该事务。以下代码展示了 TransactWriteItem 协议的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def TransactWriteItem(transact_write_items):
    # Prepare all items
    TransactionState = "PREPARING"
    for operation in transact_write_items:
        sendPrepareAsyncToSN(operation)
    
    waitForAllPreparesToComplete()

    # Evaluate whether to commit or cancel the transaction
    if all_prepares_succeeded():
        TransactionState = "COMMITTING"
        for operation in transact_write_items:
            sendCommitAsyncToSN(operation)
        waitForAllCommitsToComplete()
        TransactionState = "COMPLETED"
        return "SUCCESS"
    else:
        TransactionState = "CANCELLING"
        for operation in transact_write_items:
            sendCancellationAsyncToSN(operation)
        waitForAllCancellationsToComplete()
        TransactionState = "COMPLETED"
        return getReasonForCancellation()

为了实现写事务的时间戳排序机制，DynamoDB 在每次写操作（无论是单项写入还是事务写入）后都会将该事务的时间戳记录在对应项上。此外，存储节点还会为每个正在进行的事务持久化事务元数据，包括事务 ID 和时间戳。这些元数据附带在事务涉及的项上，并在分区重分裂等事件中随项迁移，从而确保事务执行不被结构变更干扰，可并行进行。一旦事务结束，这些元数据即被清除。

在协议的准备阶段，事务协调器向每个主存储节点发送一条 prepare 消息，其中包含时间戳、事务 ID 和针对该项的拟执行操作。存储节点仅当以下所有条件都满足时，才接受该事务中的该项写入请求：

• 该项满足所有预条件；
• 该写操作未违反系统限制（如条目大小上限）；
• 事务的时间戳大于该项上次写入时记录的时间戳；
• 当前没有其他已接受但尚未提交的事务尝试写入同一项。

以下代码展示了这一阶段的伪代码。需要指出的是，上述最后两个条件虽然正确，但较为严格，后续内容会讨论它们的松弛方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def processPrepare(input: PrepareInput):
    item = readItem(input)

    if item is not None:
        if (
            evaluateConditionsOnItem(item, input.conditions) and
            evaluateSystemRestrictions(item, input) and
            item.timestamp < input.timestamp and
            item.ongoingTransactions is None
        ):
            item.ongoingTransaction = input.transactionId
            return "SUCCESS"
        else:
            return "FAILED"
    else:
        # item does not exist
        item = Item(input.item)
        if (
            evaluateConditionsOnItem(input.item, input.conditions) and
            evaluateSystemRestrictions(input) and
            partition.maxDeleteTimestamp < input.timestamp
        ):
            item.ongoingTransaction = input.transactionId
            return "SUCCESS"

    return "FAILED"

若所有参与存储节点都接受，则事务协调器进入提交阶段；若任一节点拒绝，则协调器发出事务取消指令。提交/取消过程的伪代码如下。在提交阶段，参与节点执行本地项的写入，并将项的最后写入时间戳更新为该事务的时间戳；对于只带预条件检查但未修改的项，其时间戳也同步更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def processCommit(input: CommitInput):
    item = readItem(input)

    if item is None or item.ongoingTransaction != input.transactionId:
        return "COMMIT_FAILED"

    applyChangeForCommit(item, input.writeOperation)
    item.ongoingTransaction = None
    item.timestamp = input.timestamp
    return "SUCCESS"


def processCancel(input: CancellationInput):
    item = readItem(input)

    if item is None or item.ongoingTransaction != input.transactionId:
        return "CANCELLATION_FAILED"

    item.ongoingTransaction = None

    # item was only created as part of this transaction
    if item.wasCreatedDuringPrepare:
        deleteItem(item)

    return "SUCCESS"

当所有参与节点完成提交或取消操作后，事务协调器向请求路由器发送“事务完成”响应，指明事务是否成功提交。请求路由器再将结果返回给客户端。

对于已删除的项，由于无法继续维护最后写入时间戳，因此 DynamoDB 不使用 tombstone（永久删除标记），以避免高额存储成本及垃圾回收开销。取而代之的是，每个分区维护一个最大删除时间戳。当事务删除某项时，如果其时间戳高于当前分区的最大删除时间戳，就更新该时间戳。后续若准备写入一个在当前分区中不存在的项，存储节点会将新事务的时间戳与此分区的最大删除时间戳进行比较，以决定是否接受该事务。这种按分区划分的时间戳设计既正确又高效。

在当前机制下，部分事务可能因其时间戳低于分区最大删除时间戳而被取消，而如果采用 tombstone 机制，这类事务本可提交。但实践中，此类取消事务占比极低，不会影响系统性能与一致性。

读事务协议

DynamoDB 采用了一种两阶段无写入协议来处理只读事务，与写事务及其他系统有显著不同。为了避免在每次读操作中维护持久化且复制的数据的读取时间戳，引入了额外的延迟和成本，DynamoDB 发明了这种高效方案来执行读取事务。

协议的第一阶段：事务协调器会读取事务读取集合（read‑set）中的所有项。如果有任一项正被其他写事务处理，读取事务立即失败；否则进入第二阶段。存储节点在返回每个项的值时，还会附带该项的当前已提交的日志序列号（LSN），它代表该存储节点上最后一次写操作的序列编号，且是单调递增的。

协议的第二阶段：重新读取这些项，并对比第一阶段返回的 LSN。如果所有项的 LSN 均未改变，说明在两次读取期间未被修改，读取事务成功返回所读值；如果有任一项的 LSN 已变，则读取事务失败 。

无论事务成功或失败，存储节点都会返回 LSN，这让事务协调器能够在出现冲突时，仅针对变化的项重新执行读取，而无需回到事务开始阶段，从而避免完全重启。如果某项正处于写事务的准备阶段，存储节点会直接拒绝该读取请求。

回复与容错

DynamoDB 支持自动从存储节点故障中恢复，因此存储节点故障并不会影响事务协议的执行。如果负责某个数据项的主存储节点发生故障，该分区会自动将主节点角色切换到复制组中的其他存储节点。以前主节点已接受的事务元数据被持久化并在复制组内同步，因此新主节点可以继续处理这些事务而不会丢失信息。事务协调器也不需要感知主节点发生了变更。

然而，事务协调器失败的问题更为关键。协调器会因硬件或软件故障而崩溃，为了确保事务的原子性和最终能够完成，协调器将每笔事务及其当前状态记录在一个事务账本（ledger）中 。系统中运行有多个恢复管理器，它们会定期扫描账本，查找已接收但在合理时间内未完成的事务，并将这些事务重新分配给新的事务协调器继续执行协议。如果协调器被误判为失败而启动了操作的重复执行，并不会带来问题，因为存储节点对重复提交的写操作会进行幂等处理，识别出已执行操作并忽略它们。

事务完成后，协调器会向账本中写入“已完成”记录，表明该事务不再需要处理。相关信息可在日志中保留，用于监控与调试，也可以在后续清理。账本一般设计为 DynamoDB 表，使用事务 ID 作为主键。此外，恢复管理器会并行地扫描账本，从随机起始键开始，处理上千条未完成事务。

存储节点自身也可触发恢复流程：当某项被挂起一段时间（如长期处于 prepare 状态），其他请求读写该项时，节点会向恢复管理器发送提示，包括事务 ID 与项键，后者再依据账本状态决定是否继续处理该事务。

如果账本中显示该事务尚未完成，恢复管理器会重新分配事务给协调器，继续执行事务的后续阶段（commit 或 cancel）。

事务账本中已标记完成或不在账本中，表示该事务可能已经成功提交或被取消。此时恢复管理器不会触发新的执行流程，存储节点也因此可以安全清理该事务的挂起状态。

Questions

Why does DynmoDB not use the two-phase locking protocol?

While two-phase locking is used traditionally to prevent concurrent transactions from reading and writing the same data items, it has drawbacks. Locking restricts concurrency and can lead to deadlocks. Moreover, it requires a recovery mechanism to release locks when an application fails after acquiring locks as part of a transaction but before that transaction commits. To simplify the design and take advantage of low-contention workloads, DynamoDB uses an optimistic concurrency control scheme that avoids locking altogether.

With DynamoDB, what is the role of a transaction coordinator?

The Transaction Coordinator plays a central role in handling transactions that span multiple items or storage nodes. The TC is responsible for:

• breaking down the transaction into individual operations and coordinating these operations across the necessary storage nodes.
• ensuring that the operations follow two-phase commit and all parts of the transaction are either completed successfully or rolled back.
• assigning timestamps to ensure the correct ordering of operations and managing any potential conflicts between concurrent transactions.

Is DynamoDB a relational database management system?

No, DynamoDB is not a relational database management system. It is a NoSQL database, specifically a key-value and document store. Here’s how it differs from an RDBMS:

1. Data Model: DynamoDB does not use tables with fixed schemas like relational databases. Instead, it stores data as key-value pairs or documents (JSON-like structure). Each item can have different attributes, and there’s no need for predefined schemas.
2. Relationships: Relational databases focus on managing relationships between data (using joins, foreign keys, etc.), while DynamoDB is optimized for storing large amounts of data without complex relationships between the data items.
3. Querying: RDBMSs typically use SQL for querying data, which allows for complex joins and aggregations. DynamoDB uses its own API for querying and does not support SQL natively. While it allows querying by primary key and secondary indexes, it doesn’t support joins.
4. Consistency and Transactions: DynamoDB supports eventual consistency or strong consistency for reads, while traditional relational databases typically ensure strong consistency through ACID transactions. DynamoDB has introduced transactions, but they work differently compared to those in relational databases.
5. Scalability: DynamoDB is designed for horizontal scalability across distributed systems, allowing it to handle very large amounts of traffic and data by automatically partitioning data. In contrast, RDBMSs are typically vertically scaled and are not as naturally distributed.

How is DynamoDB’s transaction coordinator different than Gamma’s scheduler?

• DynamoDB’s transaction coordinator uses Optimistic Concurrency Control (OCC) to manage distributed transactions, ensuring atomicity without 2PC, focusing on scalability and performance in a globally distributed system.
• Gamma’s scheduler, on the other hand, uses the traditional Two-Phase Locking (2PL) protocol to guarantee strong consistency in a distributed environment, prioritizing strict coordination across nodes.

Name one difference between FoundationDB and DynamoDB?

FoundationDB: FoundationDB is a multi-model database that offers a core key-value store as its foundation, but it allows you to build other data models (such as documents, graphs, or relational) on top of this key-value layer. It’s highly flexible and provides transactional support for different types of data models via layers.

DynamoDB: DynamoDB is a NoSQL key-value and document store with a fixed data model designed specifically for highly scalable, distributed environments. It does not offer the flexibility of building different models on top of its architecture and is focused on high-performance operations with automatic scaling.

What partitioning strategy does FoundationDB use to distribute key-value pairs across its StorageServers?

FoundationDB uses a range-based partitioning strategy to distribute key-value pairs across its StorageServers.

Here’s how it works:

1. Key Ranges: FoundationDB partitions the key-value pairs by dividing the key space into contiguous ranges. Each range of keys is assigned to a specific StorageServer.
2. Dynamic Splitting: The key ranges are dynamically split and adjusted based on data distribution and load. If a particular range grows too large or becomes a hotspot due to frequent access, FoundationDB will automatically split that range into smaller sub-ranges and distribute them across multiple StorageServers to balance the load.
3. Data Movement: When a key range is split or needs to be rebalanced, the corresponding data is migrated from one StorageServer to another without manual intervention, ensuring even distribution of data and load across the system.

Why do systems such as Nova-LSM separate storage of data from its processing?

• Independent Scaling: Storage and processing resources can scale independently to meet varying load demands.
• Resource Optimization: Storage nodes focus on data persistence and I/O performance, while processing nodes handle computation, improving overall resource efficiency.
• Fault Tolerance: Data remains safe in storage even if processing nodes fail, ensuring high availability.

Reference:

• https://www.usenix.org/system/files/atc23-idziorek.pdf
• https://www.usenix.org/system/files/atc22-elhemali.pdf