阿里巴巴DBA,原去哪儿网DBA。专注于MySQL源码研究、DBA运维、CGroup虚拟化及Linux Kernel源码研究等。 github:https://github.com/HengWang/ Email:king_wangheng@163.com 微博 :@王恒-Henry QQ :506437736
分类: Mysql/postgreSQL
2012-12-16 22:23:06
目的
MySQL源码中,LF_DYNARRAY数据结构是应用于LF_PINS和LF_HASH数据结构的一种特殊数据结构。该结构不同于DYNAMIC_ARRAY动态数组结构物理分配和逻辑操作,而是一种层级分配管理方式进行组织,对于稀疏、非连续的数组存储可以有效的提高空间利用率。
数据结构
LF_DYNARRAY相关的数据结构定义在mysql源码的include/lf.h和mysys/lf_dynarray.c文件中,具体定义如下所示:
#define LF_DYNARRAY_LEVEL_LENGTH
256 #define LF_DYNARRAY_LEVELS 4 typedef struct
{ void * volatile level[LF_DYNARRAY_LEVELS]; uint size_of_element; my_atomic_rwlock_t lock; } LF_DYNARRAY; |
其中,level是一个数组指针,level[i]是LF_DYNARRAY每个层分配的首地址;size_of_element是存储的每个元素的大小;lock是原子读写锁变量,用于并发控制读写操作。LF_DYNARRAY_LEVELS表示总的层级数,默认为4;LF_DYNARRAY_LEVEL_LENGTH表示每个数据块的大小,默认为256个字段长度。
源码实现
LF_DYNARRAY数据结构的实现是一种层级关系,level[0]存储实际的数据块,level[1]存储指向数据块的指针,level[2]存储指向数据块指针的指针,依此类推。在分配存储空间时,由level的上层往下一次分配,即从level[3]开始往level[0]分配数据块。查找存储的数据时,也是通过上层逐级往下查找。
具体的层级架构如下所示:
_lf_dynarray_lvalue()函数
_lf_dynarray_lvalue()函数时返回给定idx处的内存地址,如果该地址不存在,则调用内存分配函数进行分配。具体的处理逻辑是:首先定位idx的搜索层次,通过索引数组的常量值来定位具体的值;其次,根据搜索层次,逐层查找具体的“索引”(指向下一级指针的指针),如果不存在,则先内存分配该“索引”内存块;最后,返回数据块中的idx的地址,如果数据块不存在,则先分配数据块的内存空间,然后返回idx的地址指针。处理流程图如下所示:
_lf_dynarray_lvalue()流程图
从结果可以看出,查找遍历可以通过递归的方式进行。并且MySQL也是这么实现的,如_lf_dynarray_iterate()函数。
由于其他处理函数都相对较为简单,因此,再次不做详细的分析和解释,通过源码即可很清晰的了解LF_DYNARRAY数据结构的相关操作时如何处理的。
结论
LF_DYNARRAY数据结构及其相关操作,通过层级分配管理方式,可以提高稀疏的非连续内存空间的利用率。在MySQL数据库中,这种需求较少,仅在LF_HASH扩展HASH数据结构中和PINS数据结构中使用。具体的使用情况,可以参考对应数据结构的分析。