Mysql源碼學習——沒那麼簡單的Hash

 

 

Hash鏈表的應用比較常見,其目的就是為瞭將不同的值映射到不同的位置,查找的時候直接找到相應的位置,而不需要傳統的順序遍歷或是二分查找,從而達到減少查詢時間的目的。常規的hash是預定義一定的桶(bucket),規定一個hash函數,然後進行散列。然而Mysql中的hash沒有固定的bucket,hash函數也是動態變化的,本文就進行非深入介紹。

 

 

 

 

基本結構體

 

    Hash的結構體定義以及相關的函數接口定義在include/hash.h和mysys/hash.c兩個文件中。下面是HASH結構體的定義。

 

typedef struct st_hash {

  size_t key_offset,key_length;     /* Length of key if const length */

  size_t blength;

  ulong records;

  uint flags;

  DYNAMIC_ARRAY array;              /* Place for hash_keys */

  my_hash_get_key get_key;

  void (*free)(void *);

  CHARSET_INFO *charset;

} HASH;

 

成員名 說明
key_offset hash時key的offset,在不指定hash函數的情況下有意義
key_length key的長度,用於計算key值
blength 非常重要的輔助結構,初始為1,動態變化,用於hash函數計算,這裡理解為bucket length(其實不是真實的bucket數)
records 實際的記錄數
flags 是否允許存在相同的元素,取值為HASH_UNIQUE(1)或者0
array 存儲元素的數組
get_key 用戶定義的hash函數,可以為NULL
free 析構函數,可以為NULL
charset 字符集

 

 

<font size="4"> </font><font size="3">HASH結構體裡面包含瞭一個動態數組結構體DYNAMIC_ARRAY,這裡就一並介紹瞭。其定義在<em><strong>include/my_sys.h</strong></em>中。</font>

typedef struct st_dynamic_array

{

  uchar *buffer;

  uint elements,max_element;

  uint alloc_increment;

  uint size_of_element;

} DYNAMIC_ARRAY;

成員名 說明
buffer 一塊連續的地址空間,用於存儲數據,可以看成一個數組空間
elements 元素個數
max_element 元素個數上限
alloc_increment 當元素達到上限時,即buffer滿時,按照alloc_increment進行擴展
size_of_element 每個元素的長度

 

 

 

初始化函數

 

   Hash初始化函數對外提供兩個,my_hash_init和my_hash_init2,其區別即是否定義瞭growth_size(用於設置DYNAMIC_ARRAY的alloc_increment)。代碼在mysys/hash.c中。

 

#define my_hash_init(A,B,C,D,E,F,G,H) \

          _my_hash_init(A,0,B,C,D,E,F,G,H)

#define my_hash_init2(A,B,C,D,E,F,G,H,I) \

          _my_hash_init(A,B,C,D,E,F,G,H,I)

 

/**

  @brief Initialize the hash

 

  @details

 

  Initialize the hash, by defining and giving valid values for

  its elements. The failure to allocate memory for the

  hash->array element will not result in a fatal failure. The

  dynamic array that is part of the hash will allocate memory

  as required during insertion.

 

  @param[in,out] hash         The hash that is initialized

  @param[in]     charset      The charater set information

  @param[in]     size         The hash size

  @param[in]     key_offest   The key offset for the hash

  @param[in]     key_length   The length of the key used in

                              the hash

  @param[in]     get_key      get the key for the hash

  @param[in]     free_element pointer to the function that

                              does cleanup

  @return        inidicates success or failure of initialization

    @retval 0 success

    @retval 1 failure

*/

my_bool

_my_hash_init(HASH *hash, uint growth_size, CHARSET_INFO *charset,

              ulong size, size_t key_offset, size_t key_length,

              my_hash_get_key get_key,

              void (*free_element)(void*), uint flags)

{

  DBUG_ENTER("my_hash_init");

  DBUG_PRINT("enter",("hash: 0x%lx  size: %u", (long) hash, (uint) size));

 

  hash->records=0;

  hash->key_offset=key_offset;

  hash->key_length=key_length;

  hash->blength=1;

  hash->get_key=get_key;

  hash->free=free_element;

  hash->flags=flags;

  hash->charset=charset;

  DBUG_RETURN(my_init_dynamic_array_ci(&hash->array,

                                       sizeof(HASH_LINK), size, growth_size));

}

