멤캐시(Memcach)

가장 인기 있는 NoSQL 솔루션으로 불릴 수 있는 프로젝트는 바로 Memcached입니다. 페이스북(Facebook), 트위터(Twitter), Reddit 및 유투브(YouTube)와 같은 클라우드 및 웹 서비스 회사에서 사용하는 키-밸류 스토어 기반의 인-메모리(In-Memory) 제품입니다.

 

원래 라이브저널에서 내부적인 용도로 개발 되었고 맴캐시는 작은 크기의 다량의 데이터에 접속할 때 가장 빠른 속도를 제공해줍니다. 맴캐시는 간단한 프로토콜을 넘어서 키-밸류 스토어의 데이터 모델이라 할 수 있으며, NoSQL 커뮤니티내의 산업계 표준으로 사용되고 있습니다.

 

맴캐시 클라이언트는 대다수의 프로그램 언어에서 사용이 가능합니다. 거의 오늘날 인터넷의 모든 대부분의 큰 사이트에서는 맴캐시를 사용하거나 다른 비슷한 솔루션을 사용하고 있습니다.

 

 

 

Memcached 프로그램의 위치

Memcached는 키-밸류쌍으로이루어져 간단한 데이터 타입을 저장하며, 인-메모리(In-Memory) 기반에서 데이터를 처리하기 때문에 NoSQL처럼 영구적(persistent) 으로 데이터를 디스크에 저장하지는 않습니다. 아래의 그림은 웹 서비스 아키텍처를 설명한 그림으로 여기에서 Memcached 프로그램은 프론트-엔드 웹(Front-end web) 과 백-엔드 데이터베이스(Back-end Database) 사이에 위치합니다.

[ 웹 서비스 아키텍처 ]

멤캐시드(Memcached)의 용도
멤캐시드의 용도는 데이터 요청을 가로채어 가능한 경우 이를 캐시(시스템 메모리)에서 직접 서비스 하게 만들고, 데이터베이스에 연결된 디스크 스토리지에 대한 접근을 줄이는 것이 목적입니다. 그리고 미리 계산된 값을 캐시에서 저장하고 조회하게 하여, 요청 때 마다 많은 양의 계산을 피할 수 있도록 합니다.

캐시 메모리(Cache memory)   캐시(Cache)는 주기억장치의 동작 속도가 CPU의 처리 속도를 따라 잡지못해 발생하는 병목 현상을 해결하기 위해서 보다 빠른 속도를 갖는 메모리를 주기억장치와 CPU 사이에 배치시키는 기술을 말합니다. 캐시의 용량이 주기억장치 용량보다 현저히 적기 때문에 주기억장치에 저장된 모든 내용을 캐시로 가져오는 것은 불가능하므로, 제한된 캐시 용량에서 사용자가 가져갈 데이터를 미리 메모리에서 가져오는 알고리즘이 매우 중요합니다.    [ 캐시의 개념도 ]

논리적 캐시(Cache) 확보 방법

멤캐시드에서 논리적 캐시를 확보하는 방법은 연결된 서버에서 전체 논리적 캐시의 일부분으로 시스템 메모리를 제공합니다. 예를 들면, 각 노드에 128GB의메모리 공간이 있는 10개 노드로 구성된 멤캐시드 클러스터는 전체적으로 1.28TB의 논리적 캐시를 제공합니다. 논리적 캐시는 웹 서비스를 위한 영구 데이터 저장소인 데이터베이스의 내용과 쿼리와 계산 결과들이 사용합니다.

 

캐시(Cache) 교체 알고리즘

캐시의 키와 값은 LRU(Least Recently Used) 정책과 TTL(Time To Live)을 사용하여 유지 관리됩니다. 웹 서비스에서 사용자에게 요청이 들어오면 데이터베이스에서 요청된 데이터를 인출하기 위해서 여러 번의 접근이 필요하게 됩니다. 속도를 향상시키기 위해서는 데이터베이스에서 데이터를 가져오는 횟수를 줄이고 캐시를 이용하여 데이터를 가져와야 합니다. 효율적인 캐시 교체 알고리즘을 사용하면 데이터베이스에 접근하여 데이터를 가져오는 횟수를 현저히 줄일 수 있습니다.

캐시 교체 방식   LRU(Least Recently Used): 가장 오랫동안 사용되지 않는 블록 교체 FIFO(First In First Out): 캐시내에가장 오래 있었던 블록 교체 LFU(Least Frequently Used): 사용빈도가 가장 낮은 블록 교체 Random: 후보 블록 중 한 블록을 임의로 선택 Optimal: 향후 가장 참조되지 않은 블록을 교체 (실현 불가능 알고리즘)

멤캐시드(Memcached) 아키텍처

 

