底层面经 | 个人博客

LSM Tree

读写流程

lsm-Tree适合写多读少的场景。日志结构合并树，它由三部分组成：memtable、immutable memtable和sstable。在内存，即memtable中维护以键排序的数据结构如跳表、b+树等，数据的插入、修改、删除首先在内存中进行，而且不像b+树，数据在原地修改，而是像日志一样以append方式，把数据的更新以记录形式append到内存（行的多个版本）。待写满后冻结memtable转为immutable memtable，变为只读，为了避免阻塞后续的更新，会创建一个新的memtable接替原来的memtable负责写，immutable memtable写入磁盘，形成sstable，每个immutable memtable对应一个sstable，全称为Sorted String table，它是位于磁盘上的一种持久化、有序且不可变的键值存储结构，它内部包含一系列可配置大小的Block（默认大小一般是64k）。Block的索引存储在尾部,当SSTable打开时，索引被加载到内存。然后根据key在导入内存里面再进行二分查找，找到key对应的offset之后，然后去磁盘把相应的数据块读出来。
这些SSTable文件，虽然每个文件中的key是有序的，但是文件之间完全完全无序造成还是无法查找。这里SSTable巧妙地采用了分层合并机制来解决乱序的问题。
查询时，从memtable-> immutable memtable -> sstable,在sstable倒着往前查询（最新的数据在最后），可以通过布隆过滤器、索引来优化查找速度。

LSM造成的问题

1）读放大，即读取的数据量比实际需要读取的数据量大。
2）写放大，写入的数据量比实际需要写入的数据量大。如compact操作。
3）空间放大，数据实际占用的磁盘空间比实际的大。即数据冗余。

合并策略

由于每个key的记录可能存在多份，合并时会消除冗余将数据合并成最新的一份。
trade-off

Leveling策略

size-tiered 策略

保证每一层的SSTable大小相近，同时限制每一层SSTable数量。待数量达N时进行合并写入下一层成为一个SSTable。
每一层中的SSTable文件之间可能有key重叠，所以读放大会很严重。
层数达到一定数量时，最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。

写时复制

（Copy-on-write，简称COW）是一种优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。

为什么选用LSM?

一个是随机写顺序写的问题。一个是索引结构的并发插入修改有关。在LSM中维护索引结构采用的是跳表，不需要加latch，相比b+tree可以提高索引并发。
为什么有多个immutable table? 其实是内存与磁盘的鸿沟，内存写太快了，磁盘更新效率跟不上内存。
SSTable上使用稀疏索引来查找块，那么采用哪种稀疏索引？
采用B+Tree，而且由于数据是给定的，所以b+tree的空间利用率是100%.
由于这个过程容易出现非命中查询（即查询的数据不存在），可以引入布隆过滤器，如果没有命中则数据一定不在磁盘中。
WAL

mysql分库分表、表分区

表分区

表分区实际上是把一张表在物理结构上分为多个分区，磁盘上变为多个文件，即原本是一个表文件，现在拆分成了多个表文件，逻辑上还是同一张；
表分区只能水平划分，即以行为粒度进行划分
分区类型如下：

RANGE

按照一个字段范围进行分区，仅支持整数类型字段作为分区键，如果想要以日期字段来做数据分区，需要想将其转换为整数格式的时间戳。
例子
partition by range(r_id)(
partition p1 values less than (100000),
partition p2 values less than (200000),
partition p3 values less than (300000),
partition p4 values less than maxvalue
);
– 查询 zz_range 表中不同分区的数据量
select
partition_name,table_rows
from
information_schema.partitions
where
table_name = ‘zz_range’;

LIST

枚举分区，只支持整数字段作为分区键。如果插入的数据在所有分区中找不到对应的值，会直接报错。
partition by list(l_sex)(
partition p1 values in (0),
partition p2 values in (1)
);

KEY