<font size="3">   可以看到,_my_hash_init函數主要是初始化HASH結構體和hash->array(DYNAMIC_ARRAY結構體)。</font>

動態HASH函數

 

<font size="3">   我們首先來看下hash函數的定義:</font>

static inline char*

my_hash_key(const HASH *hash, const uchar *record, size_t *length,

            my_bool first)

{

  if (hash->get_key)

    return (char*) (*hash->get_key)(record,length,first);

  *length=hash->key_length;

  return (char*) record+hash->key_offset;

}

 

static uint my_hash_mask(my_hash_value_type hashnr, size_t buffmax,

                         size_t maxlength)

{

  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));

  return (hashnr & ((buffmax >> 1) -1));

}

 

 

my_hash_key參數 說明
hash HASH鏈表結構
record 帶插入的元素的值
length 帶插入元素的值長度
first 輔助參數

<font size="3">   </font>

 

my_hash_mask參數 說明
hashnr my_hash_key的計算結果
buffmax hash結構體中的blength
maxlength 實際桶的個數

    你可能要問我怎麼有兩個?其實這和我們平時使用的差不多,第一個函數my_hash_key是根據我們的值進行Hash Key計算,一般我們在計算後,會對hash key進行一次模運算,以便計算結果在我們的bucket中。即my_hash_key的結果作為my_hash_mask的第一個輸入參數。其實到這裡都是非常好理解的,唯一讓我蛋疼的是my_hash_mask的實現,其計算結果是和第二和第三個參數有關,即Hash結構體中的blength和records有關。動態變化的,我去..

    

 

 

看到這裡我迷惑瞭,我上網經過各種百度,谷歌,終於讓我找到瞭一封Mysql Expert的回信:

 

Hi!

"Yan" == Yan Yu <yan2…@facebook.com> writes:

 

Yan> Dear MySQL experts:

Yan>      Thank you so much for your reply to my previous Qs, they are very 

Yan> helpful!

Yan>      Could someone please help me understand function my_hash_insert() 

Yan> in mysys/hash.cc?

Yan> what are lines 352 -429 trying to achieve?  Are they just some 

Yan> optimization to shuffle existing

Yan> hash entries in the table (since the existing hash entries may be in 

Yan> the wrong slot due to chaining

Yan> in the case of hash collision)?

 

<strong><font color="#ff0000">The hash algorithm is based on dynamic hashing without empty slots.</font></strong>

This means that when you insert a new key, in some cases a small set

of old keys needs to be moved to other buckets.  This is what the code

does.

 

Regards,

Monty

      紅色註釋的地方是重點,dynamic hash,原來如此,動態hash,第一次聽說,在網上下瞭個《Dynamic Hash Tables》的論文,下面圖解下基本原理。

 

<a href=http://up.aiwalls.com/2011/1214/20111214021339214.png"><img title="image" style="border-top-width: 0px; display: block; border-left-width: 0px; float: none; border-bottom-width: 0px; margin-left: auto; margin-right: auto; border-right-width: 0px" height="910" alt="image" src=http://up.aiwalls.com/2011/1214/20111214021339854.png" width="570" border="0"></a>

<font size="3"></font>

 

 

     動態Hash的本質是Hash函數的設計,圖中給出的動態hash函數隻是論文中提到的一個例子。下面就具體解讀下Mysql中的hash插入——my_hash_insert

 

my_hash_insert非深入解析

 

    首先給出my_hash_insert的源代碼,代碼在mysys/hash.c中。

 

my_bool my_hash_insert(HASH *info, const uchar *record)

