Data Model

SQL++ has a more flexible data model:

• It relaxes traditional SQL’s strict rules to handle modern, semi-structured data like JSON or CBOR.
• SQL++ databases can store self-describing data, meaning you don’t need a predefined schema (data structure).

Supports diverse data types:

• Data can be single values (scalars), tuples (a set of key-value pairs), collections (like arrays or multisets), or combinations of these.
• Unlike traditional SQL, tuples in SQL++ are unordered, which means the order of attributes doesn’t matter.

Allows duplicate attribute names but discourages them:

• This is to accommodate non-strict formats like JSON.
• However, duplicate names can lead to unpredictable query results, so they’re not recommended.

Two kinds of missing values: NULL and MISSING:

• NULL: Means an attribute exists but has no value.
• MISSING: Means the attribute doesn’t exist at all.
• This distinction is useful for clearer query results and error handling.

Importance of MISSING:

• SQL++ doesn’t stop processing if some data is missing; instead, it marks those cases as MISSING and continues.
• This makes queries more robust and tolerant of data inconsistencies.

Accessing Nested Data

SQL-92 vs. Modern Data:

• SQL-92 only supports tables with rows (tuples) containing simple values (scalars).
• Modern data formats often include nested structures, where attributes can hold complex data types like arrays, tables, or even arrays of arrays.

Nested Data Example:

• In the example, the projects attribute of an employee is an array of tuples, representing multiple projects each employee is involved in.

Querying Nested Data in SQL++:

• SQL++ can handle such nested data without adding new syntax to SQL.
• For example, a query can find employees working on projects with “security” in their names and output both the employee’s name and the project’s name.

How It Works:

• SQL++ uses left-correlation, allowing expressions in the FROM clause to refer to variables declared earlier in the same clause.
• For instance, e.projects accesses the projects of an employee e.
• This relaxes SQL’s restrictions and effectively enables a join between an employee and their projects.

Using Variables in Queries:

• SQL++ requires explicit use of variables (e.g., e.name instead of just name) because schema is optional and cannot guarantee automatic disambiguation.
• If a schema exists, SQL++ can still optimize by rewriting the query for clarity and execution.

Flexibility with Nested Collections:

• Variables in SQL++ can represent any type of data—whether it’s a table, array, or scalar.
• These variables can be used seamlessly in FROM, WHERE, and SELECT clauses.

Aliases Can Bind to Any Data Type:

• In SQL++, variables (aliases) don’t have to refer only to tuples.
• They can bind to arrays of scalars, arrays of arrays, or any combination of scalars, tuples, and arrays.

Flexibility in Querying Nested Data:

• Users don’t need to learn new query syntax for different data structures.
• The same unnesting feature is used regardless of whether the data is an array of tuples or an array of scalars.

Example:

• If the projects attribute is an array of strings (instead of tuples), SQL++ queries can still process it.
• The query would range over e.projects and bind p to each project name (a string).

Relaxed Semantics Compared to SQL:

• In traditional SQL, the FROM clause binds variables strictly to tuples.
• SQL++ generalizes this by treating the FROM clause as a function that can bind variables to any type of data—not just tuples.

Practical Outcome:

• In the example, the FROM clause produced variable bindings like {e: employee_data, p: project_name}.
• This allows the query to handle data structures that SQL would not support without extensions.

ABSENCE OF SCHEMA AND SEMI-STRUCTURED DATA

Schemaless Data:

• Many modern data formats (e.g., JSON) don’t require a predefined schema to describe their structure.
• This allows for flexible and diverse data, but it also introduces heterogeneity.

Types of Heterogeneity:

• Attribute presence: Some tuples may have a specific attribute (e.g., x), while others may not.
• Attribute type: The same attribute can have different types across tuples. For example:
  • In one tuple, x might be a string.
  • In another tuple, x might be an array.
• Element types in collections: A collection (e.g., an array or a bag) can have elements of different types. For example:
  • The first element could be a string, the second an integer, and the third an array.
• Legacy or data evolution: These heterogeneities often result from evolving requirements or data conversions (e.g., converting XML to JSON).

Heterogeneity Is Not Limited to Schemaless Data:

• Even structured databases can have heterogeneity. For example:
  • Hive’s union type allows an attribute to hold multiple types, like a string or an array of strings.

How SQL++ Handles It:

• SQL++ is designed to work seamlessly with heterogeneous data, whether the data comes from a schemaless format or a schema-based system.
• It offers features and mechanisms to process such data flexibly, without enforcing rigid structure requirements.

Missing Attributes

1. Representation of Missing Information:

   • In SQL, a missing value is typically represented as NULL (e.g., Bob Smith’s title in the first example).

   • In SQL++, there’s an additional option: simply omitting the attribute altogether (as seen in the second example for Bob Smith).

2. NULL vs. MISSING:

   • NULL: Indicates the attribute exists but has no value.

   • MISSING: Indicates the attribute is entirely absent.

   • SQL++ supports distinguishing between these two cases, unlike traditional SQL.

3. Why This Matters:

   • Some data systems or formats (e.g., JSON) naturally omit missing attributes rather than assigning a NULL value.

   • SQL++ makes it easy to work with both approaches by allowing queries to handle NULL and MISSING values distinctly.

4. Query Behavior:

   • Queries in SQL++ can propagate NULL and MISSING values as they are.

   • The system introduces the special value MISSING to represent absent attributes, allowing clear differentiation from NULL.

MISSING as a Value

What Happens When Data is Missing:

• If a query references an attribute that doesn’t exist in a tuple (e.g., e.title for Bob Smith), SQL++ assigns the value MISSING.
• This avoids query failures and ensures processing can continue.

Three Cases Where MISSING is Produced:

• Case 1: Accessing a missing attribute. For example, {id: 3, name: 'Bob Smith'}.title results in MISSING.
• Case 2: Using invalid input types for functions or operators (e.g., 2 * 'some string').
• Case 3: When MISSING is an input to a function or operator, it propagates as MISSING in the output.

SQL Compatibility Mode:

• In SQL compatibility mode, MISSING behaves like NULL for compatibility. For instance, COALESCE(MISSING, 2) will return 2, just as COALESCE(NULL, 2) does in SQL.

Propagation of MISSING in Queries:

• In queries, MISSING values flow naturally through transformations, enabling consistent handling of absent data.
• For example, in a CASE statement, if e.title evaluates to MISSING, the result of the entire CASE expression will also be MISSING.

Results with MISSING:

• If a query result includes MISSING, SQL++ will omit the attribute from the result tuple.
• In communication with external systems like JDBC/ODBC, MISSING is transmitted as NULL to ensure compatibility.

RESULT CONSTRUCTION,NESTING, AND GROUPING

Creating Collections of Any Value

Power of SELECT VALUE:

• The SELECT VALUE clause in SQL++ allows constructing collections of any type of data, not just tuples.
• It enables creating outputs that match the structure of nested data without flattening it unnecessarily.

Example Query:

• The query in Listing 10 demonstrates how to use SELECT VALUE to extract only the “security” projects of employees, resulting in a nested structure.
• Each employee’s tuple includes their ID, name, title, and a collection of their security-related projects.

Result:

• Listing 11 shows the result where each employee has a field security_proj containing a nested collection of projects that match the condition (e.g., projects with “Security” in the name).

Key Difference from Standard SQL:

• SQL’s SELECT clause can be viewed as shorthand for SELECT VALUE, but with differences:
  • SQL automatically coerces subquery results into scalar values, collections of scalars, or tuples based on context.
  • In contrast, SELECT VALUE in SQL++ consistently produces a collection and does not apply implicit coercion.

Flexibility:

• SQL++ avoids implicit “magic” by explicitly treating SELECT as shorthand for SELECT VALUE.
• This approach aligns more closely with functional programming principles, making it easier to handle and compose nested data results.

GROUP BY and GROUP AS

Introduction to GROUP BY ... GROUP AS:

• This feature extends SQL’s GROUP BY functionality, allowing groups (and their contents) to be directly accessible in the SELECT and HAVING clauses.
• It is more efficient and intuitive for creating nested results compared to traditional SQL, especially when the output nesting doesn’t directly align with the input data structure.

How It Works:

• Generalization: Unlike SQL, which limits access to grouped data in GROUP BY, SQL++ allows accessing the full group details as part of the query.
• Pipeline Model: SQL++ processes queries in a step-by-step fashion, starting with FROM, followed by optional clauses like WHERE, GROUP BY, HAVING, and ending with SELECT.

Example:

• In the query from Listing 12, employees are grouped by their project names (converted to lowercase), and a nested list of employees for each project is created.
• The GROUP BY LOWER(p) AS p GROUP AS g clause groups data and stores each group in g.
• The SELECT clause then extracts project names and employees.

Result:

• The output (shown in Listing 13) contains nested objects:
• • Each object has a proj_name (e.g., 'OLTP Security') and an employees field listing the names of employees associated with that project.

Details of GROUP BY ... GROUP AS:

• The clause produces bindings like the ones in Listing 14, where each group (g) includes all the data for its corresponding key (p).
• The result allows users to flexibly access and format the grouped data.

SQL++ Flexibility:

• SQL++ allows placing the SELECT clause either at the start or the end of a query block, enhancing readability and flexibility.
• This approach is more consistent with functional programming and reduces constraints found in traditional SQL.

Advanced Features:

• SQL++ supports additional analytical tools like CUBE, ROLLUP, and GROUPING SETS, making it highly compatible with SQL but better suited for nested and semi-structured data.

Aggregate Functions

Limitations of Traditional SQL Aggregate Functions:

• Aggregate functions like AVG and MAX in traditional SQL lack composability.
• They work directly on table columns but don’t easily integrate with more complex expressions or subqueries.

SQL++ Solution:

• SQL++ introduces composable aggregate functions, such as COLL_AVG (for calculating the average of a collection) and COLL_MAX.
• These functions take a collection as input and return the aggregated value.

Importance of Composability:

• In SQL++, data is conceptually materialized into a collection first, then passed to the composable aggregate function.
• While this materialization is conceptual, SQL++ engines optimize the execution (e.g., using pipelined aggregation).

Example 1: Calculating the Average Salary of Engineers:

• SQL Query (Listing 15): Uses AVG(e.salary) directly.
• SQL++ Core Query (Listing 16): Converts e.salary into a collection and applies the COLL_AVG function.
• SQL++ clearly defines the flow of data, making it more intuitive and flexible.

Example 2: Calculating the Average Salary of Engineers by Department:

• SQL Query (Listing 17): Uses GROUP BY and AVG.
• SQL++ Core Query (Listing 18):
  • Uses GROUP BY ... GROUP AS to form groups.
  • Feeds each group into COLL_AVG to calculate the average salary.
  • Constructs the result using the SELECT VALUE clause, explicitly specifying the output format.

Flexibility of SQL++ Style:

• SQL++ allows the SELECT clause to be written at the end of a query block, consistent with functional programming styles.
• This enhances readability and composability while maintaining compatibility with SQL.

Pivoting and Unpivoting

UNPIVOT: Transforming Attributes into Rows

1. What is Unpivoting?

   • Unpivoting is the process of converting attribute names (used as keys) into data rows.

   • This is useful for cases where key-value pairs in the data need to be analyzed as individual rows.

2. Example (Listing 19-21):

• Input: A closing_prices collection where stock symbols (amzn, goog, fb) are attributes with prices as values.

• Query (Listing 20): The UNPIVOT clause transforms these attributes into rows with fields for symbol and price.

• Output (Listing 21): A flattened structure where each row contains the date, stock symbol, and price.

Pivoting

1. Purpose of Pivoting:
   • Pivoting transforms rows into attributes (columns).
2. Example from Listings 23-25:

• Input (Listing 23): Rows of today_stock_prices where each stock symbol and its price are separate rows.
• Query (Listing 24): The PIVOT operation turns these rows into a single object, using sp.symbol as attribute names and sp.price as their values.
• Output (Listing 25): A tuple where each stock symbol (amzn, goog, fb) is an attribute, and their corresponding prices are the values.

Combining Grouping and Pivoting

1. Using Pivot with Grouping:
2. • Combining GROUP BY and PIVOT enables aggregation of grouped rows into a more structured output.
   • This is particularly useful when working with time-series data or hierarchical datasets.
3. Example Query (Listing 26):

• Input: Data from stock_prices (Listing 27), which includes stock prices for multiple dates as individual rows.
• Query:
  • Groups the data by date using GROUP BY sp.date.
  • Pivots the grouped rows to produce a nested structure where each date contains all its stock prices as attributes.
• Output (Listing 28): For each date, an object with a prices field lists the stock symbols as attributes and their respective prices as values.

Questions

SQL++ identifies aggregate functions as an SQL violation of functional composability. Give an example of an aggregate function and describe how it violates SQL’s functional composability.

• Aggregate Function:COLL_AVG()

• Violation Explanation:

  • In traditional SQL, aggregate functions like AVG processes the column and returns a single value.

  • In SQL++, this issue is resolved by providing composable versions of aggregate functions, such as COLL_AVG, which operate on collections, allowing intermediate results to flow naturally into the aggregation.

With SQL++, what is the difference between NULL and Missing?

NULL: Indicates that an attribute exists but has no value.

MISSING: Indicates that an attribute is completely absent in the data.

True or false: One must define a schema for data prior to using SQL++.

False:

• SQL++ supports schema-optional and schema-less data formats, such as JSON.
• While schemas can improve query optimization and validation, SQL++ can process data without requiring predefined schemas, making it highly flexible for semi-structured data use cases.

How does the I lease prevent a thundering herd?

The I lease (Inhibit Lease) prevents a thundering herd problem by ensuring that only one read session at a time is allowed to query the RDBMS for a missing key-value pair in the Key-Value Store (KVS). Here’s how it works:

1. Thundering Herd Problem:

   • When a key-value pair is not found in the KVS (a KVS miss), multiple read sessions might simultaneously query the RDBMS to fetch the value.

   • This can overload the RDBMS and degrade performance under high concurrency.

2. Role of the I Lease:

   • When the first read session encounters a KVS miss, it requests an I lease for the key.

   • Once the I lease is granted, the KVS prevents other read sessions from querying the RDBMS for the same key.

   • All other read sessions must “back off” and wait for the value to be updated in the KVS by the session holding the I lease.

3. Result:

   • The session with the I lease queries the RDBMS, retrieves the value, and populates the KVS.

   • Subsequent read sessions observe a KVS hit and do not need to access the RDBMS.

   • This mechanism avoids simultaneous RDBMS queries, effectively solving the thundering herd problem.

What is the difference between invalidate and refresh/refill for maintaining the cache consistent with the database management system?

• Invalidate: Deletes stale cache entries to prevent incorrect reads, but at the cost of forcing subsequent queries to access the RDBMS.
• Refresh/Refill: Proactively updates the cache with new data, ensuring consistent reads while reducing future load on the RDBMS at the expense of immediate computation.

Describe how CAMP inserts a key-value pair in the cache.

Check Cache Capacity

• If there is enough memory to store the new key-value pair:
  • The pair is inserted directly into the appropriate priority group based on its cost-to-size ratio.
  • L is not updated.
• If the cache is full:
  • CAMP selects one or more key-value pairs to evict based on their H(p) values.
  • It removes the pair(s) with the lowest H(p) values until there is sufficient space for the new pair.

Insert the New Pair

• The new key-value pair p is added to the cache, and its H(p) value is computed and recorded.
• The pair is placed in the appropriate priority queue based on its cost-to-size ratio.

How does BG compute the SoAR of a database management system?

1. Define the SLA.
2. Run a series of experiments with increasing numbers of threads (T) to find the peak throughput while ensuring SLA compliance.

Reference: https://escholarship.org/content/qt2bj3m590/qt2bj3m590_noSplash_084218340bb4e928c05878f04d01f04d.pdf

MySQL 默认 InnoDB 存储引擎，擅长事务处理，具有崩溃恢复特性。

内存结构

缓冲池

InnoDB 存储引擎是基于磁盘存储的，并将其中的记录按照页的方式进行管理。

缓冲池是一块内存区域，通过内存的速度来弥补磁盘速度较慢对数据库性能的影响。

如果要读取页面，首先从磁盘读到的页面放在缓冲池中，之后再读相同的页时，先判断该页是否在缓冲池中。若在缓冲池中则被命中，直接读取改页，否则就读取磁盘上的页。

对于修改操作，先修改缓冲池中的页，然后再以一定频率刷新到磁盘。

依据时间局部性原理与空间局部性原理，Buffer Pool 在存储当前活动数据页的时候，也会以预读的方式缓存目标数据页临近的其他数据页。对于 Buffer Pool 中数据的查询，InnoDB 直接读取返回；对于 Buffer Pool 中数据的修改，InnoDB 直接在 Buffer Pool 中修改，并在此之前将修改写入 Redo Log 中。当数据页被 LRU 算法淘汰时写入磁盘。若持久化前系统崩溃，则在重启后使用 Redo Log 进行恢复。

注意：页从缓冲池刷新回磁盘的操作并不是在每次页发生更新时触发，而是基于 Checkpoint 定时刷新回磁盘。

缓冲池以页为存储单位，采用双向链表数据结构管理缓存页，页的大小默认为 16KB，使用分区 LRU 算法淘汰数据页。

按照数据类型：索引页、数据页、Undo 页、更改缓冲页、自适应哈希索引页、锁信息页、数据字典页等。

按照页面的修改状态：

• Free page：空闲页面，未被使用过。
• Clean page：被使用（读取）过的页面，但是数据未被修改过。
• Dirty page：脏页面，被使用并且数据被修改过，导致页中数据与磁盘产生了不一致。

而且 InnoDB 允许存在多个缓冲池实例。每个页根据哈希值被分配到不同的缓冲池实例中，这样可以减少数据库内部的资源竞争，增加数据库的并发能力。

LRU List，Free List 和 Flush List

LRU 列表中加入了 midpoint 位置，位于 LRU 列表长度的 5/8 处，新加载的页会被直接放入这个位置。 midpoint 之后的列表被称为 old 列表，之前的列表就是 young 列表。young 列表中的页都是最为活跃的热点数据。

[!NOTE]

为什么不直接将读取的页放入 LRU 列表的头部呢？

因为一些操作，如索引或整张表的扫描操作，会使很多包含热点数据的缓冲页被淘汰掉。因此下次需要读取这些热点数据时，InnoDB 还需要再次访问磁盘。也就是说，将插入点设置在 LRU 列表中间的某个位置可以防止处于 young 区域的热点页面被某些大数据量的操作给淘汰掉。

缓冲池还设置了在页被加入到 midpoint 位置之后要等待多久才会被加入到 LRU 列表的热区 young 中，防止短期时间内被高频访问的节点进入 young 区域。

LRU 列表用来管理已经加载的页面，但是当数据库刚启动时，LRU 列表是空的，这时候缓存页都被存放在 Free 列表中。当有新的数据加载到缓冲池中时，首先从 Free 列表中查找是否有可用的空闲页，若有则将该页从 Free 列表中删除并放入 LRU 列表中；否则，根据 LRU 算法，淘汰 LRU 列表末尾的页，并将对应的内存空间分配给新的页。

当 Free List 页数低于 innodb_lru_scan_depth（默认为1024）时，后台清理线程会扫描 LRU List，从 old 链表底部开始淘汰干净页。

1
2
3
4
5

Buffer pool size        8191
Free buffers            6513
Database pages          1654
Old database pages      604
Modified db pages       0

[!NOTE]

为什么 Free buffers + Database pages 不等于 Buffer pool size？

