欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于一致性hash算法 C++語言的實(shí)現(xiàn)詳解

 更新時(shí)間:2013年05月07日 10:48:43   作者:  
在《基于一致性hash算法(consistent hashing)的使用詳解》一文中已經(jīng)介紹了一致性hash的基本原理,本文將會(huì)對(duì)其具體實(shí)現(xiàn)細(xì)節(jié)進(jìn)行描述,并用c++語言對(duì)一致性hash進(jìn)行了簡(jiǎn)單的實(shí)現(xiàn)

    一致性hash算法實(shí)現(xiàn)有兩個(gè)關(guān)鍵問題需要解決,一個(gè)是用于結(jié)點(diǎn)存儲(chǔ)和查找的數(shù)據(jù)結(jié)構(gòu)的選擇,另一個(gè)是結(jié)點(diǎn)hash算法的選擇。

    首先來談一下一致性hash算法中用于存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。通過了解一致性hash的原理,我們知道結(jié)點(diǎn)可以想象為是存儲(chǔ)在一個(gè)環(huán)形的數(shù)據(jù)結(jié)構(gòu)上(如下圖),結(jié)點(diǎn)A、B、C、D按hash值在環(huán)形分布上是有序的,也就是說結(jié)點(diǎn)可以按hash值存儲(chǔ)在一個(gè)有序的隊(duì)列里。如下圖所示,當(dāng)一個(gè)hash值為-2^20的請(qǐng)求點(diǎn)P查找路由結(jié)點(diǎn)時(shí),一致性hash算法會(huì)按hash值的順時(shí)針方向路由到第一個(gè)結(jié)點(diǎn)上(B),也就是相當(dāng)于要在存儲(chǔ)結(jié)點(diǎn)的有序結(jié)構(gòu)中,按查詢的key值找到大于key值中的最小的那個(gè)結(jié)點(diǎn)。因此,我們應(yīng)該選擇一種數(shù)據(jù)結(jié)構(gòu),它應(yīng)該高效地支持結(jié)點(diǎn)頻繁地增刪,也必須具有理想的查詢效率。那么,紅黑樹可以滿足這些要求。紅黑樹是一顆近似平衡的一顆二叉查找樹,因?yàn)椴僮鞅热绮迦?、刪除和查找某個(gè)值的最壞情況時(shí)間都要求與樹的高度成比例,這個(gè)在高度上的理論上限允許紅黑樹在最壞情況下都是高效的,而不同于普通的二叉查找樹。 因此,我們選擇使用紅黑樹作為結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu),除了需要實(shí)現(xiàn)紅黑樹基本的插入、刪除、查找的基本功能,我們還應(yīng)該增加另一個(gè)查詢lookup函數(shù),用于查找大于key中最小的結(jié)點(diǎn)。

image

   接下來,我們來說hash算法的選擇。一致性hash算法最初提出來,就是為了解決負(fù)載均衡的問題。每個(gè)實(shí)體結(jié)點(diǎn)會(huì)包含很多虛擬結(jié)點(diǎn),虛擬結(jié)點(diǎn)是平衡負(fù)載的關(guān)鍵。我們希望虛擬結(jié)點(diǎn)可以均衡的散列在整個(gè)“環(huán)”上,這樣不僅可以負(fù)載到不同hash值的路由請(qǐng)求,還可以當(dāng)某個(gè)結(jié)點(diǎn)down掉,原來路由到down掉結(jié)點(diǎn)的請(qǐng)求也可以較均衡的路由到其他結(jié)點(diǎn)而不會(huì)對(duì)某個(gè)結(jié)點(diǎn)造成大量的負(fù)載請(qǐng)求。這里,我們選擇使用MD5算法。通過MD5算法,可以將一個(gè)標(biāo)示串(用于標(biāo)示虛擬結(jié)點(diǎn))轉(zhuǎn)化得到一個(gè)16字節(jié)的字符數(shù)組,再對(duì)該數(shù)組進(jìn)行處理,得到一個(gè)整形的hash值。由于MD5具有高度的離散性,所以生成的hash值也會(huì)具有很大的離散性,會(huì)均衡的散列到“環(huán)”上。

   筆者用C++語言對(duì)一致性hash算法進(jìn)行了實(shí)現(xiàn),下面我將會(huì)描述下一些關(guān)鍵細(xì)節(jié)。