데이터구조

멤캐시드는 다음과 같은 4가지 주요 데이터 구조가 있습니다.

 

① 캐시 항목을 찾기 위한 해시테이블

② 캐시가 가득 찼을 때 캐시 항목 제거(eviction) 순서를 결정하는 LRU 리스트

③ 키(Key), 값(Value), 플래그 및 포인터들을 담고 있는 캐시 데이터 구조

④ 캐시 항목 데이터 메모리 관리자인 슬랩 할당자 (Slab allocator)

 

해시 테이블 구조

해쉬 테이블의 구조는 버킷(Bucket) 배열을 말합니다. 버킷 배열이란 하나의 주소를 가진 연속된 저장 공간을 말합니다. 하나의 공간은 단방향 링크드 리스트로 구성되어 있습니다.

 

[ 캐시 항목 조회에 사용되는 해쉬 테이블 데이터 구조 ]

 

 

LRU 리스트

제거(eviction) 순서를 결정하는데 사용되는 LUR는 단일 크기의 슬랩(메모리 할당 단위)마다 존재하며, 그 슬랩의 모든 캐시 항목들을 접근 순서대로 유지하는 더블 링크드 리스트(Double linked list) 입니다.

 

이중 링크드 리스트(Double linked list)   연결 리스트(linked list)는 일정한 순서를 가지는데이터 항목들을 표현하는 방법 중의 하나입니다. 배열과 같은 순차적 표현 방법과는 달리 데이터 항목들의 논리적 순서만 유지되고 기억 장소 내에서는 각 항목들의 임의의 위치를 가지도록 하는 자료 구조입니다. 연결 리스트에서는 각 데이터 항목들이 기억 장소 내의 어떤 위치에 어떤 항목이 있는지를 표시해주어야 합니다. 이를 위해 데이터 항목에는 값 뿐만 아니라 다음 항목의 위치 정보도 함께 저장해 둡니다.   이중 링크드 리스트는 임의의 항목을 찾을 때 양쪽 방향으로 검색할 수 있는 구조입니다. 이를 위해서 선행 항목을 가리키는 좌링크(LLINK)와 값을 저장하는 데이터 필드 마지막으로 다음 항목을 가리키는(RLINK)로 구성되어 있습니다. [ 이중 링크드 리스트 구조 ]

 

LUR 리스트에서 어떤 캐시 항목을 제거하는 경우 이 리스트의 마지막에 있는 캐시 항목부터 검사하여 가장 오랫동안 사용하지 않은 항목을 찾아냅니다.

 

[ LRU 데이터 구조 ]

 

캐시 데이터 구조

캐시 항목 데이터 구조는 키-값 구조로 데이터가 들어가고, 다음과 같은 메타데이터(Metadata)도 들어 있습니다.

 

① 해시테이블에서 버킷(Bucket) 당 단일 링크드 리스트를 가리키는 포인터

② LRU에서 이중 링크드 리스트에 사용되는 포인터

③ 캐시 항목에 동시에 접근하는 스레드 수를 나타내는 레퍼런스 카운터

④ 캐시 항목 상태 플래그

⑤ 키(Key)

⑥ 값 길이(Byte)

⑦ 값(Value)

 

슬랩 할당자

슬랩 할당자는 캐시 항목에 대한 메모리 관리 기능을 제공합니다. 캐시 항목은 상대적으로 크기가 작아서 시스템 콜(malloc/free)을 사용한 작은 메모리 청크(chunk)의 할당 및 해제는 속도가 느리고 스래싱(thrashing)이 발생할 가능성이높습니다. 그래서 멤캐시드는 이 방법 대신에 할당 단위로 슬랩을 사용합니다. 스랩은 내부에 많은 항목들을 포할할 수 있는 큰 메모리 청크(Chunk)입니다.

 

예를 들면, 1,024바이트 메모리 청크의 슬랩은 64바이트 이하 캐시 항목을 16개까지 저장 가능합니다. 슬랩 할당자는 우선 큰 메모리를 할당하고 Free 리스트를 유지합니다. 캐시 항목을 접근할 때마다 슬랩 할당자는 저장할 값 크기를 확인하고 수용할 수 있을 만큼 큰 슬랩내의 캐시 항목을 되돌려줍니다. 어떤 경우에는 이 방법이 공간을 비효율적으로 사용하기도 하지만 성능이 좋고 메모리 스래싱을 피할 수 있습니다.

 

스레싱(Thrashing)   가상메모리 사용으로 인하여 프로세스가 사용할 수 있는 가상메모리 페이지(Page)가 부족할 때 CPU가 사용자의 프로그램에 자원을 할당하지 못하고 성능이 저하되는 현상을 말합니다.