MySQL8.0数据字典实现一窥

1. "两级缓存+持久化"结构

整个MySQL 8.0的数据字典实现在数据字典对象分布上呈现

|--Dictionary_client

|--Shared_dictionary_cache

|--Storage_adapte

这种三级存储的方式。

1.1 Dictionary_client

Dictionary_client是整个数据字典的客户端，用户对于数据字典的操作都是通过该client实现的。

Dictionary_client中维护有三个map作为该客户端私有的缓存，如果能在私有缓存命中的话，就不需要去全局公有的Shared_dictionary_cache，甚至持久化存储中获取了。

• m_registry_uncommitted

client调用store/update接口时将object放到uncommitted map中

• m_registry_committed

事务提交后，object从uncommitted map移到committed map中

• m_registry_dropped

执行drop操作后，object移入dropped map

这三个map的类型都是Local_multi_map，本质是对std::map的封装。

每个client退出后，调用Auto_releaser的析构函数将每个map清空。

主要接口：

• acquire() acquire通过参数提供的各种类型的信息（name/id等）来组装查询的key。流程：
  1. acquire_uncommitted,从未提交map中查看是该对象是否处于未提交状态，如果是，则返回该未提交对象
  2. 从m_registry_committed中查看该对象是否处于已提交状态，如果是，那么这个对象可能被修改了，rename或者drop
  3. 该对象不存在于以上任一map，那就去全局的shared_dictionary_cache中去get
• store()
  1. 调用Storage_adapter的store接口
  2. 将操作对象从uncomitted_map移动至committed_map
• drop()
  1. 调用Storage_adapter的drop接口
  2. 将被drop的对象设置为失效
  3. 将被drop的对象放入dropped_map
• update()
  1. 通过object_id确认该对象确实存在
  2. 从uncommitted_map中看一下同一个client中是否已经修改过该对象
  3. 调用Storage_adapter的store接口
  4. 将该对象从uncommitted_map中移除

1.2 Shared_dictionary_cache

上面说到，在client的三个私有map中（极大）可能会有cache miss的现象，比如一个client中已commit的对象不可能被另一个client读到，这时候就要用到全局的缓存Shared_dictionary_cache，Shared_dictionary_cache本身也是map，30多张数据字典表各自维护一个map，其中存放的对象是Object_key + Element_cache,Element_cache是对数据字典对象的一层封装，目的在于可以统一管理所有类型的数据字典对象。以下是一个element_cache所包含的内容，实际上就是一个指向原数据字典对象的指针以及属于这个数据字典对象的key信息。

const T *m_object;   // Pointer to the actual object.
uint m_ref_counter;  // Number of concurrent object usages.

/*
  全局对象的 priamry key,一个ulonglong类型的id
  Primary_id_key Id_key;
*/
Key_wrapper<typename T::Id_key> m_id_key;      // The id key for the object.

/*
  全局对象的 name
  Item_name_key Name_key;
*/
Key_wrapper<typename T::Name_key> m_name_key;  // The name key for the object.

/* 
  辅助kye,暂时用不到
  Void_key Aux_key
*/
Key_wrapper<typename T::Aux_key> m_aux_key;    // The aux key for the object.

主要接口：

• get()：
  1. 通过key(Shared_multi_map->get())->找到返回
  2. 找不到调用get_uncached()从持久化存储中读取->找到则写回缓存(Shared_multi_map->put())
• get_uncached()：
  1. 调用Storage_adapter的get接口读持久化存储
• put()：
  1. 将element_cache放入相应的map，如果map中已经存在该element_cache，返回这个element_cache的引用，element_cache的引用计数加1
• drop()：
  1. 从map中移除element_cache
  2. element_cache中的object对象被释放，element_cache本身被放入资源池中，下次要分配element_map就从资源池中获取并初始化就可以重新使用
• dump()：
  1. 调试接口，打印map中的所有元素。所有的map都有这个接口，在进行调试的时候十分有用。

Shared_dictionary_cache基于一个最重要的数据结构便是Shared_multi_map，Share_multi_map继承自Multi_map_base（与上述client的Local_multi_map一致，再往上找的话就是std::map），通过扩展了Autolocker内部类实现multi_map的线程间同步，以及map中元素的生命周期管理。

To ensure that the mutex is locked and unlocked correctly. To delete unused elements and objects outside the scope where the mutex is locked.

