hello ---> 60
hello world ---> 40

server = hash（key）mod 3  //假设后端有3个服务器

john@example.com      89 2（S3）
mark@example.com      30 0（S1）
adam@examle.com       47 2（S3）
smith@example.com     52 1（S2）
alex@example.com     75 0（S0）
bob@example.com      22 1（S2）

john@example.com      89 1（S2）
mark@example.com      30 0（S1）-
adam@examle.com       47 1（S2）
smith@example.com     52 0（S1）
alex@example.com     75 1（S2）
bob@example.com      22 0（S1）

#服务器节点例子，第一列为地址，第二列为权重
#------ Server -------  -Mem-#
#255.255.255.255:65535  66666#
10.0.1.1:11211  600
10.0.1.2:11211  300
10.0.1.3:11211  200
10.0.1.4:11211  350
10.0.1.5:11211  1000
10.0.1.6:11211  800
10.0.1.7:11211  950
10.0.1.8:11211  100
 
 
typedef struct
{
    unsigned int point;  // point on circle
    char ip[22];
} mcs;
 
typedef struct
{
    char addr[22];
    unsigned long memory;
} serverinfo;
 
typedef struct
{
    int numpoints;
    void* modtime;
    void* array; //array of mcs structs
} continuum;
 
typedef continuum* ketama_continuum;
 
 
/** \brief Generates the continuum of servers (each server as many points on a circle).
  * \param key Shared memory key for storing the newly created continuum.
  * \param filename Server definition file, which will be parsed to create this continuum.
  * \return 0 on failure, 1 on success. */
static int
ketama_create_continuum( key_t key, char* filename )
{
    if (shm_ids == NULL) {
        init_shm_id_tracker();
    }
 
    if (shm_data == NULL) {
        init_shm_data_tracker();
    }
 
    int shmid;
    int* data;  /* Pointer to shmem location */
    unsigned int numservers = 0;
    unsigned long memory;
    serverinfo* slist;
 
    slist = read_server_definitions( filename, &numservers, &memory );
    /* Check numservers first; if it is zero then there is no error message
     * and we need to set one. */
    if ( numservers < 1 )
    {
        set_error( "No valid server definitions in file %s", filename );
        return 0;
    }
    else if ( slist == 0 )
    {
        /* read_server_definitions must've set error message. */
        return 0;
    }
#ifdef DEBUG
     syslog( LOG_INFO, "Server definitions read: %u servers, total memory: %lu.\n",
        numservers, memory );
#endif
 
    /* Continuum will hold one mcs for each point on the circle: */
    mcs continuum[ numservers * 160 ];
    unsigned int i, k, cont = 0;
 
    for( i = 0; i < numservers; i++ )
    {
        float pct = (float)slist[i].memory / (float)memory;
        // 按内存权重计算每个物理节点需要分配多少个虚拟节点，正常是160个
        unsigned int ks = floorf( pct * 40.0 * (float)numservers );
#ifdef DEBUG
        int hpct = floorf( pct * 100.0 );
 
        syslog( LOG_INFO, "Server no. %d: %s (mem: %lu = %u%% or %d of %d)\n",
            i, slist[i].addr, slist[i].memory, hpct, ks, numservers * 40 );
#endif
 
        for( k = 0; k < ks; k++ )
        {
            /* 40 hashes, 4 numbers per hash = 160 points per server */
            char ss[30];
            unsigned char digest[16];
 
            // 在节点的addr后面拼上个序号，然后以该字符串去计算hash值
            sprintf( ss, "%s-%d", slist[i].addr, k );
            ketama_md5_digest( ss, digest );
 
            /* Use successive 4-bytes from hash as numbers
             * for the points on the circle: */
            int h;
            // 16字节，每四个字节作为一个虚拟节点的hash值
            for( h = 0; h < 4; h++ )
            {
                continuum[cont].point = ( digest[3+h*4] << 24 )
                                      | ( digest[2+h*4] << 16 )
                                      | ( digest[1+h*4] <<  8 )
                                      |   digest[h*4];
 
                memcpy( continuum[cont].ip, slist[i].addr, 22 );
                cont++;
            }
        }
    }
    free( slist );
 
    // 排序，方便二分查找
    /* Sorts in ascending order of "point" */
    qsort( (void*) &continuum, cont, sizeof( mcs ), (compfn)ketama_compare );
 
    . . .
 
    return 1;
}

function hrw_hash( nodes, key )
    local entries = {}
    for k,v in pairs(nodes) do
        entries[#entries + 1] = {node=v, weight=mmh3.hash32(tostring(key),v)}
    end
    local max_weight = 1
    local max_node = 0
    local max_index = 0
    for k,v in pairs(entries) do
        if v.weight > max_weight then
            max_weight = v.weight
            max_node = v.node
            max_index = k
        end
    end
    return max_node, max_index
end

int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; // b will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j ++) {
        if (random.next() < 1.0/(j+1) ) b = j ;
    } 
    return b;
}

int ch(int key, int num_buckets) {
    random. seed(key) ;
    int b = -1; //  bucket number before the previous jump
    int j = 0; // bucket number before the current jump
    while(j<num_buckets){
        b=j;
        double r=random.next(); //  0<r<1.0
        j = floor( (b+1) /r);
    }
    return b;
}

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}