序

目前在公司 做元数据 治理平台，正好里面也涉及 借鉴mysql 数据库的东西

里面涉及

因为接入服务比较多，访问量比较高，还是有数据一致性问题的，这里不说 业务端的缓存 ，因为元数据的占用比较 大

内存数据 分为两种

1. 每个元数据节点都是存的全量数据
2. 每个元数据节点 存的是 部分数据

这两种都需要

这里就涉及向 rocketmq nacos mysql借鉴的部分

其中一个就是Mysql Buffer pool的设计

Mysql Buffe Pool

磁盘

从这可以看到 最后数据 一定是需要落地到 磁盘的，但是因为每次磁盘IO 太慢，肯定需要 中间缓存提升性能

这里就涉及2个点 一个是 内存中的操作 怎么保证一定能落到磁盘呢 这里涉及到wal 后面说

第二点 是 磁盘往内存中放数据，哪些部分是可以留在内存的，哪些是不能留在内存的？ 怎么区分呢？

首先简单想，如果让我们写代码 做磁盘的内存化 提升性能

内存大小

毕竟内存大小是有限制的，一定要在内存中保留经常使用的数据 ，提出不经常用的 （或者可以说是 就用了一次的，毕竟select 用完基本就不用了），这里可以用lru 这就是 lru链表的作用了

这里有三种，先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

这就是第一想法，每次操作 都是 从磁盘拿到内存，然后存个对应关系，这里有几个问题

1. 我需要知道 内存中 有没有空余的位置，有的话 位置在哪，没有的话 我需要替换掉哪个呢？

来一个free list 进行查询 就能知道有没有空余位置，有的话 直接给我一个地址，我就开始用就好

这里引用地址 在mysql 中叫控制块 和 缓存块的，free list 为什么存的是 控制块，而不是 缓存块，这里留一个疑问 后面回答

那如果没有 空闲位置，是不是我需要知道哪个是可以替换的，这个时候 就会再有一个列表，里面有热数据 （经常使用的数据） 和 静数据 （只用了少数几次的数据），然后从静数据 中拿一个位置

到这 初步能跑通了

为什么 free list 要用双向链表？

单向不行么？ 循环链表不行么？

首先数组和链表，因为 free list 是要经常insert/delete的 明显链表更适合。

关于删除的操作

在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

1. 删除结点中“值等于某个给定值”的结点；
2. 删除给定指针指向的结点。

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。

尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。

但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。

所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

所有肯定是用 这种双向链表

内存中 元数据 也可以使用这种方式进行处理 lru等操作，我是根据当前数据的大小判断的，如果小于某个限定值，我就全部缓存到内存中，如果大于某个限定值 开始这种 内存中存储部分 ，磁盘存所有的方式

那么你可能想问，这种根据大小 区分的方式 你又是从哪想到的？

我知道 你可能还想问 你怎么证明这个判断的真实性的？ 你不会百度知道的吧。。。但是打住，你控制下自己

磁盘为什么有 page的概念，直接要什么数据 直接给他返回不香么？

那是因为 id 基本都是自增的，查询了id =1 很大可能会查询 附近的数据，这样就可以直接从内存获取，提升性能了

其实这也是 为什么不能拿UUID 做主键的原因之一

但是对于元数据 系统这点基本就没有用了，没有规律可言 但是我是 根据操作步骤进行的 预先缓存 提升性能

回到元数据

上面说了这么说 元数据 系统中用了mysql的什么啊？

1. mysql的 内存 磁盘数据一致的方式
2. mysql的wal 保证一定落地到磁盘

虽然第二点 我们根据应用场景也用了 RocketMq的config 落地方式 写bak 然后替换

总结

内存中 元数据 也可以使用这种方式进行处理 lru等操作，我是根据当前数据的大小判断的，如果小于某个限定值，我就全部缓存到内存中，如果大于某个限定值 开始这种 内存中存储部分 ，磁盘存所有的方式

磁盘 Page 但是对于元数据 系统这点基本就没有用了，没有规律可言 但是我是 根据操作步骤进行的 预先缓存 提升性能

这第一篇就到这了，后面见