您好,登錄后才能下訂單哦!
四、代碼結(jié)構(gòu)(2) space manager
這一篇和下一篇我們來(lái)介紹dm dedup的空間管理的部分和核心流程I/O寫(xiě)流程
在此之前,我們先分析一下用到的資源有哪些,和了解dm dedup的space manager空間管理器
空間管理器,是一個(gè)巨型的數(shù)組,以allocptr申請(qǐng)指針為標(biāo),對(duì)整個(gè)space進(jìn)行掃描一周(回到current allocptr)。
用來(lái)找到空閑的塊(白色),并把它分配給一個(gè)hash request,把它變成一個(gè)綠色的塊,并把這個(gè)信息hash_pbn,放到kvs_hash_pbn的表內(nèi)。
kvs_lbn_pbn和kvs_hash_pbn的空間是預(yù)先分配好的,所以這兩個(gè)表的index都是有確定的含義,非常利于查找。
dc->kvs_hash_pbn = dc->mdops->kvs_create_sparse(md, crypto_key_size,sizeof(struct hash_pbn_value),dc->pblocks, unformatted);
dc->kvs_lbn_pbn = dc->mdops->kvs_create_linear(md, 8,sizeof(struct lbn_pbn_value), dc->lblocks, unformatted);
在創(chuàng)建kvs(key value space)的時(shí)候,有兩種選擇,一種是按照l(shuí)inear就是一一映射的lbn-pbn的方式,還有一種是hash index的方式。
其中都會(huì)將ksize和vsize會(huì)在兩種space類(lèi)型不同而會(huì)以不同的方式保存。
① kvs-lbn-pbn,linear的create space方式inram
static struct kvstore *kvs_create_linear_inram(struct metadata *md,u32 ksize, u32 vsize,u32 kmax, bool unformatted)
{
struct kvstore_inram *kvs;
u64 kvstore_size, tmp;
kvs = kmalloc(sizeof(*kvs), GFP_NOIO);
if (!kvs)
return ERR_PTR(-ENOMEM);
kvstore_size = (kmax + 1) * vsize;
kvs->store = vmalloc(kvstore_size);
/*確定kvs->store的大小,這里的思想很簡(jiǎn)單,
就是64 bit的lbn尋址到一個(gè)ksize的pbn上面,一般的pbn也是64 bit*/
/*kmax是 邏輯設(shè)備的大小,這個(gè)map-table的含義就是lbn-pbn的映射關(guān)系*/
tmp = kvstore_size;
(void)do_div(tmp, (1024 * 1024));
memset(kvs->store, EMPTY_ENTRY, kvstore_size);
kvs->ckvs.vsize = vsize;
kvs->ckvs.ksize = ksize;
kvs->kmax = kmax;
kvs->ckvs.kvs_insert = kvs_insert_linear_inram; /*插入api*/
kvs->ckvs.kvs_lookup = kvs_lookup_linear_inram; /*查找api*/
kvs->ckvs.kvs_delete = kvs_delete_linear_inram; /*刪除api*/
kvs->ckvs.kvs_iterate = kvs_iterate_linear_inram; /*迭代api*/
md->kvs_linear = kvs;
return &(kvs->ckvs);
}
我們簡(jiǎn)單看一看kvs_insert_linear_inram和kvs_lookup_linear_inram,刪除和迭代留在垃圾回收的部分介紹。
static int kvs_insert_linear_inram(struct kvstore *kvs, void *key,s32 ksize, void *value,int32_t vsize)
{
u64 idx;
char *ptr;
struct kvstore_inram *kvinram = NULL;
kvinram = container_of(kvs, struct kvstore_inram, ckvs);
idx = *((uint64_t *)key);
ptr = kvinram->store + kvs->vsize * idx; /*以lbn為key,pbn為value的map*/
memcpy(ptr, value, kvs->vsize);
return 0;
}
插入的代碼非常簡(jiǎn)單,就可以理解成linear是個(gè) u64 kvs[kmax] 這樣的數(shù)組,lbn是數(shù)組下標(biāo),而value是數(shù)組內(nèi)容。
static int kvs_lookup_linear_inram(struct kvstore *kvs, void *key,
s32 ksize, void *value,
int32_t *vsize)
{
u64 idx;
char *ptr;
int r = -ENODATA;
struct kvstore_inram *kvinram = NULL;
kvinram = container_of(kvs, struct kvstore_inram, ckvs);
idx = *((uint64_t *)key);
ptr = kvinram->store + kvs->vsize * idx;
if (is_empty(ptr, kvs->vsize))
return r;
memcpy(value, ptr, kvs->vsize);
*vsize = kvs->vsize;
return 0;
}
② kvs-hash-pbn,sparse的create space方式inram
sparse 的方式和linear不太一樣,它的組織形式會(huì)更加復(fù)雜一些
他要存 key和value兩個(gè),key_size是采用hash算法的大小,如:md5是128 bit,value是pbn是64 bit
static struct kvstore *kvs_create_sparse_inram(struct metadata *md,
u32 ksize, u32 vsize,
u32 knummax, bool unformatted)
{
struct kvstore_inram *kvs;
u64 kvstore_size, tmp;
kvs = kmalloc(sizeof(*kvs), GFP_NOIO);
/* knummax key的最大值這里是按照pbn的最大值申請(qǐng)的,物理設(shè)備的大小*/
knummax += (knummax * HASHTABLE_OVERPROV) / 100;/*額外申請(qǐng)了十分之一的空間*/
kvstore_size = (knummax * (vsize + ksize)); /*申請(qǐng)單位是vsize(pbn)64bit ksize(hash_size)128 bit*/
kvs->store = vmalloc(kvstore_size);
tmp = kvstore_size;
(void)do_div(tmp, (1024 * 1024));
memset(kvs->store, EMPTY_ENTRY, kvstore_size);
/*將所有的key都預(yù)先變成EMPTY_ENTRY= 0xFB(最新的代碼4.13是0xFF)*/
kvs->ckvs.vsize = vsize;
kvs->ckvs.ksize = ksize;
kvs->kmax = knummax;
kvs->ckvs.kvs_insert = kvs_insert_sparse_inram; /*插入api*/
kvs->ckvs.kvs_lookup = kvs_lookup_sparse_inram; /*查找api*/
kvs->ckvs.kvs_delete = kvs_delete_sparse_inram; /*刪除api*/
kvs->ckvs.kvs_iterate = kvs_iterate_sparse_inram; /*迭代api*/
md->kvs_sparse = kvs;
return &(kvs->ckvs);
}
接下來(lái)看一下插入和查找函數(shù),這個(gè)函數(shù)會(huì)比linear的難一些,只要一點(diǎn)例子會(huì)很好理解。
看到調(diào)試信息中有初始化的過(guò)程。
其中也包括兩個(gè)寫(xiě)流程包括lookup和insert,為了幫助快速理解,就按照這個(gè)例子來(lái)說(shuō)會(huì)比較容易。
static int kvs_insert_sparse_inram(struct kvstore *kvs, void *key,s32 ksize, void *value, s32 vsize)
{
u64 idxhead = *((uint64_t *)key); /*無(wú)論key是128bit還是64bit,我們?nèi)?4bit出來(lái)*/
u32 entry_size, head, tail;
char *ptr;
struct kvstore_inram *kvinram = NULL;
kvinram = container_of(kvs, struct kvstore_inram, ckvs);
entry_size = kvs->vsize + kvs->ksize; /*確立每個(gè)單位entry_size,一般是:64bit + 128 bit*/
head = do_div(idxhead, kvinram->kmax);
/*這一步算出具體key在散列的位置,是把idxhead取余為head,
hash出來(lái)的key相同的概率之前算過(guò)了是非常低,除以kmax取余,
就是給key在找位置,這個(gè)位置head也一部分key的散列屬性*/
tail = head;
/*這個(gè)循環(huán)很逗,雖然我的調(diào)試?yán)餂](méi)有顯示出它起了作用,
但是我們前面說(shuō)head雖然具有一定的散列屬性,但它在這里并不具有唯一性,
因?yàn)閗ey本身非常大128bit,他能代表一個(gè)pbn的內(nèi)容的唯一性,
取余出的head卻是一個(gè)小值,他不能唯一代表pbn,
雖然你可以認(rèn)為head:150702代表idxhead:0x24100420901436,
并且在這個(gè)head位置保存它,但它卻沒(méi)有一唯一性,
那么如果產(chǎn)生了取余后的head所在位置的*ptr已經(jīng)存在了,
就需要給這個(gè)key另找一個(gè)head來(lái)保存它,代碼這里的做法是向后取,
找到一個(gè)NULL或者被deleted掉的*ptr,在這個(gè)位置把key記錄下來(lái)*/
do {
ptr = kvinram->store + entry_size * head;
if (is_empty(ptr, entry_size) || is_deleted(ptr, entry_size)) {
memcpy(ptr, key, kvs->ksize);
memcpy(ptr + kvs->ksize, value, kvs->vsize);
return 0;
}
head = next_head(head, kvinram->kmax);
} while (head != tail);
return -ENOSPC;
}
查找的代碼和插入的代碼,幾乎就是一樣的。
就是在do{}while里先從head開(kāi)始找,找到一樣的key值,就把它的value(pbn)拿出來(lái)。
static int kvs_lookup_sparse_inram(struct kvstore *kvs, void *key,s32 ksize, void *value, int32_t *vsize)
{
u64 idxhead = *((uint64_t *)key);
u32 entry_size, head, tail;
char *ptr;
struct kvstore_inram *kvinram = NULL;
int r = -ENODATA;
kvinram = container_of(kvs, struct kvstore_inram, ckvs);
entry_size = kvs->vsize + kvs->ksize;
head = do_div(idxhead, kvinram->kmax);
tail = head;
do {
ptr = kvinram->store + entry_size * head;
if (is_empty(ptr, entry_size))
return r;
if (memcmp(ptr, key, kvs->ksize)) {
head = next_head(head, kvinram->kmax);
} else {
memcpy(value, ptr + kvs->ksize, kvs->vsize);
return 0;
}
} while (head != tail);
return r;
}
這里可能大家就會(huì)覺(jué)得很奇怪,為什么這里是這么簡(jiǎn)單的搜索方法,為什么不排序等等。
這里我的思考是這樣的:首先這個(gè)是在inram的搜索,所以本身查找的性能還是很高的,其次在這個(gè)key取余的head值,雖然它不具有唯一性,但他具有key的散列屬性,也就是說(shuō)讓它產(chǎn)生沖突的概率都不高,所以在pbn沒(méi)有申請(qǐng)很多的情況下,應(yīng)該都是直接一步就可以找到的,而且就算產(chǎn)生了沖突,它也是向后找,很可能就是下一個(gè),所以就算碰撞,它保存的位置也具有相關(guān)聯(lián)性,都會(huì)在它的后面的幾個(gè)就可以找到,我認(rèn)為這個(gè)性能應(yīng)該還不錯(cuò)。
【本文只在51cto博客作者 “底層存儲(chǔ)技術(shù)” https://blog.51cto.com/12580077 個(gè)人發(fā)布,公眾號(hào)發(fā)布:存儲(chǔ)之谷】,如需轉(zhuǎn)載,請(qǐng)于本人聯(lián)系,謝謝。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。