soyo的跨机房部署、同城双活、异地多活、9个9高可用博客yuque笔记同步site

SELECT * FROM users ORDER BY id LIMIT 10, 20;

从偏移量为10开始，返回20行记录，即第11到第30行记录

如果是limit 20000000 10，那会把前两千万条数据查出来，然后丢弃，然后从第20000001行开始返回10行，性能极低，这就是深度分页问题

深度分页优化：

可以把每次查询到的最大id记录下来，下次从这个id开始继续查：

SELECT * FROM users WHERE id > last_max_id ORDER BY id LIMIT 10;

但这种方案不能往回查，只能一页一页往后查，且查询过程中不能有新增

id不能重复，不然就会陷入死循环，比如一页的10条，ID全是12，last_max_id也为12，那么下一页的查询还是>= 12

覆盖索引 + 子查询：

SELECT * FROM users WHERE id > (SELECT id FROM users ORDER BY id LIMIT 20000000, 1) ORDER BY id LIMIT 10;

子查询在主键索引上查询，不需要回表，得到第20000001的id，然后主查询根据id进行范围查询

使用ES，ES也有深分页问题，但影响比MySQL小点

【【IT老齐074】从76237到753毫秒,海量数据大页码MySQL查询该如何优化？】https://www.bilibili.com/video/BV1PL411g7Vj?vd_source=cae07b1dce3e6abe67fcf72c43031ede

产品上解决问题：

旧表拆分为分库分表过程：

1. 双写读老阶段：通过中间件，对write sql同时进行两次转发，也就是双写，保持新数据一致，同时开始历史数据拷贝。本阶段建议施行一周；
2. 双写双读阶段：采用灰度策略，一部分流量读老表，一部分流量读新表，读新表的部分在一开始，还可以同时多读一次老表数据，进行比对检查，观察无误后，随着时间慢慢切量到新表。本阶段建议施行至少两周；
3. 双写读新阶段：此时基本已经稳定，可以只读新表，为了安全保证，建议还是多双写一段时间，防止有问题遗漏。本阶段建议周期一个月；
4. 写新读新阶段：此时已经完成了分表的迁移，老表数据可以做个冷备

MySQL主从复制

MySQL的主从是由从节点主动去读主节点的binlog，然后保存到自己的中转日志处Relay Log，并在本地执行。此时不管Slave是否已接收binlog, Slave写relay log失败、重新执行SQL语句失败等异常情况并不会被Master感知，所以数据一致性无法得到有效保障

MySQL 5.5版本提供了半同步复制模式：Master在提交事务前，会等待Slave接收binlog, 当至少有一个Slave确认接收了binlog后，Master才提交事务。具体来说，Slave在收到binlog并将其写入relay log后，会向Master发送ACK响应；Master在收到ACK响应后， 认为响应发送方Slave已经在relay log中保存了事务，这时才进行事务的提交

Master会因为向过多的Slave复制数据而压力倍增，这个问题被称为“复制风暴”。所 以实际的主从模式架构可能是一些Slave向Slave复制数据，以减轻Master的复制压力，

一主多从，从挂从

1. Master Thread： 非常核心的后台线程，主要负责将缓冲池中的数据异步刷新到磁盘，保证数据的一致性。包括脏页的刷新、刷盘redo、合并插入缓冲和undo页的回收等
2. IO Thread： InnoDB中大量使用了异步IO，IO Thread主要负责这些IO请求的回调处理。分有write、read、insert buffer和log Thread
3. Purge Thread：InnoDB 1.1加入，回收undo页，减轻Master Thread负担
4. Page Cleaner Thread：InnoDB 1.2.x版本中加入，刷新脏页，减轻Master Thread负担

InnoDB 1.0.x 版本之前的Master Thread：

由多个循环（loop）组成：主循环（loop）、后台循环（background loop）、刷新循环（flush loop）、暂停循环（suspend loop）

• 主循环（loop）：

