Consistent Hash Implementation for Redis cache servers

RedisEnvGenerator.cpp

// @(#)RedisEnvGenerator.cpp
// Time-stamp: <Qian Julian 2012-01-26 21:25:50>
// Copyright 2011
// Version: $Id: RedisEnvGenerator.cpp,v 0.0 2011/12/26 09:44:44 jqian Exp $

#include <zlib.h>
#include <assert.h>

#include "RedisEnvGenerator.h"

int
RedisEnvGenerator::addRedisEnv(const char* host, uint16_t port){
    uint32_t envId = getRedisHostId(host, port);
    {
        HostMap::iterator itr = hostMap_.find(envId);
        if(itr == hostMap_.end()){
            hostMap_.insert(HostMap::value_type(envId, PositionList()));
        }
    }
    {
        IdMap::iterator itr = idMap_.find(envId);
        if(itr == idMap_.end()){
            RedisEnvNode env(host, port);
            idMap_.insert(IdMap::value_type(envId, env));
        }
    }
    // position exists
    PositionList& plst = hostMap_[envId];
    RedisEnvNode& env = idMap_[envId];
    int cnt = 0;
    for (int i = 0; i < replica_; ++i) {
        uint32_t pos = getHostPosition(host, port, i);
        if(pos){            // no collision
            posMap_.insert(PositionMap::value_type(pos, &env));
            plst.push_back(pos);
            ++ cnt;
        }
    }
    return cnt;
}

int
RedisEnvGenerator::delRedisEnv(const char* host, uint16_t port){
    uint32_t envId = getRedisHostId(host, port);

    HostMap::iterator itr = hostMap_.find(envId);
    int cnt = 0;
    if(itr != hostMap_.end()){
        PositionList& plst = itr->second;
        for (PositionList::const_iterator it = plst.begin();
             it != plst.end(); ++ it) {
            posMap_.erase(*it);
            ++cnt;
        }
        hostMap_.erase(itr);
    }

    idMap_.erase(envId);
    return cnt;
}

RedisEnvNode&
RedisEnvGenerator::getRedisEnv(uint32_t uin){
    // first, get uin position in the circle
    uint32_t pos = getUinPosition(uin);
    // then, find the nearest position of host
    PositionMap::iterator itr = posMap_.lower_bound(pos);
    if(itr != posMap_.end()){
        return *itr->second;
    }
    // if unmatched position, return the first host in the circle
    return *posMap_.begin()->second;
}


uint32_t
RedisEnvGenerator::getHostPosition(const char* host, uint16_t port, int i){
    // format:
    // index, port, ip-string
    char buf[32];
    int rval = snprintf(buf, 32, "%d%hu%s", i, port, host);
    if(rval){
        uLong pos = crc32(0L, Z_NULL, 0);
        pos = crc32(pos, (const Bytef*)buf, rval);
        // check collision
        PositionMap::const_iterator itr = posMap_.find(pos);
        if(itr == posMap_.end()){
            return pos;
        }
    }
    return 0;
}

uint32_t
RedisEnvGenerator::getUinPosition(uint32_t uin){
    char buf[16];
    int rval = snprintf(buf, 16, "%u", uin);
    if(rval){
        return crc32(0, (const Bytef*)buf, rval);
    }
    return 0;
}

uint32_t
RedisEnvGenerator::getRedisHostId(const char* host, uint16_t port){
    char buf[32];
    int rval = snprintf(buf, 32, "%hu%s", port, host);
    if(rval){
        return crc32(0, (const Bytef*)buf, rval);
    }
    assert(0);              // what's wrong?
    return 0;
}

RedisEnvGenerator.h

/* @(#)RedisEnvGenerator.h -*- mode: c++ -*-
 * Time-stamp: <Qian Julian 2011-12-26 22:05:40>
 * Copyright 2011
 * Version: $Id: RedisEnvGenerator.h,v 0.0 2011/12/26 09:44:33 jqian Exp $
 */

#ifndef _REDISENVGENERATOR_H
#define _REDISENVGENERATOR_H 1

#include <vector>
#include <string>
#include <map>

#include "hiredis.h"

// connect to redis server, defaultly seperate uin by mode 4
struct RedisEnvNode {
    RedisEnvNode()
        : context(NULL) {}
    RedisEnvNode(const char* h, uint16_t p)
        : host(h), port(p), context(NULL) {}
    std::string host;
    uint16_t port;
    redisContext *context;
};


// consistent hash
class RedisEnvGenerator {
public:
    explicit RedisEnvGenerator(uint8_t replica)
        : replica_(replica) {}
    ~RedisEnvGenerator() {}

    int addRedisEnv(const char* host, uint16_t port);
    int delRedisEnv(const char* host, uint16_t port);
    RedisEnvNode& getRedisEnv(uint32_t uin);
private:
    // TODO: host should be hashed on the circle averagly. and position
    // can not occur collision
    uint32_t getHostPosition(const char* host, uint16_t port, int i);
    uint32_t getUinPosition(uint32_t uin);
    uint32_t getRedisHostId(const char* host, uint16_t port);

private:
    typedef std::map<uint32_t, RedisEnvNode*> PositionMap;

    // for delete host
    typedef std::vector<uint32_t> PositionList;
    typedef std::map<uint32_t, PositionList> HostMap;

    // only one instance for all replicas
    typedef std::map<uint32_t, RedisEnvNode> IdMap;

    PositionMap posMap_;
    HostMap hostMap_;
    IdMap idMap_;
    uint8_t replica_;
};

#endif /* _REDISENVGENERATOR_H */

RedisEnvGenerator.py

import zlib

class RedisEnvGenerator(object):
    """
    Get the host in the circle built with consisitent hash
    """

    def __init__(self, replica):
        self.replica = replica
        self.posMap = dict()
        self.hostMap = dict()
        # TODO: use BST for better performance
        self.posList = []

    # input:
    # hostinfo = (ip-string, port-int)
    def addHost(self, hostinfo):
        # pdb.set_trace()
        hid = self.getHostId(hostinfo)
        if not self.hostMap.get(hid):
            self.hostMap[hid] = []
        for i in range(0, self.replica):
            try:
                pos = self.getHostPosition(hostinfo, i)
                self.posMap[pos] = hostinfo
                self.hostMap[hid].append(pos)
                self.posList.append(pos)
            except:             # collision
                pass
        self.posList.sort()

    def delHost(self, hostinfo):
        hid = self.getHostId(hostinfo)
        try:
            poses = self.hostMap[hid]
            for p in poses:
                del(self.posMap[p])
                i = self.posList.index(p)
                del(self.posList[i])
            del(self.hostMap[hid])
            self.posList.sort()
        except:                 # host not exist
            pass

    def getHost(self, uin):
        pos = self.getUinPosition(uin)
        for p in self.posList:
            if p > pos:
                return self.posMap[p]
        return self.posMap[self.posList[0]]

    # private
    def getHostPosition(self, hostinfo, i):
        # index, port, ip
        strfmt = "%d%d%s" % (i, hostinfo[1], hostinfo[0])
        pos = zlib.crc32(strfmt) & 0xFFFFFFFF
        if self.posMap.get(pos): # collision
            raise
        return pos

    def getUinPosition(self, uin):
        strfmt = "%d" % (uin)
        return zlib.crc32(strfmt) & 0xFFFFFFFF

    def getHostId(self, hostinfo):
        strfmt = "%s%d" % (hostinfo[0], hostinfo[1])
        return zlib.crc32(strfmt) & 0xFFFFFFFF