MySQL的代碼中實(shí)現(xiàn)了一個Lock Free的Hash結(jié)構(gòu)，稱作LF_Hash。MySQL的不少模塊使用了LF_Hash，比如Metadata Lock就依賴于它。但由于使用的方法不正確，導(dǎo)致了bug#98911和bug#98624。理解LF_Hash的實(shí)現(xiàn)細(xì)節(jié)，可以幫助我們用好LF_Hash。

LF_HASH的基本特點(diǎn)動態(tài)擴(kuò)展

初始化時bucket的數(shù)量是1. 每個bucket平均擁有的元素(Element)是1個。因此當(dāng)元素的總數(shù)量超過bucket的數(shù)量時，就會自動分裂。每次分裂增加一倍的buckets.Lock Free

lf_hash采用Lock Free的方式實(shí)現(xiàn)，為了保證多線程操作的安全。lf_hash實(shí)現(xiàn)了一個叫做pin的東西來保證多線程操作的安全性。lf_hash的操作都需要通過pin來保護(hù)。因此lf_hash提供了獲取pin和釋放pin的函數(shù)。lf_hash自己維護(hù)了一個pin的動態(tài)數(shù)組。

內(nèi)存管理

lf_hash元素的內(nèi)存都是lf_hash分配和管理的。用戶的數(shù)據(jù)需要拷貝到lf_hash創(chuàng)建的元素中。

LF_HASH的基本操作

插入元素

//?獲取一個LF_PINS對象LF_PINS *pins = lf_hash_get_pins();//?給元素分配內(nèi)存，并拷貝用戶數(shù)據(jù)到元素中,并插入到Hash鏈表中l(wèi)f_hash_insert(lf_hash_object, pins, user_data);// 釋放LF_PINS對象lf_hash_put_pins(pins);

刪除元素

//?獲取一個LF_PINS對象LF_PINS *pins = lf_hash_get_pins();// 刪除指定key的元素lf_hash_delete(lf_hash_object, pins, key, key_length);// 釋放LF_PINS對象lf_hash_put_pins(pins);

查詢元素

// 獲取一個LF_PINS對象LF_PINS *pins = lf_hash_get_pins();// 返回指定key的第一個元素，這個元素對象會被pin住，使用完要unpin。// 被pin住的元素不能被其他線程從hash鏈表中移除el = lf_hash_search(lf_hash_object, pins, key， key_length);// 使用查找到的元素。...// unpin當(dāng)前元素lf_hash_search_unpin(pins);// 釋放LF_PINS對象lf_hash_put_pins(pins);

LF_HASH的基本結(jié)構(gòu)

lf_hash的基本結(jié)構(gòu)如下圖所示：所有的元素維護(hù)在一個全局排序鏈表里

同一個bucket的所有元素排在一起

每個bucket有一個指針，指向這個bucket的所有元素的Head

元素排序

為了能夠做到將每個bucket的元素排列到一起，lf_hash根據(jù)元素hash的反轉(zhuǎn)值進(jìn)行排序。并且要求bucket的數(shù)量必須是2的倍數(shù)。

元素Hash的反轉(zhuǎn)值

和其他Hash Table一樣, LF_HASH也是通過hash(key)得出一個32bits的整數(shù)值(hashnr)，這個值決定了元素屬于哪一個bucket.

hashnr?=?hash(key);//?size是bucket的數(shù)量bucket_id?=?hashnr?%?LF_HASH::size;?bucket_id從0開始。

Hash的反轉(zhuǎn)值是指將Hash的所有Bits的順序顛倒過來。例如

//?為了表示方便，這里假設(shè)hashnr是8位的，按8位反轉(zhuǎn)//?實(shí)際使用是32位的，按32位反轉(zhuǎn)0?->?00000000?->?00000001?->?00000001?->?10000002?->?00000010?->?0100000

排序特點(diǎn)