每秒的操作：日志缓冲刷新到磁盘（总是，即使这个事务还没提交）

合并插入缓冲（如果前一秒内的IO次数小于5次才执行这个操作）

至多刷新100个脏页到磁盘（脏页比例超过innodb_max_dirty_pages_pct（默认90，代表90%）的话执行这个操作）

切换到background loop循环（如果当前没有用户活动的话）

每十秒的操作：刷新100个脏页到磁盘（如果过去十秒内的IO次数少于200次的话）

合并至多5个插入缓冲（总是）

将日志缓冲刷新到磁盘（总是）

删除无用的undo（总是，最多尝试回收20个）

刷新100个或者10个脏页到磁盘（总是，如果脏页比例超过70%，刷100个，否则刷10个）

• 后台循环（background loop）：

删除无用的undo（总是）

合并20个插入缓冲（总是）

切换到flush loop循环（如果当前空闲的话）

跳回到主循环（如果当前不空闲的话）

• 刷新循环（flush loop）：

不断刷新100个脏页直到脏页比例小于innodb_max_dirty_pages_pct

切换到suspend loop循环

• 暂停循环（suspend loop）：

将Master Thread挂起，等待事件发生，有事件发生切换到loop主循环

InnoDB1.2.x版本之前的Master Thread：

1. InnoDB1.0.x之前的Master Thread做了许多硬编码，把参数写死了，InnoDB1.0.x开始提供了参数innodb_io_capacity，默认值200
   • 在合并插入缓冲时，合并的数量为innodb_io_capacity的5%
   • 刷新脏页时，刷新脏页的数量为innodb_io_capacity
2. innodb_max_dirty_pages_pct默认值从90调为75
3. 新增参数innodb_adaptive_flushing（自适应地刷新，默认为on，打开），通过redo log的产生速度决定最合适的刷新脏页数量，当脏页比例小于innodb_max_dirty_pages_pct时也会刷新一定量的脏页
4. 新增参数innodb_purge_batch_size，默认值20，每次回收undo页的数量由该值决定
5. 当数据库压力大时，Master Thread的主循环并不总是等待一秒，会加快速度

InnoDB1.2.x版本的Master Thread：

刷新脏页的操作分离到单独的Page Cleaner Thread线程

合并两个有序链表[306]

1

插入缓冲

当要插入数据时，对于唯一索引来说：

若索引页在内存的话，则往内存插入。若不在，则先把对应的索引页加载到内存，然后判断是否重，然后插入

对于非唯一索引而言，对应的索引页在内存的话，同上，然后写redo。

而对于不在的情况，则是将“插入xxx数据”记录到insert buffer（其实insert buffer是一个 b+树）里，同时将

写 insert buffer这个行为写一条日志到redo log（此时的redo就不是传统意义上的物理日志），整个操作没

有磁盘IO

change buffer是InnoDB1.0x对insert buffer的升级，扩展了delete buffer（标记删除），purge buffer（真

正删除）。change buffer不仅可以缓冲插入，更改和删除也可以。change buffer位于buffer pool中，大小

由innodb_change_buffer_max_size。默认为25，最多占buffer pool的25%，最大有效值可为50，超50还是

50

insert buffer 里有个bitmap用来追踪每个二级索引页的可用空间

什么时候合并insert pool到真正的二级索引页中？

1. 当二级索引页加载时，通过bitmap发现内存存在了，这时候就会合并
2. 发现二级索引页缓冲的数据占用已经小于1/32，则会强制从磁盘里读数据然后合并数据
3. master Thead 后台线程每10秒一次
4. 数据库正常关闭

什么时候change buffer落盘

1. 数据库空闲时，后台进程落盘
2. 缓冲池不够用了
3. 数据库正常关闭时
4. redo写满了

为什么要把change buffer中的记录写redo

同样也是为了持久化么。当使用到change buffer意味着内存还没有这数据，如果这时候宕机了，数据就没了

这时候做redo就是为了宕机重启后可以恢复内存数据。

