负载均衡算法

分布式算法-一致性哈希：

一个分布式系统，需要将数据存储到具体的节点上，如果用普通哈希取模进行，如果增加服务器或者服务器宕机，同一个KEY经过哈希后再对总数取模结果就和原来不同，会导致数据丢失。
所以引入一致性哈希：
先用hash函数映射到一个圆环上：

需要服务器时，先根据hash算法算出KEY的hash值，对应到这个环中的位置：如上图中的K1,顺时针找到服务器B，K1存入B中，B如果宕机了B上的数据就会落到C节点上：

这样就只会影响C节点，对其他服务器不会影响，但是可能造成C节点负担过重导致宕机。
所以又引入“虚拟节点”：
想象环上有很多虚拟节点，一个真实的服务器对应多个节点，顺时针寻找虚拟节点，就找到对应的真实服务器节点

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。

hash函数MD5加密的，但是复杂度高，有损耗；
MurMurHash非加密算法，但是快，而且碰撞率低；

#include <map>
using namespace std;

class ConsistentHash
{
public:
    ConsistentHash(int node_num, int virtual_node_num);
    ~ConsistentHash();

    void Initialize();
    size_t GetServerIndex(const char* key);

    void DeleteNode(const int index);
    void AddNewNode(const int index);

private:
    map<uint32_t,size_t> server_nodes_; //虚拟节点,key是哈希值，value是机器的index
    int node_num_;//真实机器节点个数
    int virtual_node_num_;//每个机器节点关联的虚拟节点个数
};


#include <map>
#include <string.h>
#include <sstream>
#include "consistent_hash.h"
#include "murmurhash3.h"
using namespace std;

ConsistentHash::ConsistentHash(int node_num, int virtual_node_num)
{
    node_num_ = node_num;
    virtual_node_num_ = virtual_node_num;
}

ConsistentHash::~ConsistentHash()
{
    server_nodes_.clear();
}


void ConsistentHash::Initialize()
{
    for(int i=0; i<node_num_; ++i)
    {
        for(int j=0; j<virtual_node_num_; ++j)
        {
            stringstream node_key;
            node_key<<"SHARD-"<<i<<"-NODE-"<<j;
            uint32_t partition = murmur3_32(node_key.str().c_str(), strlen(node_key.str().c_str()));
            server_nodes_.insert(pair<uint32_t, size_t>(partition, i));
        }
    }
}


size_t ConsistentHash::GetServerIndex(const char* key)
{
    uint32_t partition = murmur3_32(key, strlen(key));
    map<uint32_t, size_t>::iterator it = server_nodes_.lower_bound(partition);//沿环的顺时针找到一个大于等于key的虚拟节点

    if(it == server_nodes_.end())//未找到
    {
        return server_nodes_.begin()->second;
    }
    return it->second;
}


void ConsistentHash::DeleteNode(const int index)
{
    for(int j=0; j<virtual_node_num_; ++j)
    {
        stringstream node_key;
        node_key<<"SHARD-"<<index<<"-NODE-"<<j;
        uint32_t partition = murmur3_32(node_key.str().c_str(), strlen(node_key.str().c_str()));
        map<uint32_t,size_t>::iterator it = server_nodes_.find(partition);
        if(it != server_nodes_.end())
        {
            server_nodes_.erase(it);
        }
    }
}

void ConsistentHash::AddNewNode(const int index)
{
    for(int j=0; j<virtual_node_num_; ++j)
    {
        stringstream node_key;
        node_key<<"SHARD-"<<index<<"-NODE-"<<j;
        uint32_t partition = murmur3_32(node_key.str().c_str(), strlen(node_key.str().c_str()));
        server_nodes_.insert(pair<uint32_t, size_t>(partition, index));
    }
}

一致性哈希特点：
平衡性(Balance)
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
降低分散性