Docker Desktop - Unexpected WSL error，搜索半天解决方案，结果是没开 Windows Hypervisor Platform，解决方案在此。shell，它不支持方向键，我们可以使用 bash 来解决问题，解决方案。build 构建项目时，报错 $'\r': command not found，这是 Windows 的换行符和 Linux 不同导致的。为了避免在 clone 时进行换行符的转换，可以添加 autocrlf=false 到全局配置文件，或者可以在克隆的命令中添加该参数，更多详细的设置方法可以参考 GitHub 文档。参考《高性能 MySQL》和官方文档。使用 MySQL 的 Sakila 示例数据库，使用 MySQL 版本 8.0.41 + InnoDB 存储引擎。各种术语的官方定义可以看 MySQL 术语表，锁相关的内容可以看 InnoDB Locking，更多数据库概念可以看 CUM 15-445 课程总结。任何描述都是简化的，不会涵盖所有情况，更多细节只能看文档。或者说没有必要去记细节，任何细节都取决于实现，而实现会随着版本更新而变化，需要学习的是整体的策略。
快照（snapshot）：数据在特定时间的表示。一致性读（consistent read）：根据快照显示查询结果，也被称为一致性非锁定读。在读已提交和可重复读隔离级别下执行 SELECT 语句的默认模式是一致性读，也就是说会使用多版本并发控制（MVCC）读取数据。读已提交在每次执行一致性读时都会重置快照，而可重复读只在第一次一致性读时建立快照。锁定读（locking read）：使用 SELECT ... FOR SHARE 或者 SELECT ... FOR UPDATE 读取数据，会加读锁或者写锁，在事务提交或者回滚时释放（2PL）。
MVCC 是使用撤销日志（Undo Log）和读取视图（Read View）实现的。事务在修改记录之后会记录撤销日志，事务的回滚指针会指向该日志。读取视图包含一致性读不可见的事务 ID（事务 ID 不会在启动事务之后立即分配），读取记录时会比较记录的事务 ID 和读取视图，如果该记录对当前事务不可见，则执行撤销日志直到达到可见状态。删除操作被视为修改操作，通过修改删除标志位实现，只有当该版本记录对所有事务不可见时，才会被真正删除。撤销日志也会被记录到重做日志（Redo Log）中，实现崩溃恢复。
关于幻读的问题：DML 语句可以破坏快照，从而在可重复读隔离级别会出现幻读。（参考一致性读文档）如果将快照读和当前读混用，也会出现幻读。
1 | SELECT COUNT(c1) FROM t1 WHERE c1 = 'xyz'; |
1 | SHOW FULL PROCESSLIST; |
使用前缀索引可以减少索引的空间开销，内部节点的字符串比较会更高效，但是选择性会更低，那么匹配的主键会更多，从而需要更多次回表。所以需要选择合适的前缀长度，尽可能提高索引的选择性。索引的选择性是指不重复的索引值（基数，cardinality）和数据表的记录总数的比值。无法利用前缀索引执行分组、排序和覆盖索引扫描。
执行如下语句，city_demo 最终有 19200 条记录。
1 | CREATE TABLE city_demo(city VARCHAR(50) NOT NULL); |
查询出现次数最多的前 10 个城市，然后使用各种前缀测试索引的选择性。前缀长度为 7 比较合适，因为统计数量的偏差不算很大。
1 | SELECT COUNT(*) AS c, city |
不能只根据前缀索引选择性的值确定前缀长度，例如前缀长度为 5 的选择性看上去很接近完整列的选择性，但是如果查看出现次数最多的前 10 个城市，和完整列的结果相比，会发现数据分布很不均匀。如果查询以 South 前缀的某个城市，那么回表的次数会更多。
1 | SELECT COUNT(DISTINCT city) / COUNT(*) AS sel, |
在 film_actor 上有主键索引 PRIMARY KEY (actor_id,film_id)，有普通索引 KEY idx_fk_film_id (film_id)，以下查询计划表示合并两个索引的查询结果。索引合并策略有时效果不错，但更多时候表明表的索引建得很槽糕。如果优化器需要对多个索引做相交操作（由于多个 AND 条件），那么查看是否可以使用多列索引进行优化。
如果优化器需要对多个索引做联合操作（由于多个 OR 条件），且索引的选择性不高时，通常会在缓存、排序和合并上消耗大量 CPU 和内存资源。然而，优化器不会将这些操作计算到查询成本中，优化器只关心随机页面读取，所以有时索引合并的性能还不如全表扫描。这还会影响并发的查询，此时使用 UNION 改写，将单个查询拆分为多个查询，可以避免单个查询的执行时间过长，影响其他并发的查询（由于 2PL 协议，单个查询会在提交时才释放锁，当然不同隔离级别有细微差别）。
1 | EXPLAIN SELECT film_id, actor_id FROM film_actor |
聚簇索引的每个叶子节点都包含主键值、事务 ID、用于事务和 MVCC 的回滚指针，以及所有的剩余列。二级索引的叶子节点存储主键值而不是物理指针，所以在移动主键索引中的记录时不需要修改二级索引。如果按照主键顺序插入行，聚簇索引不会发生页分裂，从而插入性能更高（减少磁盘 I/O）也不会产生内部碎片。不应该使用随机的主键（例如 UUID），如果没有按照主键顺序插入数据，可以使用 OPTIMIZE TABLE 命令重新组织表来消除内部碎片。
对于高并发负载，按主键顺序插入会产生较多竞争，可以通过更改 innodb_autoinc_lock_mode 配置来提升性能。简单来说，有传统、连续和交错三种锁定模式，不同模式会根据语句的不同使用互斥锁（Lock）或者轻量级锁（CAS）。
可以根据慢查询日志来优化查询，使用 EXPLAIN 查看执行计划。基本准则：只选择需要的列，而不是使用 SELECT *，从而允许覆盖索引优化、减少时间（I/O）和空间开销。不要重复执行相同的查询，可以在应用层使用缓存。对于不是很重要的查询，可以将大查询分解为小查询，将查询的时间分散到一个时间段中，减少查询对服务器性能的影响（减少单次查询持有锁的时间，以及避免事务日志堆积）。例如：DELETE 大量数据，可以使用 LIMIT 分解执行；当中间查询结果能缓存和重用时，可以将连接查询分解，然后在应用层做连接。
应用 WHERE 条件的方式：① 将条件从服务器下推到存储引擎，直接在索引中使用条件过滤记录（索引条件下推，ICP），从而减少服务器访问存储引擎的次数，以及存储引擎访问基表的次数。② 使用覆盖索引获取记录（不需要回表），然后在服务器使用条件过滤记录。③ 回表之后，在服务器层使用条件。
MySQL 的局限性：无法将 UNION 外层的条件下推到内层。某些时候，等值传递会有问题（详细看书）。针对单个语句而言，无法利用多核并行执行查询，无法同时对某个表进行查询和更新（特指相关子查询）。
由于 UNION 查询无法使用到外层条件，所以需要手动将条件下推到 UNION 的各个子查询中。最好使用 UNION ALL 而不是 UNION，这样可以避免对临时表去重（UNION 查询总是会创建临时表）。
COUNT(*) 统计行数，COUNT(expr) 统计非 NULL 值的数量。性能 COUNT(*)=COUNT(1)>COUNT(主键列)>COUNT(普通列)，如下所示 COUNT(*) 实际上是 COUNT(0)。根据条件统计数量，可以使用 SUM(IF(expr, 1, 0)) 或者 COUNT(expr OR NULL)。如果允许使用近似值代替精确值，则可以去掉 WHERE 和 DISTINCT 之类的条件，优化查询性能。利用索引覆盖扫描优化性能，因为索引会比基表更小，减少 I/O 次数。
1 | mysql> EXPLAIN SELECT COUNT(*) FROM film\G |
常见的说法是，在子查询数据较少时使用 IN，而在子查询数据较大时使用 EXIST。因为使用 IN 是不相关子查询，会创建临时表，然后在临时表中查找匹配的数据。而使用 EXIST 是相关子查询，会直接在内表中查找匹配的数据（多次执行子查询）。但是，实际上优化器会做优化，使用 IN 并不意味着就会创建临时表。下面查询所有没有交易记录的顾客信息，执行计划显示该查询被转化为相关子查询，会使用覆盖索引查找匹配的数据。（推荐阅读 Optimizing Subqueries with the EXISTS Strategy）
1 | mysql> EXPLAIN SELECT * FROM customer WHERE customer_id IN ( |
而使用 EXIST 也不意味着执行相关子查询，如果将 payment 中的索引 idx_fk_customer_id 删除，然后重新执行上述查询。执行计划显示，子查询会生成索引临时表，索引用于去重，然后外表使用该索引查找匹配的数据。如果临时表较小，则会使用 MEMORY 存储引擎创建内存临时表，否则使用 InnoDB 存储引擎创建磁盘临时表。（推荐阅读 Optimizing Subqueries with Materialization）
1 | ALTER TABLE payment DROP FOREIGN KEY fk_payment_customer, DROP INDEX idx_fk_customer_id; |
1 | mysql> EXPLAIN SELECT * FROM customer WHERE EXISTS ( |
确保 ON 或者 USING 的列上有索引。确保 GROUP BY 和 ORDER BY 只涉及一个表中的列，从而允许利用索引优化（松散/紧密索引扫描、利用索引排序）。如果需要对聚合的结果做超级聚合，可以使用 GROUP BY xxx WITH ROLLUP（注意查看查询计划，确定是否有性能问题），也可以使用其他等价语句或者在应用层聚合。
上面执行 SHOW WARNINGS\G 都会显示半连接（semi join），所谓半连接就是从左表中查询和右表匹配的行。反连接（anti join）正好相反，从左表中查询和右表不匹配的行。下面的查询和上面的等价，但是更慢，没有使用半连接，在覆盖索引中使用 LIMIT 1 去重，在最后使用临时表去重（实际上没有必要，LIMIT 1 已经去重）。（推荐阅读 Optimizing IN and EXISTS Subquery Predicates with Semijoin and Antijoin Transformations）
1 | mysql> EXPLAIN SELECT DISTINCT customer.* FROM customer INNER JOIN payment USING(customer_id)\G |
如果偏移量很大，例如 LIMIT 10000, 20，那么会扫描 10020 条记录，而只有最后 20 条是有效的。如果行中有很多数据，那么 I/O 次数就会很多。MySQL 的 LIMIT OFFSET 似乎不会下推到索引，从而 10020 条记录都会回表查询。查询计划中确实没有下推，奇怪的是索引只会扫描 10020 条记录，说明索引是有 LIMIT OFFSET 信息的。（参考 Limit Offset 下推）
优化方式：① 使用覆盖索引执行 LIMIT，索引中只包含必要的列（如 ORDER BY 的列，当然默认包含主键），那么 LIMIT 扫描的数据会减少很多，最后使用主键做连接得到完整数据。（不能使用 IN，因为 ERROR 1235 (42000): This version of MySQL doesn't yet support 'LIMIT & IN/ALL/ANY/SOME subquery'）② 如果只允许顺序翻页的话，通过记录上个页面的边界值，下次查询就可以使用该值定位到目标位置，而不会做无效的扫描。③ 一次性获取多页数据，在应用层缓存起来（类似缓存 I/O）。④ 其他方法，使用预先计算的汇总表，或者使用冗余表。
1 | mysql> EXPLAIN ANALYZE SELECT * FROM payment ORDER BY customer_id LIMIT 10000, 20\G |
从文本文件读取数据，num 列有 100 万个 1、100 万个 2 和 1 个 3，测试一下 NOT IN (1, 2) 是否会使用索引。EXPLAIN ANALYZE 的结果显示，查询被分为三个区间，这样就可以利用索引范围扫描。（推荐阅读 Optimizing INSERT Statements，MySQL EXPLAIN ANALYZE，A must-know about NOT IN in SQL - more antijoin optimization）。
1 | SET @@GLOBAL.local_infile = 1; |
参考 官方文档，对象编码，数据类型，命令列表，代码仓库（7.4.2），事务，可编程性，《Redis 设计与实现》。
Redis 服务器是事件驱动程序，主要使用单线程 + I/O 多路复用处理客户端请求。不过也会使用后台线程，例如，使用 UNLINK 命令可以异步删除大键（Redis 4.0），以及将网络 I/O 委托给其他线程来提高性能（Redis 6.0）。Redis 的瓶颈在内存和网络，CPU 很少成为 Redis 的瓶颈，而且由于多线程的复杂性，Redis 核心逻辑没有使用多线程设计。如果要提高 CPU 的利用率，可以在同一个机器中启动多个 Redis 实例，并将它们视为不同的服务器。
过期删除策略：定时删除会将 CPU 时间用在和当前任务无关的过期键上，影响服务器的响应时间。惰性删除检查当前处理的键是否过期，如果不对过期键执行命令就会导致内存泄露。定期删除结合前两种策略的优点，是时间和空间的折中。Redis 使用惰性删除 + 定期删除的策略，定期删除从一定数量的数据库中随机检查一定数量的键，如果过期就删除。
Key 淘汰策略：配置 maxmemory 来指定使用内存的上限，当超过该限制时会执行淘汰策略。概括一下：① 不淘汰键，此时只支持读命令，写命令会报错。② 使用 LRU、LFU 或者随机淘汰键。③ 使用 LRU、LFU 或者随机淘汰有过期时间的键，或者淘汰 TTL 最短的键。
Redis 使用的是近似 LRU，随机抽取少量的键，然后淘汰其中最久未被访问的键（Redis 3.0 会跟踪候选键来提高性能），不使用标准 LRU 的原因是会消耗更多内存（因为需要维护访问链表）。LFU 使用概率计数器（Morris 计数器）估计键的访问频率，结合衰减期以便计数器随时间减少，也使用上述采样方式淘汰访问频率最小的键。
1 | SELECT index |
在 Redis 中，当无需修改字符串时，使用的是 C 字符串。否则，使用简单动态字符串（simple dynamic string，SDS）。相比 C 字符串有如下优点：① 获取长度的时间复杂度为 \(O(1)\)。② 自动扩容，空间预分配，不会自动缩容，但支持手动缩容。③ 二进制安全，不根据 \0 空字符判断字符串结束。
1 | struct __attribute__ ((__packed__)) hisdshdr8 { |
ziplist 是特殊编码的双向链表，非常节省内存。它存储字符串和整数值，其中整数被编码为实际整数，而不是一系列的字符。它允许在列表的任意一侧进行 push 和 pop 操作，该操作需要重新分配内存（realloc + memmove），时间复杂度和列表使用的内存量相关。
ziplist 的布局如下，<uint32_t zlbytes> 表示列表占用的字节数，<uint32_t zltail> 表示列表最后一个节点的偏移量，<uint16_t zllen> 表示列表中的节点数量（当节点数量超过 \(2^{16}-2\) 时，该值被设置为 \(2^{16}-1\)，此时需要遍历整个列表才能知道有多少节点），<uint8_t zlend> 是列表的结束标识（被设置为 0xFF）。
1 | <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> |
entry 的布局如下，<prevlen> 表示前一个节点的长度（如果小于 254 字节，则占用单个字节，否则占用 5 个字节，第一个字节被设置为 0xFE，后四个字节表示长度），<encoding> 和 <entry-data> 的编码方式取决于节点的内容。添加/删除节点可能引发级联更新（Cascade Update），不过新版 Redis 会提前计算所需空间，时间复杂度是 \(O(n)\)。
1 | <prevlen> <encoding> <entry-data> |
由于经常发生和 ziplist 的代码相关的崩溃报告，而 ziplist 实现复杂（主要源于级联更新）难以审计，所以对 ziplist 进行改进。listpack 的实现更紧凑、解析速度更快以及更易于审计和理解。listpack 的布局如下，由于没有使用偏移量，头部只占用 6 字节（ziplist 头部占用 10 字节）。依然使用 0xFF 单个字节作为结束标识，原因是这样可以很容易地识别列表的结束，而不需要额外保存末尾地址。由于没有使用偏移量，要快速定位最后一个元素实现反向遍历，很容易想到倒着存储元素的长度信息，element 的布局如下。
1 | <tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte> |
quicklist 是以 ziplist 或者 listpack 为节点的双向链表，结合 linkedlist 插入/删除快速以及 ziplist/listpack 节省空间的特点。
inset 存储整数集合（不包含重复项），按照从小到大的顺序存储在 contents 数组中。所有元素的编码方式取决于 encoding 字段，可以将元素编码为 16、32 和 64 字节。如果当前编码方式无法存储新元素，则会将所有元素的编码方式都升级为更大的类型（不会自动降级）。因为引发升级的元素总是比现有元素都小/大，所以该新元素会存放到列表开头/结尾。
1 | typedef struct intset { |
ht_table 表示两个哈希表，一般只使用 ht_table[0]，而 ht_table[1] 在扩容/缩容时使用。哈希表的大小是 2 的幂，扩容的大小为第一个大于等于 ht_used[0] * 2 的 \(2^{n}\)，缩容的大小为第一个大于等于 ht_used[0] 的 \(2^{n}\)。扩容/缩容是渐进式的，在每次对哈希表执行操作时，会 rehash 一个桶（由 rehashidx 标识）。
扩容的时机：当没有在执行 BGSAVE 或者 BGREWRITEAOF 命令且负载因子大于等于 1，当在执行 BGSAVE 或者 BGREWRITEAOF 命令且负载因子大于等于 5。因为在持久化时会创建子进程，操作系统使用写时复制（COW）优化子进程的使用，所以如果存在子进程，服务器会尽可能避免扩容（避免修改共享的页面），从而避免写时复制的开销。缩容的时机：当负载因子小于 0.1 时自动缩容。
1 | struct dictEntry { |
skiplist 使用 zset 结构作为底层实现，由跳表和哈希表组成。跳表维护多层链表，支持正序/倒序遍历，节点负责存储字符串元素 ele 和浮点数分值 score，同时会维护该节点在各层中的下一个节点的跨度 span（用于快速计算排名）。程序根据幂次定律生成节点的层数，节点层高为 k 层的概率是 (1 - ZSKIPLIST_P) * (ZSKIPLIST_P) ^ (k - 1)（其中 ZSKIPLIST_P = 0.25）。 使用跳表可以提高 ZRANGE 和 ZRANK 的效率，使用哈希表可以提高根据字符串查找分值的效率。
1 | /* ZSETs use a specialized version of Skiplists */ |
1 | struct redisObject { |
使用场景：存储字节序列（文本、序列化对象和二进制数组）或者充当计数器。默认最大可以存储 512 MB 的字符串。编码方式：① int，在保存 64 位有符号整数时使用，可以看作 Java 中的 long 类型。② embstr（embedded string），默认在字符串长度小于等于 44 字节时使用，该编码将 redisObject 和 sdshdr 存储在单个内存块中，不可修改。③ raw，该编码将 redisObject 和 sdshdr 存储在不同内存块中。
1 | SET key value [NX | XX] [EX seconds | PX milliseconds] |
使用场景：实现栈和队列。最多可以存储 \(2^{32}-1\) 个元素。编码方式：ziplist | listpack，linkedlist，quicklist。
1 | [LPUSH | RPUSH] key element [element ...] |
使用场景：存储唯一值，计算交集、并集和差集。最多可以存储 \(2^{32}-1\) 个元素。编码方式：intset，listpack，hashtable（值被设置为 NULL）。
1 | SADD key member [member ...] |
使用场景：存储键值对（对象）。最多可以存储 \(2^{32}-1\) 个键值对。编码方式：ziplist | listpack，hashtable。
1 | HSET key field value [field value ...] | HSETNX key field value |
使用场景：排行榜、速率限制器。首先按照分数排序（浮点数），然后按照字典序排序（元素都是字符串）。编码方式：ziplist | listpack，skiplist。
1 | ZADD key [NX | XX] [GT | LT] score member [score member ...] |
持久化机制：① RDB（Redis Database），以指定的时间间隔创建数据的快照。② AOF（Append Only File），记录所有写命令。（不建议单独使用 AOF）③ No persistence，不持久化。④ RDB + AOF：组合使用 RDB 和 AOF。
相比 AOF，RDB 文件表示更紧凑，允许更快地重启（就是使用快照恢复数据）。而 AOF 文件会更大，Redis 会自动重写 AOF 来减少文件大小。在发生故障时 RDB 会丢失更多数据（因为是指定时间间隔持久化），而 AOF 默认每秒执行 fsync（也可以配置为不执行 fsync，让操作系统决定何时刷盘，或者每次查询都执行，但是会很慢），最多丢失一秒的数据。如果数据很大 fork 会占用 CPU 从而阻塞客户端命令，RDB 相比 AOF 执行 fork 的频率更高（RDB 必然会执行 fork，AOF 只有在重写时执行 fork）。
重写是根据当前数据记录写命令，而不是根据旧的 AOF 文件。在 Reids 7.0 之前，重写期间到达的所有写命令最终会写入磁盘两次，因为重写 AOF 的同时 AOF 操作也依然在执行（保证数据安全），所以写命令会写入旧文件，然后还会使用缓冲区记录写命令，等待 AOF 重写完成之后将其追加到新文件。在 Redis 7.0 之后，使用 Multi Part AOF 机制，AOF 文件被分为基本文件（最多一个）和增量文件（可能有多个）。基本文件表示重写 AOF 时的数据快照（RDB 或 AOF 格式），增量文件记录创建基本文件之后的增量更改。Redis 使用临时清单文件跟踪基本文件和增量文件，当 AOF 重写完成，Redis 执行原子切换使改临时清单文件生效。
缓存穿透：频繁请求数据库中不存在的数据。解决方案：① 用户权限和参数校验，提前过滤无效请求。② 将无效键加入缓存同时设置较短的过期时间（区分无效值和正常空值），如果之后数据库中有相关数据，会导致短时间的不一致。或者可以在更新数据时删除缓存，从而保证一致性。③ 使用布隆过滤器（定期重建），一种概率数据结构，由一个位数组和多个哈希函数组成。插入元素会将所有哈希函数计算的索引位置置为 1。查询元素只要有一个计算出的索引位置不为 1，那么该元素就必定不在集合中。否则，有可能在集合中（由于哈希冲突，存在误报）。
缓存击穿：热点数据过期。解决方案：① 访问热点数据的同时重置过期时间。② 发现缓存失效时，加锁重建缓存，避免所有请求都查询数据库。其他线程会尝试加锁（使用 trylock，因为缓存重建完成之后就不需要互斥），失败之后休眠一段时间再查询缓存。③ 逻辑过期，不设置 TTL，而是在值中增加过期时间字段。如果查询缓存发现已经逻辑过期，依然加锁重建缓存，但是加锁失败的线程直接返回过期数据。
缓存雪崩：大量数据过期。解决方案：① 设计随机的过期时间（类似 Raft 里的随机选举超时），避免同时过期。
通用方案：① 缓存预热、多级缓存。② 为缓存业务添加限流（可以整体限流也可以根据用户 ID 限流）、降级（简化响应，保证核心功能稳定）和熔断（拒绝请求，防止故障扩散）策略。限流策略：固定窗口，对时间窗口内的请求计数，但是窗口切换时存在双倍流量的问题；滑动窗口，将窗口分为细粒度的时间片做计数，通过计算窗口内所有时间片计数的和来判断是否达到流量阈值，内存开销较大；漏桶算法，将请求放入桶中（排队），以恒定速率处理请求，不能处理突发流量；令牌桶算法，将令牌放入桶中（计数），以恒定的速率生成令牌，允许突发流量。③ 使用 Redis 集群提高服务可用性。
缓存一致性问题：① 更新数据不处理缓存，存在不一致的问题。② 更新数据时删除缓存。如果事务提交之后删除缓存，假设另一个请求已经读取到旧数据，但直到很久之后才设置缓存，也会存在不一致（可以延迟双删）。之所以删除缓存而不是更新缓存，是因为如果同时有多个请求更新相同的数据，更新缓存会有时序问题。③ 订阅 MySQL binlog（阿里 canal 组件，利用主从节点的日志复制），解析日志然后利用消息队列更新缓存（适合数据不过期的场景）。
使用 SET 命令获取分布式锁：① 设置过期时间，避免客户端宕机导致锁无法被释放。② 设置锁的持有者，在释放锁（删除键）时检查当前客户端是否持有锁，如果持有才执行释放操作（使用 Lua 脚本保证原子性）。避免客户端 A 持有的锁过期之后，释放客户端 B 持有的锁。③ 使用 Lua 脚本原子地执行 CAS 操作来解锁。
1 | SET lock owner NX EX max-lock-time |
1 | if redis.call("get",KEYS[1]) == ARGV[1] |