当宕机重启时：

先看事务是否提交，无提交直接回滚。提交了就看change buffer是否落盘，有，则直接使用change buffer

恢复数据；没有就通过redo 恢复changbuffer，再通过change buffer恢复数据

可以不使用change buffer，只使用redo记录吗

PS：（虽然说redo log是顺序磁盘IO，某种情况是要比change buffer的随机内存速度快的）。change只是记

录了插入这个操作，并没有真正地插入到真正的索引页上！！！

不行，因为change buffer里维护了insert bit map。用来快速追踪哪些页是需要合并插入缓冲的，当这些页

被加载到内存时，就可以被合并了。如果单靠redo log的话，当被合并的页加载到内存是无法感知的。而且

redo log是循环记载，会被加载到磁盘，也就是写入磁盘前必须** 合并插入缓冲区（因为redo log里有change **

buffer的插入记录），这会加重redo log的负担

Change Buffer = 存着很多“等待插入索引页的记录”
那么“哪些页需要合并”就是 哪些页已经有“待插入的缓存记录”但还没真正写入。
合并（Merge） = 把 Change Buffer 中某页的缓存记录，真正插入到该页中。

写了redo log，为什么buffer pool还要落盘？

缓冲池大小有限，如果需要insert的页一直没被加载，insert pool会一直积累，需要落盘腾空间

两次写？

double write由两个部分组成，一个double buffer位于内存，2mb，另外一个位于磁盘上，buffer area上，

同样也是2mb

刷新脏页时，并不是直接把脏页数据直接刷到磁盘对应的表空间，而是先copy到double write buffer。然后

由double write buffer顺序写入double write area（这时候意味着这些页数据已经被持久化了）。然后再从

double write buffer执行fsync 将里的数据刷到各自的表空间，多了两个步骤

1.脏页数据被copy到了double write buffer

2.直接落到各自的表空间前顺序写入到了double write area里

为什么要这么搞？

如果刷脏页，一个脏页16kb，如果写一半宕机了，就会出现磁盘的表数据人不人鬼不鬼的。 有了double

write area后，如果宕机重启后，会检查double write area是否有对应完整页数据，如果有的话就完整恢复

没有的话，则意味着没落盘。（其实细想的话也是一种先写日志的操作）

那么这种丢失能否通过redo恢复？答案是不行！因为redo是物理日志，记录要对页文件进行的物理修改，它记载了：对xx页偏移量500的位置写入aaa、将xx页偏移量650的位置的数据由bbb改为ccc。但现在的问题是，你的页是缺失或者只更改了一部分的！页已经发生了损坏，再对其重做是没有意义的

如果脏页在从内存中的doublewrite buffer 写入到磁盘中的doublewrite 中发生了宕机怎么办？

没有影响，这说明你还没向磁盘中刷新脏页，磁盘中的数据是完整的，宕机重启后可以根据redolog进行数据恢复

为什么要双写

两次写默认打开，可通过innodb_doublewrite关闭

自适应hash索引

InnoDB自动根据访问的频率和模式自动地为某些热点页建立哈希索引

异步IO

刷盘和从磁盘加载页数据都是异步IO，且会根据实际情况进行IO merge，如发现读取的页是连续的，就会连

续读取，而不是一页页读

刷新邻接页：

刷新一个脏页时，会检测该页所在区的所有页，如果是脏页，一起刷新，多次IO合并为一个IO，但可能有以下问题： 是否将不怎么脏的页刷新了？该页很快又变脏了 固态硬盘有较高的IOPS，是否还需要这个特性？ 为此，InnoDB1.2.x版本开始提供参数innodb_flush_neighbors决定是否启动该功能，默认为0，不启动

如一条简单的查询语句：<font style="color:rgba(25, 26, 31, 0.9);">select * from users where age='18' and name='Hollis';</font>

执行过程如下图：

结合上面的说明，我们分析下这个语句的执行流程：

