Abstraction

memcached 는 빠르고 가벼운 것에 촛점이 맞춰져 있어 기본적으로 clustering, replication 등의 기능을 지원하지 않는다. 따라서 클라이언트 라이브러리에서 key에 따라 각각의 서버에 분배하는 알고리즘을 적용해야 하는데 PHP와 Java (또한 Ruby, Python 등등) 각각의 라이브러리마다 분배하는 알고리즘이 서로 상이하여 다른 서버를 바라보는 문제가 있다.

이 문제를 해결하기 위해 모든 분배 알고리즘의 기준을 PHP의 memcached 라이브러리가 수행하는 CRC32 로 맞추기로 정했다. PHP의 기본 memcached 라이브러리는 key 값을 CRC32로 해싱하여 그 수(int)를 서버 댓수에 나눈 나머지 값으로 몇 번 서버인지를 찾는다.

PHP의 memcached 라이브러리

PHP의 memcached 라이브러리의 소스는 아래에서 찾을 수 있다. http://svn.php.net/viewvc/pecl/memcache/trunk/

해싱 함수를 초기화하는 함수는 memcached.c 에서 찾을 수 있다.
mmc_hash_crc32 가 기본으로 실행됨을 알 수 있다.

static void mmc_pool_init_hash(mmc_pool_t *pool TSRMLS_DC) /* {{{ */
{
        mmc_hash_function hash;

        switch (MEMCACHE_G(hash_strategy)) {
                case MMC_CONSISTENT_HASH:
                        pool->hash = &mmc_consistent_hash;
                        break;
                default:
                        pool->hash = &mmc_standard_hash;
        }

        switch (MEMCACHE_G(hash_function)) {
                case MMC_HASH_FNV1A:
                        hash = &mmc_hash_fnv1a;
                        break;
                default:
                        hash = &mmc_hash_crc32;
        }
       
        pool->hash_state = pool->hash->create_state(hash);
}

static unsigned int mmc_hash_crc32(const char *key, int key_len) /* CRC32 hash {{{ */
{
        unsigned int crc = ~0;
        int i;

        for (i=0; i<key_len; i++) {
                CRC32(crc, key[i]);
        }

        return ~crc;
}
/* }}} */

이 중 서버를 찾는 알고리즘은 memcache_standard_hash.c 에서 찾을 수 있다.

mmc_t *mmc_standard_find_server(void *s, const char *key, int key_len TSRMLS_DC) /* {{{ */
{
        mmc_standard_state_t *state = s;
        mmc_t *mmc;

        if (state->num_servers > 1) {
                unsigned int hash = mmc_hash(state, key, key_len), i;
                mmc = state->buckets[hash % state->num_buckets];

                /* perform failover if needed */
                for (i=0; !mmc_open(mmc, 0, NULL, NULL TSRMLS_CC) && MEMCACHE_G(allow_failover) && i<MEMCACHE_G(max_failover_attempts); i++) {
                        char *next_key = emalloc(key_len + MAX_LENGTH_OF_LONG + 1);
                        int next_len = sprintf(next_key, "%d%s", i+1, key);
                        MMC_DEBUG(("mmc_standard_find_server: failed to connect to server ‘%s:%d’ status %d, trying next", mmc->host, mmc->port, mmc->status));

                        hash += mmc_hash(state, next_key, next_len);
                        mmc = state->buckets[hash % state->num_buckets];

                        efree(next_key);
                }
        }
        else {
                mmc = state->buckets[0];
                mmc_open(mmc, 0, NULL, NULL TSRMLS_CC);
        }

        return mmc->status != MMC_STATUS_FAILED ? mmc : NULL;
}
/* }}} */

mmc_hash 라는 함수로 해싱을 수행하는 것을 알 수 있으며 mmc_hash 함수는 다음과 같다.

static unsigned int mmc_hash(mmc_standard_state_t *state, const char *key, int key_len) /* {{{ */
{
        unsigned int hash = (state->hash(key, key_len) >> 16) & 0x7fff;
        return hash ? hash : 1;
}
/* }}} */

Java 코드

따라서 위 알고리즘을 Java 측에서 구현하면 동일한 분배 알고리즘을 구현할 수 있다. CRC32 해싱을 Java로 구현했다.

private int getServerNode(String key) {
         
    CRC32 c = new CRC32();
    for (int i=0; i< key.length(); i++) {
        c.update(key.charAt(i));
    }
         
    int mmc_hash = (int) ((c.getValue() >> 16) & 0x7fff);
 
    return mmc_hash % serverList.length;
}

기타

CRC32 해싱을 지원하는 memcached 클라이언트 라이브러리를 이용할 경우에는 굳이 위 함수를 구현하지 않아도 되며 기본 값으로 CRC32를 선언해주기만 하면 된다.

Ruby, Python 등에서 memcached 에 접근할때도 PHP를 기준으로 한 CRC32 해싱으로 설정하면 서로 다른 언어에서 동일한 서버로 분배할 수 있어 편리하다.

References