1、首先定義實(shí)體結(jié)點(diǎn)類、虛擬結(jié)點(diǎn)類。一個(gè)實(shí)體結(jié)點(diǎn)對(duì)應(yīng)多個(gè)虛擬結(jié)點(diǎn)。

  實(shí)體結(jié)點(diǎn) CNode_s:

復(fù)制代碼 代碼如下:

/*實(shí)體結(jié)點(diǎn)*/
class CNode_s
{
public:
    /*構(gòu)造函數(shù)*/
    CNode_s();
    CNode_s(char * pIden , int pVNodeCount , void * pData);

    /*獲取結(jié)點(diǎn)標(biāo)示*/
    const char * getIden();

    /*獲取實(shí)體結(jié)點(diǎn)的虛擬結(jié)點(diǎn)數(shù)量*/
    int getVNodeCount();

    /*設(shè)置實(shí)體結(jié)點(diǎn)數(shù)據(jù)值*/
    void setData(void * data);

    /*獲取實(shí)體結(jié)點(diǎn)數(shù)據(jù)值*/
    void * getData();
private:
    void setCNode_s(char * pIden, int pVNodeCount , void * pData);
    char iden[100];/*結(jié)點(diǎn)標(biāo)示串*/
    int vNodeCount; /*虛擬結(jié)點(diǎn)數(shù)目*/
    void * data;/*數(shù)據(jù)結(jié)點(diǎn)*/
};

虛擬結(jié)點(diǎn) CVirtualNode_s:虛擬結(jié)點(diǎn)有一指針指向?qū)嶓w結(jié)點(diǎn)
復(fù)制代碼 代碼如下:

/*虛擬結(jié)點(diǎn)*/
class CVirtualNode_s
{
public:
    /*構(gòu)造函數(shù)*/
    CVirtualNode_s();
    CVirtualNode_s(CNode_s * pNode);

    /*設(shè)置虛擬結(jié)點(diǎn)所指向的實(shí)體結(jié)點(diǎn)*/
    void setNode_s(CNode_s * pNode);

    /*獲取虛擬結(jié)點(diǎn)所指向的實(shí)體結(jié)點(diǎn)*/
    CNode_s * getNode_s();

    /*設(shè)置虛擬結(jié)點(diǎn)hash值*/
    void setHash(long pHash);

    /*獲取虛擬結(jié)點(diǎn)hash值*/
    long getHash();
private:
    long hash; /*hash值*/
    CNode_s * node; /*虛擬結(jié)點(diǎn)所指向的實(shí)體結(jié)點(diǎn)*/
};


2、hash算法具有可選擇性,定義一個(gè)hash算法接口,方便以后進(jìn)行其他算法的擴(kuò)展。

      這里創(chuàng)建MD5hash類,并繼承該接口,通過MD5算法求hash值。

類圖:

image  

CHashFun接口:

復(fù)制代碼 代碼如下:

/*定義Hash函數(shù)類接口,用于計(jì)算結(jié)點(diǎn)的hash值*/

class CHashFun
{
public:
    virtual long getHashVal(const char *) = 0;
};

CMD5HashFun 類繼承CHashFun接口,實(shí)現(xiàn)獲取hash值的getHashVal函數(shù):
復(fù)制代碼 代碼如下:

/*用MD5算法計(jì)算結(jié)點(diǎn)的hash值,繼承CHashFun父類*/
class CMD5HashFun : public CHashFun
{
public:
    virtual long getHashVal (const char * );
};