①使用连接器，通过客户端/服务器通信协议与 MySQL 建立连接。并查询是否有权限

②Mysql8.0之前检查是否开启缓存，开启了 Query Cache 且命中完全相同的 SQL 语句，则将查询结果直接返回给客户端；

③由解析器（分析器）进行语法分析和语义分析，并生成解析树。如查询是select、表名users、条件是age=’18’ and name=’Hollis’，预处理器则会根据 MySQL 规则进一步检查解析树是否合法。比如检查要查询的数据表或数据列是否存在等。

④由优化器生成执行计划。根据索引看看是否可以优化

⑤执行器来执行SQL语句，这里具体的执行会操作MySQL的存储引擎来执行 SQL 语句，根据存储引擎类型，得到查询结果。若开启了 Query Cache，则缓存，否则直接返回。

假如我们有一张表case_event，其中有一个字段state，它有三个值，分布是INIT、SUCCESS、以及 FAILED。

那么在定时任务中，我们需要把 INIT 的数据扫描出来进行执行，一般来说是这么写的 SQL：

1
2
3
4
5

SELECT * FROM case_event
WHERE STATE = 'INIT' 
ORDER BY ID 
LIMIT 200;
//以上的数据拿出来执行 那么这时候状态就会变成 success 或者 Fail 

这个 SQL 看上去没啥问题，其实就是每次扫描200条记录处理。

但是这个SQL其实是一个典型的 bad case，因为他会出现一个致命的问题，那就是可能会导致扫描任务一直无法执行。

因为上述的 SQL 相当于默认了每一条记录执行之后，都能把状态推进到 SUCCESS 或者 FAILED。但是事实上并不一定的，尤其是在一些有很复杂的业务逻辑，或者一些外部调用的时候，这个地方就变成了一个分布式事务，我们没办法保证最后的 INIT->SUCCESS 或者 INIT->FAILED 一定能成功。即还是INIT

那如果不能成功，就会导致一部分失败的状态一直处于 INIT 状态，那么他就会每次都会被扫描起来（因为他还在前200条之内），然后还是不成功，下次还会被扫描出来。

这样一方面会大大降低任务的效率，一直在重复执行这些不断失败的任务，另一方面，一旦失败的条数达到了200条，那么就意味着每次扫出来的数据都是这200条，导致后面的任务永远无法被执行到。

而如果你的SQL 是这么写的，那么这个问题就更大了：

1
2
3
4

SELECT * FROM case_event
WHERE STATE in ('INIT' ,'FAILED')
ORDER BY ID 
LIMIT 200;

相当于你在不断的重复执行那些固定的任务，而后面的很多任务一直无法被执行。

一直在重复执行者两百条永远执行失败的任务，而后面的任务就管了一点了

如何解决这个问题呢，有一个方式，那就是增加一个游标，让你的每次查询都往后移动，如：

1
2

select * from task where status = 'init' and id > #{id}
order by id limit 200

这里每次查询的时候，都把上一次的查询结果中的最大id 带过来，然后就可以避免再次扫描到重复的任务了，就可以让本次任务调度正常完成执行。

https://juejin.cn/post/7350228838151847976

这个的话，如果说是磁盘占用其实都是一样的，比如说你一个字段为20，那么磁盘所占用的一定是20

但如果从内存占用来说，这两个就有比较大的区别的了。你把这个字段读到内存时，为这个字段申请的内存是根据varchar（xx）这东西来确定的，因为我们操作系统本身为数据申请内存，都有预申请的一个过程，一次申请多少呢。

总结的核心结论：

