[Memcached] About Memcached

Memcached?

 

무료 오픈소스인 고성능 분산 메모리 객체 캐싱 시스템이지만 웹 서비스의 DB 부하를 경감시키기 위해 만들어 졌습니다.

 

공식 홈페이지에서 Memcached를 설명하는 부분이다. 이 내용을 조금 더 자세히 보면

• 오픈소스 : BSD license로 수정 및 배포 제한 없음
• 고성능 : 멀티 쓰레드를 통해 빠른 처리 속도를 지원
• 분산 : 노드의 확장을 통한 분산처리 지원
• 메모리 : 모든 데이터를 메모리에 저장하여 빠르게 접근/처리 가능
• 캐싱 시스템 : 자주 사용되는 데이터를 미리 저장해두어 DB의 로드를 줄여 처리 속도 향상

같은 특징을 가지고 있다.

Memcached는 데이터를 key-value 구조로 메모리에 저장한다. key를 통해 빠르게 데이터에 접근할 수 있다. Memcached에서 데이터는 문자열만 지원하며 HTML과 같이 상대적으로 작고 정적인 데이터를 캐싱할 때 사용된다.

 

구조

Memcached의 핵심 구조는 다음과 같다.

• key, value, 만료 시간 및 기타 정보를 담고 있는 캐시 데이터 구조
• 데이터를 빠르게 찾기 위한 Hash Table
• 메모리 관리자인 Slab Allocator
• 캐시가 가득 찼을 때 캐시 항목의 제거 순서를 결정하는 LRU list

하나 씩 살펴보자

 

1. Hash Table

 

Memcached에서 빠른 데이터 검색을 위해 해쉬 테이블을 사용한다. 각각의 버킷은 데이터들의 linked-list 형태이다. 그리고 버킷을 배열 형태로 유지하여 키의 해쉬값을 통해 빠른 접근이 가능하다. 데이터 접근 시 키 값의 해쉬값을 구하여 테이블의 인덱스에 해당하는 버킷으로 이동하여 원하는 데이터를 찾을 수 있다.

 

해쉬 테이블의 기본 크기는 2¹⁶이며 저장된 데이터의 수가 테이블 크기의 1.5배가 되면 확장이 진행된다. 테이블의 최대 크기는 2³²이다. 확장이 진행되는 코드는 아래과 같다.

​x
//assoc.c
​
void assoc_start_expand(uint64_t curr_items) {
    if (started_expanding)
        return;
​
    if (curr_items > (hashsize(hashpower) * 3) / 2 &&
        hashpower < HASHPOWER_MAX) {
        started_expanding = true;
        pthread_cond_signal(&maintenance_cond);
    }
}

 

해쉬 테이블 자료 구조에 관한 상세 내용은 여기에서 확인할 수 있다.

 

 

Slab allocator

Memcached와 redis를 비교하여 장점으로 나타내는 내용 중 하나가 효율적인 메모리 관리이다. 바로 slab이 효율적인 메모리 사용을 제공하는 것이다. 그렇다면 slab은 무엇일까?

 

slab은 일종의 메모리 할당 단위로 일정한 크기의 메모리인 chunk의 집합으로 구성되어있다. Memcached에서는 slab 리스트를 유지하여 데이터를 저장할 메모리를 할당한다. Memcached에서는 다양한 크기의 chunk를 가진 slab class들을 유지하고 있습니다. chunk 크기의 최소값인 48kb를 가진 slab부터 시작하여 1.5배 큰 chunk를 가진 slab 리스트를 가지고 있습니다. MAX_SLAB_CLASS는 201로 정의 되어 있지만 chunk의 크기가 slab의 크기보다 작을 때 까지만 할당됩니다.

데이터를 저장할 경우 적절한 크기의 chunk를 가진 slab을 찾아 데이터를 저장합니다. 이렇게 사용가능한 메모리를 미리 할당해 두고 사용하기 때문에 malloc/free 함수보다 빠른 할당이 가능하며, 메모리 파편화가 덜 일어나게 됩니다.

 

3. LRU list

LRU(Least Recentrly Used) 알고리즘은 가장 오래 쓰이지 않은 항목부터 삭제해 나가는 알고리즘입니다. Memcached에서는 LRU 정책을 통해 메모리를 재사용하는데 이를 위한 LRU list를 가지고 있습니다.

 

LRU list는 double-linked-list 형태로 구현되어 있습니다. 캐시 항목에 접근한 순서를 유지하며 가장 오래된 항목을 찾을 때 TAIL 부터 검색해 재사용이 가능한 곳을 삭제합니다.

Memcached는 Lazy-Expiring 정책을 사용합니다. 이는 키가 만료되어도 노드에서 삭제하지 않는 것을 의미합니다. 만료된 키에 접근할 경우 해당 키를 검사하여 만료 여부를 확인 후 메모리에서 제거하게 됩니다.

 

4. 캐시 데이터 구조

Memcached에서 캐시 데이터를 저장하기위해 key/value 이외에도 추가적인 데이터를 포함한 구조를 사용한다.

• key, key의 길이
• data, data의 크기
• 만료 시간
• 최근 접근 시간
• 해쉬 테이블에서 다음 노드를 가르키는 포인터
• LRU list에서 double-linked-list를 위해 사용되는 포인터
• 해당 캐시 항목에 동시에 접근하는 스레드 수
• 캐시항목 상태 플래그

Memcached 소스코드를 보면 다음과 같은 구조체를 확인할 수 있다.

xxxxxxxxxx
//memcached.h
​
/**
 * Structure for storing items within memcached.
 */
typedef struct _stritem {
    /* Protected by LRU locks */
    struct _stritem *next;
    struct _stritem *prev;
    /* Rest are protected by an item lock */
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

 

Memcached의 구성 요소에 대해 알아보았다.