在 hash 分区中，想要使用一个字段作为分区键，要么这个字段本身是整数类型，要么这个字段经过哈希函数处理后，能够得到一个整数的哈希值才行。但在 key 分区中，除开不支持 text、blob 两种类型外，其他类型的字段都可以作为分区键。
在 key 分区中也可以不显式指定分区键，MySQL 会自动选择，但不管是自己显式声明分区键，亦是 MySQL 自动选取分区键，都会遵循如下规则：

表中只存在主键或唯一字段时，分区键必须为主键/唯一键的部分或全部字段，不允许选择其他字段。
表中主键、唯一字段同时存在时，分区键必须为主键和唯一键共有的部分或全部字段。
当表中不存在主键或唯一键时，分区键可以是除 text、blob 类型外的任意单个或多个字段。
partition by key(k_name)partitions 3;

HASH

哈希分区中支持两种哈希分区法：

常规哈希：基于某个整数型字段，直接做取模，最后根据余数来决定数据的分区。
线性哈希：基于某个字段哈希之后的哈希值，进行取模运算，最后根据余数来决定数据的分区。
常规哈希只能基于整数型字段对数据做划分；线性哈希则可以不限制字段的类型，只要能够通过 MySQL 哈希函数，转换出哈希值的字段类型都可以作为分区键（但本质上 MySQL 中好像没有提供将字符串转换为数值类型的哈希函数）。
– 选用 h_id 作为分区键，划分为三个分区
partition by hash(h_id)partitions 3;
– 使用线性哈希分区
partition by linear hash(lh_id)partitions 3;

SUB

又称子分区，所谓的子分区是指基于表分区后的结果，进一步做分区处理，也就是基于一个分区再做分区，好比一张表可以基于日期中的年份做分区，基于年份做了分区后，还可以基于年分区进一步做月分区。
这种方式要求每个一级分区下的二级分区数量都一致，同时二级分区的类型只能为 hash、key 类型。
partition by range(year(register_time))
subpartition by hash(month(register_time))
(
partition p1 values less than (2000)(
subpartition p1_s1,
subpartition p1_s2
),
partition p2 values less than (2020)(
subpartition p2_s1,
subpartition p2_s2),
partition p3 values less than maxvalue(
subpartition p3_s1,
subpartition p3_s2
)
);

COLUMNS

cloumns 分区实际上是 range、list 分区的变种，cloumns 分区可以使得 range、list 的分区键由多个字段来组成，同时支持的字段类型也相对更丰富一些，但这种分区法一般用的极少

分表

垂直分表
当一张表由于字段过多时，会导致表中每行数据的体积变大，一方面会导致磁盘 IO 次数增多，影响数据的读写效率；同时另一方面结果集响应时还会占用大量网络带宽，影响数据的传输效率；再从内存维度来看，单行数据越大，缓冲区中能放下的热点数据页会越少，当读写操作无法在内存中定位到相应的数据页，从而又会产生大量的磁盘 IO。
垂直分表可以根据冷热字段对表进行拆分。拆分的表中需要保存外键来建立联系。
由于修改数据时会同时修改多张表，所以需要使用事务来保证原子性。
水平分表
当一张表内的数据量过大（一般要求控制在 500-1200w 之间），查询性能就会下降，从而需要对表进行水平拆分。
水平分表后，多个表的表结构、索引相同，数据不同，每张表中会存储不同范围的数据。
水平分表和表分区十分类似，一般会选用水平分表方案。
由于数据会被存储到多个表中，所以进行增删改查数据前，需要定位到相应的表中再进行操作。且进行聚合操作时，需要从多个表中取出数据，再在后端进行聚合操作，或者依赖 Redis、ES 等第三方中间件来完成。
另外，可能出现多个表中 ID 相同，数据不同的情况，所以要合理设置 ID 规则来避免。比如可以设置交叉增长的 ID；可以利用特殊算法（雪花算法等）生成有序的分布式 ID；利用第三方中间件生成 ID 等。
###分库

水平分库