long CMD5HashFun::getHashVal(const char * instr)
{
    int i;
    long hash = 0;
    unsigned char digest[16];

    /*調(diào)用MD5相關(guān)函數(shù),生成instr的MD5碼,存入digest*/
    md5_state_t md5state;
    md5_init(&md5state);
    md5_append(&md5state, (const unsigned char *)instr, strlen(instr));
    md5_finish(&md5state, digest);

    /* 每四個(gè)字節(jié)構(gòu)成一個(gè)32位整數(shù),
    將四個(gè)32位整數(shù)相加得到instr的hash值(可能溢出) */
    for(i = 0; i < 4; i++)
    {
        hash += ((long)(digest[i*4 + 3]&0xFF) << 24)
            | ((long)(digest[i*4 + 2]&0xFF) << 16)
            | ((long)(digest[i*4 + 1]&0xFF) <<  8)
            | ((long)(digest[i*4 + 0]&0xFF));
    }
    return hash;
}

3、擴(kuò)展紅黑樹結(jié)構(gòu)中的查找函數(shù),用于查找紅黑樹中大于key值中最小的結(jié)點(diǎn)。
復(fù)制代碼 代碼如下:

util_rbtree_node_t* util_rbtree_lookup(util_rbtree_t *rbtree, long key)
{
    if((rbtree != NULL) && !util_rbtree_isempty(rbtree))
    {
        util_rbtree_node_t *node = NULL;
        util_rbtree_node_t *temp = rbtree->root;
        util_rbtree_node_t *null = _NULL(rbtree);
        while(temp != null)
        {
            if(key <= temp->key)
            {
                node = temp; /* update node */
                temp = temp->left;
            }
            else if(key > temp->key)
            {
                temp = temp->right;
            }
        }
        /* if node==NULL return the minimum node */
        return ((node != NULL) ? node : util_rbtree_min(rbtree));
    }
    return NULL;
}

4、創(chuàng)建一致性hash類。使其具有插入、刪除、查找實(shí)體結(jié)點(diǎn)的功能。

具體算法和操作過程已經(jīng)在代碼注釋中說明。

復(fù)制代碼 代碼如下:

class CConHash
{
public:
    /*構(gòu)造函數(shù)*/
    CConHash(CHashFun * pFunc);

    /*設(shè)置hash函數(shù)*/
    void setFunc(CHashFun * pFunc);

    /*增加實(shí)體結(jié)點(diǎn) , 0代表成功 , -1代表失敗*/
    int addNode_s(CNode_s * pNode);

    /*刪除實(shí)體結(jié)點(diǎn) , 0代表成功 , -1代表失敗*/
    int delNode_s(CNode_s * pNode);

    /*查找實(shí)體結(jié)點(diǎn)*/
    CNode_s * lookupNode_s(const char * object);

    /*獲取一致性hash結(jié)構(gòu)的所有虛擬結(jié)點(diǎn)數(shù)量*/
    int getVNodes();
private:
    /*Hash函數(shù)*/
    CHashFun * func;
    /*虛擬結(jié)點(diǎn)總個(gè)數(shù)*/
    int vNodes;
    /*存儲(chǔ)虛擬結(jié)點(diǎn)的紅黑樹*/
    util_rbtree_t * vnode_tree;
};
/*輔助函數(shù),虛擬結(jié)點(diǎn)轉(zhuǎn)化為紅黑樹結(jié)點(diǎn)*/
util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode);

 
CConHash::CConHash(CHashFun * pFunc)
{
    /*設(shè)置hash函數(shù)*/
    assert(pFunc!=NULL);
    this->func = pFunc;
    this->vNodes = 0;
    /*初始化紅黑樹*/
    vnode_tree = new util_rbtree_s();
    util_rbtree_init(vnode_tree);
}

