RandomLog: MySQL Query cache笔记


  有点麻烦,有点难懂.
  尽管如此,还是记下目前所理解的大致情况.

  首先是两个数据结构.


// sql/sql_cache.h
struct Query_cache_memory_bin
{
  Query_cache_memory_bin() {}                 /* Remove gcc warning */
#ifndef DBUG_OFF
  ulong size; //基本的size大小,实际上,free_blocks存放的接近size大小的block.大于前一个bin而小于后一个bin
#endif
  uint number; // free_blocks 里的数量
  Query_cache_block *free_blocks; //存放相似size大小的block

  inline void init(ulong size_arg)
  {
#ifndef DBUG_OFF
    size = size_arg; 
#endif
    number = 0; 
    free_blocks = 0; 
  }
};

struct Query_cache_memory_bin_step
{
  Query_cache_memory_bin_step() {}            /* Remove gcc warning */
  ulong size; //bin的大小
  ulong increment;  //bin之间的便宜量
  uint idx;  //bin群中,第一个关联此step的下标
  inline void init(ulong size_arg, uint idx_arg, ulong increment_arg)
  {
    size = size_arg;
    idx = idx_arg;
    increment = increment_arg;
  }
};


  query cache的大概结构式这样的.
+----------------------------------------------------+
| step array 当作cache的一级索引                          |
|     存放的主要信息是某一个size大小的bin群起始的位置偏移  |
+----------------------------------------------------+
| bin array 当作cache的二级索引                           |
|     存放的主要是size大小的bin群组                       |
+----------------------------------------------------+
|  实际的cache 区域                                        |
+----------------------------------------------------+

  对于cache的step和bin的一些换算关系如下
  current_bin_count = ( pre_bin_count + QUERY_CACHE_MEM_BIN_PARTS_INC ) * QUERY_CACHE_MEM_BIN_PARTS_MUL;
   
  简单地说,在一级索引step里,下级cache单位块的数量按上级数量的基础,加上一定的增量,以某种倍数增长.
  
  至于大小方面,有
  current_bin_size = pre_bin_size >> QUERY_CACHE_MEM_BIN_STEP_PWR2
  也就是上级cache的单位块按照一定数量递减.

  查看源代码计算一下,可以知道,
  current_bin_count * current_bin_size <= pre_bin_size.
  意思是,在进行进一步分块的时候,尽管块的数量增加了,但是总量还是小于等于上一级的块的大小.

  接着,要提提实际cache的分布了.

  源代码里有这么一个图.
sql/sql_cache.cc
For example:
 query_cache_size>>QUERY_CACHE_MEM_BIN_FIRST_STEP_PWR2 = 100,
 min_allocation_unit = 17,
 QUERY_CACHE_MEM_BIN_STEP_PWR2 = 1,
 QUERY_CACHE_MEM_BIN_PARTS_INC = 1,
 QUERY_CACHE_MEM_BIN_PARTS_MUL = 1
 (in followed picture showed right (low) bound of bin):
      |       100>>1  50>>1       |25>>1|
      |  |         |       |  |  |
      | 100  75 50  41 33 25  21 18 15| 12  | -  bins right (low) bounds
      |\---/\-----/\--------/\--------|---/ |
      |  0     1 2    3  |     | - steps
       \-----------------------------/ \---/
  
  这图一开始也没明白.
  后来似乎懂了.
  假设cache块的大小事100.
  按照公式计算,每次分块,大小减去一半,数量按照公式计算取整.
  50>>1是一次分块,得到块的大小是25.根据公式计算分为( 2 + 1) * 1 = 3块.
  于是从25开始,以8为增量划分块.

  增量的计算也是有公式的.
  inc = (prev_size - mem_bin_size) / mem_bin_count
  以50>>1这个例子来说.
  pre_size = 50 , men_bin_size = 25 , men_bin_count = 3
  所以增量是8.

  如何解释这个增量公式呢.
  首先,每次mem_bin_size是折半递减的.
  那么,从内存分布上来说,prev_mem_bin_size的大小恰好是当前bin群起始的偏移量.
  只要明白这就那个增量公式就好理解了.
  先得到bin群的偏移量起点,然后计算当前bin大小的偏移量,就能正确分布了.

  但,既然在bin的结构里已经有了size这个成员用来表示bin的大小了,那何必用inc来计算偏移呢.
  
  挣扎了几天给自己的解释是,这是它查找bin的算法决定的.

  注意到代码里的注释部分,有这么句话:
  When a new block is allocated we find most suitable memory block
(minimal of >= required size). If such a block can not be found, we try
to find max block < required size 

  也就是在寻找合适的bin的时候,他会后弦尝试寻找合适大小的bin块,当找不到的时候,会在不满足大小的最大的bin群里寻找.
  那么,既然大小不满足,为什么要向小的群里找而不是大的群里找呢.

  看它寻找bin的算法.


// sql/sql_cache.cc
uint Query_cache::find_bin(ulong size)
{
  DBUG_ENTER("Query_cache::find_bin");
  // Binary search
  int left = 0, right = mem_bin_steps;
  do
  {
    int middle = (left + right) / 2;
    if (steps[middle].size > size)
      left = middle+1;
    else
      right = middle;
  } while (left < right); //采用折半查找的方式,在step数组里寻找合适的位置.按照降序排列
  if (left == 0) 
  {
    // first bin not subordinate of common rules
    DBUG_PRINT("qcache", ("first bin (# 0), size %lu",size));
    DBUG_RETURN(0);
  }//left是不满足size的最大块组,即,应该是满足点的右方
  uint bin =  steps[left].idx - 
   (uint)((size - steps[left].size)/steps[left].increment);
  //idx可能是step结束的bin的下标.因此后半部计算的是size多出bin_size部分占的大小.也就是说,其实是从小于的step部分取出来的.
  DBUG_PRINT("qcache", ("bin %u step %u, size %lu step size %lu",
   bin, left, size, steps[left].size));
  DBUG_RETURN(bin);
}


  过程是寻找不满足大小的第一个bin群(bin群按照降序排列).
  此时,size必然是大于left的最小大小,但是小于right的最小大小.

  因此,只能在left的群组里以增量方式寻找合适的大小.

  这样,这个有些古怪的cache结构及大致记录完毕了.

  总结一下,其实或许应该称这个cache结构拥有二层索引.
  第一层是一个step范围索引,索引了某个区间范围的bin组.
  第二层是一个bin,增量范围索引,索引了bin组内,各个增量的cache快.
  +-----+
  |     | <---step数组     +----------------------+
  +-----+                 | size = bin           |  <--- bin 数组
  |size |  =============> +----------------------+
  +-----+                 | size = bin + incre   |
  |     |                 +----------------------+
  |     |                 |  ....                +
  |     |                 |                      |
  +-----+                 +----------------------+
  
  bin里各自维护了各自大小的block链表.

RandomLog

2009-04-26

MySQL Query cache笔记

没有评论:

发表评论

爽文