开发者学堂课程【PolarDB for PostgreSQL 内核解读系列课程：【视频】存储管理1】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1042/detail/15328
存储管理1
内容介绍
一、存储引擎架构和原理
二、页面和元组
三、buffer 管理
四、淘汰算法
一、存储引擎架构和原理
今天主要会介绍主流存储引擎架构和原理，pg页面布局和原组buffer管理及淘汰算法，介绍架构原理的原因是出于引擎相对来讲是很复杂的，如果大家不懂得原理只看代码难度有点大，所以先将各种各样的原理为大家介绍清楚，让大家有一个基本概念的了解，第一部分讲解存储引擎架构和原理，本节课讲解的是存储引擎架构和原理，下一节课将会讲解其他剩余部分。
1.存储层级
讲解存储引擎通常都会先讲解
类似于这样的一张图片，因为存储引擎主要看的是性能和性价比，这张图可以看到最快的是上面CPU的寄存器，之后是CPU的Catch，下面是内存memory，然后是shd，再然后是传统的硬盘，然后是演成的磁盘或者一些磁带，可以看到越向下价格越便宜越向上性能越高但是价格很贵，基于这个特点要决定如何进行数据分成的设计，包括现在用到的数据库基本都是通过如何Memory和CPUCatch这一层和下面磁盘的一层包括shd和传统的盘他们之间如何进行协调，这是整个存储引擎设计的基础，从右面这张图可以看到是比较感性的数据，CPU的l1 catch假设是0.5纳秒，如果将其放大成0.5秒相当于到了后面磁带这一块会达到31年，这里一秒钟就能够完成的事情到了这里需要六十多年才能够完成，性能差别是非常非常大的，包括大家常用的DRAM和SSD，其实他们两个之间也差了三个数量级，很多存储的设计和硬件都是与硬件息息相关的，这些数据会作为设计的主要依据。
2.存储访问原理
存储引擎的访问原理是数据都存储在磁盘上了，磁盘中有这么多的数据一般都会以配置或者block形式存在，配置和block一般页面大小在8k~64k之间一般是这样的设计，这个数据如果被用户使用时会创建buffer pool，buffer pool主要是将数据缓存到内存中，这样就避免了数据访问每次都从盘读取，能做到磁盘的加速，如果全放在内存中，内存远远不够大，会涉及到在buffer pool中如果内容不够了需要将一些不常使用的数据淘汰掉，涉及到淘汰的算法，这就是存储引擎基本的原理
3.cache fusion
下面看一下存储引擎基本原理扩展出来的一些架构，首先是cache fusion，如果大家比较熟悉orache rac，IBM purescale，在十年前最先进的架构就是这样的，cache fusion的特点是多个节点，那时还不讲究分布式，多个节点，如果想同时修改数据可以利用cache fusion的方式，中间有一种cache，cache相当于数据首先基于共享存储的方式，数据是一部分，在读取数据时先将其读取到cache中，如果别人想要数据再将其从cache中传递给别人，Pure scale也是类似于这种做法，但是不同点是有专门管理的共享buffer的组件叫做CF，CF里面有全集的buffer还有锁相关的管理，rac相当于全局的buffer和锁的能力在每个节点上，而每个节点相当于管理一部分数据相关共享的数据，提供了类似于partition的能力，这是他们之间的不同但是本质上都是catch fusion的架构，这是十年前大家比较熟悉的，在国内做这种集群都是使用这种方法进行更改，改这种集群时其实也是做了一些设计，在这个过程中主要还是涉及到了buffer pool，Buffer pool本身就是今天所讲解的内容，如何将其移到中心进行管理，中心管理也有相应的buffer pool淘汰的策略。
4.polar DB共享存储架构
polar DB共享存储架构是比较新的，与rac的相同点是利用共享存储不同点在于DB的节点数据通过日志进行传递，包括日志传递到共享存储，这种架构叫做load sdd，整个对日志的改造比较大，节点之间的数据可以读redo进行数据的恢复生成数据，polar DB共享存储架构已经开源了，包括底层的polar FS用来做共享存储，各项存储会将一些sign，赛服一些快设备模拟成一套共享存储的系统，上层所有节点都可以读到分布式文件系统，同样新配置的数据。
5.xengine lsmtree架构
xengine 利用的是lsmtree架构，比较早是htfs存储引擎中使用到，后来包括Rock DB国内除了int以外OB，TDB KV的引擎都是利用了lsm tree的特点，它的特点是有内存中的memTable，mem table会管理最新更新热的数据，些数据慢慢就变成了不可修改的mem table，之后再经过一层一层的contention变成了l0ll2不同级别磁盘的文件，文件以extent方式管理，里面也会有block的概念类似于叶，好处是会分层，分层以后可以通过分层确定每一层，因为越来越冷了就会使用便宜一点的硬件进行存储，另外contention做了一些类似于FPGA的优化，减少本身CPU的开销。
6.云原生关系型数据库polar DB
云原生关系型数据库polar DB做了三层层解耦，serverless，多主架构和HTP的能力，其实以前很早的时候就做了计算和存储的分离，分离以后其实就是利用在云上资源是资源池化，资源池化以后计算和存储可以分别扩展，就不是一对一的关系了，分别扩展灵活性更大更节省资源，现在会将计算节点内存这一层面单独拿出来变成一层共享内存，这一层的好处是CPU和内存又进行了一次解耦，他们两个可以分别进行扩展，这种架构首先云上池化包括内存的池化，CPU的磁化，云化是有要求的，另外依赖于RDMA包括最新推出的两百g的RDMA网络才能很好的应对buffer pool，江西扩展成上t或者10t水平的buffer pool，有了这个以后整个serverless的能力得到了很大的体现，各层之间都可以分别扩展，因为在云上用多少就可以付多少钱，在这种情况下减少了浪费，原来放置在一台机器上CPU满了但是内存没有满这就造成了浪费，现在分层进行解耦，分层的扩展，分层的计费
二、页面和元组
现在看一下页面和元组的介绍，前面主要是为了让大家能够了解存储有关的架构，些架构，其实想要实现都与这节课有关，例如要有解原组和页面的结构，要了解Buffer pool是如何进行管理的对其进行一些修改
1.my SQL InnoDB的段页式管理
元组比较典型的部分例如my SQL InnoDB的段页式管理，这种管理首先会有segment的概念，Segment中会有extent，Extend中再分成page，page中再分成row相当于会在segment里面加extent page，这种里面有几层，有几层以后管理就会有层次感，相对来讲，管理逻辑会更清晰但是同时代码复杂度也提高了，mySQL的代码里面有回滚段，有不同的segment，这些segment都有自己对应的结构，每一个结构都需要进行了解，相对来讲这部分会简化很多
2.XEngine的(Extent+Block)存储管理
XEngine底层是KV，KV的存储也是类似于行存虽然有extent，里面data Block相当于page里面，也是类似于row的方式管理，key是它的组件包括value的信息包括原数据也在其中做了一些管理，还有数据删除信息作为compare依据都是在其中的，加速访问In的信息
3.PG的页面结构
PG页面结构首先在PG文件中，文件中没有太多文件相关的头尾内容，主要是一个一个8k来切，这种情况其实与mySQL比起来代码复杂度会清晰很多，进入8k页以后，8k中有配置的Header，Header中会保存页面的基本信息，页面尾部有special为了判断尾部是否被写坏是用来做检测的标志，当从后面加入一个tuple对应前面会生成一个item，这样他们之间有一个连线，前面扩展item后面扩展tuple，最终他们两个都到中间就不能进行扩展了，page的孩子首先有PD isn这是一个比较重要的结构，页面进行修改时对应的修改需要有日志，这就是日志的isn，这个isn决定了页面的新旧程度，之后有checksun信息，flag，low以及upper，low和upper相当于item的位置，他们两个在一间可能会知道他们之间的差距，如果太小就不能插数据了，一般包括orch都有检测或者一些参数的设置，如果中间的差值也就是水位如果偏低就不能修改了，页面占有率达到百分之多少就不能进行修改了
这里可以看到page header结构，isn checksun，upper相关的一些信息，也包括item信息，item信息中包括偏移，状态，状态到底是Normal还是indirect，hot会修改了以后一个tuple会指向另一个tuple，在这种情况下就会有hot的标记，这个其实就是管理page header的。
4.PG的原组结构
一个tuple中就是一个元组，元组首先有元组的头后面存储数据
所以前面是header，后面是存了各个字段的值，其中比较重要的是oid信息包括XMin，xmax创建史的事务ID和删除时的事务ID，创建时的CommandID删除时的CommandID，tuple ID在页面中的位置，字段的数量，标志的信息，空字段的信息都在header tuple data中保存还包括一些状态信息，这些状态信息都是用64切了很多状态位，每个状态位代表一个星期，对于存储引擎的改造每一个状态位都要进行了解利用好，如果想要新加一个状态位要先查看这个状态为是否有空缺，否则新加一个变量或者字段在这里影响比较大，因为本身对数据的结构内存的膨胀影响较大
三、buffer 管理
1.创建 buffer 管理结构
现在讲解一下buffer的管理，首先看一下buffer的原理PD buffer的管理首先有一个buffer的table，这其实是哈希表，哈希表下面buffer的描述符和buffer pool做映射，做快速的定位和查询，所以buffer的描述符和buffer pool是一一对应的，有一个描述符就有一个Buffer pool，Buffer pool相当于12345排，首先在启动PG会定义buffer pool的大小也就是共享内存有多大，Buffer pool的大小定义好以后确定了这里面可以切除多少buffer pool的数据页，切了多少数据页对应就会建多少个buffer description描述符进行描述Buffer pool里面要存的内容其实就是将数据页里的数据文件中的某一块buffer key定义页面大小，页面大小load到buffer中，其实就是将里面数据原封不动的读取进来这块内存，款内存里面的状态信息是在buffer description里面进行描述里面记录了一些相关信息，日志buffer与哪个文件的Buffer有关系这些信息都是在其中进行记录的，除了这个结构以外，还有free list链表结构，刚开始创建时会将所有的页面都创起来，所有的都是free list因为所有的buffer都没有加载相关的数据，如果现在要读取数据，例如读取表rdone某一个数据进行查询，这是一个数据文件里面包含了很多page，要将page加载到buffer pool，加载到buffer pool以后对应的描述符要进行修改，因为要变成一一对应的并且将相应关系附到哈希表中，这样在下次使用到这个page时就可以定位到是哪个表哪个位置对应的是现在所需要的buffer pool，这个数据被用到以后会将free list里面对应的信息删除，List会随着使用慢慢的变少，如果free list里面没有相关可用的页面要用到clock sleep算法，将buffer pool中的数据进行淘汰，是基本原理，下面查看对应的管理结构，首先在buffer pool包括describe，哈希表都是存在Share memory里面的，Share memory的创建利用MemoryAnd selfish创建内存和信号，创建内存之前首先会计算大小将大小所有创建的内存都计算出来，计算出来以后统一进行创建，计算时进入到buffer manager相关的内存，首先n buffer当时定义了有多少个buffer，定义了多少buff Pro就是多少buff，对应的每一个都要做Buffer describe做buffer的描述符申请这样的空间，之后进行catch line对齐操作，pg较新是为性能优化做的，新的PG做的主要几件事情是Cache line的对齐，原先是一个锁祝以后不能再进行访问了，现在将其切成小一点的锁，细粒度的锁减少锁冲突，PG最新版本做的优化主要是性能方面比较多，之后是数据块一些相关数据，另外一只free list在做buff以及里面哈希表对应的的petition一些计算和统计，统计完以后需要对其进行内存的计算，哈希表本身是做了t和buffer ID，Buffer ID是buffer pool中12345向下排的ID，Buffer tech是上面tag的信息是他们之间的映射关系，描述符中最重要的结构下面也会讲到，首先要将内存创建出来，第二部分是查看buffer描述符，查看pg11和旧一点的9.4，他们之间的差距还是挺大的
第一做了cache line的对齐，为了cache line对齐将io block这些锁移掉了，这里首先有tag,buffer tag包好了Real or not.有table space，data space以及Relation组成，这三个其实就唯一对应了表数据文件，oid有了以后就能查到对应的是哪个文件，文件是哪个表，表下面对应着folk number，folk number指的是对应的是数据文件，fsm文件，可见性文件对应的是文件类型，文件类型确定以后block number对应的是哪个block，文件有了以后通过定位到这个文件再定位到block number，这样就可以将某个唯一的block读取出来。变量定义的是包含了flag和refcount，use count，refcount和use count都是淘汰算法中用到的，下面看一下字段是如何进行定义的使用了18个字段，用的是refcount，第四个beet用的是use count，十个beet使用的是flag，flag有十个数位，第二个位是d类位，第三个是Minute位，第四个是正在进行io的位，所以这里面每一个beet都会进行很好的利用，在存储引擎做设计时就是要这样精打细算来实现这样才能产生较高效的访问，后面还有free next是将free list串起来，只要没有进行使用的buffer串到free list上，下面是content log再提取buffer访问内容时需要加这个锁，现在看一下buffer describe老的版本也就是9.4版本
对应的refcount，use count，Describe flag是分别进行保存的，包括io的lock也是放在这里面的，现在在进行buffer创建时lock都是单独进行创建的，变动还是比较大的，主要是与cache line有关，还包括小性能的优化，之后是mark bufferdirty如果页面进行了修改，修改以后要进行标记此页面做了修改，淘汰这个页面时要先落盘，进行标记很简单，类似于先将状态读取出来，读取以后设置了dirty的标志位，Buffer described下次进行使用的时候就知道是怎样的状态了。
2.获取buffer流程
比较重要的函数是read buffer common，最早在改write架构时要弄buffer pool改动是比较大的，首先会判断是否是extent，extent是在调用函数时读一个数据页，这个数据页在传入p new时知道要读取的是新的数据页，新的数据页会调取smgr存储的接口获取block number，在做共享存储版本架构设计时这种存储的函数需要跨机器到共享存储获取block number，类似于这种都会涉及到一些修改，包括 buffer alloc下一步会获取buffer的描述符查看页面是否存在，如果不存在要使用淘汰算法获取buffer，第一部使用buffer table的 look up是查黑表的过程，如果发现了在buffer pool需要获取Description，之后聘入buffer就可以使用了，等待buffer查看是否有其他队其进行io处理，然后会retain找到的buffer，如果buffer中不存在会利用get buffer利用free list或者 sleep获得buffer，首先会判断free list中是不是大于零有空前页，如果没有空前页利用buffer Description利用Crab算法进行页面，如果得到的页面存在并且是张页面这时会进行刷张，刷张之前要保证页面的isn是怎样的，页面的isn有没有落盘需要保证isn先落盘，张页需要进行刷盘flash buffer正在刷盘时调用的是存储相关的接口，然后会以新的buffer对应buffer的Description会产生变化要插入到哈希表中，这样就得到了新的buffer描述符，如发现就返回buffer ID，如果extent需要扩展新的页面使用零填充新的buffer页面，然后去调用存储的extent接口将文件写到页面的后面，如果buffer已经得到了，但是这个buffer之前没有读到需要的数据页没有读到buffer pool中这时要利用smgr read将磁盘中的数据页加载到buffer pool中再将加载后的buffer pool对应的描述符ID返回给用户，这就是获取buffer的过程。
四、淘汰算法
1.常用缓存淘汰算法
淘汰算法主要是在buffer管理时有满的时候，buffer用完了以后需要把buffer中不常用，淘汰代价最小的页面进行淘汰，这是基本的策略，常用算法有FIFO先进先出算法，LFU主要与频度有关，LRU与时间有关，2Q利用了FIFO和LRU的两个队列进行数据的淘汰，新的淘汰算法也都是类似于这种，recxency是不是最近使用过的，Frequent频率这两个信息一起决定应该淘汰哪个，将recently和frequent做了结合这样比较新的淘汰算法。
PG使用的是clock sweep算法，clock sweep算法将buffer看成一个环，环会有一个指针挨个判断环上的数据，依据是refcount和use count，refcount在今天正在使用肯定是不会进行淘汰的，如果引用的数等于零时曾经被使用的次数会起作用，例如refcount是零了但是use count原来是2会将其减1这样经过这样不停的处理，慢慢use count会变成0，变成0的时候发现refcount和use count都变成了0，此时这个页面就可以被淘汰了这样就符合了淘汰的条件，淘汰的控制结构有自己的stralogy保护，包含next buffer就是指针转的位置，first free buffer和last free buffer相当于将free list串了起来相当于free list的两个头数据，在使用buffer时首先会聘buffer就是增加了refcount用完了以后要安聘，安聘buffer时refcount会减一，最终如果大家都不使用ref凑你赶紧就变为了0，变成零以后才符合被淘汰的前提条件，另一个与refcount有关再用一次就会将refcount use count加一，加一以后慢慢use count就变大了，通过淘汰策略clock sweep算法慢慢的将use count减小到零的时候才能被淘汰掉。
2.代码
以上就是今天的内容，再来查看一下代码
Create memory函数用来创建buffer pool，这个函数相当于在post master启动时就会进行创建，创建共享内存时，首先利用方法将size加起来利用size不断的加与共享内存有关的，加完以后进行调用进行shell memory的创建，创建时会调用一些share memory的函数，对于类似于pg这种多进程的架构其实共享内存的使用是很多的，例如一个进程经常想加开关进行控制，这个操作很简单，但是开关控制如果涉及多个进程同时访问的情况就需要考虑如何将它加到共享内存中加一个变量，有时一个变量也要加入到共享内存中计算机尺寸，都要使用这种方法，有时候可能看起来一个修改很简单，单个进程编程时加一个变量就可以控制它判断就可以了，但是在这里需要考虑怎么样添加全局Share memory变量才能保证多个进程可以同时访问，访问时要考虑如何对其进行锁保护，与进程有关是很复杂的，与buffer有关的也演示了一部分，Buffer的memory size是n buffer，buffer的描述符从block size在层一下，最后类似于这样的结构保存哈希表的结构也需要进行创建，包括锁需要每一个buffer中对应创建锁，这是创建的过程，创建好以后read buffer是真正读数据页的，读取数据页时的参数如下
先是relation对应的folk number，block number都存在了在这种情况下首先能将这些转化成add tag读取信息，首先会传入进来获取对应的block number，如果需要extent扩展时需要知道原来有多少页才能再后面扩展，这里也可以看到local的buffer是临时表的标志，正常情况下走的是buffer alloc，buffer alloc中构造了新的tag，tag相当于用了里面的node信息创建了extent信息，tag主要与文件的几个oid有关包括folk number和块的号，有了这个以后就唯一的对应了bucket数据页，唯一的数据页用buffer table 找一下，找到以后进行聘判断是否有io在进行访问，最后会返回回来。如果没有找到需要通过Switch获取buff，首先看free buffer是否大于零，到底有没有free buffer，如果有free buff从这里获取就可以，如果没有需要rent scrape算法，这个算法是利用了page信息循环的找buffer，转圈的时候判断refcount等于零，等于0以后判断user count如不等于0要减1，如果等于零，就将其返回回去，返回回去就是已经找到了可以被淘汰的page，找到了page以后原来的page可能对应有自己的buffer tag，但是新的page需要新的描述符，buffer淘汰要用来存储新的页面所以需要将新的页面信息加进去，如果找到了buffer pool就将其返回来，会做extent场景先赋零在进行页面的扩展，然后回read page最后将buffer的描述符返回去，无论什么情况，最终需要的数据页要么已经在磁盘中直接返回去或者没在磁盘中要找到页面淘汰一个页面或者是free list或者淘汰页面，将磁盘中的数据加载的页面再加描述服务返回来，这样就可以使用buffer pool里面的信息相当于page，page有了以后可以在里面找对应的tuple访问其中的内容。
回顾一下今天所讲的内容，先讲解了整体架构，为了让大家更好的了解什么是存储引擎以及在存储引擎中都会涉及到哪些方面的修改，之后简单的介绍了页面相关的布局包括MySQL x engine还有pg页面的布局以及对应的数据结构，原组的头和状态信息，之后介绍了buffer管理的几层结构分别是怎样的，buffer描述符是比较重要的盘中的页面和映射关系，之后是真正使用buffer时如何读取流程，最后讲解了一些常用的淘汰算法以及clock sweep如何利用评定的方式修改ref count和use count，最终获取ref count和use count都等于0符合条件被淘汰的页面。