int CConHash::addNode_s(CNode_s * pNode)
{
    if(pNode==NULL) return -1;
    int vCount = pNode->getVNodeCount();
    if(vCount<=0) return -1;
    CVirtualNode_s * virtualNode ;
    util_rbtree_node_t * rbNode;
    char str [100];
    char num[10];
    strcpy(str,pNode->getIden());
    long hash = 0;
    /*生成虛擬結(jié)點(diǎn)并插入到紅黑樹中*/
    for(int i=0;i<vCount;i++)
    {
        virtualNode = new CVirtualNode_s(pNode);
        /*采用str+“i”的方法產(chǎn)生不同的iden串,用于后面的hash值計(jì)算*/
        itoa(i,num,10);
        strcat(str,num);
        hash = func->getHashVal(str);
        virtualNode->setHash(hash);
        if(!util_rbtree_search(vnode_tree,hash))
        {
            /*生成紅黑樹結(jié)點(diǎn)*/
            rbNode = vNode2RBNode(virtualNode); 
            if(rbNode!=NULL)
            {
                /*將該結(jié)點(diǎn)插入到紅黑樹中*/
                util_rbtree_insert(vnode_tree,rbNode);
                this->vNodes++;
            }
        }
    }
    return 0;
}

int CConHash::delNode_s(CNode_s * pNode)
{
    if(pNode==NULL) return -1;
    util_rbtree_node_t * rbNode;
    char str [100];
    char num [10];
    strcpy(str,pNode->getIden()); 
    int vCount = pNode->getVNodeCount();
    long hash = 0;
    CVirtualNode_s * node = NULL;
    /*將該實(shí)體結(jié)點(diǎn)產(chǎn)生的所有虛擬結(jié)點(diǎn)進(jìn)行刪除*/
    for(int i=0;i<vCount;i++)
    {
        itoa(i,num,10);
        strcat(str,num);/*采用該方法產(chǎn)生不同的iden串*/
        hash = func->getHashVal(str);
        rbNode = util_rbtree_search(vnode_tree,hash);
        if(rbNode!=NULL)
        {
            node = (CVirtualNode_s *) rbNode->data;
            if(node->getNode_s()==pNode && node->getHash()==hash)
            {
                this->vNodes--;
                /*將該結(jié)點(diǎn)從紅黑樹中刪除*/
                util_rbtree_delete(vnode_tree,rbNode);
                delete rbNode;
                delete node;
            }
        }
    }
    return 0;
}

CNode_s * CConHash::lookupNode_s(const char * object)
{
    if(object==NULL||this->vNodes==0) return NULL;
    util_rbtree_node_t * rbNode;
    int key = this->func->getHashVal(object);
    /*在紅黑樹中查找key值比key大的最小的結(jié)點(diǎn)*/
    rbNode = util_rbtree_lookup(vnode_tree,key);
    if(rbNode!=NULL)
    {
        return ((CVirtualNode_s *) rbNode->data)->getNode_s();
    }
    return NULL;
}

int CConHash::getVNodes()
{
    return this->vNodes;
}

 
util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode)
{
    if(vnode==NULL) return NULL;
    util_rbtree_node_t *rbNode = new util_rbtree_node_t(); 
    rbNode->key = vnode->getHash();
    rbNode->data = vnode;
    return rbNode;
}

5、創(chuàng)建一個(gè)客戶端類,對(duì)一致性hash算法進(jìn)行測(cè)試。

      寫了一個(gè)getIP的函數(shù),模擬隨機(jī)產(chǎn)生的IP字符串。

復(fù)制代碼 代碼如下:

#include<iostream>
#include"CNode_s.h"
#include"CVirtualNode_s.h"
#include"CHashFun.h"
#include"CMD5HashFun.h"
#include"CConHash.h"
#include<string.h>
#include<time.h>

using namespace std;

void getIP(char * IP)
{
    int a=0, b=0 , c=0 , d=0;
    a = rand()%256;
    b = rand()%256;
    c = rand()%256;
    d = rand()%256;
    char aa[4],bb[4],cc[4],dd[4];
    itoa(a, aa, 10);
    itoa(b, bb, 10);
    itoa(c, cc, 10);
    itoa(d, dd, 10);
    strcpy(IP,aa);
    strcat(IP,".");
    strcat(IP,bb);
    strcat(IP,".");
    strcat(IP,cc);
    strcat(IP,".");
    strcat(IP,dd);
}