Free buffers 和 Database pages 分别表示空闲列表和 LRU 列表中的页面数。

但是缓冲池中的页还可能会被分配给自适应哈希索引元数据页，Lock 信息页，压缩页等，这些页不需要基于普通的 LRU 列表进行维护。

缓冲是通过 unzip_LRU 来管理压缩页，因为压缩页的大小可能是 1KB、2KB、4KB、8KB 这些小于 16KB的页面。

unzip_LRU 是怎样从缓冲池中分配内存的呢？

⾸先，在 unzip_LRU 列表中对不同压缩页⼤⼩的页进⾏分别管理。其次，通过伙伴算法进⾏内存的分配。例如对需要从缓冲池中申请页为 4KB 的⼤⼩，其过程如下：

1. 检查 4KB 的 unzip_LRU 列表是否有可用的空闲页；
2. 若有，则直接使用；
3. 否则，检查 8KB 的 unzip_LRU 列表；
4. 若能得到空闲页，将页分成 2 个 4KB 页，存放到 4KB 的 unzip_LRU 列表；
5. 若不能，从 LRU 列表中申请一个 16KB 的页，将页分为 1 个 8KB 的页和 2 个 4KB 的页，分别存放到对应的 unzip_LRU 列表中。

在 LRU 列表中的页被修改之后，该页变成脏页，即该缓冲池页和磁盘页中的数据产生了不一致。之后数据库回通过 checkpoint 机制将脏页刷新到磁盘，Flush 列表就是脏页列表。脏页既存在于 LRU 列表中，也存在于 Flush 列表中。LRU 列表用来管理缓冲页的可用性，Flush 列表用来管理缓冲页的刷新，二者互不影响。

[!NOTE]

InnoDB 中，页面清理线程会周期性地从 LRU List 和 Flush List 中刷写脏页；当进行日志文件轮转或日志文件即将填满时，检查点机制也会触发对 Flush List 中脏页的批量刷新以推进 Redo 日志的检查点位置。

这里的日志文件轮换指的是当重做日志写入到当前日志文件达到一定容量或达到指定条件时，MySQL 会停止往这个文件继续写，而是切换到下一个预先配置好的日志文件上继续写入。

检查点刷新与页面清理线程共享 Flush List，区别在于检查点会关注推进 redo log 写入位置，而页面清理线程更关注缓冲池空间管理。

更改缓冲

该缓冲也是缓冲池中的一部分，但是只针对非唯一二级索引的插入、删除标记和物理删除操作，不支持聚簇主键索引、唯一索引（除删除标记）及其他特殊索引类型（如全文、空间索引）。

在执行 DML 语句时，如果该语句要查找的索引页未在缓冲池中，系统不会直接操作磁盘，而是将数据变更存放在更改缓冲区中；当未来数据被读取时将数据合并恢复到缓冲池中，再将合并后的数据刷新到磁盘中。

Change Buffer 大小默认占 Buffer Pool 的 25%，在引擎启动时便初始化完成，其物理结构为一棵名为 ibuf 的 B-Tree。Change Buffer 的生效条件为：

• innodb_change_buffering 已启用：若将该变量设置为 none，则关闭所有缓冲；否则可选择性缓冲 inserts、deletes、purges 等操作。
• 目标二级索引页不在缓冲池中：只有在索引页不在 Buffer Pool 时，才将修改缓存到 ibuf；若页已在内存，则直接修改页本身。
• 表或索引页未被强制合并：在发生强制合并（如慢速关闭 --innodb-fast-shutdown=0）前，缓冲仍被保留；合并后 ibuf 会将缓存应用到 B-Tree 页。

该缓冲合并变更到数据的时机为：

• 页被读入缓冲池时（On-demand Merge）：当后续查询需要读取某个被缓冲修改的二级索引页时，InnoDB 会在返回数据前先将 ibuf 中对应的缓存记录合并到页内。
• 主线程空闲时（Background Merge）：InnoDB 的主线程（Master Thread）在系统空闲或后台作业期间，会批量合并 ibuf，以减少 IO 峰值对 OLTP 性能的影响。
• 慢速关闭时（Slow Shutdown）：若以 innodb_fast_shutdown=0 重启或关闭，系统会进行全量合并，确保提交前所有缓冲都应用到磁盘页中。
• ibuf B-Tree 分裂时：当 ibuf 树或其位图页分裂，或下一次合并会导致超出 innodb_change_buffer_max_size 限制时，InnoDB 会触发部分合并以释放空间。

数据页：发生 DML 时立即更新。

非唯一的二级索引页：发生 DML 时，变更会先存储在 Change Buffer 中，延迟合并。

唯一的二级索引页：由于需要立即检查唯一性，变更不会存储在 Change Buffer 中。

自适应哈希索引

InnoDB 监控对索引页的访问频度，当检测某些页频繁被访问且 B-Tree 查找性能不足时，会动态建立哈希索引，以加速查询；与 Change Buffer 机制互不干扰。

Redo 日志缓冲

Redo log 重做日志用于记录事务对磁盘数据页的修改，用于崩溃恢复，可实现持久性。

InnoDB 的日志缓冲区（log buffer）只用于缓存 redo log 的生成数据，默认大小为 16 MB，用来在事务提交前暂时保留日志，减少对磁盘的频繁写入。

InnoDB 除了包含缓冲池之外，还有 Redo 日志缓冲。InnoDB 首先将 Redo 日志信息放入该缓冲区，之后按一定频率将其刷新到磁盘的 Redo 日志文件中，这个频率一般情况下是一秒一次。

也就是说，Redo log 由两部分构成：

1. 重做日志缓冲（内存中）：用于暂时存储事务修改的日志。当日志量达到一定程度或事务提交时，InnoDB 会将这些日志刷新到磁盘上的 Redo Log 文件。
2. 重做日志文件（磁盘中）：用于持久化保存事务修改的日志。

写入和刷新策略：

补充：

• write 指将缓冲区内容写入到操作系统文件缓存中；
• flush 指调用 fsync() 等系统调用，将操作系统缓存的内容真正写到磁盘；
• 若想同时保证二进制日志（binlog）和 redo 日志的同步，可结合 sync_binlog=1 使用，以避免 binlog 丢失。

下列三种情况会导致 Redo 日志缓冲中的内存刷新到磁盘的 Redo 日志文件中：

1. Master Thread 每秒将 Redo 日志缓冲刷新到 Redo 日志文件中；
2. 每个事务提交时会将 Redo 日志缓冲刷新到 Redo 日志文件中；
3. 当 Redo 日志缓冲的剩余空间小于 1/2 时，Redo 日志缓冲刷新到 Redo 日志文件中。

注意：Undo Log 记录事务的回滚信息和 MVCC 版本，不经日志缓冲区，而是直接写入 undo 表空间中的数据页。

当 MySQL 意外宕机后，InnoDB 会在启动时自动执行崩溃恢复，其中包括读取并应用 redo log 的操作，以将那些已经提交但尚未刷写到磁盘的数据页修改重做到磁盘上，从而保证数据的持久性与一致性。整个恢复分为分析、重做（Redo）和回滚（Undo）三个阶段：在重做阶段，InnoDB 会对比日志记录与磁盘页上的 LSN，将丢失的已提交修改应用回去；在回滚阶段，则撤销所有未提交的事务，以确保数据库最终处于一致状态。

额外的内存池

InnoDB 中对内存的管理通过内存堆来实现额。在对一些数据结构本身的内存进行分配时，需要从额外的内存池中进行申请，当该区域的内存不足时，会从缓冲池中进行申请。

磁盘结构

System tablespace（系统表空间）是默认的共享存储区域，通常由数据目录下名为 ibdata1 的文件（或多个通过 innodb_data_file_path 定义的文件）组成，用于保存 InnoDB 的数据字典、undo 日志和更改缓冲区；如果没有启用独立表空间或通用表空间，部分表和索引的数据也会存储在此处。该表空间在自动扩展（autoextend）模式下可按需增长，但在表被截断或删除后不会自动回收操作系统层面的空间。

**数据字典：**数据字典是由各种表对象的元数据信息（表结构，索引，列信息等）组成的内部表。

**修改缓冲：**内存中 Change Buffer 对应的持久化区域，同样为了数据完整性而设置。

InnoDB 的独立表空间（file-per-table）为每个数据库在数据目录下创建单独的子文件夹，每个表对应一个 .ibd 文件来存放该表的所有行数据、索引结构和变更缓冲（原插入缓冲）页；与此同时，每张表的结构定义仍保存在同名的 .frm 文件（MySQL 8.0 之后改为数据字典存储）。尽管表的数据和索引被分离到各自的 .ibd 文件中，诸如回滚日志、系统事务信息、双写缓冲等元数据仍持续写入共享的系统表空间（ibdata1），因此启用独立表空间后，系统表空间也不会停止增长。每个新创建的独立表空间文件初始大小约为 96 KB，并会根据表的需要自动扩展。

**通用表空间（General Tablespace）是指可以用于存储多个表的表空间，它位于用户自定义的位置，可以存储来自不同数据库的表和索引。**通用表空间是一个由 CREATE TABLESPACE 命令创建的共享表空间，创建时必须指定该表空间名称和 ibd 文件位置，ibd 文件可以放置于任何 MySQL 实例有权限的地方。通用表空间存在的目的是为了在系统表空间与独立表空间之间作出平衡。系统表空间与独立表空间中的表可以向通用表空间移动，反之亦可，但系统表空间中的表无法直接与独立表空间中的表相互转化。每个共享表空间初始大小为 64KB。

通用表空间允许多个表共享一个表空间文件，这与传统的每个表单独使用自己的表空间（独立表空间）不同。通过这种方式，可以更灵活地管理数据文件，特别是在管理存储多个小表时。通用表空间提供了以下好处：

• 减少小表空间碎片：如果每个表都有独立的表空间，那么大量的小表会导致存储碎片。而使用通用表空间可以集中管理这些小表，减少碎片。
• 灵活的存储分配：通用表空间可以跨多个文件存储表的数据，这使得人们能够更灵活地管理磁盘空间，避免单一表空间文件过大或过小的问题。

创建共享表空间：create tablespace space_name add datafile file_name engine=engine_name;

为某个表指定表空间：create table table_name ... tablespace space_name;

**Undo tablespace 撤销表空间：**在 MySQL 8.0 及更高版本中，InnoDB 在实例首次初始化时会自动创建 两个 独立的 Undo 表空间（默认为 undo_001.ibu 和 undo_002.ibu），以保证在事务回滚和一致性读（MVCC）过程中有至少两个回滚段可供轮换；每个表空间的初始大小均为 16 MB，并可按需自动扩展（最小扩展步长 16 MB，最大至 256 MB），当表空间超过 innodb_max_undo_log_size 后会被标记并截断以回收旧日志空间；这些 Undo 表空间专用于存储撤销日志，从而将大量长事务的日志写入负载与系统表空间分离，提升 I/O 并发性能并防止 ibdata1 无限增长。

系统表空间是默认的共享存储区域，早期版本中所有的撤销日志都存放其中；而从 MySQL 5.7 开始，可以通过配置独立 Undo 表空间，将撤销日志与系统表空间中的数据字典、change buffer 等内容分离，从而改进 I/O 分布和空间管理。

InnoDB 的临时表空间分为会话临时表空间（Session Temporary Tablespaces）和全局临时表空间（Global Temporary Tablespace），两者分别用于存储用户显式创建的临时表、优化器内部创建的临时表，以及这些表的回滚段。当你在 SQL 中使用子查询且需要落盘临时表（例如数据量超出内存限制或 optimizer 决定使用 on-disk 临时表）时，这些临时表会被创建到会话临时表空间中，而其回滚信息则存储在全局临时表空间中。

如何在高并发访问下，既充分利用数据库的并发能力，又保证每个用户对数据的读写操作保持一致性呢？为此，数据库系统引入了锁（locking）机制，这也是它与文件系统的一个关键区别。

而且这里需要澄清，只有当系统真正需要更高锁粒度时，行级锁才会出现开销，而 InnoDB 本身并不依赖锁升级机制，因为单个锁与多个锁的成本是相当的。也就是说，在不需要非常高并发写冲突控制的情况下，InnoDB 不会主动为每一行都添加行锁；只有当真的有并发冲突需要保护同一行时，才会产生行级锁对应的数据结构开销。

锁是计算机中协调多个进程或线程并发访问某一资源的机制。

在MySQL中，事务中的锁（行锁、表锁等）会一直保留到事务结束（COMMIT 或 ROLLBACK）。

lock 与 latch

1. Latch（闩锁）
   • 也称为轻量级锁或临界区锁，主要用于保护数据库内部的临时数据结构与内存资源，确保多个线程在访问或修改同一份临界资源时不会产生并发安全问题。
   • 必须保证其持有时间极短：一旦线程完成对临界资源的访问，必须立即释放 latch，否则会严重影响整个系统的并发性能。
   • 在 InnoDB 存储引擎内部，latch 进一步分为两类：
     • Mutex（互斥量）：最简单的二元互斥锁，用于保护对某个共享资源的独占访问。
     • RWLock（读写锁）：允许多个读线程同时进入临界区，但写线程独占，保证读写操作对同一资源的并发正确性。
   • 无死锁检测：由于 latch 的持有时间极短，InnoDB 不会对其进行死锁检测。一旦某线程在短时间内未能获取到 latch，往往是因为有其他线程暂时占用，系统会进行短暂等待或重试，直到拿到 latch 才继续执行。
2. Lock（事务锁）
   • 针对数据库对象（如表、页、行）而设计，由事务进行获取和释放：
     • 加锁操作（例如加行锁、页锁）只会在事务提交（COMMIT）或回滚（ROLLBACK）时才被释放（不同的隔离级别下，锁的释放时机可能会有所区别）。
     • Lock 的持有时间较长（往往跨越整个事务执行过程），因此对并发冲突的检测和处理必须更完整。
   • 支持死锁检测与处理：当多个事务彼此等待对方持有的锁而陷入循环等待时，InnoDB 会自动检测死锁并选择性地回滚某个事务以打破循环，从而保证系统不会长期阻塞。
   • 锁级别包括：意向锁（Intention Lock）、行级锁（Record Lock）、间隙锁（Gap Lock）、次序锁（Next-Key Lock）等，它们共同配合以实现更高效、更细粒度的并发控制。

锁问题

通过锁定机制可以实现事务的隔离性要求，使得事务可以并发地工作。锁提高了并发，但是却会带来潜在的问题。不过好在因为事务隔离性的要求，锁只会带来三种问题，如果可以防止这三种情况的发生，那将不会产生并发异常。

脏读

在理解脏读（Dirty Read）之前，需要理解脏数据的概念。但是脏数据和之前所介绍的脏页完全是两种不同的概念。脏页指的是在缓冲池中已经被修改的页，但是还没有刷新到磁盘中，即数据库实例内存中的页和磁盘中的页的数据是不一致的，当然在刷新到磁盘之前，日志也已经被写入到了重做日志文件中。而所谓脏数据是指事务对缓冲池中行记录的修改，并且还没有被提交（commit）。

对于脏页的读取，是非常正常的。脏页是因为数据库实例内存和磁盘的异步造成的，这并不影响数据的一致性（或者说两者最终会达到一致，即当脏页都刷新到磁盘）。并且因为脏页的刷新是异步的，不影响数据库的可用性，因此可以带来性能的提高。

脏数据却截然不同，脏数据是指未提交的数据，如果读到脏数据，即一个事务可以读取到另外一个事务中未提交的数据，则显然违反了数据库的隔离性。

脏读指的就是在不同的事务下，当前事务可以读到另外事务未提交的数据，简单来说就是可以读到脏数据。

脏读发生的条件是需要事务的隔离级别为 READ UNCOMMITTED，而目前绝大部分的数据库都会至少设置成 READ COMMITTED。InnoDB 存储引擎默认的事务隔离级别为 REPEATABLE READ，Microsoft SQL Server 数据库为 READ COMMITTED，Oracle 数据库同样也是 READ COMMITTED。

[!NOTE]

关于 InnoDB 默认采用 RR 隔离级别的原因可参考：为什么 InnoDB 默认采用 RR 隔离级别？

脏读隔离看似毫无用处，但在一些比较特殊的情况下还是可以将事务的隔离级别设置为 READ UNCOMMITTED。例如 replication 环境中的 slave 节点，并且在该 slave 上的查询并不需要特别精确的返回值。

不可重复读

不可重复读指在同一个事务（会话）内多次读取同一数据集时，由于另一个事务对该数据集进行了 DML 修改（插入、更新或删除），导致第一次和第二次读取的结果不一致。换句话说，同一事务中对同一行数据执行两次 SELECT 查询，若中间有其他事务提交了修改，使得这两次查询得到不同的数据，就发生了不可重复读。

大多数数据库（如 Oracle、Microsoft SQL Server、PostgreSQL 等）在默认隔离级别为 READ COMMITTED 时，允许发生不可重复读，因为读取的是已提交数据，一般被认为可接受，不会引起严重一致性问题。

InnoDB 存储引擎默认隔离级别是 REPEATABLE READ，在该级别下使用 Next-Key Locking（锁定索引记录本身以及其前一个 gap 范围）来防止不可重复读和幻读。

• 当事务第一次扫描索引行时，会对这条数据及其相邻的 gap 区间加锁，阻止其他事务在该范围内插入或修改行。
• 因此，同一事务的后续读取始终只能看到最初加锁时的“快照”数据，不会因他人提交修改而改变读取结果。

若将隔离级别设置为 READ COMMITTED，InnoDB 只对具体记录加行锁（Record Lock），不再对 gap 进行加锁，因此允许在两次读取之间对行或 gap 进行插入/更新，从而出现不可重复读。

丢失更新

丢失更新指的是：当两个事务（或两个并发操作）都希望修改同一行数据时，后提交的那个更新“覆盖”了先提交的更新，导致先前的修改最终没有被保存，从而出现数据不一致。例如：

1. 事务 T1 将行记录 r 更新为 v1，但是事务 T1 并未提交。
2. 与此同时，事务 T2 将行记录 r 更新为 v2，事务 T2 未提交。
3. 事务 T1 提交。
4. 事务 T2 提交。

但是，在当前数据库的任何隔离级别下，都不会导致数据库理论意义上的丢失更新问题。这是因为，即使是 READ UNCOMMITTED 的事务隔离级别，对于行的 DML 操作，需要对行或其他粗粒度级别的对象加锁。因此在上述步骤 2) 中，事务 T2 并不能对行记录 r 进行更新操作，其会被阻塞，直到事务 T1 提交。

虽然数据库能阻止丢失更新问题的产生，但是在生产应用中还有另一个逻辑意义的丢失更新问题，而导致该问题的并不是因为数据库本身的问题。实际上，在所有多用户计算机系统环境下都可能产生这个问题。简单地说来，出现下面的情况时，就会发生丢失更新：

1. 事务 T1 查询一行数据，放入本地内存，并显示给一个终端用户 User1。
2. 事务 T2 也查询该行数据，并将取得的数据显示给终端用户 User2。
3. User1 修改该行记录，更新数据库并提交。
4. User2 修改该行记录，更新数据库并提交。

显然，这个过程中用户 User1 的修改更新操作丢失了，而这可能会导致一个恐怖的结果。设想银行发生丢失更新现象，例如一个用户账号中有 10000 元人民币，他用两个网上银行的客户端分别进行转账操作。第一次转账 9000 人民币，因为网络和数据的关系，这时需要等待。但是这时用户操作另一个网上银行客户端，转账 1 元，如果最终两个转账都成功了，用户的帐号余额是 9999 人民币，第一次转的 9000 人民币并没有得到更新，但是在转账的另一个账户却会收到这 9000 元，这导致的结果就是钱变多，而账不平。