• <font style="color:rgb(0, 0, 0);">VARCHAR</font>的“可变长度”特性主要体现在磁盘存储上，使其能节省空间。
• 在内存中，为了性能和简化数据读取流程，MySQL 会为 <font style="color:rgb(0, 0, 0);">VARCHAR</font>列预先分配其定义的最大长度 (**<font style="color:rgb(0, 0, 0);">N</font>**) 所需的空间。
• 这种内存分配机制意味着过度定义**** **<font style="color:rgb(0, 0, 0);">VARCHAR</font>**的最大长度 (**<font style="color:rgb(0, 0, 0);">N</font>**) 会直接导致内存浪费，这种浪费是普遍存在的（不仅限于排序操作）。
• 因此，在定义 <font style="color:rgb(0, 0, 0);">VARCHAR</font>字段时，务必根据实际业务需求，选择一个足够用但又不会过度冗余的最大长度 (**<font style="color:rgb(0, 0, 0);">N</font>**)，以平衡磁盘空间节省和内存使用效率。<font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>的流行与其在单字节长度前缀下的存储效率优化有关。

1. 磁盘存储（节省空间）：
   • <font style="color:rgb(0, 0, 0);">VARCHAR</font>在磁盘上存储的是实际数据 + 一个或两个字节的长度前缀。
   • 长度前缀指示了该字段值实际占用的字节数。
   • 因此，磁盘空间占用是可变的，只取决于实际存储的数据长度（加上很小的长度前缀开销）。定义的最大长度 (<font style="color:rgb(0, 0, 0);">VARCHAR(N)</font>) 只限制了能存储多少数据，不影响实际存储空间（除非数据达到最大长度）。
2. 内存分配（固定大小）：
   • 当 MySQL 从磁盘读取一行数据到内存时，它需要预先为每一列分配内存空间。
   • 在读取具体数据内容之前，MySQL 只知道该列的定义：它是一个 <font style="color:rgb(0, 0, 0);">VARCHAR</font>，并且其最大允许长度是**** **<font style="color:rgb(0, 0, 0);">N</font>**字节。
   • MySQL 无法在读取数据之前知道该字段在这一行中的实际长度是多少（是 10 还是 20？）。这个实际长度信息是存储在数据本身的开头（长度前缀）。
   • 为了能够安全地接收从磁盘读取出来的整行数据（包括所有列），MySQL 必须为每个 <font style="color:rgb(0, 0, 0);">VARCHAR</font>列分配足够容纳其最大可能长度 (**<font style="color:rgb(0, 0, 0);">N</font>**) 的内存空间。
   • 关键原因：性能。 如果每次读取一行时，都尝试先读取长度前缀，再根据这个长度精确申请内存，然后再读取实际数据，会导致大量的、细碎的内存分配操作和额外的 I/O 定位。这会极大地降低数据读取的性能。预先按最大长度分配内存虽然可能浪费一些空间，但避免了频繁的内存申请开销，是性能与内存利用之间的权衡。
3. 定义长度 (**<font style="color:rgb(0, 0, 0);">N</font>**) 的重要性：
   • 正因为内存分配是按定义的最大长度 (<font style="color:rgb(0, 0, 0);">N</font>) 进行的，所以 <font style="color:rgb(0, 0, 0);">VARCHAR(N)</font>中的 <font style="color:rgb(0, 0, 0);">N</font>直接影响内存消耗。
   • 即使你存储的实际数据很短（比如 <font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>只存了 10 个字符），MySQL 在内存中也会为该字段预留 255 字节（或根据字符集计算出的最大字节数）的空间。
   • 过度定义**** **<font style="color:rgb(0, 0, 0);">N</font>**(如**** **<font style="color:rgb(0, 0, 0);">VARCHAR(1000)</font>**但实际只用 10 字节) 会导致严重的内存浪费。 这种浪费不仅发生在排序等需要临时表的操作中（如原文所述），也发生在任何将行数据读入内存的操作中（如简单的 <font style="color:rgb(0, 0, 0);">SELECT</font>查询、连接操作、在内存中更新数据等）。这就是为什么强调“即使不排序，也可能有其它内存不够的问题出现”。