int main()
{
    srand(time(0));
    freopen("out.txt","r",stdin);
    /*定義hash函數(shù)*/
    CHashFun * func = new CMD5HashFun();
    /*創(chuàng)建一致性hash對(duì)象*/
    CConHash * conhash = new CConHash(func);

    /*定義CNode*/
    CNode_s * node1 = new CNode_s("machineA",50,"10.3.0.201");
    CNode_s * node2 = new CNode_s("machineB",80,"10.3.0.202");
    CNode_s * node3 = new CNode_s("machineC",20,"10.3.0.203");
    CNode_s * node4 = new CNode_s("machineD",100,"10.3.0.204");

    conhash->addNode_s(node1);
    conhash->addNode_s(node2);
    conhash->addNode_s(node3);
    conhash->addNode_s(node4);

    /*動(dòng)態(tài)更改結(jié)點(diǎn)數(shù)據(jù)值*/
//  node1->setData("99999999");

    int ans1 ,ans2 ,ans3 ,ans4;
    ans1=ans2=ans3=ans4=0;

    char object[100];
    CNode_s * node ;
    /*動(dòng)態(tài)刪除結(jié)點(diǎn)*/
    //conhash->delNode_s(node2);
    for(int i =0;i<30;i++)
    {
    //  getIP(object);
    //  cout<<object<<endl;
        cin>>object;
        node = conhash->lookupNode_s(object);
        if(node!=NULL)
        {
            cout<<object<<"----->\t"<<node->getIden()<<" \t "<<(char *)node->getData()<<endl;
            if(strcmp(node->getIden(),"machineA")==0) ans1++;
            if(strcmp(node->getIden(),"machineB")==0) ans2++;
            if(strcmp(node->getIden(),"machineC")==0) ans3++;
            if(strcmp(node->getIden(),"machineD")==0) ans4++;
        }
    }

    cout<<"Total test cases : "<<ans1+ans2+ans3+ans4<<endl;
    cout<<"Map to MachineA : "<<ans1<<endl;
    cout<<"Map to MachineB : "<<ans2<<endl;
    cout<<"Map to MachineC : "<<ans3<<endl;
    cout<<"Map to MachineD : "<<ans4<<endl;
    fclose(stdin);
    return 0;
}

6、刪除結(jié)點(diǎn)對(duì)hash路由的影響測(cè)試

image

測(cè)試結(jié)果截圖:

imageimage

分析:上面兩幅圖,左邊為原始四個(gè)實(shí)體結(jié)點(diǎn)的路由情況,后面為刪除結(jié)點(diǎn)2(Node2)之后的路由情況。不難發(fā)現(xiàn),MachineB down之后,原先的路由請(qǐng)求,較均衡地負(fù)載到了其他機(jī)器結(jié)點(diǎn),而且對(duì)原先路由到其他結(jié)點(diǎn)的請(qǐng)求沒有影響。比如139.149.184.125這個(gè)請(qǐng)求仍會(huì)路由到MachineD,并不會(huì)因?yàn)榻Y(jié)點(diǎn)的減少而造成影響。但是,如果是增加實(shí)體結(jié)點(diǎn),可能會(huì)造成增加前后路由情況不一致的現(xiàn)象,因?yàn)槁酚蓞^(qū)間的更加狹小,但是不會(huì)有特別大的影響。 另一方面,可以發(fā)現(xiàn)實(shí)體結(jié)點(diǎn)的虛擬結(jié)點(diǎn)個(gè)數(shù)比例分配情況很大程度影響了結(jié)點(diǎn)的負(fù)載路由情況,比例大致與虛擬結(jié)點(diǎn)個(gè)數(shù)相一致。

總結(jié):

   本文首先通過介紹實(shí)現(xiàn)一致性hash算法的關(guān)鍵算法和數(shù)據(jù)結(jié)構(gòu)的選擇分析,選擇了紅黑樹作為虛擬結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu),以及MD5算法作為Hash函數(shù)用于計(jì)算結(jié)點(diǎn)的hash值。并使用C++語言,對(duì)一致性hash算法進(jìn)行了實(shí)現(xiàn),實(shí)現(xiàn)了一致性hash實(shí)體結(jié)點(diǎn)的增加、刪除、查找等基本功能,并進(jìn)行了測(cè)試分析。由于筆者水平有限,存在很多有待改進(jìn)的地方,因此本文僅供大家參考、討論學(xué)習(xí)。