这里需要澄清的是，以上银行问题的发生和数据库无关，而是业务逻辑的问题。

也就是说，如果我们直接写 UPDATE account SET cash = cash - 9000 WHERE user = pUser;，那么 InnoDB 会对满足 user = pUser 的那一行加 X 锁，保证同时不会有别的事务也在修改它。但在很多业务里，我们并不能“直接更新”——往往要先读余额（SELECT），做业务判断（比如余额是否足够、是否与外部系统交互等），然后再走 UPDATE。在你只使用普通的 SELECT … 而没有加锁（FOR UPDATE）时，数据库不会对这条记录加行级排他锁，这时别的事务就可能同时也读到同一个旧余额，然后各自计算完毕后分别执行 UPDATE，造成后面那笔更新把前面那笔更新覆盖——这才是真正的丢失更新。

要避免丢失更新发生，需要让事务在这种情况下的操作变成串行化，而不是并行的操作。即在上述四个步骤的 1) 中，对用户读取的记录加上一个排他 X 锁。同样，在步骤 2) 的操作过程中，用户同样也需要加一个排他 X 锁。通过这种方式，步骤 2) 就必须等待 1) 和 3) 完成，最后完成步骤 4)。

InnoDB 存储引擎中的锁

锁的类型

按照兼容性可分为：

• 共享锁（S Lock），允许事务读一行数据。
• 排他锁（X Lock），允许事务删除或更新一行数据。

如果一个事务 T1 已经获得了 r 行的共享锁，那么另外的事务 T2 可以立即获得 r 行的共享锁，因为读取并没有改变 r 行的数据，称这种情况为锁兼容（Lock Compatible）。但若有其他的事务 T3 想获得 r 行的排他锁，则其必须等待事务 T1、T2 释放 r 行上的共享锁──这种情况称为锁不兼容。

下表显示了共享锁和排他锁的兼容性：

此外，InnoDB 存储引擎支持多粒度锁定，这种锁定允许事务在行级上的锁和表级上的锁同时存在。为了支持在不同粒度上进行加锁操作，InnoDB 存储引擎支持一种额外的锁方式，称之为意向锁（Intention Lock）。意向锁是将锁定的对象分为多层次，意向锁意味着事务希望在更细粒度（fine granularity）上进行加锁。

若将上锁的对象看成一棵树，那么对最下层的对象上锁，也就是对最细粒度的对象进行上锁，那么首先需要对粗粒度的对象上锁。如下图，如果需要对页上的记录 r 进行 X 锁，那么首先需要对数据库 A、表、页上意向锁 IX，最后对记录 r 上 X 锁。若其中任何一个部分导致等待，那么该操作需要等待粗粒度锁的完成。比如说，在对记录 r 加 X 锁之前，已经有事务对该表进行了 S 表锁，那么表上已存在 S 锁，之后事务需要对记录 r 在表上加上 IX，由于不兼容，所以该事务需要等待表锁操作的完成。

InnoDB 存储引擎支持意向锁的设计比较简练，其意向锁即为表级别的锁。设计目的主要是为了在一个事务中揭示下一行将被请求的锁类型。其支持两种意向锁：

1. 意向共享锁（IS Lock）：事务想要获得一张表中某几行的共享锁；
2. 意向排他锁（IX Lock）：事务想要获得一张表中某几行的排他锁。

由于 InnoDB 存储引擎支持的是行级别的锁，因此意向锁其实不会阻塞除全表扫描以外的任何请求。下表展示了表级意向锁与行级锁的兼容性：

在 InnoDB 1.0 版本之前，用户只能通过命令 SHOW FULL PROCESSLIST、SHOW ENGINE INNODB STATUS 等来查看当前数据库中锁的请求，然后再判断事务锁的情况。

从 InnoDB 1.0 开始，在 INFORMATION_SCHEMA 架构下添加了表 INNODB_TRX、INNODB_LOCKS、INNODB_LOCK_WAITS。通过这三张表，用户可以更简单地监控当前事务并分析可能存在的锁问题。

下表是对于表 INNODB_TRX 的定义：

下表是对于 INNODB_LOCKS 的定义：

另外需要特别注意的是，在查看 INNODB_LOCKS 的内容时，lock_data 这个值并非是可信的值。例如当用户运行一个范围查找时， lock_data 可能只返回第一行的主键值。与此同时，如果当前资源被锁住了，若锁住的页因为 InnoDB 存储引擎缓冲池的容量，导致该页从缓冲池中被刷出，则在查看 INNODB_LOCKS 表时，该值同样会显示为 NULL，即 InnoDB 存储引擎不会从磁盘进行再一次的查找。

在通过表 INNODB_LOCKS 查看了每张表上锁的情况后，用户就可以来判断由此引发的等待情况了。当事务较小时，用户就可以人为地、直观地进行判断。但是当事务量非常大，其中锁和等待也时常发生，这个时候就不会这么容易判断。但是通过表 INNODB_LOCK_WAITS ，可以很直观地反映当前事务的等待。表 INNODB_LOCK_WAITS 的结构如下表。

总的来说，用户可以结合 INNODB_TRX、INNODB_LOCKS、INNODB_LOCK_WAITS 三张表进一步查询。比如：

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

SELECT
  r.trx_id      AS waiting_trx_id,
  r.trx_mysql_thread_id AS waiting_thread,
  r.trx_query     AS waiting_query,
  b.trx_id      AS blocking_trx_id,
  b.trx_mysql_thread_id AS blocking_thread,
  b.trx_query     AS blocking_query
FROM information_schema.innodb_lock_waits w
INNER JOIN information_schema.innodb_trx b
  ON b.trx_id = w.blocking_trx_id
INNER JOIN information_schema.innodb_trx r
  ON r.trx_id = w.requesting_trx_id\G
*************************** 1. row ***************************
waiting_trx_id:    73122F
waiting_thread:    471719
waiting_query:    NULL
blocking_trx_id:   7311FC
blocking_thread:   471718
blocking_query:    NULL
1 row in set (0.00 sec)

按照锁的粒度可分为：

全局锁：对整个数据库实例加锁，实例处于只读状态。

使用场景：进行整个数据库的逻辑备份，对所有的表进行锁定，从而获取一致性视图，保证数据完整性（DDL，DML 语句被阻塞，DQL 正常运行）。

步骤：

1. 加锁：flush tables with read lock;
2. 数据备份：mysqldump -h192.168.200.202 -uroot -p1234 db01 > db01.sql
3. 解锁：unlock tables;

产生的问题：

如果在主库上备份，备份期间不能执行插入、更新等操作，业务基本上停摆。

如果在从库上备份，备份期间从库不能执行主库同步过来的二进制日志，导致主从延迟。

解决方法：

备份时，加上参数 -single-transaction 来完成不加锁的一致性数据备份（快照读取）：mysqldump -single-transaction -h192.168.200.202 -uroot -p1234 db01 > db01.sql

表级锁：开销小，加锁快；锁定力度大，发生锁冲突概率高，并发度最低；不会出现死锁。

表**共享-**读锁：当表被 READ 锁定时，其他会话只能获取该表的 READ 锁，不能获取 WRITE 锁。READ 锁的会话可以进行读取操作（SELECT），但不能进行写入操作（INSERT、UPDATE、DELETE 等）。同时，加了 READ 锁的会话可以与其他 READ 锁并发读取表数据，但不能有写入操作。

表**独占-**写锁：当表被 WRITE 锁定时，其他所有会话都不能对该表进行任何操作（无论是读还是写），只有当前会话可以进行读写操作。写锁是独占锁，一旦被某个会话持有，其他会话都必须等待该锁被释放。

使用语法：

1
2

lock tables table_name1, table_name2 read/write;
unlock tables / 客户端断开连接;

当客户端与 MySQL 服务器断开连接时，MySQL 会自动释放当前会话持有的所有表锁。这是为了防止锁永远保持不释放的情况，因为锁定表的会话已经断开，不再能主动解锁。

元数据锁（meta data lock，MDL）

元数据是控制表结构、表逻辑相关的信息。加锁过程由系统自动控制，无需显式使用。

当我们执行诸如 CREATE TABLE、DROP TABLE、ALTER TABLE 等 DDL（数据定义语言）语句时，MySQL 需要对表的元数据进行修改。在这些情况下，MDL 锁可以防止其他事务同时进行操作，确保结构修改的安全性。

当我们执行 SELECT、INSERT、UPDATE、DELETE 等 DML（数据操作语言）语句时，MySQL 也会申请 MDL 锁以保护表结构，防止在读取或写入数据的过程中表结构发生改变。

MDL 锁的类型：

MDL 共享锁（MDL Shared Lock）：

• 当事务对表进行读取（如 SELECT）或普通的数据操作（如 INSERT、UPDATE）时，会申请 MDL 共享锁。
• 共享锁之间是兼容的，即多个事务可以同时持有 MDL 共享锁，这样可以允许多个事务同时读写表中的数据。

MDL 排他锁（MDL Exclusive Lock）：

• 当事务要对表进行结构修改（如 ALTER TABLE）时，会申请 MDL 排他锁。
• MDL 排他锁与其他所有类型的锁都不兼容。因此，在表结构被修改期间，其他事务将被阻塞，直到持有排他锁的事务提交或回滚。

查看 MDL：select * from performance_schema.metadata_locks;

意向锁

意向锁的出现是为了支持 InnoDB 的多粒度锁，它的主要作用是用来协调表级锁和行级锁之间的关系，从而提升锁定机制的性能和效率。它的核心用途是为了在表级别加锁时能够快速判断是否存在冲突，防止误加表级锁而导致锁冲突或死锁。

意向锁本质：只是用于标识即将进行的锁操作。它主要用于快速判断是否可以对表或表中某些行施加其他类型的锁。

我们需要加表锁时，需要判断表中有没有数据行被锁定，以确定是否能加锁成功。

之前没有意向锁，我们就得遍历表中所有数据行来判断有没有行锁；有了意向锁这个表级锁之后，我们直接判断意向锁是否存在便可知表中是否有数据行被锁定。

有了意向锁之后，要执行的事务 A 在申请行锁（写锁）之前，数据库会自动先给事务 A 申请表的意向排他锁。当事务 B 去申请表的互斥锁时就会失败，因为表上有意向排他锁之后事务 B 申请表的互斥锁时会被阻塞。

1. 意向共享锁（IS）：由语句 select ... lock in share mode; 添加。

• 当一个事务打算对表中的某些行加共享锁（S 锁）时，它会在表级别加一个意向共享锁（IS 锁）。
• 意向共享锁之间是兼容的，可以允许多个事务同时对表中不同的行加共享锁。

1. 意向排他锁（IX）：由 insert，update，delete，select … for update; 添加。

• 当一个事务打算对表中的某些行加排他锁（X 锁）时，它会在表级别加一个意向排他锁（IX 锁）。
• 意向排他锁之间也是兼容的，允许多个事务同时对表中不同的行加排他锁或共享锁。

查看：select * from performace_schema.data_locks;

下表中的 S 和 X 指的是表级锁，意向锁不会与行级的读写锁互斥！！！

意向锁的使用场景

1. 行级锁与表级锁的兼容性检测：
   • 当一个事务需要对表中的某些行加锁时，它会先在表级别加上相应的意向锁（IS 或 IX）。
   • 这样，当其他事务尝试获取表级锁（例如 LOCK TABLES）时，只需要检查表级别的意向锁状态，就可以知道是否可以安全地进行加锁操作。
2. 防止死锁：
   • 通过使用意向锁，可以有效防止死锁的发生。例如，如果两个事务同时尝试对表的不同部分加锁，如果没有意向锁的机制，可能会导致相互等待，最终陷入死锁。
   • 意向锁通过明确锁的意图，可以提前检测到潜在的冲突，从而避免死锁情况的出现。

行级锁：开销大，加锁慢；锁定粒度小，发生锁冲突概率低，并发度高；会出现死锁。通过对索引中叶子节点的索引项加锁来实现。

行级锁的具体实现包含：记录锁，间隙锁和邻键锁。

记录锁（record lock）：锁定单个行的锁，防止其它事务对此进行 update 和 delete，在 Read committed、Repeatable read 隔离级别下都支持。

• 共享锁（S）：允许一个事务读一行，阻止其它事务获得相同数据集的排他锁。
• 排他锁（X）：允许获取排他锁的事务更新数据，阻止其它事务获得相同数据集的共享锁和排他锁。

间隙锁（gap lock）：锁定索引记录间隙（不含该记录），确保索引记录间隙不变，防止其它事务在这个间隙进行插入操作以产生幻读，在 Repeatable read 隔离级别下支持。间隙锁可共存，一个事务采用的间隙锁不会阻止另一个事务在同一间隙上采用间隙锁。

以 SELECT * FROM employees WHERE age BETWEEN 25 AND 30 FOR UPDATE; 为例：

InnoDB 会对二级索引 age 的叶子节点加锁，包括：

• 范围内存在的所有索引项（记录锁）。
• 范围内不存在记录的“间隙”部分（间隙锁）。

随后，对这些索引项所指向的聚簇索引中的行数据加锁。

也就是说这种情况下，二级索引和聚簇索引的多个节点都会被加锁，以避免幻读和保证一致性。

除了上述例子的一致性锁定读之外，UPDATE 和 DELETE 在查询非唯一索引时也会使用间隙锁。

间隙锁可能带来的问题

1. 降低并发性能：间隙锁锁住的是一个范围，而不是具体的行，因此可能导致较多事务被阻塞。例如，一个简单的范围查询可能锁住比预期更多的行或区间。
2. 死锁风险增加：由于间隙锁锁定的范围较广，在高并发场景下，多个事务可能会竞争相邻的间隙，导致死锁。
3. 仅适用于索引字段：间隙锁只能作用于有索引的字段。如果字段没有索引，在 InnoDB 下会退化为表锁，从而进一步降低性能。

临键锁（next-key lock）：行锁和间隙锁的组合，同时锁住数据以及数据前面的间隙（左开右闭区间），在 Repeatable read 隔离级别下支持。该锁用于解决幻读问题。

当查询的索引是针对唯一属性列时，临键锁会退化为记录锁，因为没必要锁一个区间，所有该字段的值都是唯一值。

此外，对于非唯一索引，如果查询的数据存在，那么 InnoDB 还会对该索引中的下一个区间加间隙锁。

假设我们创建一个表：

1

CREATE TABLE z ( a INT, b INT, PRIMARY KEY(a), KEY(b) );

表 z 的列 b 是辅助索引，若在会话 A 中执行下面的 SQL 语句：

1
2
3
4
5
6

INSERT INTO z SELECT 1,1;
INSERT INTO z SELECT 3,1;
INSERT INTO z SELECT 5,3;
INSERT INTO z SELECT 7,6;
INSERT INTO z SELECT 10,8;
SELECT * FROM z WHERE b=3 FOR UPDATE;

很明显，这时 SQL 语句通过索引列 b 进行查询，因此其使用传统的 Next-Key Locking 技术加锁，并且由于有两个索引，其需要分别进行锁定。对于聚集索引，其仅对列 a 等于 5 的索引加上 Record Lock。而对于辅助索引，其加上的是 Next-Key Lock，锁定的范围是 (1, 3)，特别需要注意的是，InnoDB 存储引擎还会对辅助索引下一个键值

加上 gap lock，即还有一个辅助索引范围为 (3, 6) 的锁。因此，若在新会话 B 中执行下面的 SQL 语句，都会被阻塞：

1
2
3

SELECT * FROM z WHERE a = 5 LOCK IN SHARE MODE;
INSERT INTO z SELECT 4,2;
INSERT INTO z SELECT 6,5;

第一个 SQL 语句不能执行，因为在会话 A 中执行的 SQL 语句已经对聚集索引中列 a = 5 的值加上 X 锁，因此执行会被阻塞。第二个 SQL 语句，主键插入 4，没有问题，但是插入的辅助索引值 2 在锁定的范围 (1, 3) 中，因此执行同样会被阻塞。第三个 SQL 语句，插入的主键 6 没有被锁定，5 也不在范围 (1, 3) 之间。但插入的值 5 在另一个锁定的范围 (3, 6) 中，故同样需要等待。而下面的 SQL 语句，不会被阻塞，可以立即执行：

1
2
3

INSERT INTO z SELECT 8,6;
INSERT INTO z SELECT 2,0;
INSERT INTO z SELECT 6,7;

从上面的例子中可以看到，Gap Lock 的作用是为了阻止多个事务将记录插入到同一范围内，而这会导致 Phantom Problem 问题的产生。例如在上面的例子中，会话 A 中用户已经锁定了 b = 3 的记录。若此时没有 Gap Lock 锁定 (3, 6)，那么用户可以插入索引 b 列为 3 的记录，这会导致会话 A 中的用户再次执行同样查询时会返回不同的记录，即导致 Phantom Problem 问题的产生。

用户可以通过以下两种方式来显式地关闭 Gap Lock：

• 将事务的隔离级别设置为 READ COMMITTED
• 将参数 innodb_locks_unsafe_for_binlog 设置为 1

在上述的配置下，除了外键约束和唯一性检查依然需要的 Gap Lock，其余情况仅使用 Record Lock 进行锁定。但需要牢记的是，上述设置破坏了事务的隔离性，并且对于 replication，可能会导致主从数据的不一致。此外，从性能上来看，READ COMMITTED 也不会优于默认的事务隔离级别 READ REPEATABLE。

在 InnoDB 存储引擎中，对于 INSERT 的操作，其会检查插入记录的下一条记录是否被锁定，若已经被锁定，则不允许查询。对于上面的例子，会话 A 已经锁定了表 z 中 b = 3 的记录，即已经锁定了 (1, 3) 的范围，这时若在其他会话中进行如下的插入同样会导致阻塞：

1

INSERT INTO z SELECT 2,2;

因为在辅助索引列 b 上插入值为 2 的记录时，会监测到下一个记录 3 已经被索引。而将插入修改为如下的值，可以立即执行：

1

INSERT INTO z SELECT 2,0;

需要注意的是，对于唯一键值的锁定，Next-Key Lock 降级为 Record Lock 仅存在于查询所有的唯一索引列。若唯一索引由多个列组成，而查询仅是查找多个唯一索引列中的其中一个，那么查询其实是 range 类型查询，而不是 point 类型查询，故 InnoDB 存储引擎依然使用 Next-Key Lock 进行锁定。

InnoDB 存储引擎默认的事务隔离级别是 REPEATABLE READ，在该隔离级别下，其采用 Next-Key Locking 的方式来加锁。而在事务隔离级别 READ COMMITTED 下，其仅采用 Record Lock。

此外，用户可以通过 InnoDB 存储引擎的 Next-Key Locking 机制在应用层面实现唯一性的检查。例如：

1
2
3
4
5

SELECT * FROM table WHERE col = xxx LOCK IN SHARE MODE;

If not found any row:
  # unique for insert value
  INSERT INTO table VALUES (...);

如果用户通过索引查询一个值，并对该值加上一个 SLock，那么即使查询的值不存在，其锁定的也是一个范围。因此若没有返回任何行，那么新插入的值一定是唯一的。或许有读者会疑问：如果在进行第一步 SELECT … LOCK IN SHARE MODE 操作时，有多个事务并发操作，那么这种唯一性检查机制是否存在问题？其实并不会，因为这时会导致死锁，只有一个事务的插入操作会成功，而其余的事务会抛出死锁错误。如下表所示：