重要成员变量：

 /*
   m_free_list实际上维护了一个LRU队列，引用计数归零的element
   说明当前没有被使用，因此被放到free_list的尾部。可以看作是map的
   缓存。
 */
 Free_list<Cache_element<T>> m_free_list;  // Free list.
 /*
   1.在进行put操作时，我们需要根据给定的object创建新的element，
   此时并不知道cache中是否有该对象，执行get之后，如果找到了该element，
   那么该element就应该被丢弃，我们不会把它直接删除，只要m_element_pool
   还有空间，就会把它先存到pool中，供下次使用。
   2.在进行remove操作时，被remove的element也会被存入element_pool中。
 */

 std::vector<Cache_element<T> *> m_element_pool;  // Pool of allocated elements.
 

其中重要的成员函数就是对map的读写：

1. template <typename K>
   Cache_element<T> *use_if_present(const K &key);
/*
  对应的其实就是get，通过key返回被封装成Cache_element的object的指针，
  返回指针的同时该element对象的引用计数+1。
*/


2. void remove(Cache_element<T> *element, Autolocker *lock);
/*
  调用父类Multi_map_base的remove_single_element()方法。
*/


3. void add_single_element(Cache_element<T> *element)方法。
/*
  而put则直接调用父类Multi_map_base的add_single_element()方法。
*/

内部类 Autolocker

class Autolocker {
   private:
    // Vector containing objects to be deleted unconditionally.
    typedef std::vector<const T *, Malloc_allocator<const T *>>
        Object_list_type;
    Object_list_type m_objects_to_delete;

    // Vector containing elements to be deleted unconditionally, which
    // happens when elements are evicted while the pool is already full.
    typedef std::vector<const Cache_element<T> *,
                        Malloc_allocator<const Cache_element<T> *>>
        Element_list_type;
    Element_list_type m_elements_to_delete;
    
    ...
}

注： m_objects_to_delete->object对象不复用，用完即删。m_elements_to_delete->element对象放回element_pool，下次使用时直接从pool中取出init后继续使用。

1.3 Storage_adapter(读写InnoDB)

既然是cache就有可能产生cache miss，这里的cache miss指的是通过特定的key在Shared_dictionary_cache维护的map实例中找不到目标对象，这时候就要调用Storage_adapter的接口来读取持久化存储中的数据对象了（MySQL数据字典持久化存储在InnoDB）

主要接口：

• core_get()
  1. 从m_core_registry(一个专门存放系统数据字典对象的map)中获取core_object(如dd_properties/tables之类的数据字典表)
• core_store()
  1. 存储一个系统表core_object对象
• core_drop()
  1. 删除一个系统表core_object对象
• get()
  1. 先通过core_get找系统表core_object对象
  2. 在bootstrap::Stage::CREATED_TABLES阶段之前的所有查询都认为数据字典对象不存在
  3. 打开一个读取数据字典的事务，去读取持久化存储，如果找到则将元组中所含的数据字典信息恢复成内存object
• store()
  1. store接口兼有update/insert功能，它会先查一次主键，存在就调用update逻辑，不存在则调用insert逻辑
• drop()
  1. delete一条表对象记录（及与之相关的所有记录）

2. 查询

2.1 key的定义

现在我们知道数据字典对象分布在dictionary_client/Shared_dictionary_cache/Storage_adapter中，那么查询中如何获取相应的数据字典对象呢？

一二级cache都是map结构，所以要拿数据字典对象只要知道key就可以，数据字典所有的key都继承自Object_key,所有类型定义在sql/dd/impl/raw/object_keys.h.

以Primary_id_key为例：每个数据字典表都有一个id列作为主键，而Primary_id_key就是用于基于id的读操作

• Primary_id_keyclass Primary_id_key : public Object_key { public: Primary_id_key() {}

Primary_id_key(Object_id object_id) : m_object_id(object_id) {}

// Update a preallocated instance.

void update(Object_id object_id) { m_object_id = object_id; }

public:

virtual Raw_key *create_access_key(Raw_table *db_table) const;

virtual String_type str() const;

bool operator<(const Primary_id_key &rhs) const {

return m_object_id < rhs.m_object_id;

}

private:

Object_id m_object_id;

};

Primary_id_key只有一个成员变量m_object_id，其对应的就是各个数据字典表的主键。

主要接口：

• update()：
  1. 用于更新Primary_id_key
• create_access_key()：
  1. 将当前的Primary_id_key组装成Raw_key，Raw_key将会在下文介绍
• str()：
  1. 调试接口，打印key信息
• operator<()：
  1. 重载<，用于在map中判断key的大小关系

2.2 从map中查询

从map中查询比较简单，因为已经在key中已经重载了比较符，只要调用相应的get接口（实际上是map的find接口）就可以。

2.3 从持久化存储中查询

从持久化中查找信息需要重新构建key，由此引出Raw_key/Raw_record/Raw_table的概念。

struct Raw_key {
  uchar key[MAX_KEY_LENGTH];
  int index_no;
  int key_len;

  key_part_map keypart_map;