LF_HASH的全局排序鏈表看起來是這樣的:

為了書寫方便，假設(shè)hash值的長度是8bit.

這個鏈表是按hash值的反向bit位排序的，因此最低位為0的排在一起，為1的排在一起。

最低位相同的元素，又按第二低位排序。第二低位相同的，按第三低位排序。

hash值相同的按hash key排序(這個不是重點(diǎn)，這里可以忽略)。

Bucket的數(shù)量必須是2的倍數(shù)

當(dāng)bucket的數(shù)量是2的倍數(shù)時我們會發(fā)現(xiàn)當(dāng)bucket size是1時，所有元素會分到同一個bucket中。

當(dāng)bucket size是2時，最低1位相同的元素會分到同一個bucket中。

當(dāng)bucket size是4時，最低2位相同的元素會分到同一個bucket中。

bucket每擴(kuò)展1倍，多1bit用來分bucket.

這個規(guī)律使得每個bucket的元素在全局鏈表中排列在一起。

如果將bucket id反轉(zhuǎn)，我們會發(fā)現(xiàn)全局鏈表是按照元素的 bucket id的反轉(zhuǎn)值分bucket的。bucket id的反轉(zhuǎn)值就是當(dāng)前bucket的里的最小值。當(dāng)bucket size是1時，所有的元素在bucket 0中。

當(dāng)bucket size是2時，按照hash值的最低位(反轉(zhuǎn)值的最高位)分bucket，0的分在bucket 0中，1分在bucket 中。排序規(guī)律符合要求，bucket 0和1的元素分別排列在一起。

當(dāng)bucket size是4時，按照最低2位的值分bucket，00的分在bucket 0, 01分在bucket 2中。10排在bucket 1中，11排在bucket 3中。排序規(guī)律要求，每個bucket的元素仍然是排列在一起的。

因此以2的倍數(shù)來擴(kuò)展lf_hash的bucket時全局鏈表不需要任何變動

原有的buckets不需要變動

只需要將新的buckets指向自己的第一個元素。

Bucket Parent

你可能已經(jīng)注意到了，按2的倍數(shù)擴(kuò)展。實(shí)際上就是將原bucket能容納的排序值的范圍分成兩半。前一半保留在原來的bucket中，后一半放到一個新bucket中。lf_hash中稱這個被分裂的bucket為parent。Parent bucket是固定的，根據(jù)bucket id可以算出parent. 對于bucket id的反轉(zhuǎn)值來說，是將低位的1清零。

對bucket id來說，就是將高位的1清零。

uint?parent?=?my_clear_highest_bit(bucket);

Dummy 元素

每個Bucket中都是一個指針，指向全局鏈表中這個bucket的最小元素，即head。為了避免這個指針隨著head的變化而變化：初始化一個bucket時會生成一個dummy元素，把dummy元素插入到全局鏈表中。

dummy元素的hash指定為bucket id。

bucket id的反轉(zhuǎn)值是bucket中所有元素的最小值。所以dummy元素始終是這個bucket的鏈表的head。bucket的指針將始終指向這個dummy元素。

區(qū)分用戶元素和Dummy元素

用戶元素的hash值可能會等于bucket id，為了避免將這個元素插到dummy元素的前面(lf_hash中用的是前插)。lf_hash會將用戶元素的的hash反轉(zhuǎn)值的最低位變?yōu)?。這樣就保證了dummy元素的hash反轉(zhuǎn)值最小且唯一。

元素管理

為了Lock Free, lf_hash自己管理元素的內(nèi)存分配。

元素結(jié)構(gòu)

lf_hash的元素使用一塊連續(xù)的內(nèi)存，包含兩部分信息：LF_SLIST 鏈表和hash相關(guān)的信息

用戶數(shù)據(jù)。放在LF_SLIST之后，

LF_SLISTlink:? ? ? ? 指向鏈表中的下一個元素