插入意向锁

插入意向锁是间隙粒度的锁，精细到单个索引页里某两个值之间的区间，用于标识事务计划在某个索引间隙内插入数据而加设的锁。它并不锁定具体已存在的行，而是将要插入的位置所在的间隙临时锁定为计划插入，从而允许多个事务在同一间隙内并发插入不同的记录。也就是说，插入意向锁仅表示意向，不直接阻塞其他事务对同一间隙的插入，只要插入位置互不冲突即可并发执行。

它介于行级（Record Lock，锁已存在行）和页/表级（锁整页或整表）之间，用来协调多个事务同时往同一个区间插入新行，而不去阻塞彼此。该锁的设计初衷是提高并发插入能力，减少因行锁或表级锁而产生的阻塞。

当执行 INSERT 语句时，InnoDB 会先定位插入值在聚集索引（或唯一索引）中的正确位置。在真正写入新行之前，InnoDB 会对该插入间隙加上插入意向锁，以表明本事务计划在此间隙插入数据。只有当此时该间隙已经被其他事务以 Gap Lock 形式范围锁定（如执行范围扫描加锁）时，才能导致当前插入意向锁请求被阻塞。否则，插入意向锁之间互不冲突。

获得插入意向锁后，InnoDB 会继续在实际要插入的新行位置加行级写锁，确保后续写操作的原子性与一致性。在插入完成并提交后，这条新插入行上的行锁保持至事务结束，然后随着事务提交释放；插入意向锁在加行锁后也会被释放，不会持续阻塞。

任何普通的 INSERT 操作（包括单行插入和多行插入），在执行前都会对目标插入点所在的索引空隙加一个插入意向锁，表明当前事务打算在此处插入新行，但不会阻塞同一区间的其他插入操作。

InnoDB 在 REPEATABLE READ 隔离级别下，针对不同类型的索引检索与扫描操作采取了不同的锁策略：

• 执行的范围扫描（如 SELECT … FOR UPDATE、UPDATE、DELETE 等）会使用 Next-Key 锁，它相当于给索引记录加上行锁（Record Lock），同时对该记录之前的空隙加上间隙锁，从而禁止并发事务在此间隙插入幻行。
• 当对唯一索引进行等值查询（unique index + … WHERE key = value）时，如果能精确匹配到某条已存在记录，InnoDB 会直接对该记录加行级锁（Record Lock），而不再对前置间隙加锁（即不使用 Gap Lock）。这种唯一索引 + 等值匹配的情况被 InnoDB 自动优化为仅行锁，以减少锁级别和冲突。
• InnoDB 的行锁是加在索引记录上的，如果某条查询完全不经过索引（例如全表扫描、非索引列条件），InnoDB 会退化为给整张表加表级锁。
• 当在 唯一索引上执行等值查询，但该值在表中不存在（即要锁定某个不存在的记录）时，InnoDB 会对对应索引位置的空隙加上间隙锁，防止其他事务在该位置插入新行。
• 在非唯一索引上执行等值查询（ordinary index + WHERE key = value）时，InnoDB 会先沿索引向右遍历查找匹配行；若查到的最后一个值仍不满足等值条件，Next-Key 锁会退化为仅加间隙锁，而不是继续对某条不存在的记录加行锁。
• 在唯一索引上执行范围查询（WHERE key BETWEEN a AND b 或 WHERE key > a 等），InnoDB 访问到第一个不满足条件的值后就停止，这也保证了越界位置的间隙锁效果——只锁定真正满足条件的记录之前的空隙，避免后续出现新的幻行。

按照加锁机制可分为：

乐观锁

乐观锁假设冲突在系统中出现的频率较低，因此在数据库事务执行过程中，不会频繁地去锁定资源。相反，它在提交更新的时候才检查是否有其他事务已经修改了数据。

可以通过在数据表中使用版本号或时间戳来实现，每次读取记录时，同时获取版本号或时间戳，更新时检查版本号或时间戳是否发生变化。

如果没有变化，则执行更新并增加版本号或更新时间戳；如果检测到冲突（即版本号或时间戳与之前读取的不同），则拒绝更新。

悲观锁

悲观锁假设冲突是常见的，因此在数据处理过程中，它会主动锁定数据，防止其他事务进行修改。

可以直接使用数据库的锁机制，如行锁或表锁，来锁定被访问的数据。常见的实现是 SELECT FOR UPDATE 语句，它在读取数据时就加上了锁，直到当前事务提交或回滚后才释放。

解决库存超买问题

乐观锁

1

UPDATE inventory SET count = count - 1, version = version + 1 WHERE product_id = 1 AND version = current_version;

因此乐观锁通过不断递增的版本号来控制并发事务。

悲观锁

1
2
3
4

START TRANSACTION;
SELECT * FROM inventory WHERE product_id = 1 FOR UPDATE;
UPDATE inventory SET count = count - 1 WHERE product_id = 1;
COMMIT;

由此可见，悲观锁会在事务开始时直接锁定库存记录，直到事务结束。

一致性非锁定读

一致性非锁定读是一种利用多版本并发控制（MVCC）的读取方式。当事务执行普通的 SELECT 语句时，即使另一事务正在对同一行进行 UPDATE 或 DELETE，读取操作也不会被阻塞。

InnoDB 会为每条记录在 undo 段中保存历史版本。当读取请求到来时，若目标行正被加锁或已被修改，InnoDB 会取用该行的快照数据（历史版本）而非等待当前锁的释放，从而实现非锁定地读取一致性数据。

每次对行执行更新或删除时，InnoDB 会将修改前的行数据写入 undo 段，形成一个快照版本。一个行记录可能拥有多个历史版本，每个版本对应不同时间点的值。通过在事务启动时或者读取时确定一个合适的版本，InnoDB 能保证读取到符合隔离级别要求的“旧数据”或“最新已提交数据”，而不去抢占当前正在被写锁定的行。

由于读取操作无需等待行级锁释放，InnoDB 的并发性能大幅提升。读操作不会阻塞写操作，写操作也不会过度影响其它读事务。

在大多数情况下，事务仅需访问行快照，即可保证数据一致性，无须引入额外锁，从而避免死锁与锁等待带来的性能开销。

**READ COMMITTED：**每次读取都会取当前最新的“已提交”快照。若在同一事务中连续执行两次相同查询，第二次查询可能看到其他事务已提交的更新。

**REPEATABLE READ（InnoDB 默认）：**事务启动后即确定一个读取视图（snapshot），所有后续读取都基于该视图中的版本。无论其他事务如何提交，当前事务看到的行数据都是事务开始时的一致快照。

一致性锁定读

在 InnoDB 默认的 REPEATABLE READ 隔离级别下，普通的 SELECT 都是非锁定的一致性读，通过 MVCC 机制读取快照而不会阻塞或等待行锁。但在某些业务场景中，用户需要显式地对读取到的数据加锁，以强制保证数据逻辑上的一致性，此时就需要使用“一致性锁定读”。

InnoDB 支持对 SELECT 语句加锁的两种方式：

• SELECT … FOR UPDATE
• SELECT … LOCK IN SHARE MODE

其中：

• SELECT … FOR UPDATE
  • 会对检索到的每一行记录加上排他锁。
  • 一旦某行被 X 锁锁定，其他事务既不能对该行加 X 锁，也不能加 S 锁，必须等该事务提交或回滚后才可访问。
• SELECT … LOCK IN SHARE MODE
  • 会对检索到的每一行记录加上共享锁。
  • 其他事务可以对该行继续加共享锁（并发读取），但若尝试加排他锁就会被阻塞，直到 S 锁释放。

SELECT … FOR UPDATE/LOCK IN SHARE MODE 必须在显式事务内执行，也就是在执行之前要先执行：

• BEGIN 或 START TRANSACTION
• 或者将会话设置为 SET AUTOCOMMIT=0，然后执行 SELECT … FOR UPDATE／SELECT … LOCK IN SHARE MODE。

只有在事务结束后（提交或回滚），这些行锁才会被释放，其他事务才能继续操作这些行。

对于一致性非锁定读，就算目标行正在被 X 锁锁定，InnoDB 依然能通过读取行的历史快照来返回结果，不会阻塞。

自增长与锁

自增长在数据库中是非常常见的一种属性。在 InnoDB 存储引擎的内存结构中，每个含有自增长值的表都有一个自增长计数器（auto-increment counter）。当对含有自增长计数器的表进行插入操作时，这个计数器会被初始化，执行如下语句来得到计数器的值：

插入操作会依据这个自增长计数器的值加 1 赋予自增列。这个实现方式称做 AUTO-INC Locking。这种锁其实是采用一种特殊的表锁机制，为了提高插入的性能，锁不是在一个事务完成后才释放，而是在完成对自增长值插入的 SQL 语句后立即释放。

虽然 AUTO-INC Locking 从一定程度上提高了并发插入的效率，但还是存在一些性能上的问题。首先，对于有自增长值的列的并发插入性能较差，事务必须等待前一个插入的完成（虽然不用等待整个事务的结束）。其次，对于 INSERT … SELECT 的大数据量插入，会影响插入的性能，因为此时另一个事务中的插入会被阻塞。

从 MySQL 5.1.22 版本开始，InnoDB 存储引擎中提供了一种轻量级互斥量的自增长实现机制，这种机制大大提高了自增长值插入的性能。并且从该版本开始，InnoDB 存储引擎提供了一个参数 innodb_autoinc_lock_mode 来控制自增长的模式，该参数的默认值为 1。

下表对插入操作进行分类：

innodb_autoinc_lock_mode 有三个有效值可供设定，具体如下：

此外，还需要特别注意的是，在 InnoDB 存储引擎中自增长的实现和 MyISAM 不同。MyISAM 存储引擎是表锁设计，自增长不考虑并发插入的问题。因此在 master 上用 InnoDB 存储引擎，在 slave 上用 MyISAM 存储引擎的 replication 架构下，用户必须考虑这种情况。

上表中，并发插入问题指的是在高并发场景下，用互斥量（mutex）保护自增计数器时会出现的两类问题：

1. ID 分配成为串行瓶颈
   • 互斥量会让每个插入请求都要轮流抢一次锁，才能执行 counter++ 并分配一个自增值。这在并发插入很高时，会频繁争抢同一个互斥量，造成吞吐下降。
2. 自增 ID 不连续或乱序
   • 互斥量模式下，插入时就分配 ID。如果某个事务分配到 ID 后回滚，这个号就空了，导致跳号更明显。
   • 并发事务各自抢到互斥量分配 ID，但可能是后抢到的人先真正写入、先提交，最终物理插入顺序与 ID 逻辑顺序并不一致。

在 InnoDB 存储引擎中，如果要让某个列使用 AUTO_INCREMENT 功能，必须满足两个条件：

1. 该列要有索引；
2. 在对应索引中，它必须是最左边（第一列）。

如果把自增列放在联合索引但不是第一个字段，或者根本没给它建立索引，InnoDB 会报错并拒绝插入；而 MyISAM 在相同情况下则不会报异常。

外键和锁

InnoDB 在创建外键时，如果外键列上没有显式索引，会自动为该列创建一个索引，以避免全表扫描带来的锁争用。
当对子表执行插入或更新外键列（即要引用父表某条记录）时，InnoDB 必须先查询父表确保对应的主键（或唯一键）存在。

但简单的 一致性非锁定读（普通 SELECT）并不能保证在事务并发环境中数据的一致性——可能会出现脏写或幻读情形。

因此，InnoDB 在查询父表时会使用 SELECT … LOCK IN SHARE MODE，对父表所查的行加一个 S 锁（共享锁）。这样做有两个作用：

1. 防止父表被并发事务删除或更新：如果父表对应行已被其他事务加了 X 锁（排他锁），子事务在 LOCK IN SHARE MODE 时就会阻塞，直到父锁释放为止。
2. 保证外键引用时数据不会不一致：只有拿到父表的 S 锁，才能证明此父键在本事务内是稳固存在的、不被其他事务删除或修改。

如果此时父表相应行已经被别的事务用 SELECT … FOR UPDATE 或 UPDATE/DELETE 加上了 X 锁，子表的外键检查就必须等这一 X 锁释放后才能继续。

也就是说，外键引用操作会被刻意设计成主动等待父表可读且稳固的状态，从而避免插入不存在的父记录或引用已改/已删的数据。

阻塞

因为不同锁之间的兼容性关系，在有些时刻一个事务中的锁需要等待另一个事务中的锁释放它所占用的资源，这就是阻塞。阻塞并不是一件坏事，其是为了确保事务可以并发且正常地运行。

在 InnoDB 存储引擎中，参数 innodb_lock_wait_timeout 用来控制等待的时间（默认是 50 秒），innodb_rollback_on_timeout 用来设定是否在等待超时时对进行中的事务进行回滚操作（默认为 OFF，代表不回滚）。参数 innodb_lock_wait_timeout 是动态的，可以在 MySQL 数据库运行时进行调整：

1
2

mysql> SET @@innodb_lock_wait_timeout=60;
Query OK, 0 rows affected (0.00 sec)

而 innodb_rollback_on_timeout 是静态的，不可在启动时进行修改，如：

1
2

mysql> SET @@innodb_rollback_on_timeout=on;
ERROR 1238 (HY000): Variable 'innodb_rollback_on_timeout' is a read only variable

当发生超时，MySQL 数据库会抛出一个 1205 的错误，如：

1
2
3
4
5

mysql> BEGIN;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT * FROM t WHERE a = 1 FOR UPDATE;
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction

需要注意的是，在默认情况下 InnoDB 不会回滚超时引发的错误异常，其实 InnoDB 在大部分情况下都不会对异常进行回滚。

死锁

死锁的概念

死锁是指两个或两个以上的事务在执行过程中，因争夺锁资源而造成的一种互相等待的现象。若无外力作用，事务都将无法推进下去。解决死锁问题最简单的方式是不 要有等待，将任何的等待都转化为回滚，并且事务重新开始。毫无疑问，这的确可以避免死锁问题的产生。然而在线上环境中，这可能导致并发性能的下降，甚至任何一个事务都不能进行。而这所带来的问题远比死锁问题更为严重，因为这很难被发现并且浪费资源。

解决死锁问题最简单的一种方法是超时，即当两个事务互相等待时，当一个等待时间超过设置的某一阈值时，其中一个事务进行回滚，另一个等待的事务就能继续进行。在 InnoDB 存储引擎中，参数 innodb_lock_wait_timeout 用来设置超时时间。

超时机制虽然简单，但是其仅通过超时后对事务进行回滚的方式来处理，或者说其是根据 FIFO 的顺序选择回滚对象。但被超时的事务所占权重比较大，如事务操作更新了很多行，占用了较多的 undo log，这时采用 FIFO 的方式，就显得不合适了，因为回滚这个事务的时间相对另一个事务所占用的时间可能会很多。

因此，除了超时机制，目前数据库还普遍采用 wait-for graph（等待图）的方式来进行死锁检测。较之超时的解决方案，这是一种更为主动的死锁检测方式。InnoDB 存储引擎也采用的这种方式。wait-for graph 要求数据库保存以下两种信息：

• 锁的信息链表
• 事务等待链表

通过上述链表可以构造出一张图，而在这个图中若存在回路，就代表存在死锁，因此资源间相互发生等待。在 wait-for graph 中，事务为图中的节点。而在图中，事务 T1 指向 T2 边的定义为：事务 T1 等待事务 T2 所占用的资源，也就是事务之间在等待相同的资源，而事务 T1 发生在事务 T2 的后面。

假设当前事务和锁的状态如下图：

在 Transaction Wait Lists 中可以看到共有 4 个事务 t1、t2、t3、t4，故在 wait-for graph 中应有 4 个节点。而事务 t2 对 row1 占用 X 锁，事务 t1 对 row2 占用 S 锁。事务 t1 需要等待事务 t2 对 row1 的资源，因此在 wait-for graph 中有条边从节点 t1 指向节点 t2。事务 t2 需要等待事务 t1、t4 所占用的 row2 对象，故而存在节点 t2 到节点 t1、t4 的边。同样，存在节点 t3 到节点 t1、t2、t4 的边，因此最终的 wait-for graph 如下图：

可以发现存在回路 (t1, t2)，因此存在死锁。通过上述的介绍，可以发现 wait-for graph 是一种较为主动的死锁检测机制，在每个事务请求锁并发生等待时都会判断是否存在回路，若存在则有死锁。通常来说，InnoDB 存储引擎选择回滚 undo 量最小的事务。

wait-for graph 的死锁检测通常采用深度优先的算法实现，在 InnoDB 1.2 版本之前，都是采用递归方式实现。而从 1.2 版本开始，对 wait-for graph 的死锁检测进行了优化，将递归用非递归的方式实现，从而进一步提高了 InnoDB 存储引擎的性能。

死锁示例

如果程序是串行的，那么不可能发生死锁。死锁只存在于并发的情况，而数据库本身就是一个并发运行的程序，因此可能会发生死锁。下表的操作演示了死锁的一种经典的情况，即 A 等待 B， B 在等待 A，这种死锁问题被称为 AB-BA 死锁。

在上述操作中，会话 B 中的事务抛出了 1213 这个错误提示，即表示事务发生了死锁。死锁的原因是会话 A 和 B 的资源在互相等待。大多数的死锁 InnoDB 存储引擎本身可以侦测到，不需要人为干预。但是在上面的例子中，在会话 B 中的事务抛出死锁异常后，会话 A 中马上得到了记录 2 的这个资源，这其实是因为会话 B 中的事务发生了回滚，否则会话 A 中的事务是不可能得到该资源的。之前说过 InnoDB 存储引擎并不会回滚大部分的异常，但死锁除外。发现死锁后，InnoDB 存储引擎会马上回滚一个事务，这一点需要注意。因此如果在应用程序中捕获了 1213 这个错误，其实并不需要对其进行额外回滚。

此外还有另一种死锁，即当前事务持有了待插入记录的下一个记录的 X 锁，但是在等待队列中存在一个 S 锁的请求，则可能会发生死锁。来看一个例子，首先根据如下代码创建测试表 t，并导入一些数据：

1
2
3
4

CREATE TABLE t (
  a INT PRIMARY KEY
) ENGINE=InnoDB;
INSERT INTO t VALUES (1), (2), (4), (5);

下面演示两会话（会话 A 和会话 B）并发执行时发生死锁的过程：

事务 A 在时间点 3：

执行 SELECT * FROM t WHERE a = 4 FOR UPDATE;

这条语句会对主键值 a=4 的记录加 X 锁。到此时刻，事务 A 持有对记录 (a=4) 的 X 锁，且锁保持不释放（事务尚未提交或回滚）。

事务 B 在时间点 4：

执行 SELECT * FROM t WHERE a <= 4 LOCK IN SHARE MODE;

由于条件 a <= 4 会匹配到主键值 1, 2, 4 三条记录，因此事务 B 需要对这些记录的索引范围（Range）加 S 锁。其中，对 (a=4) 那条记录上的 S 锁请求会因为事务 A 已经持有该行的 X 锁而被阻塞，导致事务 B 进入等待队列。

事务 A 在时间点 5：

执行 INSERT INTO t VALUES (3);

插入新行 a=3 时，InnoDB 需要在索引（聚簇索引）上为记录 3 所在位置加上插入意向锁（Gap Lock / Next-key Lock）。由于 InnoDB 的聚簇索引按主键值顺序存储，此时 a=3 属于介于 a=2 与 a=4 之间的间隙。

然而，事务 B 已在索引范围上对 (a <= 4) 加了 S 锁，并且正等待获取 (a=4) 上的 S 锁。换句话说，此时索引上存在：