  Raw_key(int p_index_no, int p_key_len, key_part_map p_keypart_map)
      : index_no(p_index_no), key_len(p_key_len), keypart_map(p_keypart_map) {}
};

Raw_key是一个简单的结构体，可以把它看作是去查询持久化存储索引的key，需要关注的有两个变量。

• index_no：需要查询的索引是表上的第几个索引，所有数据字典表的主键索引都是第一个。
• keypart_map：一个key中可能包含了好几列的信息，MySQL使用bitmap(小端存储)的形式来标记到底会用到哪几列的。比如，一个key中包含了三列：

a    b    c
1    0    0   // keypart_map = 1,只用第一列a
1    1    0   // keypart_map = 3,用a/b两列
1    0    1   // keypart_map = 5,用a/c两列
...

这个在基于复合key进行范围扫描的时候非常有用。

Raw_table维护了一个待访问数据字典表的table_list，从这里面可以拿到一个TABLE对象，进而可以通过它来读写持久化中的元组信息(TABLE->record0).

主要接口：

• find_record()：
  1. 通过key从持久化存储中找到一条数据，并将数据填写到Raw_record
• prepare_record_for_update()：
  1. 读出一条已存在的record，并将更新的信息写入TABLE->record0
• prepare_record_for_insert()：
  1. 构建一条新的Raw_record(Raw_new_record)
• open_record_set()：
  1. 初始化一次扫描，并产生一个符合条件的记录结果集。

Raw_record是一个持久化元组buffer和可操作内存对象的一个转换载体。

主要接口：

• update()：
  1. 实际上就是调用handler的ha_update_row接口，数据由Raw_table的prepare_record_for_update提供
• drop()：
  1. 实际上是调用handler的ha_delete_row接口
• store()：
  1. 将数据存入到record的TABLE对象的filed中
• read_xx()：
  1. 将数据从TABLE对象的field中按类型读取出来
• insert()(Raw_new_record的成员，Raw_record的子类)：
  1. 实际上就是调用handler的ha_write_row接口，数据由Raw_table的prepare_record_for_insert提供

Raw_record_set是由Raw_table::open_record_set产生的结果集，可以调用其提供的next()接口实现结果集的遍历。

主要接口：

• current_record()：
  1. 指向当前Raw_record
• next()：
  1. 指向下一条Raw_record

4.代码分布及类的继承关系

4.1 代码分布

• 数据字典相关代码位于sql/dd
• 数据字典表定义（表结构/索引/约束等）代码位sql/dd/impl/tablesundefinedtables路径下面主要是对数据字典表的定义，其中.cc文件就是创建表的定义，如tables.cc,其中就定义了tables这张数据字典表是如何创建的，包括表名/列的定义/索引的定义等；而与之对应的tables.h中则是一些枚举类型，用来表示各个列/索引在表中的相对位置。
• 对数据字典对象进行相应的操作代码位sql/dd/impl/typesundefinedtypes路径下面实现了各个数据字典表从内存对象到持久化存储相互转换的内容，如restore_attributes(从持久化存储中读出数据拼出表的内存对象)store_attributes(将内存对象分别写入持久化数据字典)，serialize/deserialize(内存对象到sdi文件之间的相互转换)等，其命名为xx_impl.h/xx_impl.cc
• 内存对象到持久化存储的交互，读写存储引擎等代码位于sql/dd/impl/cache（包括key的定义等）

4.2 主要类的继承关系

数据字典表2

namespace dd {
    Weak_object
        Entity_object   
            Dictionary_object
                Tablespace
                Schema
                Event
                Routine
                    Function
                    Procedure
                Charset
                Collation
                Abstract_table
                    Table
                    View
                Spatial_reference_system
                Index_stat
                Table_stat
            Partition
            Trigger
            Index
            Foreign_key
            Parameter
            Column
        Partition_index 
        Partition_value
        View_routine
        View_table
        Tablespace_file
                Foreign_key_element
        Index_element
        Column_type_element
        Parameter_type_element
    Object_table
        Dictionary_object_table
    Object_type
    Object_table_definition   
}

数据字典缓存2

dd::cache {
    dd::cache::Dictionary_client
    Object_registry
    Element_map
    Multi_map_base
        Local_multi_map
        Shared_multi_map
    
    Cache_element
    Free_list
    Shared_dictionary_cache
    
    Storage_adapter
}

参考

[1] https://note.youdao.com/yws/public/resource/d73e1962c7f00aadd4df680f2e9d1722/xmlnote/18D8F2ECF3CD470FA932DA04FC6346AA/5481

[2] https://yq.aliyun.com/articles/61286

[3] https://blog.51cto.com/14136767/2334464

数据字典脑图