{

    int flag;

    size_t idx,halfbuff,first_index;

    my_hash_value_type hash_nr;

    uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);

    HASH_LINK *data,*empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;

 

    if (HASH_UNIQUE & info->flags)

    {

        uchar *key= (uchar*) my_hash_key(info, record, &idx, 1);

        if (my_hash_search(info, key, idx))

            return(TRUE);               /* Duplicate entry */

    }

 

    flag=0;

    if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))

        return(TRUE);               /* No more memory */

 

    data=dynamic_element(&info->array,0,HASH_LINK*);

    halfbuff= info->blength >> 1;

 

    idx=first_index=info->records-halfbuff;

    if (idx != info->records)                /* If some records */

    {

        do

        {

            pos=data+idx;

            hash_nr=rec_hashnr(info,pos->data);

            if (flag == 0)              /* First loop; Check if ok */

                if (my_hash_mask(hash_nr, info->blength, info->records) != first_index)

                    break;

            if (!(hash_nr & halfbuff))

            {                       /* Key will not move */

                if (!(flag & LOWFIND))

                {

                    if (flag & HIGHFIND)

                    {

                        flag=LOWFIND | HIGHFIND;

                        /* key shall be moved to the current empty position */

                        gpos=empty;

                        ptr_to_rec=pos->data;

                        empty=pos;              /* This place is now free */

                    }

                    else

                    {

                        flag=LOWFIND | LOWUSED;     /* key isn't changed */

                        gpos=pos;

                        ptr_to_rec=pos->data;

                    }

                }

                else

                {

                    if (!(flag & LOWUSED))

                    {

                        /* Change link of previous LOW-key */

                        gpos->data=ptr_to_rec;

                        gpos->next= (uint) (pos-data);

                        flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);

                    }

                    gpos=pos;

                    ptr_to_rec=pos->data;

                }

            }

            else

            {                       /* key will be moved */

                if (!(flag & HIGHFIND))

                {

                    flag= (flag & LOWFIND) | HIGHFIND;

                    /* key shall be moved to the last (empty) position */

                    gpos2 = empty; empty=pos;

                    ptr_to_rec2=pos->data;

                }

                else

                {

                    if (!(flag & HIGHUSED))

                    {

                        /* Change link of previous hash-key and save */

                        gpos2->data=ptr_to_rec2;

                        gpos2->next=(uint) (pos-data);

                        flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);

                    }

                    gpos2=pos;

                    ptr_to_rec2=pos->data;

                }

            }

        }

        while ((idx=pos->next) != NO_RECORD);

 

        if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)

        {

            gpos->data=ptr_to_rec;

            gpos->next=NO_RECORD;

        }

        if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)

        {

            gpos2->data=ptr_to_rec2;

            gpos2->next=NO_RECORD;

        }

    }

  /* Check if we are at the empty position */

 

  idx= my_hash_mask(rec_hashnr(info, record), info->blength, info->records + 1);

  pos=data+idx;

  if (pos == empty)

  {

    pos->data=(uchar*) record;

    pos->next=NO_RECORD;

  }

  else

  {

    /* Check if more records in same hash-nr family */

    empty[0]=pos[0];

    gpos= data + my_hash_rec_mask(info, pos, info->blength, info->records + 1);

    if (pos == gpos)

    {

      pos->data=(uchar*) record;

      pos->next=(uint) (empty – data);

    }

    else

    {

      pos->data=(uchar*) record;

      pos->next=NO_RECORD;

      movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));

    }

  }

  if (++info->records == info->blength)

    info->blength+= info->blength;

  return(0);

}

    同時給出動態hash函數如下:

 

static uint my_hash_mask(my_hash_value_type hashnr, size_t buffmax,

                         size_t maxlength)

{

  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));

  return (hashnr & ((buffmax >> 1) -1));

}

<font size="3">  </font>

   可以看出,hash函數是hash key與buffmax的模運算,buffmax即HASH結構中的blength,由my_hash_insert中最後幾行代碼可知:info->blength+= info->blength; 其初始值為1,即blength = 2^n,而且blengh始終是大於records。這個動態hash函數的基本意思是key%(2^n)。依然用圖解這個動態hash函數。

 

image

    hash函數基本清楚瞭,但是mysql的具體實現還是比較值得探討的。那封回信中也提到瞭without empty slots,是的,它這種實現方式是根據實際的數據量進行桶數的分配。我這裡大概說下代碼的流程(有興趣的還需要大傢自己仔細琢磨)。

  1. 根據flag去判斷是否是否唯一Hash,如果是唯一Hash,去查找Hash表中是否存在重復值(dupliacate entry),存在則報錯。
  2. 進行桶分裂,對應代碼中的if (idx != info->records)分支。這個分支有些費解,稍微提示下:gpos和ptr_to_rec指示瞭低位需要移動的數據,gpos2和ptr_to_rec2隻是瞭高位需要移動的數據。LOWFIND表示低位存在值,LOWUSED表示低位是否進行瞭調整。HIGH的宏意義基本相同。if (!(hash_nr & halfbuff)) 用於判斷hash值存在高位還是低位。
  3. 計算新值對應的bucket號,插入。如果此位置上存在元素(一般情況都存在,除非是empty,概率比較小),調整原始元素的位置

摘自 心中無碼

發佈留言