• 事务 A：已对 a=4 加了 X 锁，还需要对间隙 (2, 4) 加插入意向 X 锁，才能插入 a=3。
• 事务 B：已对间隙 (2, 4)（更准确地说是对 a <= 4 范围）请求 S 锁，其中包括 (a=2)、(a=4) 以及它们之间的间隙。

为何形成死锁？

• 事务 B 正在等待 (a = 4) 上的 S 锁，而当事务 A 在时间点 5 尝试插入 a=3 时，InnoDB 会先对 (a = 3) 的插入位置加 X 锁（Gap Lock 或 Next-key Lock）。由于事务 B 已对 (a <= 4) 这个范围中的间隙（包括 (2, 4)）持有 S 锁请求（还未获得，但已在等待队列中），所以此时：
  • 事务 A 需要等到 Gap Lock 获得，而 Gap Lock 又受限于事务 B 已在其上排队的 S 锁；
  • 同时，事务 B 需要等到 (a = 4) 上的 S 锁释放，而 (a = 4) 由事务 A 持有 X 锁；
• 这样就形成循环等待：
  • 事务 A 等待事务 B 在间隙 (2, 4) 上的 S 锁释放（因为事务 B 在关键范围上排队），
  • 事务 B 等待事务 A 释放 (a = 4) 上的 X 锁。

由于两者互相等待、谁都无法前进一步，InnoDB 判定为死锁。

InnoDB 如何选择回滚？

在常见的 AB-BA 死锁（即会话 A 等待会话 B 持有的资源，同时会话 B 等待会话 A 持有的资源）场景中，InnoDB 会回滚产生的事务中undo log 使用量最小的那个，以尽量减少回滚开销。

然而本例中的死锁类型不同：它属于插入意向锁与共享锁（Gap Lock/S 锁）之间的循环等待。此时应回滚哪一个事务呢？

• 事务 A：已持有 (a=4) 的 X 锁，而正在尝试插入 a=3（需要对间隙 (2, 4) 加 X 锁），此时这一步才触发死锁检测；
• 事务 B：已在时间点 4 提出对 a <= 4 范围的 S 锁请求，但尚未获得该锁，处于等待状态。

InnoDB 在检测到此时的死锁后，会回滚 undo log 记录量最大的事务。对比：

• 事务 A：已读取并锁定了整行 a=4，其 undo log 可能包含对索引与行锁记录的修改；
• 事务 B：尚未真正获取任何锁（仅在等待）；其 undo log 体积更小。

排查死锁的简单流程

1. 查看死锁日志 show engine innodb status;
2. 找出死锁对应的 SQL
3. 分析这些 SQL 的加锁情况
4. 模拟死锁的发生过程
5. 分析死锁日志
6. 分析死锁结果

锁升级

锁升级（Lock Escalation）是指将当前锁的粒度降低。举例来说，数据库可以把一个表的 1000 个行锁升级为一个页锁，或者将页锁升级为表锁。如果在数据库的设计中认为锁是一种稀有资源，而且想避免锁的开销，那么数据库中会频繁出现锁升级现象。

Microsoft SQL Server 数据库的设计认为锁是一种稀有的资源，在适合的时候会自动地将行、键或分项锁升级为更粗粒度的表级锁。这种升级保护了系统资源，防止系统使用太多的内存来维护锁，在一定程度上提高了效率。

在 Microsoft SQL Server 数据库中，由于锁是一种稀有的资源，因此锁升级会带来一定的效率提高。但是锁升级带来的一个问题却是因为锁粒度的降低而导致并发性能的降低。

InnoDB 存储引擎不存在锁升级的问题。因为其不是根据每个记录来产生行锁，相反，其根据每个事务访问的每个页对锁进行管理的，采用的是位图的方式。因此不管一个事务锁住页中一个记录还是多个记录，其开销通常都是一致的。

也就是说，在 InnoDB 中，每当一个事务要对某个页内的若干行加锁时，会在该页对应的 lock 对象（lock_rec_t）后面附加一个位图（bitmap），用来表示该页内哪些行被锁住了。每条记录在页内有一个唯一的 heap_no 编号，对应到位图中的一个比特位。当事务锁定某行时，就将该行对应 heap_no 的位图位置置为 1。多个行的锁请求会共用同一个 lock 对象，通过设置不同的 bit 来记录多个行锁。该方式极大地减少了内存开销，避免了行级锁的逐个对象管理及锁升级问题。

假设一张表有 3,000,000 个数据页，每个页大约有 100 条记录，那么总共有 300,000,000 条记录。若有一个事务执行全表更新的 SQL 语句，则需要对所有记录加 X 锁。若根据每行记录产生锁对象进行加锁，并且每个锁占用 10 字节，则仅对锁管理就需要差不多 3 GB 的内存。而 InnoDB 存储引擎根据页进行加锁，并采用位图方式，假设每个页存储的锁信息占用 30 个字节，则锁对象仅需 90 MB 的内存。由此可见两者对于锁资源开销的差距之大。

B+ 树索引中的锁

在 InnoDB 源码层面，B+ 树锁通常包含两种基本类型：

• 索引锁（Index Lock）：对应代码中的 dict_index->lock，用于保护整个 B+ 树索引结构，主要在结构修改（SMO）时使用。
• 页锁（Page Lock）：对应 B+ 树中各数据页的锁变量，用于并发访问控制。非叶子节点页与叶子节点页都可以加锁。

在 MySQL 5.6 版本中：

1. 查询（SELECT）请求
   • 首先对 B+ 树索引加一个共享锁（S LOCK），随后仅在找到目标叶子节点后，对该叶子页再次加 S LOCK，然后释放索引锁。
2. 修改（UPDATE/DELETE/INSERT）请求
   • 若仅修改叶子页数据：先对索引加 S LOCK，再在找到叶子页后对该叶子页加排它锁（X LOCK），然后释放索引锁。
   • 若修改触发了结构变化（SMO）：
     1. 对整个 B+ 树索引升级为 X LOCK；
     2. 执行 btr_cur_search_to_nth_level 定位页面；
     3. 在必要时对父节点直到根节点都施加 X LOCK，防止并发干扰。
   • 非叶子节点并不显式加锁，这导致在 SMO 过程中，查询操作可能被阻塞，产生性能抖动。

从 MySQL 8.0 开始，引入了更细化的锁机制：

1. SX 锁（Shared eXclusive Intent Lock）
   • 在可能发生结构修改时，用于表示预期会写入该分支但尚未真正改动，不会与 S LOCK 冲突，但会与 X LOCK 和其它 SX LOCK 冲突。
2. 非叶子节点页锁
   • 不再只锁叶子页，而对查找路径上所有非叶子节点页先后加锁（先父后子），实现所谓的锁耦合（Latch Coupling），从而缩小锁范围。

B+ 树遍历锁机制：从根到叶

下面以 MySQL 8.0+ 的机制为例，详细描述锁如何从根节点一路向下传递到叶子节点。

这里提前说明，索引锁和根节点的页锁不是一个东西。

读操作

1. 申请索引级共享锁（S LOCK on dict_index）
   • 客户端提交 SELECT … FROM table WHERE key = … FOR UPDATE/LOCK IN SHARE MODE 时，InnoDB 会先对目标表的聚簇索引（dict_index 对象）加一个共享锁（S LOCK），用来保证当前索引结构不会被并发的结构修改操作破坏。
2. 从根节点开始逐级查找
   • 根节点会被先加页级 S LOCK。一旦对根页加锁成功，InnoDB 才继续往下访问子节点。
   • InnoDB 根据查询条件计算散列，然后通过 btr_cur_search_to_nth_level() 在根节点页中查找下一级页面指针。
3. 加锁子节点并逐步下降
   • 当从根节点读取到下一层节点的页号后，会释放根节点的 S LOCK，然后对该子节点页加 S LOCK，确保在当前事务继续寻找下一级时，不会遭到并发页分裂或合并等结构修改。
   • 重复上述过程：在子节点加锁成功后，再释放父节点的锁，然后对孙子节点加 S LOCK……如此递归，直到叶子节点。
   • 这种先子后父的锁耦合方式，保证了在任何时刻只有当前路径上的一部分节点被锁住，避免一次性锁定整棵树，提升并发性能。
4. 在叶子节点加锁并释放索引锁
   • 当定位到叶子节点后，对叶子页加上 S LOCK，并同时在页内搜索目标记录。若是 FOR UPDATE，则将对该记录使用 X LOCK（通过行锁实现）；若是 LOCK IN SHARE MODE，则使用 S LOCK。
   • 此时可以释放最初的索引级共享锁（dict_index->lock），因为页锁已足以保证后续读取过程中不被结构修改破坏。

写操作

1. 申请索引级共享锁（S LOCK on dict_index）
   • 当执行 UPDATE t SET col=… WHERE key=… 时，InnoDB 依旧首先加索引级 S LOCK，防止在查找路径上结构变化。
2. 递归锁定路径上的非叶子节点
   • 执行与读场景相同的路径查找，但依次对每个非叶子节点页加 S LOCK（并在获得子节点锁后立即释放父节点锁），保证当前页不被分裂或重组删除。
3. 在叶子页加 X LOCK
   • 定位到叶子页后，加上一个排它锁（X LOCK），并在页内根据 heap_no 对应到位图将该行锁定。此时可释放索引级共享锁（dict_index->lock）。
4. 执行更新
   • 对目标记录进行写操作，如更新列值。若更新值导致插入新记录或页内空间不足，就会触发叶子页分裂，此时需要对分裂路径重新加锁。
   • 如果触发了页分裂，则会将当前路径上涉及分裂的非叶子节点也升级为 SX LOCK 或 X LOCK，并相应地执行分裂操作。
5. 完成后释放锁
   • 事务结束时，InnoDB 会遍历该事务的 trx_locks 链表，逐个释放所有页锁和行锁。

这部分的具体内容可参考：OLTP 索引

What is the IQ Framework?

The IQ framework is a solution designed for Cache-Augmented SQL (CASQL) systems, which combine relational databases (RDBMS) and key-value stores (KVS) to boost performance by caching database query results. However, CASQL systems often face challenges related to stale data and race conditions. The IQ framework ensures strong consistency while maintaining high performance.

Challenges in CASQL Systems

1. Stale Data in Cache:

   • Cached data in the KVS can become outdated if updates to the RDBMS are not properly synchronized.

   • For example, if a record in the database is modified, but the corresponding cache entry isn’t updated, subsequent reads might return incorrect values.

2. Concurrency Issues:

   • Multiple sessions accessing and modifying the same key in KVS concurrently can lead to inconsistent results.

   • Example:

     • One session updates a value while another session modifies it based on outdated data.

3. RDBMS and Cache Coordination:

   • While RDBMS ensures transactional consistency, KVS often lacks this capability, making it difficult to synchronize their states.

Key Features of the IQ Framework

1. Lease Mechanism: Inhibit (I) and Quarantine (Q):
   1. I Lease (for reads):
      1. Ensures that only one session can query the RDBMS for a cache miss and update the KVS.
      2. Other sessions attempting to read the same key must “back off” and wait.
   2. Q Lease (for writes):
      1. Required for modifying, deleting, or incrementally updating keys in the KVS.
      2. If an I lease exists, the Q lease invalidates it to ensure the write operation’s integrity.
      3. The KVS ignores I’s write operation because this I lease is no longer valid.
2. Lease Expiry:
   1. A lease for a key has a fixed life time and is granted to one KVS connection (thread) at a time.
   2. Expired leases are automatically released, ensuring system availability.
   3. The finite life time enables the KVS to release the lease and continue processing operations in the presence of node failures hosting the application.
3. Session-based Model:
   1. The framework operates through sessions, similar to the two-phase locking protocol.
   2. Leases can be acquired either before or during an RDBMS transaction, providing flexibility.

Implementing ACID Properties

原子性 (Atomicity)： IQ 框架确保事务的操作同时在数据库 (RDBMS) 和缓存 (KVS) 中执行。也就是说，操作不会只在数据库中完成而没有更新缓存。这种设计假设 KVS 中的数据是 RDBMS 数据的一部分，因此如果遇到问题，可以直接删除 KVS 中的数据来保持一致。

一致性 (Consistency)： IQ 框架保证事务在数据库和缓存中的数据状态从一个有效状态变为另一个有效状态。如果数据库的事务回滚 (abort)，那么缓存中的操作也不会被应用，确保不会留下无效的缓存数据。

隔离性 (Isolation)： 即使有多个会话 (session) 同时执行，IQ 框架也让每个会话看起来像是独立执行的，避免了并发问题。例如，即使两个用户同时读写相同的数据，他们看到的结果也是正确且一致的。

持久性 (Durability)： 持久性是由数据库 (RDBMS) 提供的，而缓存 (KVS) 则作为数据库的一部分镜像。KVS 存储的数据是在内存中的副本，但一旦数据库中的事务提交，数据就会被持久保存。

CAS 操作只能保证单一操作的原子性，但无法在多个并发会话中保证强一致性。 由于数据库和缓存系统中的操作顺序可能不一致，会导致数据不同步。

在并发场景下：CAS 无法感知其他会话在其读取后对数据的更改。 多个会话同时执行 CAS 操作时，可能导致更新丢失或顺序混乱，如本例中 S2 的更新被 S1 覆盖。

Q 租约用于写操作，确保某一时刻只有一个会话能够修改目标键值。如果某个键值已有 Q 租约，其他会话（如 S1）会被要求退避（back off）或中止操作。

Invalidate

What is Snapshot Isolation?

Snapshot isolation is a multi-version concurrency control mechanism commonly used in RDBMS to allow concurrent transactions to execute efficiently. It guarantees:

1. Consistent Snapshot: All reads in a transaction observe the same consistent state of the database, as it existed at the transaction’s start.
2. Conflict Detection: A transaction can only commit if its updates do not conflict with updates made by other transactions since its snapshot was taken.

The Problem

Snapshot isolation can cause a race condition between a write session (S1) and a read session (S2) when KVS is involved. The issue unfolds as follows:

1. Write Session (S1):

   • S1 modifies the RDBMS and triggers a delete operation in the KVS to invalidate outdated key-value pairs.

   • S1 commits the transaction after completing its changes in the RDBMS.

2. Read Session (S2):

   • S2 starts after S1’s delete operation in the KVS. It observes a KVS miss for a key-value pair because S1 has invalidated it.

   • S2 queries the RDBMS to recompute the key-value pair. However, because snapshot isolation allows S2 to read an older snapshot of the database, it retrieves outdated (stale) data.

   • S2 inserts this stale data back into the KVS before S1 commits its changes to the RDBMS.

3. Inconsistency:

   • After both sessions complete, the KVS contains a stale key-value pair inconsistent with the RDBMS, leading to incorrect results for future reads.

Solution

I Lease (Inhibit Lease):

• Used by read sessions (e.g., S2).
• When a read session observes a KVS miss, it requests an I lease for the key (k_j) from the KVS server.
• The I lease allows the read session to query the RDBMS, compute a value, and insert the computed key-value pair into the KVS.
• If a Q lease is already in place, the I lease is denied, and the read session is told to back off and retry later.

Q Lease (Quarantine Lease):

• Used by write sessions (e.g., S1).
• When a write session plans to invalidate a key in the KVS, it requests a Q lease for the key (k_j).
• The Q lease prevents other sessions (including those holding I leases) from modifying or inserting the key in the KVS.
• Multiple Q leases can be granted for the same key since deleting a key is idempotent (doesn’t create conflicts).

Optimization

The Problem

• In the original scenario, write sessions (e.g., S1) immediately delete key-value pairs in the KVS as soon as they acquire a Q lease (e.g., Step 1.3 in Figure 3).
• This can cause read sessions (e.g., S2) to encounter KVS misses, triggering redundant operations like querying the RDBMS, recalculating values, and reinserting them into the KVS.

The Proposed Optimization

Deferring Key Deletion Until Write Commit

1. Key Changes:

   • Instead of deleting the key immediately in Step 1.3, the write session (S1) holds the Q lease and defers the deletion until the write session commits (Step 1.5).

   • While S1 is mid-flight, the invalidated key-value pair remains in the KVS for other read sessions (S2) to observe.

2. Handling KVS Hits:

   • Read sessions like S2 that encounter a KVS hit consume the “stale” key-value pair, treating it as valid.

   • This is acceptable because S2’s actions can be serialized to occur before S1, which is still in progress and has not yet committed its RDBMS changes.

3. Handling Write Aborts:

   • If a write session (S1) encounters an exception and aborts, the Q lease is released without deleting the key.

   • The current key-value pair in the KVS remains valid and accessible to other sessions.

Implementation Details

1. Versioning Concept:

   • The optimization can be conceptualized as maintaining a temporary version of the key-value pair for use by all sessions except the one currently invalidating it (S1).

   • Once S1 commits, the temporary version is removed.

2. Abort Command:

   • If a write session (S1) aborts due to constraints or exceptions, an abort command releases all Q leases held by S1 without deleting the key-value pair.

   • Without this command, Q leases would expire naturally after a timeout, during which no other session could modify or access the key.

Re-Arrangement Window:

• With this optimization, S2 and S1 can be re-arranged in a serializable schedule where S2 logically occurs before S1.
• Without the optimization, the re-arrangement window shrinks to zero because S2 would have already queried the RDBMS for stale data, violating consistency.

Refresh and Incremental Update

Key Issues with Compare-and-Swap (CAS)

• CAS Limitation:

  • CAS alone cannot ensure strong consistency. It provides atomic updates to a single key-value pair but does not coordinate these updates with RDBMS transactions.

• Example (Figure 2):

  • KVS writes can occur either:

    1. Prior to the RDBMS transaction, or

    2. As part of the RDBMS transaction.

  • Problem: If the RDBMS transaction aborts, the KVS will retain the modified key-value pair, potentially exposing dirty reads to other sessions.

• Figure 6 (Dirty Read Problem):

  • Write session S1 modifies a key-value pair in KVS.
  • S1’s transaction later aborts, but the intermediate KVS value is consumed by a read session S2 before the rollback, leading to inconsistencies.

• Developer Responsibility:

  • Without additional mechanisms, developers must implement complex logic to restore KVS key-value pairs to their original values when RDBMS transactions abort.

Race Conditions with Incremental Updates (δ Operations)

• Figure 7 (Snapshot Isolation with δ Operations):

• • Write session S1 updates the RDBMS and KVS using an incremental update (e.g., appending to a value).
  • Concurrently, read session S2 queries the RDBMS and overwrites the key-value pair in the KVS.
  • Result: The KVS reflects inconsistent state, as S2’s overwrite may invalidate S1’s incremental change.

• Figure 8 (Reordering KVS Operations):

• • Delaying KVS updates until after the RDBMS transaction doesn’t solve the problem.

• Example in Figure 8:

• • S1 appends a change to a value based on its RDBMS view.
  • S2 modifies the RDBMS during S1’s execution, which S1 unknowingly incorporates into its KVS update.
  • Problem: S2’s modifications are reflected twice in the KVS, introducing inconsistencies.

Solution

Key Concepts in the Solution

1. Q Leases for Write Sessions:

   • A Q lease must be obtained for each key-value pair that a session intends to update.

   • This prevents race conditions by locking the key-value pair until the session completes its operations.