相關(guān)文章

  • C語言的getc()函數(shù)和gets()函數(shù)的使用對(duì)比

    C語言的getc()函數(shù)和gets()函數(shù)的使用對(duì)比

    這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對(duì)比,從數(shù)據(jù)流中一個(gè)是讀取字符一個(gè)是讀取字符串,需要的朋友可以參考下
    2015-08-08
  • C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)

    C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)

    list相較于vector來說會(huì)顯得復(fù)雜,它的好處是在任意位置插入,刪除都是一個(gè)O(1)的時(shí)間復(fù)雜度,下面這篇文章主要給大家介紹了關(guān)于C++中l(wèi)ist的使用與模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下
    2022-05-05
  • C語言細(xì)致講解線程同步的集中方式

    C語言細(xì)致講解線程同步的集中方式

    多線程中的線程同步可以使用,CreateThread,CreateMutex 互斥鎖實(shí)現(xiàn)線程同步,通過臨界區(qū)實(shí)現(xiàn)線程同步,Semaphore 基于信號(hào)實(shí)現(xiàn)線程同步,CreateEvent 事件對(duì)象的同步,以及線程函數(shù)傳遞單一參數(shù)與多個(gè)參數(shù)的實(shí)現(xiàn)方式
    2022-05-05
  • VC List Control控件如何刪除選中的記錄實(shí)例詳解

    VC List Control控件如何刪除選中的記錄實(shí)例詳解

    這篇文章主要介紹了VC List Control控件如何刪除選中的記錄實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C語言中字符串處理函數(shù)sscanf的用法

    C語言中字符串處理函數(shù)sscanf的用法

    一直對(duì)于一些日期字符串中數(shù)字的提取比較頭疼,現(xiàn)看到 sscanf 對(duì)于字符串中的內(nèi)容提取較方便,本文主要介紹了C語言中字符串處理函數(shù)sscanf的用法,具有一定參考價(jià)值,感興趣的可以了解一下
    2023-08-08
  • C語言函數(shù)指針與回調(diào)函數(shù)的實(shí)現(xiàn)

    C語言函數(shù)指針與回調(diào)函數(shù)的實(shí)現(xiàn)

    本文主要介紹了C語言函數(shù)指針與回調(diào)函數(shù)的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-05-05
  • C語言實(shí)現(xiàn)楊輝三角實(shí)例

    C語言實(shí)現(xiàn)楊輝三角實(shí)例

    這篇文章主要介紹了C語言實(shí)現(xiàn)楊輝三角的方法,主要通過數(shù)組簡(jiǎn)單實(shí)現(xiàn),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2014-09-09
  • Atom安裝配置C/C++詳細(xì)教程

    Atom安裝配置C/C++詳細(xì)教程

    Atom (一款開源的代碼編輯器)是github專門為程序員推出的一個(gè)跨平臺(tái)文本編輯器。這篇文章主要介紹了Atom安裝配置C/C++教程,需要的朋友可以參考下
    2020-05-05
  • C++ Cartographer加載配置文件過程介紹

    C++ Cartographer加載配置文件過程介紹

    這篇文章主要介紹了Cartographer加載配置文件過程,谷歌優(yōu)秀的激光SLAM開源框架Cartographer算法簡(jiǎn)單,但是程序部分太多需要學(xué)習(xí)的地方了,不論是整體框架的結(jié)構(gòu),還是數(shù)據(jù)的使用,都是非常優(yōu)美的
    2023-03-03
  • C++中純虛函數(shù)的實(shí)例詳解

    C++中純虛函數(shù)的實(shí)例詳解

    純虛函數(shù)就是一個(gè)在基類中的虛函數(shù),差別只是在一般的虛函數(shù)聲明的后面加了“=0”,下面這篇文章主要給大家介紹了關(guān)于C++中純虛函數(shù)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-06-06

最新評(píng)論