水平分库和水平分表相似，并且关系紧密，水平分库就是将单个库中的表作水平分表，然后将子表分别置于不同的子库当中，独立部署。
因为库中内容的主要载体是表，所以水平分库和水平分表基本上如影随形。
例如用户表，我们可以使用注册时间的范围range来分表，将2020年注册的用户表usrtb2020部署在usrdata20中，2021年注册的用户表usrtb2021部署在usrdata21中。

垂直分库

特点，按业务归属

同样的，垂直分库和垂直分表也十分类似，不过垂直分表拆分的是字段，而垂直分库，拆分的是表。
垂直分库是将一个库下的表作不同维度的分类，然后将其分配给不同子库的策略。
例如，我们可以将用户相关的表都放置在usrdata这个库中，将订单相关的表都放置在odrdata中，以此类推。
垂直分库的分类维度有很多，可以按照业务模块划分（用户/订单…），按照技术模块分（日志类库/图片类库…），或者空间，时间等等。

面试题

分表要停服嘛？不停服怎么做？

不用停服。不停服的时候，应该怎么做呢，主要分五个步骤：

编写代理层，加个开关（控制访问新的DAO还是老的DAO，或者是都访问），灰度期间，还是访问老的DAO。

发版全量后，开启双写，既在旧表新增和修改，也在新表新增和修改。日志或者临时表记下新表ID起始值，旧表中小于这个值的数据就是存量数据，这批数据就是要迁移的。

通过脚本把旧表的存量数据写入新表。

停读旧表改读新表，此时新表已经承载了所有读写业务，但是这时候不要立刻停写旧表，需要保持双写一段时间。

当读写新表一段时间之后，如果没有业务问题，就可以停写旧表啦

分布式ID

主键生成机制。
数据库被切分后，不能再依赖数据库自身的主键生成机制啦，最简单可以考虑UUID，或者使用雪花算法生成分布式ID。雪花算法是一种生成分布式全局唯一ID的算法，生成的ID称为Snowflake IDs。这种算法由Twitter创建，并用于推文的ID。
一个Snowflake ID有64位。

第1位：Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。

接下来前41位是时间戳，表示了自选定的时期以来的毫秒数。

接下来的10位代表计算机ID，防止冲突。

其余12位代表每台机器上生成ID的序列号，这允许在同一毫秒内创建多个Snowflake ID。

一致性哈希

背景

场景：三台缓存服务器0，1，2号，用于缓存图片，现在有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。
第一种方法采用普通哈希，即hash（图片名称）% N，这里有三台服务器，故N=3

虽然普通哈希能把数据均匀放到三台服务器上，但是如果服务器存满了，需要增加服务器节点，此时N变为4，那么之前存放的数据采用该哈希函数计算得到的地址也会产生变化，即5%3 = 2 => 5 % 4 = 1，那么就需要将所有数据重新计算后搬迁到新的位置上，导致开销很大。
因此出现了一致性哈希方法

步骤

一致性哈希的函数不再对服务器数量进行取模，而是hash(图片名称) % 2^32，即对2^32取模
一致性哈希将整个哈希值空间按照顺时针组成一个虚拟圆环：哈希环
对每台服务器，用该函数进行哈希，具体可以选择服务器的IP等关键字作为哈希函数的输入，确定在哈希环上的位置
使用该算法定位数据访问相应的服务器：将数据key使用hash计算出值，确定此数据在环上的位置，从此位置沿环顺时针，遇到的第一台服务器就是其定位的服务器，如下面的图，1 2数据对应服务器A,3对应B,4对应C

优点

前面提到的普通哈希函数，如果简单对服务器数量进行取模，那么服务器数量变化会导致缓存的雪崩，从而很有可能导致系统的崩溃。而一致性哈希算法就可以很好解决这个问题，因为当需要增加或减少服务器时，只会使得哈希环上的一部分数据缓存失效，不至于将所有压力都同时间集中到后端服务器上
可扩展哈希的扩展过程也很相似，每次扩容后，只需把溢出的桶中所有元素进行重映射
hash 环的倾斜在极端情况下，仍然有可能引起系统的崩溃，为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点，一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。具体做法可以在服务器ip或主机名的后面增加编号来实现，加入虚拟节点以后的hash环如下：