2. Steps for Write Sessions:

   • Step 1: Obtain Q leases for the keys to be updated before committing the RDBMS transaction. This can happen:

     • Before starting the RDBMS transaction.

     • As part of the RDBMS transaction.

   • Step 2: Write the updated key-value pairs to the KVS after committing the RDBMS transaction.

   • Step 3: Release the Q leases once the KVS is updated.

   • Automatic Cleanup: If a Q lease expires, the KVS deletes the associated key-value pair to avoid stale data.

3. Command Design for Write Operations:

   • QaRead (Quarantine-and-Read):

     • Acquires a Q lease on the referenced key and reads its value from the KVS.

     • If a Q lease for the same key is already held by another session, the requesting session receives an abort message, must roll back its RDBMS transaction, release all leases, back off, and retry later.

     • If no value exists in the KVS (a KVS miss), the application can:

       • Skip updating the key, or
       • Query the RDBMS, compute a new value, and insert it using SaR (below).

     • If a QaRead lease encounters an I lease held by a read session, it invalidates the I lease to prevent race conditions.

   • SaR (Swap-and-Release):

     • Updates the value of a key in the KVS with the new value and releases the Q lease.
     • If the new value is null, the Q lease is simply released without updating the KVS.

Handling Race Conditions

1. Q Leases for Concurrent Write Sessions:

   • If two write sessions request Q leases for the same key, the KVS resolves the conflict by:

     • Aborting one session.
     • Ensuring the aborted session retries later, serializing its updates after the session holding the Q lease.

   • This guarantees a valid serial schedule in the RDBMS and KVS.

2. Read Sessions and I Leases:

   • Read sessions use I leases to avoid race conditions when querying the KVS.

   • If a write session issues a QaRead that encounters an existing I lease, the I lease is invalidated to ensure the KVS reflects the latest updates from the RDBMS.

Integration with Two-Phase Locking

• The Q lease mechanism resembles two-phase locking:

  1. Growing Phase: The session acquires all necessary Q leases using QaRead before committing its RDBMS transaction.

  2. Shrinking Phase: The session releases all Q leases using SaR after committing its RDBMS transaction.

• Flexibility:

  • A session can issue QaRead commands either before starting the RDBMS transaction or as part of the transaction.

Key Concepts of Incremental Updates

1. Incremental Update Command: IQ-δ:

   • Purpose: Allows a write session to perform an incremental update, such as appending data to an existing key-value pair.

   • Syntax: IQ-δ(ki, δi)

     • ki: The key to be updated.
     • δi: The incremental change to apply (e.g., the value to append).

2. Similarities to QaRead:

   • Q Lease Requirement: Before issuing the IQ-δ command, the session must obtain a Q lease for the key ki to ensure exclusive access.

   • Abort on Conflict:

     • If another session already holds a Q lease on the same key (ki), the KVS returns an abort message.

     • The write session must:

       1. Release all its leases.

       2. Abort its ongoing RDBMS transaction (if any).

       3. Retry the operation later.

优化关键点总结

1. 保留旧版本（Older Version）：

   • 当写会话（S1）更新某键值对 (ki-vi) 时，KVS 暂时保留该键值对的旧版本 (ki-vi_old)，直到 S1 提交。

   • 这避免了读会话在写会话更新期间遇到 KVS miss。

2. 写会话的更新视图：

   • 写会话（S1）在更新期间必须能够看到自己的修改结果（ki-vi_new）。

   • KVS 确保为 S1 提供其最新的更新视图。

Questions

Why is it acceptable for invalidate to delete cache entries?

Consistency Assurance: The cache entry being invalidated represents stale data that is no longer consistent with the current state of the RDBMS. Deleting it prevents read sessions from accessing outdated information.

How is a lease different than a lock?

• Lease: Has a fixed lifetime and expires automatically after a certain duration. This makes leases useful in distributed systems where failures or delays could otherwise cause indefinite blocking.
• Lock: Typically remains active until explicitly released, which can lead to deadlocks or indefinite resource contention if not managed properly.

True or False: IQ leases require changes to the RDBMS software.

False:

IQ leases do not require changes to the RDBMS software.

Instead, they extend the functionality of the Key-Value Store (KVS) by introducing new lease-based commands (e.g., QaRead and SaR) to coordinate operations between the KVS and the RDBMS. This design leverages existing RDBMS features without altering its underlying implementation.

What factors does CAMP consider when selecting a victim?

H(p) = L + size(p) / cost(p)

What is the definition of cost? Provide an example.

• Computation Time: The time required to regenerate or recompute the data if it is evicted from memory.
• Access Latency: The time it would take to fetch the data from disk or another slower storage tier.
• Importance: The priority or weight assigned to the data based on how frequently or critically it is used.

How does CAMP insert a key-value pair in memory?

When a new key-value pair p needs to be inserted into memory, CAMP performs the following steps:

1. Check Cache Capacity

• If there is enough memory to store the new key-value pair:
• • The pair is inserted directly into the appropriate priority group based on its cost-to-size ratio.
  • L is not updated.
• If the cache is full:
• • CAMP selects one or more key-value pairs to evict based on their H(p) values.
  • It removes the pair(s) with the lowest H(p) values until there is sufficient space for the new pair.

2. Insert the New Pair

• The new key-value pair p is added to the cache, and its H(p) value is computed and recorded.
• The pair is placed in the appropriate priority queue based on its cost-to-size ratio.

With BG, what is the definition of Service Level Agreement, SLA?

SLA, e.g., 95% of requests to observe a response time equal to or faster than 100 msec with at most 0.1% of requests observing unpredictable data for 10 minutes.

Name one reason why a system may produce unpredictable data?

Eventual consistency. Or multiple threads are updating the same data item.

Reference: https://dl.acm.org/doi/abs/10.1145/2663165.2663318

索引组织表

在 InnoDB 存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表（index organized table）。在 InnoDB 存储引擎表中，每张表都有一个主键（Primary Key），如果在创建表时没有显式地定义主键，则 InnoDB 存储引擎会按如下方式选择或创建主键：

• 首先判断表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主键。
• 如果不符合上述条件，InnoDB 存储引擎会自动创建一个 6 字节大小的指针。

当表中有多个非空唯一索引时，InnoDB 存储引擎将选择建表时第一个定义的非空唯一索引为主键。这里需要非常注意的是，主键的选择依据的是定义索引的顺序，而不是建表时列的顺序。

以下是一个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

mysql> CREATE TABLE z (
  a INT NOT NULL,
  b INT NULL,
  c INT NOT NULL,
  d INT NOT NULL,
  UNIQUE KEY (b),
  UNIQUE KEY (d), UNIQUE KEY (c)
);
Query OK, 0 rows affected (0.02 sec)

mysql> INSERT INTO z SELECT 1,2,3,4;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0

虽然 c、d 列都是非空唯一索引， 都可以作为主键的候选，但是在定义的过程中，由于 d 列首先定义为唯一索引，故 InnoDB 存储引擎将其视为主键。

逻辑存储结构

从 InnoDB 存储引擎的逻辑存储结构看，所有数据都被逻辑地存放在一个空间中，称之为表空间（tablespace）。表空间又由段（segment）、区（extent）、页（page）组成。页在一些文档中有时也称为块（block），InnoDB 存储引擎的逻辑存储结构大致如下：

表空间

表空间可以看做是 InnoDB 存储引擎逻辑结构的最⾼层，所有的数据都存放在表空间中。在默认情况下 InnoDB 存储引擎有一个共享表空间 ibdata1，即所有数据都存放在这个表空间内。如果用户启用了参数 innodb_file_per_table，则每张表内的数据可以单独放到一个表空间内。

如果启用了 innodb_file_per_table 的参数，需要注意的是每张表的表空间内存放的只是数据、索引和插入缓冲 Bitmap 页，其他类的数据，如回滚信息、插入缓冲索引页、系统事务信息、双写缓冲等还是存放在原来的共享表空间内。这同时也说明了另一个问题：即使在启用了参数 innodb_file_per_table 之后，共享表空间还是会不断地增加其大小。

以 Undo 日志为例：在事务提交之前，共享表空间的空间占用会不断增长。而且 InnoDB 存储引擎不会在执行 rollback 时去收缩这个表空间。虽然 InnoDB 不会回收这些空间，但是会自动判断这些 Undo 信息是否还需要，如果不需要，则会将这些空间标记为可用空间，供下次 Undo 使用。

段

表空间是由多个段组成的，常见的段有数据段、索引段、回滚段等。因为前面已经介绍过了 InnoDB 存储引擎表是索引组织的，因此数据即索引，索引即数据。那么数据段即为 B+ 树的叶子节点**，索引段即为 B+ 树的非索引节点。回滚段包含了事务执行过程中用于数据回滚的旧数据。

区

段由一个或多个区组成，区通常为 64 个连续的页，也就是总共 1MB 的数据。为了保证页的连续性，InnoDB 存储引擎会一次从磁盘申请 4 ~ 5 个区。连续的256个数据区为一个数据区组。使用区而非单独的页进行数据分配可优化磁盘操作，减少索引时磁盘寻道时间，特别是在大量数据进行读写时。

但是，这里还有这样一个问题：在用户启用了参数 innodb_file_per_table 后，创建的表默认大小是 96KB。区中是 64 个连续的页，创建的表的大小至少是 1MB 才对啊？

其实是因为有时我们可能只是创建一个很小的表，只插入一条或几条数据，此时 直接分配 1MB 区块是很浪费的，所以在每个段开始时，先最多用 32 个页大小的碎片页（fragment page） 来存放数据（也就是数据页）；在使用完这些页之后才是 64 个连续页的申请。

页

页是 InnoDB 存储数据的基本单元，标准大小为 16 KB，索引树上的一个节点就是一个页，也就意味着数据库每次读写都是以 16 KB 为单位的，即一次最少从磁盘中读取 16KB 的数据到内存，一次最少写入 16KB 的数据到磁盘。

在 InnoDB 存储引擎中，常见的页类型有：

• 数据页（B-tree Node）
• undo 页（Undo Log Page）
• 系统页（System Page）
• 事务数据页（Transaction System Page）
• 插入缓冲位图页（Insert Buffer Bitmap）
• 插入缓冲空闲列表页（Insert Buffer Free List）
• 未压缩的二进制大对象页（Uncompressed BLOB Page）
• 压缩的二进制大对象页（Compressed BLOB Page）

行

InnoDB 存储引擎是面向行（row-oriented）的，也就是说数据是按行进行存放的。每个页存放的行记录也是有硬性定义的，最多允许存放 16KB / 2 ~ 200 行的记录，即 7992 行记录。

这里提到了 row-oriented 的数据库，也就是说，存在有 column-oriented 的数据库。

InnoDB 行记录格式

行数据拥有多中记录格式，如 COMPACT、REDUNDANT、DYNAMIC 等。

COMPACT

Compact 行记录是在 MySQL 5.0 中引入的，其设计目标是高效地存储数据。一个页中存放的行数据越多，其性能就越高。下图是 Compact 行记录的格式：

Compact 行记录格式的前部是一个非 NULL 变长字段长度列表，并且其是按照列的顺序逆序放置的。其长度为：

• 若列的长度小于 255 字节，用 1 字节表示；
• 若大于 255 字节，用 2 字节表示。

变长字段的长度最大不可以超过 2 字节，这是因在 MySQL 数据库中 VARCHAR 类型的最大长度限制为 65535。变长字段之后的第二个部分是 NULL 标志位，该位指示了该字段中是否有 NULL 值，有则用 1 表示。该部分所占的字节数应为 1 字节。接下来的部分是记录头信息（record header），固定占用 5 字节（40 位），每位的含义如下：

最后的部分就是实际存储每个列的数据。需要特别注意的是，NULL 不占该部分任何空间，即 NULL 除了占有 NULL 标志位，实际存储不占有任何空间。

另外有一点需要注意的是，每行数据除了用户定义的列外，还有两个隐藏列，分别是：

• 事务 ID 列（6 字节）
• 回滚指针列（7 字节）

共计额外占用 13 字节。

若 InnoDB 表没有定义主键，每行还会增加一个 6 字节的 rowid 列。

接下来用一个具体示例来分析 Compact 行记录 的内部结构：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE mytest (
  t1 VARCHAR(10),
  t2 VARCHAR(10),
  t3 CHAR(10),
  t4 VARCHAR(10)
) ENGINE=INNODB CHARSET=LATIN1 ROW_FORMAT=COMPACT;
mysql> INSERT INTO mytest VALUES ('a','bb','bb','ccc');
mysql> INSERT INTO mytest VALUES ('d','ee','ee','fff');
mysql> INSERT INTO mytest VALUES ('d',NULL,NULL,'fff');

表 mytest 有 4 个字段：

• t1，t2，t4 是 VARCHAR（变长）
• t3 是 CHAR（定长）

插入三条记录后，查看表空间文件 mytest.ibd。

找到某记录存储起点 0x0000c078，解释如下：

1
2
3
4
5
6
7
8
9
10
11

03 02 01    -- 变长字段长度列表，逆序

00       -- NULL 标志位（第一行无 NULL）

00 00 10 00 2c   -- Record Header（5 字节）

00 00 00 2b 68 00 -- RowID（6 字节）

00 00 00 00 06 05  -- Transaction ID（6 字节）

80 00 00 00 32 01 10 -- Roll Pointer（7 字节）

接下来是列数据（按顺序）：

1
2
3
4
5
6
7

61       -- 'a'

62 62     -- 'bb'

62 62 20 20 20 20 20 20 20 20 -- CHAR 类型需补齐

63 63 63    -- 'ccc'

现在第一行数据就展现在用户眼前了。需要注意的是，变长字段长度列表是逆序存放的，因此变长字段长度列表为 03 02 01，而不是 01 02 03。此外还需要注意 InnoDB 每行有隐藏列 TransactionID 和 Roll Pointer。同时可以发现，固定长度 CHAR 字段在未能完全占用其长度空间时，会用 0x20 来进行填充。

接着再来分析下 Record Header 的最后两个字节，这两个字节代表 next_recorder，0x2c 代表下一个记录的偏移量，即当前记录的位置加上偏移量 0x2c 就是下条记录的起始位置。所以 InnoDB 存储引擎在页内部是通过一种链表的结构来串连各个行记录的。

第二行将不做整理，除了 RowID 不同外，它和第一行大同小异。现在来关注有 NULL 值的第三行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

03 01/* 变长字段长度列表，逆序 */

06  /* NULL 标志位，第三行有 NULL 值 */

00 00 20 ff 98/* Record Header */

00 00 00 2b 68 02/* RowID */

00 00 00 00 06 07/* TransactionID */

80 00 00 00 32 01 10/* Roll Pointer */

64/* 列1 数据 'd' */

66 66 66/* 列4 数据 'fff' */

第三行有 NULL 值，因此 NULL 标志位不再是 00 而是 06，转换成二进制为 00000110，为 1 的值代表第 2 列和第 3 列的数据为 NULL。在其后存储列数据的部分，用户会发现没有存储 NULL 列，而只存储了第 1 列和第 4 列非 NULL 的值。因此这个例子很好地说明了：不管是 CHAR 类型还是 VARCHAR 类型，在 Compact 格式下 NULL 值都不占用任何存储空间。

行溢出数据

我们将过大的字段数据存放到溢出页中，目的是让每个数据页能够存储更多的数据行，也就是减少数据页的膨胀和磁盘 I/O。

Compact 和 Redundant

InnoDB 存储引擎可以将一条记录中的某些数据存储在页外的数据页而非页内。一般认为 BLOB，TEXT 这类的大对象列类型的存储会把数据存放在数据页页外。但是，这个理解有点偏差，BLOB 可以不将数据放在溢出页面，而且即便是 VARCHAR 列数据类型，依然有可能被存放为行溢出数据。

首先对 VARCHAR 数据类型进行研究。MySQL 数据库的 VARCHAR 类型可以存放 65535 字节。但是，是真的吗？真的可以存放 65535 字节吗？

如果创建 VARCHAR 长度为 65535 的表，用户会得到下面的错误信息：

1
2
3
4
5

mysql> CREATE TABLE test (
  -> a VARCHAR(65535)
  -> ) CHARSET=latin1 ENGINE=InnoDB;

ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. You have to change some columns to TEXT or BLOBs

从错误消息可以看到 InnoDB 存储引擎并不支持 65535 长度的 VARCHAR。这是因为还有别的开销，通过实际测试发现，能存储 VARCHAR 类型的最大长度为 65532。以上长度的单位都是字节⚠️。

此外需要注意的是，MySQL 官方手册中定义的 65535 长度是指所有 VARCHAR 列的长度总和。如果列的长度总和超过这个长度，依然无法创建。

但是有没有想过，InnoDB 存储引擎的页为 16KB，即 16384 字节，怎么能存放 65532 字节呢？

因此，在一般情况下，InnoDB 存储引擎的数据都是存放在页类型为 B-tree node 中。但是当发生行溢出时，数据存放在页类型为 Uncompress BLOB 页中。

来看下面一个例子：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE t (
  -> a VARCHAR(65532)
  -> ) ENGINE=InnoDB CHARSET=latin1;
Query OK, 0 rows affected (0.15 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 65532);
Query OK, 1 row affected (0.08 sec)
Records: 1 Duplicates: 0 Warnings: 0

在上述例子中，首先创建了一个列 a 长度为 65532 的 VARCHAR 类型表 t，然后插入了列 a 长度为 65532 的记录。我们可查看表文件，内容如下：

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

page offset 00000000, page type <File Space Header> 

page offset 00000001, page type <Insert Buffer Bitmap> 

page offset 00000002, page type <File Segment inode> 

page offset 00000003, page type <B-tree Node>, page level <0000> 

page offset 00000004, page type <Uncompressed BLOB Page> 

page offset 00000005, page type <Uncompressed BLOB Page> 

page offset 00000006, page type <Uncompressed BLOB Page> 

page offset 00000007, page type <Uncompressed BLOB Page> 

Total number of page: 8 

Insert Buffer Bitmap: 1

Uncompressed BLOB Page: 4

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

可以观察到表空间中有一个数据页节点 B-tree Node，另外有 4 个未压缩的二进制大对象页（Uncompressed BLOB Page）。在这些页中才真正存放了 65532 字节 的数据。

既然实际存放的数据都在 BLOB 页中，那数据页中又存放了些什么内容呢？

可以看到，从 0x0000c093 到 0x0000c392 数据页中其实只保存了 VARCHAR(65532) 的前 768 字节的前缀（prefix）数据（这里都是 'a'），之后是偏移量，指向行溢出页，也就是前面用户看到的 Uncompressed BLOB Page。因此，对于行溢出数据，其结构如下图：

那么多长的 VARCHAR 是保存在单个数据页中的，从多长开始会保存在 BLOB 页呢？可以这样进行思考：InnoDB 存储引擎表是索引组织的，即 B+Tree 的结构，这样每个页中至少应该有两条记录（否则失去了 B+Tree 的意义，变成链表了）。因此，如果页中只能存放下一条记录，那么 InnoDB 存储引擎会自动将行数据存放到溢出页中。

考虑下面表的一种情况：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> CREATE TABLE t (
  -> a VARCHAR(9000)
  -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.13 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 9000);
Query OK, 1 row affected (0.04 sec)

mysql> INSERT INTO t
  -> SELECT REPEAT('a', 9000);
Query OK, 1 row affected (0.04 sec)

表 a 变长字段列的长度为 9000，故能存放在一个数据页中，但是这并不能保证两条长度为 9000 的记录都能存放在一个页中。此时查看磁盘文件，如下：

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

page offset 00000000, page type <File Space Header>

page offset 00000001, page type <Insert Buffer Bitmap>

page offset 00000002, page type <File Segment inode>

page offset 00000003, page type <B-tree Node>, page level <0000>