hashnr? ? hash的反轉(zhuǎn)值

key? ? ? ? ?指針指向key值

LF_ALLOCATOR

LF_ALLOCATOR負(fù)責(zé)元素的管理。

LF_ALLOCATOR::top

Hash鏈表中的元素被刪除后，并不會被釋放(free)掉。它們會被放到一個鏈表中(lf_hash中稱作棧)，top指向鏈表中的第一個元素(棧頂)。當(dāng)向Hash鏈表中插入一個元素時，會從這個鏈表中取一個元素使用。如果沒有可供使用的元素，才會通過my_malloc分配一個新的。

用LF_SLIST::key指向下一個元素

這里要注意的一點(diǎn)是，這個鏈表是使用LF_SLIST::key連在一起的。為什么不使用LF_SLIST::link呢？那是因?yàn)?#xff0c;是因?yàn)閘f_hash lock free的設(shè)計。

問題

除非Destroy整個Hash，LF_ALLOCATOR中未使用的元素是不會釋放的。如果這個HASH鏈表在某個時刻特別大，占用內(nèi)存特別多。這些內(nèi)存就會一直被占用，直到整個Hash被釋放掉。

PIN的機(jī)制

Lock Free意味著多個線程可能同時在使用一個元素。一個元素從全局鏈表中移除后，不能被立刻放入到LF_ALLOCATOR::top 指向的Free元素鏈表中。別的線程可能正在使用這個元素。如果此時放到free鏈表中，又被別的線程重用了，就可能會造成錯誤。lf_hash用LF_PINS來保護(hù)一個正在使用的元素不被刪除或者重用。我們可以將PIN想象成一個鎖。

LF_PINS::pin

std::atomic?pin[LF_PINBOX_PINS];

pin包含4個指針，可以同時引用4個元素，看代碼中最多用了3個。這是因?yàn)閘f_hash鏈表在操作的過程中最多可以使用到連續(xù)的三個元素previous, current, next。這3個元素要同時pin住。

線程在將一個元素放入Free元素鏈表之前，要檢查所有的pin。如果有任何pin引用了這個元素，則要等待這個元素的引用被取消后才能繼續(xù)操作。

LF_PINS::purgatory

如果并發(fā)的線程很多，遍歷所有的pin就會消耗較長的時間。因此lf_hash并不是每刪除一個元素做一次遍歷操作。而是對多個要刪除的元素一起做遍歷操作。這些要刪除的元素會臨時的放入LF_PINS::purgatory鏈表。只有當(dāng)purgatory的元素數(shù)量到達(dá)LF_PURGATORY_SIZE(10個)時或這個pin被釋放時，才做一次遍歷。沒有被引用的元素會被放到LF_ALLOCATOR::top指向的Free 元素鏈表中去。

當(dāng)將一個元素放入purgatory時，其他的線程可能正在讀取這個元素，也可能正在讀取這個元素的LF_SLIST::link。因此puragory鏈表使用LF_SLIST::key將要purge的元素鏈接到一起的。難道并發(fā)的線程不訪問這個元素的LF_SLIST::key嗎？會訪問，為了能夠訪問到正確的值，lf_hash有下面這個設(shè)計。

刪除標(biāo)記

每個元素都有一個DELETED的標(biāo)記位，在將元素從全局鏈表中移除之前，首先要將元素標(biāo)記為DELETED。看代碼時，你可能會迷惑。因?yàn)長F_SLIST中，并沒有一個DELETED標(biāo)記位。那是因?yàn)镈ELETED標(biāo)記位共享了link的最低位。

之所以能夠和link共享最低位，是因?yàn)閘ink是一個指針指向一個內(nèi)存地址。內(nèi)存地址總是4/8字節(jié)對齊的，最低位一定是0。

刪除的過程找到元素

標(biāo)記為DELETED

從全局鏈表中移除

加入purgatory鏈表，會修改元素的LF_SLIST::key

