PG内核解读-第3节存储管理1
一、主流存储引擎架构和原理
目前，在选择存储引擎时，主要看性能和性价比。如上图所示，最快的是CPU Registers，然后是CPU Caches，Main Memory，Flash Disk以此类推。
同一件事CPU L1 Cache Ref的完成时间是0.5ns，Tape Archives完成的时间是31.7年。所以存储引擎间，性能差距非常大。
接下来，讲一讲。存储引擎访问的原理。数据存储在磁盘上，磁盘里的数据一般以page或block的啊形式存在。page和block的页面在8k到64k之间。
用户在使用数据时，一般会创建一个Buffer Pool，把数据缓存到内存里。从而避免数据访问从磁盘读取，加速磁盘运行。当内存不够时，会淘汰不常用的数据。
随着时代的发展，基于上述原理，扩展出了Cache Fusion架构，如上图所示。十年前，大家通常会使用Cache Fusion，同时在多个节点修改数据。
上图是PolarDB共享存储架构，节点间的数据通过日志进行传递。目前，PolarDB共享存储架构已经开源。
接下来，讲一讲XEngine的LSMTree架构。内存里的Active Memtable主要管理并更新热数据。当数据逐渐变成不可修改的Memtable，经过compactions变不同级别的文件，以Extent方式进行管理。
云原生关系型数据库PolarDB综合了三层解耦，Serverless，多主架构，HTAP。当计算存储分离之后，在云上将资源池化，计算存储可以分别扩展，进一步节省资源。
目前，计算节点的内存层变成共享内存，CPU和内存通过解耦，可以分别扩展。节点数量按需自动横向扩展，线性扩展事务处理和数据分析能力，最大化资源利用率，降低客户成本。
二、页面和元组
接下来，介绍一下页面和元组。如上图所示，MySQLInnoDB通过段页式进行管理。segment包含了extent，extent包含了page，page包含了row。MySQLInnoDB的管理逻辑更清晰，代码更复杂。
XEngine拥有类似于MySQLInnoDB的结构，它通过Extent和Block的方式进行存储管理。
接下来，讲一下PG的页面结构。PG的页面结构相比MySQL的代码更清晰。8k里配置了Header，用来保存页面的基本信息。页面尾部的special标志，用来判断或检测。当增加一个Tuple时，会生成一个item。
Header有一个pd_lsn，在修改页面时，需要修改对应的日志。pd_lsn决定了页面的新旧程度。
如上图所示，一个元组包括一个Header，以及各个字段的值。在Header里，元组的OID代表对象ID（可选）；xmin代表创建交易id；xmax代表销毁交易id；cmin代表创建命令id；cmax代表破坏命令id；ctid代表元组id（页面/项目）；natts代表属性数；infomask代表元组标志；hoff代表元组头的长度；bitsbit表示NULL的位图。
三、Buffer管理
PG Buffer的Buffer table，相当于一个哈希表，映射Buffer的描述符和Buffer pool，从而快速定位查询。在启动PG时，会定义Buffer pool的大小，从而确定了Buffer pool的数据页。
首先，Buffer pool，descriptors，哈希表等，都存在SharedMemory里。创建内存之前，会计算大小，然后统一进行创建。
接下来，讲一讲Buffer的描述符。PG11的bufferDesc，为了cache line对齐，将io lock单独管理，从而实现高效访问。
上图是Bufferer的访问流程。其中，比较重要的函数是ReadBuffer_common。首先，isExtend会判断是否扩展新页面。通过获取页面编号，扩展新页面。
然后，BufferAlloe会获取buffer描述符，查找页面是否存在，不存在则用淘汰算法获取buffer。
如果发现在bufferpool中存在fbuf hash table,通过bufd获取buffer描述符，然后返回对应的buf描述符。
如果bufferpool不存在，可以利用Freelist或cocksweep获取可用buffer。
如果是脏页，则通过脏页刷盘，调用存储写buffer接口。然后，插入新的buf描述符到hash表，获取新的buffer描述符。
如果需要扩展新页面，则使用0填充新页面，调用存储接口写贝面到文件。
四、淘汰算法
接下来，介绍一下淘汰算法。当Buffer用完后，需要淘汰Buffer里不常用的页面。常用的策略是FIFO，即先进先出。
LFU淘汰一定时期内被访问次数最少的页面，以次数作为参考。LRU淘汰最长时间未被使用的页面，以时间作为参考。
2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。新的淘汰算法CAR，通过Frequency和Recency作为参考。
PG使用ClockSweep算法，把Buffer看成一个环，通过指针判断环上的数据。ClockSweep通过REFCOUNT和USAGECOUNT，实现整个淘汰过程。Buffer中淘汰页面代码的引用数为O，使用数减1，使用为O可淘汰。
函数CreateSharedMemory在post master启动时，会创建共享内存。首先，利用size添加所有的共享内存，然后创建SharedMemory。淘汰算法就是把磁盘里的数据加载到页面，再返回描述符，访问对应的内容。