page offset 00000004, page type <Uncompressed BLOB Page>

page offset 00000005, page type <Uncompressed BLOB Page>

Total number of page: 6

Insert Buffer Bitmap: 1

Uncompressed BLOB Page: 2

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

我们可知，确实行数据被存放到溢出页中。

但是，如果可以在一个页中至少放入两行数据，那 VARCHAR 类型的行数据就不会存放到 BLOB 页中去。经过多次试验测试，发现这个阈值的长度为 8098。

如用户建立一个列为 VARCHAR(8098) 的表，然后插入 2 条记录：

1
2
3
4
5
6
7
8
9
10

mysql> CREATE TABLE t (
  -> a VARCHAR(8098)
  -> ) ENGINE=InnoDB;
Query OK, 0 rows affected (0.12 sec)

mysql> INSERT INTO t SELECT REPEAT('a', 8098);
Query OK, 1 row affected (0.04 sec)

mysql> INSERT INTO t SELECT REPEAT('a', 8098);
Query OK, 1 row affected (0.03 sec)

接着查看磁盘文件，可以发现此时的行记录都是存放在数据页中，而不是在 BLOB 页中。

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

page offset 00000000, page type <File Space Header>

page offset 00000001, page type <Insert Buffer Bitmap>

page offset 00000002, page type <File Segment inode>

page offset 00000003, page type <B-tree Node>, page level <0000>

page offset 00000004, page type <Freshly Allocated Page>

page offset 00000005, page type <Freshly Allocated Page>

Total number of page: 6

Freshly Allocated Page: 2

Insert Buffer Bitmap: 1

File Space Header: 1

B-tree Node: 1

File Segment inode: 1

另一个问题是，对于 TEXT 或 BLOB 的数据类型，用户总是以为它们是存放在 Uncompressed BLOB Page 中的，其实这也不准确。是否放在数据页中还是 BLOB 页中，和前面讨论的 VARCHAR 一样，至少保证一个页能存放两条记录。

当然既然用户使用了 BLOB 列类型，一般不可能存放长度这么小的数据。因此在大多数的情况下 BLOB 的行数据还是会发生行溢出，实际数据保存在 BLOB 页中，数据页只保存数据的前 768 字节。

Compressed 和 Dynamic

InnoDB 1.0.x 版本开始引入了新的文件格式（file format，用户可以理解为新的页格式），以前支持的 Compact 和 Redundant 格式称为 Antelope 文件格式，新的文件格式称为 Barracuda 文件格式。

Barracuda 文件格式下拥有两种新的行记录格式：Compressed 和 Dynamic。

新的两种记录格式对于存放在 BLOB 中的数据采用了完全的行溢出方式，如下图：

在数据页中只存放 20 个字节的指针，实际数据都存放在 Off Page 中，而之前的 Compact 和 Redundant 两种格式会存放 768 个前缀字节。

Compressed 行记录格式的另一个功能就是：存储在其中的行数据会以 zlib 的算法进行压缩，因此对于 BLOB、TEXT、VARCHAR 这类大长度类型的数据能进行非常有效的存储。

CHAR 的行结构存储

通常理解 VARCHAR 是存储变长度的字符类型，CHAR 是存储固定长度的字符类型。而在前面的内容中，我们可以发现每行的变长字段长度的列表都没有存储 CHAR 类型的长度。

然而，值得注意的是之前给出的两个例子中的字符集都是单字节的 latin1 格式。从 MySQL 4.1 版本开始，CHAR(N) 中的 N 指的是字符的长度，而不是之前版本的字节长度。

也就是说在不同的字符集中，CHAR 类型列内部存储的可能不是定长的数据。例如下面的这个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

mysql> CREATE TABLE j (
  -> a CHAR(2)
  -> ) CHARSET=GBK ENGINE=InnoDB;
Query OK, 0 rows affected (0.11 sec)

