我的书签
添加书签
移除书签简介
在MySQL8.0中增加了一个新的数据结构叫做Link_buf，它是一个无锁的数据结构，这个数据结构主要用于redolog以及buffer pool的flush list.
这个数据结构简单来看就是一个拥有固定大小的数组，而对于InnoDB使用来说里面保存的就是写入log buffer或者加入到flush list的数据的大小.数组的每个元素可以被原子的更新.
由于在8.0种写入log buffer会有空洞的产生，因此这个数据结构就用来track当前log buffer的写入情况,也就是说每次写入的数据大小都会保存在linkbuffer中，而每次写入的位置通过start lsn来得到(hash), 假设有空洞(某些lsn还没有写入)，那么它对应在linkbuffer中的值就是0,这样就能很简单的track空洞.
最后要注意的是这个数据结构的前提就是LSN是一直增长且不会重复的.因此在InnoDB中只在redolog中使用.
之后在分析redolog的时候，我们可以详细的看到这个数据结构的使用.
源码分析
核心字段
我们先来看这个数据结构的核心字段.
- Distance 这个累心表示了我们的Link_buf所包含的内容的类型(一般是lsn_t).
- m_capacity 表示Link_buf的大小.
- m_links所有的内容都是保存在这里(也就是一个动态数组).
- m_tail表示当前buffer的结尾(这里的结尾的意思是第一个空洞的位置,也就是可以保证m_tail之前都是连续的).
1. template <typename Position = uint64_t>
2. class Link_buf {
3. public:
4. typedef Position Distance;
5. .....................................
6. */** Capacity of the buffer. */*
7. size_t m_capacity;
9. */** Pointer to the ring buffer (unaligned). */*
10. std::atomic<Distance> *m_links;
12. */** Tail pointer in the buffer (expressed in original unit). */*
13. alignas(INNOBASE_CACHE_LINE_SIZE) std::atomic<Position> m_tail;
14. };
 
构造函数
这里构造函数就是根据传递进来的capacity,创建对应大小的数组(m_links),然后初始化数组的内容.
1. template <typename Position>
2. Link_buf<Position>::Link_buf(size_t capacity)
3. : m_capacity(capacity), m_tail(0) {
4. if (capacity == 0) {
5. m_links = nullptr;
6. return;
7. }
9. ut_a((capacity & (capacity - 1)) == 0);
11. m_links = UT_NEW_ARRAY_NOKEY(std::atomic<Distance>, capacity);
13. for (size_t i = 0; i < capacity; ++i) {
14. m_links[i].store(0);
15. }
16. }
  
添加内容
add_link函数主要是用来将将要写入的数据的在lsn中的起始以及结束位置进行保存.流程如下。
- 首先根据from计算当前的写入lsn应该在数组的那个位置.
- 然后保存写入的大小到当前的slot.
1. template <typename Position>
2. inline void Link_buf<Position>::add_link(Position from, Position to) {
3. ut_ad(to > from);
4. ut_ad(to - from <= std::numeric_limits<Distance>::max());
6. const auto index = slot_index(from);
8. auto &slot = m_links[index];
10. ut_ad(slot.load() == 0);
12. slot.store(to - from);
13. }
slot_index函数就是用来计算slot，计算方式很简单，和数组的大小取模，这里或许有疑问了，如果当前的slot已经被其他的lsn占据了应该怎么办？这里的解决方式就是通过has_space进行判断.
1. template <typename Position>
2. inline size_t Link_buf<Position>::slot_index(Position position) const {
3. return position & (m_capacity - 1);
4. }
判断空间
has_space函数就是用来判断对应的position是否已经被占据.
1. template <typename Position>
2. inline bool Link_buf<Position>::has_space(Position position) const {
3. return tail() + m_capacity > position;
4. }
advance_tail_until
这个函数用来更新m_tail字段，m_tail字段之前解释过，主要是为了保证它之前的slot都是连续的.
1. template <typename Position>
2. template <typename Stop_condition>
3. bool Link_buf<Position>::advance_tail_until(Stop_condition stop_condition) {
4. auto position = m_tail.load();
6. while (true) {
7. Position next;
9. bool stop = next_position(position, next);
11. if (stop || stop_condition(position, next)) {
12. break;
13. }
15. */* Reclaim the slot. */*
16. claim_position(position);
18. position = next;
19. }
21. if (position > m_tail.load()) {
22. m_tail.store(position);
24. return true;
26. } else {
27. return false;
28. }
29. }
而上面的代码可以看到每次都会读取next_position,这个函数用来返回下一个slot是否为0,如果是0则返回true，也就是说已经到达空洞.
1. template <typename Position>
2. bool Link_buf<Position>::next_position(Position *position*, Position &*next*) {
3. const auto index = slot_index(position);
5. auto &slot = m_links[index];
7. const auto distance = slot.load();
9. ut_ad(position < std::numeric_limits<Position>::max() - distance);
11. next = position + distance;
13. return distance == 0;
14. }