c++

###智能指针
智能指针是一个类，这个类的构造函数中传入一个普通指针，析构函数中释放传入的指针。智能指针的类都是栈上的对象，所以当函数（或程序）结束时会自动被释放，

shared_ptr
基于引用计数的智能指针。可随意赋值，直到内存的引用计数为0的时候这个内存会被释放。
weak_ptr
引用计数有个问题就是如果两个指针互相引用形成环，那么两个指针指向的内存均无法释放。弱指针是用于引用共享指针使用的。共享指针每次被引用都会计数+1，但是弱指针只引用不计数，也就是说共享指针如果进行析构了，那么即使有弱指针引用，也会将内存释放；所以弱指针使用的时候，还需要注意判断指针是否非空。
unique_ptr
不支持赋值和拷贝，会报错。只能通过std::move()来转移指针。

类型转换

static_cast用于在类型之间进行转换，它是编译时强制转换。
const_cast主要用于去除指针或引用类型的const属性。此操作可能会导致未定义的行为，所以需要慎用。
dynamic_cast主要用于运行时的从父类指针向子类指针转换，如果转换不成功则返回nullptr。
reinterpret_cast可以将指针或引用转换为任何类型的指针或引用。reinterpret_cast实现依赖于编译器和硬件，可能导致未定义的行为。
为什么还引入这些类型转换？
主要有三点，更安全、更灵活、可读性更好。
什么是隐式转换？
隐式转换是指在表达式中自动进行的类型转换。比如int 和 double相加，会把int先转为double，然后再进行求和。如果不想让其尝试隐式转换，可以在编译选项添加-Werror=conversion。或者explicit关键字来让变量禁止隐式转换。

move()和forward()

move和forward的内部实现本质上都调用了static_cast，它们的使用场景不同。前者会将任何一个变量无条件地转化成右值，用于move语义；而后者则会有条件地（当且仅当该变量是右值，如果输入的变量是左值，那么forward将输入的变量转化成左值）将变量转化成右值，通常用于在模版函数中转发和保留原始变量的左值和右值属性。

B+tree

二级索引的value应该选主键还是数据所在块的指针？

如果选择数据所在块的指针，虽然寻址会很方便，但是如果B+tree进行了分裂和删除，所在块已经不是原来数据存放的地址了，就会失效；而且选择主键的话虽然要进行搜寻，但是由于大部分内部节点都在缓存，所以其实很多情况下只需要在内存中遍历，开销很小。

B+树的缺点，随机读写为什么比顺序读写慢?

跟磁盘结构有关，SSD的流行，SSD的随机写性能很差。随机写会导致多个页面发生变动，需要时常进行磁盘碎片的整理，这个过程得把磁盘中的页读到内存中，增加了IO次数。随机读的话会频繁移动磁臂，移动磁臂所花费的时间是ms级别的。
顺序io则不会导致上述问题

LRU,缓冲池

15445的LRU算法，在链表中的页在换出的时候，需要将页写入磁盘。那么要等待页写入磁盘后再继续读写吗？怎么做优化？
其实可以换出时将脏页使用链表存储连接。steal机制
如何进行刷脏：检查点进程控制WAL和缓冲池，确保两者协同工作。只有在缓冲池中的数据页完成落盘后相关的操作日志记录才能从WAL中丢弃。
如何进行200Gcache的刷脏？
脏页按照日志的LSN来排序，如果一个脏页被写了多次，那么它应该用哪一次的LSN来排序？
跟它的故障恢复有关，其实需要按第一次LSN，在进行redo的时候，都是需要顺序按LSN来重做的。
如果checkpoint5~10分钟做一次刷脏，磁盘承受不住，该怎么做？
做增量检查点，保证平缓地进行磁盘刷数据。

进程通信的方法