mysql> INSERT INTO j SELECT 'ab';
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> SET NAMES GBK;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO j SELECT '我们';
Query OK, 1 row affected (0.04 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO j SELECT 'a';
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

在上述例子中，表 j 的字符集是 GBK。用户分别插入了两个字符的数据 ‘ab’ 和 ‘我们’，然后查看所占字节，可得如下结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

mysql> SELECT a,CHAR_LENGTH(a),LENGTH(a)
  -> FROM j\G;
*************************** 1. row ***************************
a: ab
CHAR_LENGTH(a): 2
LENGTH(a): 2
*************************** 2. row ***************************
a: 我们
CHAR_LENGTH(a): 2
LENGTH(a): 4
*************************** 3. row ***************************
a: a
CHAR_LENGTH(a): 1
LENGTH(a): 1
3 rows in set (0.00 sec)

通过不同的 CHAR_LENGTH 和 CHAR 函数可以观察到：前两个记录 ‘ab’ 和 ‘我们’ 字符串的长度都是 2。但是内部存储上 ‘ab’ 占用 2 字节，而 ‘我们’ 占用 4 字节。如果通过 HEX 函数查看内部十六进制的存储，可以看到：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> SELECT a,HEX(a)
  -> FROM j\G;
*************************** 1. row ***************************
a: ab
HEX(a): 6162
*************************** 2. row ***************************
a: 我们
HEX(a): CED2C3C7
*************************** 3. row ***************************
a: a
HEX(a): 61
3 rows in set (0.00 sec)

因此对于多字节字符编码，如 GBK、UTF-8 等，的 CHAR 数据类型的存储，InnoDB 存储引擎在内部将其视为变长字符类型。这也就意味着在变长长度列表中会记录 CHAR 数据类型的长度。

我们可查看磁盘文件：

整理后可以得到如下结果：

第一行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

02     /* 变长字段长度 2，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 10 00 1c /* Recoder Header */

00 00 00 b6 2b 2b /* RowID */

00 00 00 51 52 da /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

61 62   /* 字符 'ab' */

第二行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

04     /* 变长字段长度 4，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 18 ff d5 /* Recoder Header */

00 00 00 b6 2b 2c /* RowID */

00 00 00 51 52 db /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

c3 d2 c3 c7     /* 字符 '我们' */

第三行记录：

1
2
3
4
5
6
7
8
9
10
11
12
13

02     /* 变长字段长度 2，将 CHAR 视作变长类型 */

00     /* NULL 标志位 */

00 00 20 ff b7 /* Recoder Header */

00 00 00 b6 2b 2d /* RowID */

00 00 00 51 53 17 /* TransactionID */

80 00 00 00 2d 01 10 /* Roll Point */

61 20   /* 字符 'a' */

上述例子清楚地显示了 InnoDB 存储引擎内部对 CHAR 类型在多字节字符集类型的存储。CHAR 类型被明确视为变长字符类型，对于未能占满长度的字符还是填充 0x20。InnoDB 存储引擎内部对字符的存储和我们用 HEX 函数看到的也是一致的。因此可以认为在多字节字符集的情况下，CHAR 和 VARCHAR 的实际行存储基本是没有区别的。

InnoDB 数据页结构

InnoDB 数据页由以下 7 个部分组成，如下图所示：

1. File Header（文件头）
2. Page Header（页头）
3. Infimum 和 Supremum Records
4. User Records（用户记录，即行记录）
5. Free Space（空闲空间）
6. Page Directory（页目录）
7. File Trailer（文件结尾信息）

其中 File Header、Page Header、File Trailer 的大小是固定的，分别为 38、56、8 字节，这些空间用于标记该页的一些信息，如 Checksum、数据页所在 B+ 树索引的层数等。User Records、Free Space、Page Directory 这些部分为实际的行记录存储空间，因此大小是动态的。

下图中具体分析了数据页中的各组成部分：

File Header

File Header 用来记录页的一些头信息，由下图中的 8 个部分组成，共占用 38 字节。

下图是 InnoDB 中页的类型：

Page Header

接着 File Header 部分的是 Page Header，该部分用来记录数据页的状态信息，由 14 个部分组成，共占用 56 字节，如下图所示。

需要注意的是，这里的堆结构指的是页内记录的排布方式，并不是数据结构中的堆 heap，也就是在 InnoDB 的一个数据页中，行记录是按照一定规则存储在一个称为“堆”的区域中。这个“堆”具有以下特征：

1. 数据页内的记录不是顺序排布，而是通过链表和 slot 引用来组织的；
2. 堆中的第一个 slot 是 Infimum（表示最小值），最后一个是 Supremum（最大值）；
3. 每个记录都包含一个 next record 指针，指向下一条记录；
4. PAGE_HEAP_TOP：表示当前堆的顶部，新的记录一般会存入这里。

其次，PAGE_DIRECTION：最后插入的方向，这个属性记录了最后一条插入记录的方向，主要用于优化后续插入操作的位置判断，避免每次都从头或尾查找插入位置。

示例：

假设你有一个数据页，用于存储用户年龄的索引，页中原来已有以下记录（已按顺序）：

[20] -> [30] -> [40] -> [50]

现在你要往页里插入新的值：

情况 1：插入 [45]

它的插入位置在 [40] 和 [50] 之间：

• InnoDB 在查找插入位置时，可能从 PAGE_LAST_INSERT 指向的上一个插入位置（比如 [30]）出发。
• 发现现在是往右边插入的，所以：
  • 设置 PAGE_DIRECTION = PAGE_RIGHT（0x02）；
  • 这样下次如果还要插入更大的记录，比如 [48]，就可以直接从 [45] 或 [50] 向右查找，加速插入位置的定位。

情况 2：插入 [25]

• 插入位置在 [20] 和 [30] 之间，InnoDB 会发现你是在“往左边插入”，
• 设置 PAGE_DIRECTION = PAGE_LEFT（0x01）；
• 如果下次你又插入 [22]，系统会直接从上次插入的 [25] 向左找，避免从 Supremum 重新查找。

情况 3：乱序插入

• 你现在插入一条 [42]，下一次又插入 [21]，再下一次插入 [51]，插入方向完全没有规律；
• InnoDB 会识别到你插入方向变化太频繁，就会设置：
  • PAGE_DIRECTION = PAGE_NO_DIRECTION（0x05）；

这时候优化机制关闭，下次插入位置会重新全页查找。

Infimum 和 Supremum Record

在 InnoDB 存储引擎中，每个数据页中有两个模拟的行记录，用来限定记录的边界。Infimum 记录是比该页中任何主键值都要小的值，Supremum 指比任何可能大的值还要大的值。这两个值在页创建时被建立，并且在任何情况下不会被删除。而且在 InnoDB 中，这两个伪行记录的类型是 Char(8)。下图显示了 Infimum 和 Supremum 记录。

User Record 和 Free Space

User Record 就是之前讨论过的部分，即实际存储行记录的内容。再次强调，InnoDB 存储引擎表总是 B+ 树索引组织的。

Free Space 很明显指的就是空闲空间，同样也是个链表数据结构。在一条记录被删除后，该空间会被加入到空闲链表中。

Page Directory

Page Directory 是 InnoDB 数据页中的一个结构，用于帮助快速定位页内记录的位置。它相当于是数据页内部的一个加速查找索引，而且是逆序存放的。

和很多人以为的不同，InnoDB 并不是每条记录都在 Page Directory 中有一个指针。

相反，它是稀疏的目录（sparse directory），即：

• 一个槽通常指向一组记录中最前面的那条；
• 这组记录一般有 4～8 条，由 n_owned 表示。

n_owned 是什么？

n_owned 表示：该槽负责的记录数量。

假设某页中实际有 12 条记录，按主键顺序如下：

a b c d e f g h i j k l

可能在 Page Directory 中只存了以下 3 个槽指针：

Slot 1 -> a

Slot 2 -> e

Slot 3 -> i

这表示：

Slot 1 覆盖记录 a、b、c、d；

Slot 2 覆盖 e、f、g、h；

Slot 3 覆盖 i、j、k、l。

为什么这样做？稀疏目录的好处是什么？

好处是节省空间 + 提高效率：

• 若每条记录都在 Page Directory 里有个槽，占用空间太大；
• 稀疏存储后，只需要少量槽位，通过二分查找就可以迅速定位到一个“接近位置”；
• 然后用链表（通过 next_record 指针）继续遍历几条记录，就能找到目标。

查询流程小结

当你需要在页中找一个记录（比如查主键 = f）时，流程如下：

1. 从 Page Directory 中进行二分查找，发现 f 应该在 e 开头的槽中；
2. 然后从 e 出发，用链表结构沿着 next_record 指针遍历；
3. 依次到 f，查找成功。

⚠️ Page Directory 只是个“粗索引”，最终还要依赖链表来完成精确定位。

File Trailer

为了检测页是否已经完整地写入磁盘（如可能发生的写入过程中磁盘损坏、机器关机等），InnoDB 存储引擎的页中设置了 File Trailer 部分。

File Trailer 只有一个 FIL_PAGE_END_LSN 部分，占用 8 字节。前 4 字节代表该页的 checksum 值，最后 4 字节和 File Header 中的 FIL_PAGE_LSN 相同。将这两个值与 File Header 中的 FIL_PAGE_SPACE_OR_CHKSUM 和 FIL_PAGE_LSN 值进行比较，看是否一致（checksum 的比较需要通过 InnoDB 的 checksum 函数来进行比较，不是简单的等值比较），以此来保证页的完整性（not corrupted）。

在默认配置下，InnoDB 存储引擎每次从磁盘读取一个页就会检测该页的完整性，判断页是否发生 Corrupt，这就是通过 File Trailer 部分进行检测，而该部分的检测会有一定的开销。

InnoDB 数据页结构实例分析

在 MySQL 技术内幕的这一节中，Record Header 中的最后 2 字节内容代表的是下一行中实际存储数据的部分的初始位置。

以 0000c107 对应的行为例，我们从 0000c100 开始看：因为表中只存在一个 Char(10) 类型的字段，而且字符集是 UTF8，因此 Char 字段会被视为可变字符，并会在行记录的开始记录其长度 0a。之后的 00 代表该行中没有为 NULL 的字段，而且该行中页确实没有 NULL 字段。接着是 5 字节的 Header。之后是主键 00 00 00 05，因为该表中我们指定了主键且主键类型为 INT，因为这里存储的是 4 字节的主键的内容，而不是 6 字节的 ROWID。再就是 6 字节的 Transaction ID 和 7 字节的 Roll Pointer。最后是 10 字节的 Char 字段的数据。一共 34 个字节，正好对应着下一条行数据的实际存储数据的起始位置。Perfecto！

Named File Formats 机制

随着 InnoDB 存储引擎的发展，新的页数据结构有时用来支持新的功能特性。例如前面提到的 InnoDB 1.0.x 版本提供了新的页数据结构来支持表压缩功能，完全的溢出（Off page）大变长字符串类型字段的存储。这些新的页数据结构和之前版本的页并不兼容，因此从 InnoDB 1.0.x 版本开始，InnoDB 存储引擎通过 Named File Formats 机制来解决不同版本下页结构兼容性的问题。

InnoDB 存储引擎 1.0.x 版本之前的文件格式（file format）定义为 Antelope，将这个版本支持的文件格式定义为 Barracuda。新的文件格式总是包含之前版本的页格式。图 4-8 显示了 Barracuda 文件格式和 Antelope 文件格式之间的关系，Antelope 文件格式有 Compact 和 Redundant 的行格式，Barracuda 文件格式既包括了 Antelope 所有的文件格式，另外新加入了之前已经提到过的 Compressed 和 Dynamic 行格式。

分区表

分区功能并不是在存储引擎层完成的，因此不是只有 InnoDB 存储引擎支持分区，常见的存储引擎 MyISAM、NDB 等都支持。但也并不是所有的存储引擎都支持，如 CSV、FEDERATED、MERGE 等就不支持。在使用分区功能前，应该对选择的存储引擎对分区的支持有所了解。

MySQL 数据库在 5.1 版本时添加了对分区的支持。分区的过程是将一个表或索引分解为多个更小、更可管理的部分。就访问数据库的应用而言，从逻辑上讲，只有一个表或一个索引，但是在物理上这个表或索引可能由数个小物理分区组组成。每个分区都是独立的对象，可以独自处理，也可以作为一个更大对象的一部分进行处理。

MySQL 数据库支持的分区类型为水平分区，并不支持垂直分区。此外，MySQL 数据库的分区是局部分区索引，一个分区中既存放了数据又存放了索引。而全局分区是指，数据存放在各个分区中，但是所有数据的索引放在一个对象中。目前，MySQL 数据还不支持全局分区。

大多数人会有这样一个误区：只要启用了分区，数据库就会运行得更快。这个结论是存在很多问题的。就我的经验来看，分区可能会给某些 SQL 语句性能带来提高，但是分区主要用于数据库高可用性和性能的管理。在 OLTP 应用中，对于分区的使用应该非常小心。总之，如果只是一味地使用分区，而不理解分区是如何工作的，也不清楚你的应用如何使用分区，那么分区极有可能会对性能产生负面的影响。

目前 MySQL 数据库支持以下几种类型的分区：

• RANGE 分区：行数据基于属于一个给定连续区间的列值被放入分区。
• LIST 分区：和 RANGE 分区类似，只是 LIST 区间内的是离散的值。
• HASH 分区：根据用户自己定义的表达式的返回值来进行分区，返回值不能为负数。
• KEY 分区：根据 MySQL 数据库提供的哈希函数来进行分区。

你不能创建不带索引的分区，如果表中存在主键或唯一索引时，分区列必须是唯一索引的一个组成部分，因此下面创建分区的 SQL 语句会因缺少索引而产生错误：

1
2
3

mysql> create table t1 (id int not null, val int not null, unique key (id)) partition by hash(val) partitions 4;

ERROR 1503 (HY000): A PRIMARY KEY must include all columns in the table's partitioning function (prefixed columns are not considered).

唯一索引可以是允许 NULL 值的，并且分区列只要是唯一索引的一个组成部分，不需要整个唯一索引列都是分区列。

如果建表时没有指定主键，唯一索引，可以指定任何一个列为分区列。

分区类型

RANGE 分区

第一种分区类型是 RANGE 分区，也是最常用的一种分区类型。下面的 CREATE TABLE 语句创建了一个 id 列的区间分区表。当 id 小于 10 时，数据插入 p0 分区；当 id 大于等于 10 小于 20 时，数据插入 p1 分区。

1
2
3
4
5
6

CREATE TABLE t(
  id INT
) ENGINE=INNODB
PARTITION BY RANGE (id)(
  PARTITION p0 VALUES LESS THAN (10),
  PARTITION p1 VALUES LESS THAN (20));

查看表在磁盘上的物理文件，启用分区之后，表不再由一个 ibd 文件组成了，而是由建立分区时的各个分区 ibd 文件组成，如下面的 t#P#p0.ibd、t#P#p1.ibd：

1
2
3
4
5
6
7
8
9

mysql> system ls -lh /usr/local/mysql/data/test2/t*

-rw-rw---- 1 mysql mysql 8.4K 7月 31 14:11 /usr/local/mysql/data/test2/t.frm

-rw-rw---- 1 mysql mysql  28 7月 31 14:11 /usr/local/mysql/data/test2/t.par

-rw-rw---- 1 mysql mysql  96K 7月 31 14:12 /usr/local/mysql/data/test2/t#P#p0.ibd

-rw-rw---- 1 mysql mysql  96K 7月 31 14:12 /usr/local/mysql/data/test2/t#P#p1.ibd

接着插入如下数据：

1
2
3
4
5
6
7
8
9
10
11

mysql> INSERT INTO t SELECT 9;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO t SELECT 10;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

mysql> INSERT INTO t SELECT 15;
Query OK, 1 row affected (0.03 sec)
Records: 1 Duplicates: 0 Warnings: 0

因为表 t 根据列 id 进行分区，所以数据是根据列 id 的值的范围存放在不同的物理文件中的。

由于我们定义了分区，因此对于插入的值应该严格遵守分区的定义，当插入一个不在分区中定义的值时，MySQL 数据库会抛出一个异常。

LIST 分区

LIST 分区和 RANGE 分区非常相似，只是分区列的值是离散的，而非连续的。如：

1
2
3
4
5
6
7
8

mysql> CREATE TABLE t (
  -> a INT,
  -> b INT) ENGINE=INNODB
  -> PARTITION BY LIST(b)(
    -> PARTITION p0 VALUES IN (1,3,5,7,9),
    -> PARTITION p1 VALUES IN (0,2,4,6,8)
    -> );
Query OK, 0 rows affected (0.26 sec)

不同于 RANGE 分区中定义的 VALUES LESS THAN 语句，LIST 分区使用 VALUES IN。因为每个分区的值是离散的，因此只能定义值。

在用 INSERT 插入多个行数据的过程中遇到分区未定义的值时，MyISAM 和 InnoDB 存储引擎的处理完全不同。MyISAM 引擎会将之前的行数据都插入，但之后的数据不会被插入。而 InnoDB 存储引擎将其视为一个事务，因此没有任何数据插入。

HASH 分区

HASH 分区的主要目的是将数据均匀地分配到预定义的各个分区中，以确保每个分区中的数据量大致相同。与 RANGE 和 LIST 分区需要显式指定某个列值或值集合应存储在哪个分区不同，HASH 分区的分配过程由 MySQL 自动完成。用户只需基于用于分区的列，指定一个返回整数的表达式，同时设置表应被划分的分区数量即可。

要使用 HASH 分区来分割一个表，要在 CREATE TABLE 语句上添加一个：PARTITION BY HASH(expr) 子句，其中 expr 是一个返回一个整数的表达式。它可以仅仅是字段类型为 MySQL 整型的列名。此外，用户很可能需要在后面再添加一个：PARTITIONS num 子句，其中 num 是一个非负的整数，它表示表将要被分割成分区的数量。如果没有包括一个 PARTITIONS 子句，那么分区的数量将默认为 1。

MySQL 数据库还支持一种称为 LINEAR HASH 的分区，它使用一个更加复杂的算法来确定新行插入到已经分区的表中的位置。它的语法和 HASH 分区的语法相似，只是将关键字 HASH 改为 LINEAR HASH。MySQL 数据库根据以下的方法来进行分区的判断：

• 取大于分区数量 4 的下一个 2 的幂值 V，V = POWER(2, CEILING(LOG(2, num))) = 4；
• 所在分区 N = YEAR('2010-04-01') & (V - 1) = 2。

LINEAR HASH 分区的优点在于，增加、删除、合并和拆分分区将变得更加快捷，这有利于处理含有大量数据的表。它的缺点在于，与使用 HASH 分区得到的数据分布相比，各个分区间数据的分布可能不太均衡。

KEY 分区

KEY 分区和 HASH 分区相似，不同之处在于 HASH 分区使用用户定义的函数进行分区，KEY 分区使用 MySQL 数据库提供的函数进行分区。对于 InnoDB 存储引擎，MySQL 数据库使用其内部的哈希函数，这些函数基于与 PASSWORD() 一样的运算法则。如：

1
2
3
4
5
6

mysql> CREATE TABLE t_key (
  -> a INT,
  -> b DATETIME) ENGINE=InnoDB
 -> PARTITION BY KEY (b)
 -> PARTITIONS 4;
Query OK, 0 rows affected (0.43 sec)

在 KEY 分区中使用关键字 LINEAR 和在 HASH 分区中使用具有同样的效果，分区的编号是通过 2 的幂算法得到的，而不是通过模数算法。

COLUMNS 分区

在前面介绍的 RANGE、LIST、HASH 和 KEY 这四种分区中，分区的条件是：数据必须是整型，如果不是整型，那么就需要通过函数将其转化为整型，如 YEAR()、TO_DAYS()、MONTH() 等函数。MySQL 5.5 版本开始支持 COLUMNS 分区，可视为 RANGE 分区和 LIST 分区的一种进化。COLUMNS 分区可以直接使用非整型的数据进行分区，分区根据类型直接比较而得，不需要转化为整型。此外，RANGE COLUMNS 分区可以对多个列的值进行分区。

COLUMNS 分区支持以下的数据类型：

• 所有的整型类型，如 INT、SMALLINT、TINYINT、BIGINT。FLOAT 和 DECIMAL 则不予支持。
• 日期类型，如 DATE 和 DATETIME。其余的日期类型不予支持。
• 字符串类型，如 CHAR、VARCHAR、BINARY 和 VARBINARY。BLOB 和 TEXT 类型不予支持。

对于日期类型的分区，我们不再需要 YEAR() 和 TO_DAYS() 函数了，而是可以直接使用 COLUMNS，如：

1
2
3
4
5
6
7
8

CREATE TABLE t_columns_range(
  a INT,
  b DATETIME
) ENGINE=INNODB
PARTITION BY RANGE COLUMNS (B)(
  PARTITION p0 VALUES LESS THAN ('2009-01-01'),
  PARTITION p1 VALUES LESS THAN ('2010-01-01')
);

同样可以直接使用字符串的分区：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

CREATE TABLE customers_1 (
  first_name VARCHAR(25),
  last_name VARCHAR(25),
  street_1 VARCHAR(30),
  street_2 VARCHAR(30),
  city VARCHAR(15),
  renewal DATE
)
PARTITION BY LIST COLUMNS(city) (
  PARTITION pRegion_1 VALUES IN('Oskarshamn', 'Högsby', 'Mönsterås'),
  PARTITION pRegion_2 VALUES IN('Vimmerby', 'Hultsfred', 'Västervik'),
  PARTITION pRegion_3 VALUES IN('Nässjö', 'Eksjö', 'Vetlanda'),
  PARTITION pRegion_4 VALUES IN('Uppvidinge', 'Alvesta', 'Växjo')
);

对于 RANGE COLUMNS 分区，可以使用多个列进行分区，如：

1
2
3
4
5
6
7
8
9
10
11
12

CREATE TABLE rcx (
  a INT,
  b INT,
  c CHAR(3),
  d INT
) Engine=InnoDB
PARTITION BY RANGE COLUMNS(a,d,c) (
  PARTITION p0 VALUES LESS THAN (5,10,'ggg'),
  PARTITION p1 VALUES LESS THAN (10,20,'mmmm'),
  PARTITION p2 VALUES LESS THAN (15,30,'sss'),
  PARTITION p3 VALUES LESS THAN (MAXVALUE,MAXVALUE,MAXVALUE)
);

MySQL 5.5 开始支持 COLUMNS 分区，对于之前的 RANGE 和 LIST 分区，用户可以用 RANGE COLUMNS 和 LIST COLUMNS 分区进行很好的代替。

子分区

子分区（subpartitioning）是在分区的基础上再进行分区，有时也称这种分区为复合分区（composite partitioning）。MySQL 数据库允许在 RANGE 和 LIST 的分区上再进行 HASH 或 KEY 的子分区，如：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE ts (a INT, b DATE) ENGINE=InnoDB
 -> PARTITION BY RANGE (YEAR(b))
 -> SUBPARTITION BY HASH (TO_DAYS(b))
 -> SUBPARTITIONS 2 (
   -> PARTITION p0 VALUES LESS THAN (1990),
   -> PARTITION p1 VALUES LESS THAN (2000),
   -> PARTITION p2 VALUES LESS THAN MAXVALUE
 );
Query OK, 0 rows affected (0.01 sec)

表 ts 被 范围分区成 p0、p1、p2；

每个主分区又被 子分区（HASH） 成两个子分区，比如 p0 变成：p0sp0、p0sp1；

最终形成了 3（主分区） × 2（子分区） = 6 个物理分区。

子分区的建立需要注意以下几个问题：

• 每个子分区的数量必须相同。
• 要在一个分区表的任何分区上使用 SUBPARTITION 来明确定义任何子分区，就必须定义所有的子分区。
• 每个 SUBPARTITION 子句必须包括子分区的一个名字。
• 子分区的名字必须是唯一的。

子分区可以用于特别大的表，在多个磁盘间分别分配数据和索引。MySQL 本身并不直接支持通过语法控制每个分区或子分区映射到哪个磁盘路径，但你可以通过以下方式间接实现这一点：

操作方法一：使用多个表空间 + DATA DIRECTORY 和 INDEX DIRECTORY

MyISAM 引擎可以使用如下方式手动指定每个分区/子分区存放的目录（通常每个目录挂载不同磁盘）：

1
2
3
4
5
6
7
8
9
10
11
12

CREATE TABLE big_table (
  id INT,
  name VARCHAR(100)
)
ENGINE = MyISAM
PARTITION BY HASH(id)
PARTITIONS 6 (
  PARTITION p0 DATA DIRECTORY = '/disk0/data' INDEX DIRECTORY = '/disk0/index',
  PARTITION p1 DATA DIRECTORY = '/disk1/data' INDEX DIRECTORY = '/disk1/index',
  ...
  PARTITION p5 DATA DIRECTORY = '/disk5/data' INDEX DIRECTORY = '/disk5/index'
);

⚠️ 仅支持 MyISAM，不支持 InnoDB。并且要求 innodb_file_per_table=OFF，否则无效。

操作方法二：使用 Linux 下的软链接（适用于 InnoDB）

虽然 InnoDB 不支持 DATA DIRECTORY 语法，但可以使用 软链接 将分区/子分区文件（.ibd）手动移动到不同磁盘，如：

步骤：

一、创建分区表（比如在 /var/lib/mysql 中）：

1
2
3
4
5
6
7
8

CREATE TABLE big_partition (
  id INT,
  dt DATE
) ENGINE=InnoDB
PARTITION BY RANGE (YEAR(dt)) (
  PARTITION p0 VALUES LESS THAN (2020),
  PARTITION p1 VALUES LESS THAN (2025)
);

二、关闭 MySQL 服务

移动分区数据文件到其他磁盘目录

1
2
3

mv /var/lib/mysql/db/big_partition#P#p0.ibd /disk0/big_partition#P#p0.ibd

ln -s /disk0/big_partition#P#p0.ibd /var/lib/mysql/db/big_partition#P#p0.ibd

三、重启 MySQL 服务

⚠️ 你必须启用 innodb_file_per_table=1 且使用独立表空间

操作方法三：使用 LVM 或 RAID 逻辑卷

将多个磁盘组合成一个逻辑卷，然后整个 MySQL 数据目录或表空间都部署在这个卷上，由底层逻辑卷管理器决定调度和负载均衡，对 MySQL 透明。

分区中的 NULL 值

MySQL 数据库允许对 NULL 值做分区，但是处理的方法与其他数据库可能完全不同。MySQL 数据库的分区是视 NULL 值小于任何一个非 NULL 值，这和 MySQL 数据库中处理 NULL 值的 ORDER BY 操作是一样的。因此对于不同的分区类型，MySQL 数据库对于 NULL 值的处理也是各不相同。

对于 RANGE 分区，如果向分区列插入了 NULL 值，则 MySQL 数据库会将该值放入最左边的分区。例如：

1
2
3
4
5
6
7
8
9

mysql> CREATE TABLE t_range(
  a INT,
  b INT) ENGINE=InnoDB
  PARTITION BY RANGE(b)(
    PARTITION p0 VALUES LESS THAN (10),
    PARTITION p1 VALUES LESS THAN (20),
    PARTITION p2 VALUES LESS THAN MAXVALUE
  );
Query OK, 0 rows affected (0.01 sec)

接着向表中插入 (1,1)、(1,NULL) 两条数据，并观察每个分区中记录的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

mysql> INSERT INTO t_range SELECT 1,1;
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO t_range SELECT 1,NULL;
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM t_range\G;
*************************** 1. row ***************************
a: 1
b: 1
*************************** 2. row ***************************
a: 1
b: NULL
2 rows in set (0.00 sec)

可以看到两条数据都放入了 p0 分区，也就是说在 RANGE 分区下，NULL 值会放入最左边的分区中。另外需要注意的是，如果删除 p0 这个分区，删除的将是小于 10 的记录，并且还有 NULL 值的记录，这点非常重要：

1
2
3
4
5
6

mysql> ALTER TABLE t_range DROP PARTITION p0;
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0

mysql> SELECT * FROM t_range;
Empty set (0.00 sec)

在 LIST 分区下要使用 NULL 值，则必须显式地指出哪个分区中放入 NULL 值，否则会报错，如：

1
2
3
4
5
6
7
8
9
10
11

mysql> CREATE TABLE t_list(
  -> a INT,
  -> b INT) ENGINE=INNODB
 -> PARTITION BY LIST(b)(
   -> PARTITION p0 VALUES IN (1,3,5,7,9),
   -> PARTITION p1 VALUES IN (0,2,4,6,8)
 );
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_list SELECT 1, NULL;
ERROR 1526 (HY000): Table has no partition for value NULL

若 p0 分区允许 NULL 值，则插入不会报错：

1
2
3
4
5
6
7
8
9
10
11
12

mysql> CREATE TABLE t_list(
  -> a INT,
  -> b INT) ENGINE=INNODB
 -> PARTITION BY LIST(b)(
   -> PARTITION p0 VALUES IN (1,3,5,7,9,NULL),
   -> PARTITION p1 VALUES IN (0,2,4,6,8)
 );
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_list SELECT 1, NULL;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0

HASH 和 KEY 分区对于 NULL 的处理方式和 RANGE 分区、LIST 分区不一样。任何分区函数都会将含有 NULL 值的记录返回值为 0。例如：

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

mysql> CREATE TABLE t_hash(
  -> a INT,
  -> b INT) ENGINE=InnoDB
 -> PARTITION BY HASH(b)
 -> PARTITIONS 4;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO t_hash SELECT 1,0;
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO t_hash SELECT 1,NULL;
Query OK, 1 row affected (0.01 sec)

mysql> SELECT table_name, partition_name, table_rows
  -> FROM information_schema.PARTITIONS
  -> WHERE table_schema=DATABASE() AND table_name='t_hash'\G;
*************************** 1. row ***************************
table_name: t_hash
partition_name: p0
table_rows: 2
*************************** 2. row ***************************
table_name: t_hash
partition_name: p1
table_rows: 0
*************************** 3. row ***************************
table_name: t_hash
partition_name: p2
table_rows: 0
*************************** 4. row ***************************
table_name: t_hash
partition_name: p3
table_rows: 0
4 rows in set (0.00 sec)

分区和性能

我们常听到开发人员说“对表做个分区”，然后数据库的查询就会快了。这是真的么？实际上可能根本感受不到查询速度的提升，甚至会发现查询速度会明显下降。因此，若要合理使用分区之前，必须了解分区的使用环境。

数据库的应用大致分为两类：一类是 OLTP（在线事务处理），如 Blog、电子商务、网络游戏等；另一类是 OLAP（在线分析处理），如数据仓库、数据挖掘。在一个实际的应用环境中，可能看上去属于 OLTP 的应用，也有 OLAP 的应用。例如游戏平台，玩家操作的数据游戏数据库应用属 OLTP 的，但游戏平台厂商可能需要对玩家产生的日志进行分析，通过分析得到的结果来更好地服务于游戏，预测玩家的行为等，而这却是 OLAP 的应用。

对于 OLAP 的应用，分区的确是可以很好地提高查询的性能，因为 OLAP 应用大多数查询需要频繁地扫描一张很大的表。假设有一张 1 亿行的表，其中有一个时间戳属性列，用户的查询需要从这张表中获取一年的数据。如果按照时间戳进行分区，则只需要扫描相应的区即可，这就是前面介绍的 Partition Pruning 技术。

但对于 OLTP 的应用，分区这时就会小心。在这种应用下，通常不可能会去获取一张大表中 10% 的数据，大家的查询是通过索引定位几条记录即回，而根据 B+ 树结构的原理可知，对于一张大表，一般的 B+ 树需要 2～3 次的磁盘 IO。因此 B+ 树可以很好地完成检索，不需要分区的帮助，并且设计不好的分区会带来严重的性能问题。

我发现很多开发团队会认为含有 1000W 行的表是一张非常巨大的表，所以他们往往会选择采用分区，如对主键做 10 个 HASH 的分区，这样每个分区就只有 100W 的数据；同时他们应该这样更快了，SELECT * FROM t WHERE pk=@pk。但他们没有考虑过这样一种情况：100W 和 1000W 行的数据本身构成的 B+ 树的层级是一样的，而查找都是 2 层。那么上述主键分区的索引并不会带来性能的提升。好吧，如果 1000W 的 B+ 树的高度是 3，100W 的 B+ 树的高度是 2，那么上述主键分区的索引可以避免 1 次 IO，从而提高查询的效率。这没问题，但是张表只有主键索引，没有任何其他的列需要建立查询的。如果还有这样的 SQL 语句：SELECT * FROM TABLE WHERE KEY=@key，这时对于 KEY 的查询要扫描所有的 10 个分区，即使每个分区的查询开销为 2 次 IO，则一共需要 20 次 IO。而对于原来单表的设计，对于 KEY 的整查询只需要 2～3 次 IO。

接着来看如下的表 Profile，根据主键 ID 进行了 HASH 分区，HASH 分区的数据为 10，表 Profile 有接近 1000W 的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

mysql> CREATE TABLE `Profile` (
  -> `id` int(11) NOT NULL AUTO_INCREMENT,
  -> `nickname` varchar(20) NOT NULL DEFAULT '',
  -> `password` varchar(32) NOT NULL DEFAULT '',
  -> `sex` char(1) NOT NULL DEFAULT '',
  -> `rdate` date NOT NULL DEFAULT '0000-00-00',
  -> PRIMARY KEY (`id`),
  -> KEY `nickname` (`nickname`)
  -> ) ENGINE=InnoDB
 -> PARTITION BY HASH (id)
 -> PARTITIONS 10;
Query OK, 0 rows affected (1.29 sec)

mysql> SELECT COUNT(nickname) FROM Profile;
*************************** 1. row ***************************
count(1): 9999248
1 row in set (1 min 24.62 sec)

因为是根据 HASH 分区的，所以每个区分的记录数大致是相同的，即数据分布比较均匀：

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
41
42
43
44

mysql> SELECT table_name, partition_name, table_rows
  -> FROM information_schema.PARTITIONS
  -> WHERE table_schema=DATABASE() AND table_name='Profile'\G;
*************************** 1. row ***************************
table_name: Profile
partition_name: p0
table_rows: 990703
*************************** 2. row ***************************
table_name: Profile
partition_name: p1
table_rows: 1086519
*************************** 3. row ***************************
table_name: Profile
partition_name: p2
table_rows: 976474
*************************** 4. row ***************************
table_name: Profile
partition_name: p3
table_rows: 986937
*************************** 5. row ***************************
table_name: Profile
partition_name: p4
table_rows: 993667
*************************** 6. row ***************************
table_name: Profile
partition_name: p5
table_rows: 978046
*************************** 7. row ***************************
table_name: Profile
partition_name: p6
table_rows: 990703
*************************** 8. row ***************************
table_name: Profile
partition_name: p7
table_rows: 978639
*************************** 9. row ***************************
table_name: Profile
partition_name: p8
table_rows: 1085334
*************************** 10. row ***************************
table_name: Profile
partition_name: p9
table_rows: 982788
10 rows in set (0.80 sec)