執(zhí)行purge過程，如果purgatory鏈表有10個元素。

查找元素的過程pin當(dāng)前元素

拷貝元素的hash key指針到臨時變量,會讀取LF_SLIST::key

檢查元素是否是DELETED，如果是則移動到下一個元素。

比較元素的hashnr和key，如果hashnr和key都小于要查找的hashnr和key則，移動到下一個元素。

可以看到，刪除的過程中是先標(biāo)記DELETED，然后修改LF_SLIST::key。而在查找元素時，是先拷貝LF_SLIST::key，然后檢查DELETED標(biāo)記。這就保證了查找中使用的key是正確的key。

LF_PINBOX

Pinbox是pin的管理器，所有的pin放在一個動態(tài)數(shù)據(jù)里。pinarray pin的動態(tài)數(shù)組

LF_PINBOX::pinstack_top_ver

和LF_ALLOCATOR::top類似，pinstack_top_ver指向free pin的鏈表(棧)。但它存儲的不是指針，而是第一個元素在pinarray中的index. LF_PINS::link用來指向下一個pin在pinarray中的index。

當(dāng)用戶調(diào)用lf_hash_put_pins()時，會將pin放入這個鏈表。當(dāng)調(diào)用lf_hash_get_pins()時，會從pinstack_top_ver取出一個free pin。如果free pin的鏈表是空的(top是0)，則會給pinarray中增加一個元素。

top version

LF_ALLOCATOR::top上的lock free操作是通過Pin來保護(hù)。那么LF_PINBOX::pinstack_top_ver上的lock free操作又是做到的呢? 為了做到lock free， LF_PINBOX::pinstack_top_ver上使用了version的方法。

每次操作free pin鏈表時，都會將version加1。在做atomic_compare_exchange操作時，pinstack_top_ver作為一個整數(shù)，整體進(jìn)行操作。

由于top只有16位，這就限制了pinarray最多只能有LF_PINBOX_MAX_PINS(65535)個元素。

PIN使用上的問題

從pin的設(shè)計可以看出，pin的使用原則是保護(hù)lf_hash操作本身的。一個操作完成后,pin就可以釋放了。MySQL中有些lf_hash的pin是長期持有的。如MDL_context::m_pins，這個pin是在session第一次調(diào)用時獲取，session退出時才釋放。它會導(dǎo)致：session的數(shù)量最多只能有65535個

session的數(shù)量很大時，導(dǎo)致pinarray很大。因此元素的purge操作效率很低。

前面說過purgatory中的元素到達(dá)LF_PURGATORY_SIZE(10個)時或者釋放pin時，才會釋放。由于這些pin到session結(jié)束時才釋放，就會導(dǎo)致元素的釋放不及時。分配的元素更多，占用內(nèi)存更多。

動態(tài)數(shù)組

lf_hash中的bucket和pin都使用了動態(tài)數(shù)組。為了實(shí)現(xiàn)lock free，在動態(tài)擴(kuò)展時不拷貝內(nèi)存，它做了特殊的設(shè)計。

多級數(shù)組

這個數(shù)組LF_DYNARRAY_LEVELS(4).

LevelIndex范圍

00 到 255

1256 到 256*256-1

2256*256 到 256*256*256-1

3256*256*256 到 256*256*256*256-1

0級

0級包含256個指針，指向index 0到255的元素。這些元素初始化時不分配，用到時才分配。

1級

1級包含256個指針，每個指針指向一個0級數(shù)組。

2級

2級包含256個指針，每個指針指向一個1級數(shù)組。

3級

3級包含256個指針，每個指針指向一個2級數(shù)組。

相關(guān)資源：mysql錯誤以及處理方式_mysql語法錯誤怎么辦-MySQL文檔類資源...

總結(jié)

以上是生活随笔為你收集整理的MySQL源码解读之数据结构-LF_DYNARRAY的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。