1.socket和RPC有什么关系
以模块调用的简单性忽略通讯的具体细节。RPC实际上底层就是由socket实现的，RPC的出现实际上是希望程序之间的通信只需要通过简单的模块功能的调用来进行网络通信，让操作就像是在同一台机器同个程序一样。

事务的隔离级别

传统隔离级别

其实是用于2PL而定义的。RU，会产生读脏、不可重复读、幻读。RC则不会读脏，RR不会读脏、可重复读。
可串行化则全部解决。读脏是指读到其他事务未提交的数据，其实是因为RU在实现时读行不加锁，修改才加锁，如果对同个行进行访问，那么其他事务就算加了锁，依旧能够读该行，导致出现读脏；不可重复读就更容易解释了，因为修改后第二次读取发现数据不一致，幻读则是由于行的插入和删除导致事务执行相同的select读取到的结果集不一样；然后是读已提交，它多加了读锁的实现，两阶段锁第一阶段只加锁，第二阶段释放锁，但是读已提交能够在收缩阶段加读锁；那么就意味着待其他事务提交后，再次读同个行会出现不一致的数据，这就是不可重复读。
可重复读，则在收缩阶段只能释放锁，保证了不会出现上述情况，但是依旧不能解决插入操作导致的幻读，需要多加一个index lock的实现才能解决，gap lock，也就是实现可串行化。
t

快照隔离级别

快照隔离级别是多版本并发控制中引入的一种隔离级别。实际上MVCC只能实现读已提交，可重复读，而可串行化的实现需要引入乐观并发控制OCC或者2PL（悲观）来实现。
MVCC实现:
MVCC在不同的存储引擎中实现也不同，传统TP数据库如pgsql,mysql的out-of-memory实现中，采用读视图read view加上物理上存储数据的不同版本（pgsql append在原表中，mysql append在undo log中），事务的时间戳采用逻辑时间戳，时间戳大代表创建的时间晚；
读视图存在于每一个事务中，新建时事务创建一个事务，该事务会创建当前数据库事务快照集，通过这个快照集我们能确定哪些事务在该事务创建时是仍活跃的（未提交，因此我们在读取时不能读取到该事务创建的新版本数据）；

快照读

通过read view来遍历数据的所有版本，找到能读取的版本，能解决读脏，不可重复读和幻读问题，同时读事务和写事务并不冲突（无需上锁），能解决读写冲突，但是不能解决写写冲突：假设事务A先更新了数据x，进行了提交，事务B早于事务A创建，很明显读不到事务A的新创建的版本，而是基于旧版本更新了数据x，这样一来把事务A的更新给覆盖了，也就是lost update。对于这种读称为快照读

当前读

为了保证在更新时能读取到最新的数据版本，我们就需要保证该数据此时不被其他事务所更改，因此就需要引入2pl。这样一来对同一数据的更新就可以实现冲突可串行化，保证顺序对数据进行读取后更新。

MVCC中的写偏序（write skew)

在前面，我们解决lost update，也就是对同一数据更新时如何保证冲突可串行化。但是还有一种情况，在MVCC中更新的是不同的数据，但是却也出现了更新错误，也就是写偏序。
写偏序是指MVCC的读写循环依赖。如下例子，事务A读取了事务B接下来要更新的元组B，事务B也读取了事务A接下来要更新的元组A，出现了两个读写依赖，造成了事务的循环依赖：

因为MVCC的实现中，读（select)不加锁，在进行读取时能够读取到旧版本，有一种业务场景需要我们先判断某个条件再去更新其他数据。事务A中，我们发现数据tupleB符合条件后对其他数据tupleA进行加锁然后更新，但是在更新时却有其他事务B来更新这个条件（tupleB)，那么就会出现逻辑错误。因此，我们引入了select的当前读机制。
在mysql的当前读机制中，select语句也可以加共享锁或排他锁，只需在语句最后加for update或for share即可。这样一来就可以保证写偏序的解决，这也就是可串行化的快照隔离级别。

实际上MVCC的实现非常灵活，没有标准。
sql-server的快照隔离