4. 255 字节的特殊性：
   • 长度前缀需要占用空间。对于最大长度 <font style="color:rgb(0, 0, 0);">N</font><= 255 字节的 <font style="color:rgb(0, 0, 0);">VARCHAR</font>，长度前缀只需要 1 个字节。
   • 对于最大长度 <font style="color:rgb(0, 0, 0);">N</font>> 255 字节的 <font style="color:rgb(0, 0, 0);">VARCHAR</font>，长度前缀需要 2 个字节。
   • 因此，<font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>是一个非常常见的定义：
     • 它充分利用了单字节长度前缀能表示的最大长度（255）。
     • 定义 <font style="color:rgb(0, 0, 0);">VARCHAR(256)</font>会导致长度前缀变成 2 字节，而实际能存储的数据只比 <font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>多 1 字节（256 vs 255），但长度前缀开销翻倍（2字节 vs 1字节）。从存储效率角度看，<font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>是单字节长度前缀下的最优选择。
     • 注意： 这里的 255/256 指的是字节数，不是字符数。对于多字节字符集（如 UTF8MB4），一个字符可能占用多个字节，<font style="color:rgb(0, 0, 0);">VARCHAR(255)</font>能存储的字符数会少于 255。

TOPK

堆排序

维护一个 n = k 的堆 PriorityQueue，for i < 数据量级来元素就加进去，如果超过了 k，就poll 堆顶元素

时间复杂度就是 数据量级 log K

空间复杂度，因为堆本质其实就是一数组，空间为 O k

类似快排法

使用hash

对于这种问题

字典树

混合查询

有一批文件，每个文件里面有很多单词，如何快速统计所有单词的出现次数?

数据重复、是否存在问题

位图

bitmap 其实就是对HashSet或者数组的一个压缩版

Java的BItSet

海量数据的极致优化还有 压缩位图

布隆过滤器

解决 return true 就表示 可能在 和 return false 就表示 一定不在的

解决的业务问题：

找出排名前500的数

堆本质上就是一颗完全二叉树

多路堆，最优解

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
45
46
47
48
49
50
51
52
53

import java.util.*;

public class Top500FromSortedArrays {

    static class Node {
        int value;      // 元素值
        int row;        // 来自哪个数组
        int index;      // 在该数组中的下标（倒序移动）
        
        Node(int value, int row, int index) {
            this.value = value;
            this.row = row;
            this.index = index;
        }
    }

    public static List<Integer> top500(int[][] arrs) {
        int k = arrs.length;  // 数组个数 (10000)
        PriorityQueue<Node> maxHeap = new PriorityQueue<>(
                (a, b) -> b.value - a.value   // 大顶堆
        );

        // 初始化：每个数组的最后一个元素入堆
        for (int i = 0; i < k; i++) {
            int lastIndex = arrs[i].length - 1;
            maxHeap.offer(new Node(arrs[i][lastIndex], i, lastIndex));
        }

        List<Integer> result = new ArrayList<>(); // 存前500
        for (int count = 0; count < 500 && !maxHeap.isEmpty(); count++) {
            Node top = maxHeap.poll();
            result.add(top.value);

            // 往前移动一个位置，继续加入该数组的下一个大值
            if (top.index - 1 >= 0) {
                maxHeap.offer(new Node(arrs[top.row][top.index - 1], top.row, top.index - 1));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 构造一个简单的测试用例 (真实情况是10000×500，这里只演示)
        int[][] data = {
                {1, 3, 5, 7, 9},
                {2, 4, 6, 8, 10},
                {11, 12, 13, 14, 15}
        };

        System.out.println(top500(data));  // 输出最大的前5个
    }
}

两个大文件中找出共同URL

64 byte * 50 亿 ，一个文件 320g 全加载到内存 建立Hash表，那肯定是不现实的。

还是 分治

对A ：hash(url) % 1000 -> 1000个小文件 命名为 a0,a1,a2….. a999

对B：同样，hash一定得相同

那么a99 和 b99里面可能存在相同的。但a99和a98里面的就不可能出现相同的

然后再把小文件加载到内存，建立hashmap