Memcached의 확장성 개선

Computer Science/Cache 2012. 11. 6. 13:04

이 글은 INTEL사에서 작성한 Enhancing the Scalability of Memcached를 번역한 기사입니다. 본 내용은 2012년도 9월17일(월)에 개최되는 개발자 컨퍼런스 DEVEIW 2012에서 원문과 동일한 제목의 세션으로 발표가 진행될 예정입니다. hello world 독자분들과 DEVIEW 참석자분들을 위한 참고자료로 기고되었으며 PDF로도 다운받으실 수 있습니다.

Memcached의 확장성 개선.pdf

1 Memcached 및 웹 서비스 소개

Memcached는 Facebook[1], Twitter[2], Reddit[3] 및 YouTube[4]와 같은 클라우드 및 웹 서비스 제공 회사에서 사용하는 key-value 메모리 캐시로, 웹 데이터를 소비자에게 서비스하는 데 있어 지연 시간을 줄이고 데이터베이스 및 컴퓨팅 서버[5]에 대한 증설을 줄여주게 한다. Latency를 줄이는 것 외에도 memcached의 확장성 있는 아키텍처 (scale-out) 는 memcached 서버를 간단하게 추가만 하여 처리량을 높일 수 있다. 그러나 코어 수가 4개를 넘으면 성능 저하가 발생하기 때문에 수직 scalability (scale-up) 에는 문제가 있다[1][6].

이 연구에서는 왕복 시간 (RTT, Round-Trip Time)에 대한 1밀리초 이하의 지연에 대한 SLA (Service Level Agreement)를 유지하면서 concurrent data structure, 새로운 캐시 교체 알고리즘 및 네트워크 최적화를 활용하여 Intel® Xeon® E5 서버 프로세서에서 현 버전(v1.6)의 오픈 소스와 비교했을 때 6배 이상 처리량을 높이는 memcached 최적화 방법을 소개한다. 그림 1은 v1.6 memcached 베이스라인에 비해 6배 빠른 속도의 최적화된 버전을 보여준다. 여기서는 32개의 논리적 코어에서 최적화된 버전이 초당 3억 1천 5백 만 처리량 (RPS)을 제공하며, 1밀리초의 절반 수준의 RTT를 보인다.

그림 1 기본 오픈 소스 코드 버전 1.6.0_beta1 및 최적화된 버전의 구성을 사용하여 측정한 최대 처리량 비교

Memcached는 key-value 쌍으로 이뤄진 간단한 데이터 타입을 저장하며, NoSQL 데이터베이스와 유사하지만 NoSQL처럼 영구적 (persistent) 이지는 않다. Memcached는 모든 key-value 쌍을 메모리에 저장하므로 서버장애나 오류가 발생했을 때 저장된 데이터가 모두 손실된다. 이 글에서는 키 (key)와 해당 키의 값(value)을 지칭할 때 '캐시 항목 (cache item)' 이라는 용어를 사용한다. 이때 키는 고유한 값이다. 웹 서비스 아키텍처에서 memcached 애플리케이션은 그림 2에서 보는 바와 같이 프론트엔드 (Front-end) 웹 서버 (또는 계층 (tier))와 백엔드 (Back-end) 데이터베이스 사이에 위치한다.

그림 2 프론트엔드 웹 계층 및 백엔드 데이터베이스 사이에 위치하는 memcached 서버

Memcached의 용도는 데이터 요청을 가로채어 가능한 경우 이를 캐시 (시스템 메모리)에서 직접 서비스 하게 만들고, 백엔드 데이터베이스에 연결된 디스크 스토리지 access를 줄이는 것이 목적이다. 그리고 미리 계산된 값을 캐시에서 저장하고 조회하게 하여, 요청 때 마다 많은 양의 계산을 피할 수도 있다. 두 경우 모두 조회 또는 data 결과를 계산하는 시간이 줄어들게 된다. Memcached 논리적 캐시에는 서버군들로 구성이 되어, 각 서버는 전체 논리적 캐시의 일부분으로 시스템 메모리를 제공한다 [7][8][9]. 예를 들어, 각 노드에 128GB의 메모리 공간이 있는 10개 노드로 구성된 memcached 클러스터는 전채적으로 1.28TB의 논리적 캐시를 제공한다. 논리적 캐시는 웹 서비스를 위한 영구 데이터 저장소인 백엔드 데이터베이스 또는 컴퓨팅 서버의 query/계산 결과 데이터로 채워진다. 캐시 항목은 LRU (Least Recently Used) 정책과 TTL (Time To Live)을 사용하여 유지 관리된다. 항목이 제거되면 해당 슬롯은 최신 항목으로 채워진다.

웹 서비스에서 하나의 요청 (http request) 은 memcached, 데이터베이스 및 기타 서비스로의 여러 번의 요청이 필요할 수 있다. 효율적인 캐싱 전략을 사용하면 memcached에 대한 조회 횟수는 데이터베이스 조회 횟수보다 몇 십 배 많을 수 있다 (DB 조회를 줄임). Memcached의 시스템 메모리에서 데이터 조회는 같은 데이터를 데이터베이스에서 조회하는 것보다 열 배 이상 빠르며 (마이크로 초 대 밀리 초 단위), 대부분의 경우 데이터를 on-demand로 계산/조회 하는 것보다 몇 십 배 이상 빠르다. 따라서 웹 서비스 요청에 대해 빠른 사용자 응답 시간을 제공하기 위해서는 데이터베이스 조회 및 on-demand 계산은 피해야 한다.

1.1 용어

이 글에서는 다음과 같은 용어를 사용한다.

LRU (Least Recently Used) – memcached에서 캐시 항목 추가를 위한 공간을 확보하기 위해 캐시에서 필요 없는 항목을 결정 eviction 알고리즘. 가장 오래된 항목들을 evict하는 알고리즘.

Base – 수정되지 않은 기본 버전(1.6.beta_0)의 memcached이며, memcached.org에서 직접 다운로드 가능.

Bags – 성능 향상을 위해 최적화된 버전의 memcached 약어. 'Bags'은 'Bag LRU'라는 수정된 LRU 캐시 업데이트 전략이고, 개발된 코드의 첫 번째 섹션이다.

RTT (Round Trip Time) – memcached 요청이 경과된 시간으로, 클라이언트로 응답이 올 때까지 클라이언트에서 서버로 가는 요청 경과 시간 포함.

SLA (Service Level Agreement) – 사용자에 대한 수용할 수 있는 웹 서비스 요청 응답 시간을 유지하기 위해 허용되는 최대 RTT. 응답 시간이 SLA를 넘어서는 경우 웹 서비스 요청을 생성하는 데 수용할 수 없는 응답 시간이 나타난다. (프런트엔드 웹 티어로 전송되는) 웹 서비스 요청당 (memcached논리적 캐시로 전송되는) 여러 memcached 요청이 있을 수 있다. 이 글에서는 프런트엔드 웹 계층 클라이언트 요청에 대한 memcached SLA 응답 시간은 1밀리초이다.

NIC (Network Interface Card) – 시스템에 사용된 네트워크 카드.

2 memcached 아키텍처

2003년 memcached가 도입될 당시에는[5] 여러 코어가 있는 x86 프로세서가 매우 적었으며 멀티 소켓 서버의 가격이 매우 비쌌다. Intel® Xeon® 듀얼코어는 2005년, 쿼드코어 프로세스는 2009년까지는 출시되지 않았다. 오늘날, 듀얼 소켓, 8코어 및 16코어 서버 시스템은 웹 서비스를 위한 구성 요소이며, 프로세서 개발 로드맵에 따르면 코어 개수의 증가는 계속 될 것으로 보인다[10]. 이러한 첨단 시스템은 여러가지 워크로드에서 여러 스레드 또는 프로세스를 사용하여 동시에 실행할 수있게 되어 있으나, memcached는 현재의 데이터 구조 및 소프트웨어 아키텍처 때문에 아직 그것이 불가능하다 [1][6].

2.1 데이터 구조

memcached는 다음과 같은 4가지 주요 데이터 구조가 있다.

캐시 항목을 찾기 위한 해쉬 테이블
캐시가 가득 찼을 때 캐시 항목 제거 (eviction) 순서를 결정하는 LRU (least recently used) list
키 (key), 데이터 (value), 플래그 및 포인터들을 담고 있는 캐시 데이터 구조
캐시 항목 데이터 메모리 관리자인 슬랩 할당자 (slab allocator)

해쉬 테이블 데이터 구조는 bucket 배열이다. 배열 크기 (k) 는 항상 2의 거듭제곱이고 '2^k-1'의 값을 구해 hash 마스크로 사용한다. Bit-wise AND (예: hash_value & hash_mask) 계산으로 hash 값이 들어 있는 bucket을 신속하게 찾아낸다. bucket들은 NULL로 끝나는 캐시 항목의 linked-list이다. 그림 3는 이러한 데이터 구조를 보여준다.

그림 3 캐시 항목 조회에 사용되는 해쉬 테이블 데이터 구조

제거 (eviction) 순서를 결정하는 데 사용되는 LRU는 단일 크기의 슬랩 (아래 설명된 메모리 할당 단위) 마다 존재하며, 그 슬랩의 모든 캐시 항목들을 접근 순서대로 유지하는 double linked-list이다. Double linked-list를 형성하기 위한 포인터들은 각 캐시 항목 구조에 유지되며, 캐시 항목이 LRU에서 위치 조정될 때마다 수정된다. LRU list에서 어떤 캐시 항목을 제거 (eviction) 하는 경우 이 list의 tail에 있는 캐시 항목부터 검사하여 메모리 재사용이 가능한 가장 오래된 캐시 항목을 찾아낸다. 그림 4는 LRU 데이터 구조를 보여준다.

그림 4 캐시 항목 제거 순서를 결정하는 데 사용되는 현 버전의 오픈 소스 LRU 데이터 구조

캐시 항목 데이터 구조에 key/value 쌍 데이터가 들어있고, 또 다음과 같은 metadata 들이 들어있다.

해쉬 테이블에서 bucket 당 single linked-list를 가르키는 포인터
LRU에서 double linked-list에 사용되는 포인터
캐시 항목에 동시에 접근하는 스레드 수를 나타내는 reference counter
캐시 항목 상태 플래그
키 (key)
값 길이 (바이트)
값 (value)

슬랩 할당자는 캐시 항목에 대한 메모리 관리 기능을 제공한다. 캐시 항목은 상대적으로 크기가 작아서, 시스템 call (malloc/free)을 사용한 작은 메모리 청크 (chunk)의 할당 및 해제는 속도가 느리고 스래싱 (thrashing)이 발생할 가능성이 높다. 그래서 memcached는 이 방법 대신 메모리 할당 단위로 슬랩을 사용한다. 슬랩은 내부에 많은 항목들을 포함할 수 있는 큰 메모리 chunk이다. 예를 들어 1,024 byte 메모리 chunk의 슬랩은 64바이트 이하 캐시 항목을 16개까지 저장 가능하다. 슬랩 할당자는 이렇게 큰 메모리를 할당하고 free list를 유지한다. 캐시 항목이 접근 될 때마다 슬랩 할당자는 저장할 값 크기를 확인하고 수용할 수 있을 만큼 큰 슬랩내의 캐시 항목을 돌려준다. 어떤 경우에는 이 방법이 공간을 비효율적으로 사용하기도 하지만 성능이 좋고 메모리 스래싱을 피할 수 있다.

2.2 명령어

Memcached 서버는 3가지 기본 명령어를 지원한다.

GET - 캐시 항목 조회
STORE - 캐시 항목 추가
DELETE - 캐시 항목 제거

또한 통계 (stats), 교체 (replacements), 연산 (arithmetic), 플러시 (flush) 및 업데이트 (updates)를 비롯한 15가지의 기타 명령들이 있다. 이런 명령어들의 코드 경로는 일반적으로 위 기본 명령의 순서를 따른다. 예를 들어, 교체 (replacement)는 먼저 캐시 항목을 삭제 (DELETE)한 후 새로운 캐시 항목을 해쉬 테이블 및 LRU에 저장 (STORE) 한다. GET 명령은 memcached 여러 명령 중 workload에서 가장 많이 사용되는 명령이어서 여기서는 GET 명령을 중점적으로 다룬다[11].

3가지 기본 명령어 (GET, STORE, DELETE)에 대한 memcached에서의 실행 흐름은 다음과 같다.

1. NIC에 요청 packet이 도착하고 libevent에 의해 처리

2. worker thread

연결 및 데이터 패킷을 받기
명령 및 데이터를 확인

3. Hash 값은 키 데이터에서 생성

4. 해쉬 테이블과 LRU 처리를 위해 global cache lock 획득 (Critical Section 시작)

(STORE만 해당)
- 캐시 항목 메모리 할당
- 캐시 항목 데이터 구조에 데이터를 저장 (플래그, 키, 값)
해쉬 테이블에서 캐시 항목을 GET, STORE, DELETE하기 위해 해쉬 테이블을 탐색
캐시 항목을 LRU 앞에 삽입 (GET, STORE) 또는 제거 (DELETE) 하면서 LRU 수정
캐시 항목 플래그를 업데이트

5. Global cache lock 해제 (Critical Section 끝)

6. 응답 구성

7. (GET만 해당) global cache lock 확인 (assert)

캐시 항목 ref count를 1 감소
global cache lock 해제

8. 요청한 클라이언트 (프론트엔드 웹 서버)로 응답 전송

2.3 프로세스 흐름

그림 5에 데이터 요청 처리 시 cache cluster 관점에서 memcached 프로세스 흐름이 설명되어있다. 여러 서버가 함께 작동하여 더욱 큰 단일 논리적 데이터 캐시 역할을 수행한다. 기본적으로 이러한 서버는 대규모 DHT (distributed hash table: 분산 해쉬테이블)을 구성한다. 그림 5를 찬찬히 살펴보면 클라이언트 (일반적으로 사용자를 위한 응답을 구성하는 웹 tier 서버 형태나 계산용 데이터가 필요한 컴퓨팅 서버 형태) 가 memcached로의 요청을 담당하는 것을 알 수 있다. Memcached가 시작되면 이러한 요청을 처리하기 위해 일반적으로 서버의 프로세서 (core) 개수에 맞게 일정한 수의 worker thread가 생성된다.

그림 5 오픈 소스 v1.6에서 캐시 항목 명령 (STORE/GET/DELETE)을 위한 프로세스 흐름

클라이언트 요청들은 각 worker thread로 분산되어 처리된다. GET 명령의 경우, 각 스레드는 키와 그 키의 값 (value) 데이터 위치를 찾기 위해 해쉬 테이블 조회를 해야 한다. 또한 그 key-value가 최근에 액세스되었음을 표시하고 제거 (eviction) 순서를 업데이트하기 위해 LRU list 앞으로 이동한다. 안타깝게도 이 두 가지 code path에 공유 데이터 구조에 대한 serialization (순차화)이 필요하다. 그렇게 데이터를 찾으면 worker thread가 시스템 메모리에서 데이터를 조회하고 요청한 클라이언트로 전송한다.

해쉬 테이블로의 접근을 보호하는 global cache lock을 통해 해쉬 테이블의 스레드 안정성 (thread-safety)을 보장한다. 또한 캐시 제거 (eviction) 관리하기 위해 유지되는 LRU linked-list에서는, 스레드 안정성을 보장하기 위해 캐시 항목의 LRU linked-list가 수정될 때도 동일한 global cache lock을 사용한다. 스레드는 네트워크 프로토콜 래퍼 (wrapper)인 'libevent'에 의해 만들어진다. 스레드는 'libevent'에서 요청을 대기하고 있다가 요청을 받으면 패킷에서 데이터를 빼내고 명령을 디코딩 한다. 캐시 항목에 대한 명령 (GET/STORE/DELETE/ARITHMETIC)이라고 가정한다면, 스레드는 키에서 hash 값을 계산하고 global cache lock을 획득한다. 스레드는 명령이 완료될 때까지 lock을 유지한 후 lock을 해제하고 응답을 구성한다. 이렇게 하면 memcached가 효과적으로 순차화 (serialize) 되어 데이터 일관성 및 스레드 안전성이 보장된다.

2.4 성능 병목

Global cache lock은 [1] 및 [6]에 설명된 것처럼 스레드가 4개 이상인 경우 성능 병목이 되는 주 원인이다. 이 증상은 테스트 (그림 7 및 표 1)를 통해서도 확인할 수 있다. 그림 7은 오픈 소스 memcached에서 코어가 4개를 넘어설 때 처리량이 감소되는 것으로 나타난다. 이 lock은 coarse-grained (긴 code path를 serialize하기 때문에) 이어서, 순차 실행 시 소요되는 시간이 많으며 worker 스레드 간의 lock 경합이 높다.

이를 확인하기 위해 Intel® Vtune™ Amplifier XE1을 사용하여 stack trace를 생성하여 profiling 한 결과 대부분의 실행 시간이 lock (global cache lock 대기 등)에서 소요된 것으로 나타났다. Stack trace를 더 자세히 확인한 결과 global cache lock이 경합을 유발한 것으로 나타났다. 문제의 신속한 확인을 위해 global cache lock을 제거하자 (안전하지 않지만 효율적이라는 가정 하에), read-only (GET) 워크로드에서 처리량이 크게 증가했다.

여러 다른 연구에서도 밝혀진 것과 같이 lock 경합이 프로그램의 병렬 성능 저하를 야기한다. 참고 문헌 [12]는 경합과, 경합이 프로그램 성능 저하에 어떤 영향을 주는지에 대한 심도 있는 분석이 되어 있다. 우리는 global cache lock에 대한 경합을 피하면 병렬 성능 및 애플리케이션 성능 scalability가 개선될 것이라는 결론을 내렸다.

점유율	함수	DSO (Dynamic Shared Object)
60.40%	_spin_lock	[kernel.kallsyms]
1.40%	ixgbe_poll	/lib/modules/…/ixgbe/ixgbe.ko
1.10%	net_rx_action	[kernel.kallsyms]
1.10%	__pthread_mutex_lock_internal	/lib64/libpthread-2.12.so
1.10%	assoc_find	/usr/local/lib/memcached/default_engine.so
1.10%	copy_user_generic_string	[kernel.kallsyms]
1.00%	tcp_sendmsg	[kernel.kallsyms]
0.90%	irq_entries_start	[kernel.kallsyms]
0.80%	pthread_mutex_unlock	/lib64/libpthread-2.12.so
0.70%	GI_vfprintf	/lib64/libc-2.12.so
0.70%	audit_syscall_exit	[kernel.kallsyms]
0.60%	ip_route_input	[kernel.kallsyms]
0.60%	ixgbe_resume	/lib/modules/…/ixgbe/ixgbe.ko
0.50%	tcp_ack	[kernel.kallsyms]

표 1 8개의 스레드로 memcached가 실행되는 서버에서 캡처한 routine 별 CPU 사용량 순위

그림 7 3~4개의 코어에서 최대 성능을 표시하는 Base (1.6 버전) memcached의 확장 성능

3 memcached 최적화

이 절에서는 multicore 서버에서 다중 스레드 실행을 위한 애플리케이션 확장성을 개선하기 위해 memcached를 최적화하는 것에 대해 간략히 설명하려고 한다. 현재 memcached 아키텍처를 확인한 후 global cache lock과 기본 성능 병목 현상을 최소화하거나 제거하는 기술을 알아본다.

목표는 다음과 같다.

키의 수와 관계없는 동일한 성능 (즉, 1개 키와 100만 개의 키 조회) 제공
LRU 제거를 위해 업데이트된 캐시 교체 전략에서는 그 이상의 hit rate. Benchmarking에서 사용된 워크로드에서 캐시 된 값 조회에 대해 90% 이상의 hit rate
캐시 관리를 위한 LRU 정확도 (LRU 상태를 기준으로 정확한 값이 제거 됨)

이러한 목표에 대한 진행 상태를 측정하기 위해, 트랜잭션 set를 replay한 가상 워크로드를 사용하여 Base의 hit rate를 측정했다. 이 절에 설명된 최적화는 오픈 소스 memcached 1.6 버전에 새로운 엔진으로 구현되었다. 2012년 7월 현재, 이 최적화된 버전은 GitHub (https://github.com/rajiv- kapoor/memcached/tree/bagLRU) 에서 소스 코드를 다운로드할 수 있다.

3.1 데이터 구조

최적화를 위해 두 개의 데이터 구조, 해쉬 테이블과 LRU가 수정되었다.

해쉬 테이블 lock 메커니즘이 병렬 액세스를 허용되게 바뀜
Bag LRU – 데이터 구조가 single linked-list bag (즉, 컬렉션)을 가진 서로 다른 크기의 LRU list의 배열로 변경됨

해쉬 테이블에서 알고리즘은 변경하고 있지만 해쉬 테이블 데이터 구조에 대한 물리적 변경은 없다. 해쉬 테이블 bucket을 수정하는 데 필요한 striped lock을 구현한다. striped lock은 해쉬 테이블 영역에 구현된 세분화된 lock의 집합 (global 해쉬 테이블 lock과 대조적)이다. 이 구현을 위해 먼저 Z개의 lock 집합을 생성하여 초기화한다. 여기서 Z는 2의 거듭제곱이며 2의 거듭제곱을 유지하면서 비트마스크를 사용하여 lock ID를 신속하게 계산한다. linked-list을 이동하기 위해 'Z-1' 값을 잠글 bucket과 bit-wise AND를 수행하여 해당 bucket을 보호하는 lock이 획득된다. 이 프로토콜은 모든 Z번째 bucket (그림 8)에 대해 공유된 lock을 제공하여 해쉬 테이블 lock에 대한 경합을 줄인다. 테스트에서는 lock의 개수로 Z=32가 적합한 값이었다.

LRU는 대규모 데이터 구조 변경이 필요한 위치이다. 병렬 LRU를 더 많이 구축하여 병렬 해쉬 테이블의 이점을 얻기 위해 병렬 LRU 데이터 구조에 대한 개념을 조사했다. Lock 회피 LRU 알고리즘과 데이터 구조에는 [13] 및 [14]와 같은 두가지 좋은 아이디어가 있다.

이 두 개념으로부터 힌트를 얻은 bag LRU 개념으로 캐시 항목의 single linked-list 'bags'을 구현했다. 각 'bag'은 비슷한 시간대에 insert나 touch된 항목들이 들어있고, atomic insert가 가능하다. 이 모델에 필요한 캐시 항목 'clean-up' 기능이 필요하며 이 용도로 'cleaner thread'가 존재한다. 이 스레드는 만료되었거나 유효하지 않은 캐시 항목을 제거하고 bags에서 유지관리를 수행한다. 다이어그램 및 로직을 비롯한 새로운 데이터 구조에 대한 보다 자세한 설명은 3.5 절을 참조하면 된다.

3.2 명령

2.2 절에 설명된 memcached 명령이나 프로토콜에는 변경된 내용이 없다. 차이점이라면 명령 실행 방법론뿐이다.

그림 8 각 bucket을 보호하는 striped lock 추가

3.3 프로세스 흐름

그림 9는 수정 후 업데이트된 프로세스 흐름을 나타낸다. 위에서부터 아래까지 클라이언트, libevent 및 worker thread 기능이 동일하게 유지된다. 해쉬 테이블 조회를 위한 순차화된 명령과 LRU 처리가 병렬 방식으로 작동하도록 수정된다.

DELETE 및 STORE 명령은 striped lock (이전에 설명됨) (그림 8)이 있는 병렬 해쉬 테이블 방식을 사용하며 GET 명령은 non-blocking 및 병렬 방식으로 실행된다.

그림 9 최적화된 버전의 1.6.0_beta1에서 캐시 항목 명령 (STORE/GET/DELETE)에 대한 프로세스 흐름

아래 설명된 알고리즘 변경은 hash chain 손상을 방지하고 제거 중인 캐시 항목 포인터를 유지한다. 캐시 항목 제거시 스레드가 preempt 되더라도 올바른 bucket에서 진행할 가능성이 높다. 이는 차단 해제된 GET과는 미묘한 차이가 있다. 캐시 항목에 대해 스레드가 오랫동안 preempt 된 후 그 캐시 항목이 이동되었다면 GET은 false negative를 반환한다 (memcached가 캐시 항목이 해쉬 테이블에 실제로 있음에도 불구하고 '캐시 항목 없음'을 반환).

이 방법에 대한 찬반 양론이 있는데, memcached는 영구적 (persistent) 이지 않은 "cache" data를 다루기 때문에 false negative 문제보다 lock을 제거하여 추가 처리량을 실현하는 것에 촛점을 맞추었다. False negative가 문제가 되는 경우 striped lock을 사용하면 된다 (어느 정도의 성능 저하가 있다). 하지만 예상한 대로 코어 수가 늘어나면 striped lock이 다시 경합 지점이 될 수 있다.

이렇게 하여 LRU 처리는 위의 3.2 절과 3.5 절에 설명된 것처럼 non-blocking 및 병렬화 되었다. 각 bags에서는 single linked-list가 있어서 캐시 항목을 atomic하게 삽입할 수 있어서 새로운 캐시 항목을 bag에 넣는 동안에 lock이 필요가 없어졌다. 여전히 CAS (Compare-and-Swap) 명령이 필요하며 이 경우 STORE 명령들만 수행되는 경우에는 경합 지점이 될 수 있다. 그러나 가장 많이 쓰이는 명령인 GET에 대해서 최적화를 했기 때문에 lock 또는 GET에 필요한 CAS 없이 bag LRU를 구현할 수 있었다.

3.4 병렬 해쉬 테이블 조회

Memcached 트랜잭션 실행해보면 가장 처음으로 나타나는 성능저하 문제는 순차화된 해쉬 테이블 조회이다. 이전의 대부분의 Memcached 병렬 성능 고도화 노력들은 스레드가 캐시의 특정 부분 (예. 파티션) 만 액세스하는 해쉬 테이블 분할에 중점을 두었다. 이렇게 하면 [16]에서 보여진 대로 lock 경합을 제거하고 성능을 높일 수 있다. 이 방식의 단점은 단일 파티션의 캐시 항목을 여러 차례 자주 액세스하여 해당 파티션을 처리하는 스레드 들이 포화 상태일 수 있다는 점이다. 마찬가지로 어떤 파티션을 선호하는 트래픽 패턴을 가진 워크로드에서는 처리 성능이 저하될 수 있다. 파티션의 전체적인 성능은 lock 경합을 유발하지 않는 캐시를 조회 하는 스레드 들로 제한된다.

이런 구현 방식은 트래픽의 대부분을 차지하는 GET 명령의 처리량을 최적화한다. 참고 문헌 [11]에서는 Facebook의 캐시 서버의 상당 부분을 차지하는 트래픽이 GET 명령임을 보여준다. 이 비율은 불과 몇 개 되지 않는 write가 대부분인 workload의 캐싱 tier만 제외하면, 어떤 경우 GET이 99.8%를 차지할 만큼 높다. 이 내용은 [15] 및 [16]에서 수행한 성능 테스트와 일치한다 (두 테스트 방법 모두 GET 명령에 대한 처리량만 측정했다).

이러한 특징을 염두에 두고 GET 명령을 처리할 때 어떠한 lock도 필요 없는 병렬 해쉬 테이블이 설계되었다. [12에서 보면 lock 경합은 아무리 짧더라도 성능에 영향을 준다 (트랜잭션 지연, Latency SLA에 의한 전체 처리량). 미래에는 CPU가 더 빨라지고 코어 수도 늘어나므로 lock 경합도 증가할 것이다. 새로운 설계에서는 이러한 경향을 고려하여 GET에 대한 lock 경합을 완전히 제거했다.

3.4.1 GET lock 제거

GET에서 lock을 제거하기 위해서는 hash chain 확장 (expansion) 과 수정 (즉, 삽입 및 제거) 이라는 두 가지 경우를 해결해야 한다.

해쉬 테이블이 bucket보다 훨씬 많은 양의 캐시 항목을 포함하는 경우 '확장 (expansion)'이 필요하다. 이 경우 캐시 항목을 더 많이 추가하면 hash chain의 길이가 늘어나고 캐시 항목을 찾는데 필요한 시간과 RTT가 증가한다. 이렇게 시간상 손해를 보지 않기 위해서, bucket 양의 2배인 새로운 해쉬 테이블을 다음과 같이 할당한다.

모든 캐시 항목을 이전 테이블에서 가져옴
키들을 해싱
캐시 항목들을 새로운 테이블에 삽입

Assoc_get() 로직:

bucket 결정을 위한 hash 해쉬 마스킹

     If (! expanding)
 
     |    hash chain bucket을 확인하여 있는 경우 캐시 항목 반환
 
     |    If (캐시 항목이 없음)
 
     |    |     If (확장 && 확장 bucket이 bucket보다 큼)
 
     |    |    | 새로운 큰 테이블에서 bucket 찾기
 
     |    |    | 이전 bucket이 비워질 때까지 대기
 
     |    |    | 새로운 hash bucket을 확인하여 있는 경우 캐시 항목 반환
 
     else if expanding
 
     |    확장이 이전 테이블에 있는지 확인
 
    |    hash chain bucket을 확인하여 있는 경우 캐시 항목 반환
 
    |    If (캐시 항목이 없음)
 
    |    |    If (확장 bucket이 bucket보다 큼)
 
    |    |    새로운 큰 테이블에서 bucket 찾기
 
    |    |    |    이전 bucket이 비워질 때까지 대기
 
    |    |    |    새로운 hash bucket을 확인하여 있는 경우 캐시 항목 반환

캐시 항목을 찾을 때 확장 중인지 확인한다. 확장 중이 아니라면 GET 명령이 정상적으로 실행되고, 항목이 있는 경우 찾은 캐시 항목을 반환한다. 이때 확장이 다시 시작이 되었을 경우가 있는데, 그 사이 캐시 항목이 이동될 수 있다. 이 경우 프로세스는 이전 bucket (이동 전에 있었던 hash table의 bucket)이 비워질 때까지 대기한 후 그 캐시 항목에 대한 새로운 해쉬 테이블과 bucket을 확인한다.

만약 해쉬 테이블의 확장이 진행 중인 경우 이전 bucket이 이미 이동되었는지 확인한다. 이전 bucket이 이동되지 않은 경우 이전 bucket에서 캐시 항목을 찾는다. 비슷하게, 캐시 항목이 없는 경우 이전 bucket에 'bucket 이동'이 발생했는지 확인한다. 그런 경우 새로운 해쉬 테이블을 확인한다.

다음으로 해결해야 할 문제는 STORE 및 DELETE 코드에서 처리되는 hash chain 수정이다. 포인터가 올바른 순서로 변경되기만 한다면 GET에는 hash chain traversal 대한 문제가 없다.

3.4.2 STORE/DELETE lock 제거

STORE 및 DELETE 명령은 현재 오픈 소스 구현과 매우 비슷하다. Hash chain 및 동일한 chain 또는 캐시 항목에 대한 동시에 여러 건의 삽입/삭제를 안전하게 처리하기 위해 STORE 및 DELETE는 그림 8에서 설명된 striped lock을 사용한다.

Assoc_delete() 로직:

     캐시 항목 bucket 확인
 
     bucket lock 획득
 
     If (expanding)
 
     |    If (확장 bucket이 bucket보다 큼)
 
     |    |    bucket lock 해제
 
     |    |    새로운 bucket 확인
 
     |    |    bucket lock 획득
 
     |    캐시 항목이 있는 경우 bucket에서 캐시 항목 삭제
 
    |    bucket lock 해제
 
    Else if not expanding
 
    |    캐시 항목이 있는 경우 bucket에서 캐시 항목 삭제
 
    |    bucket lock 해제

확장 중인 bucket 이동을 비롯한 모든 hash chain 수정에는 striped lock이 필요하다. 이렇게 하면 bucket lock을 얻은 후 확장을 확인하기 때문에 STORE 및 DELETE가 보다 간편해진다. STORE 또는 DELETE routine에서 수정이 필요한 bucket이 확장으로 인하여 이동 중 이라면, 이전 bucket이 비워지고 새로운 bucket을 확인할 때까지 bucket lock을 잡고 있어야 한다. Lock을 획득한 후 이동이 시작되면 lock이 해제 될 때까지 확장하지 못한다. 이 로직은 STORE, DELETE 및 MOVE에 동일하게 적용된다.

Assoc_insert() 로직:

     캐시 항목 bucket 확인
 
     bucket lock 획득
 
     If (expanding)
 
     |    If (확장 bucket이 현재 bucket보다 큼)
 
     |    |    bucket lock 해제
 
     |    |    새로운 bucket 찾기
 
     |    |    bucket lock 획득
 
     |    bucket 조회. 캐시 항목이 없는 경우, bucket에 삽입
 
     |    bucket lock 해제
 
    Else if (not expanding)
 
    |    bucket 조회. 캐시 항목이 없는 경우, bucket에 삽입
 
    |    bucket lock 해제

3.5 병렬 LRU Eviction

캐시 항목 제거 순서를 결정하기 위해서는 일반적인 double linked list LRU 구현체를 대신할 수 있는 병렬 알고리즘이 필요하다. 'Bag' 구현의 개념은 캐시 항목을 타임스탬프 기반의 'bags'로 그룹화하는 것이다. 이러한 bag에서는 캐시 항목의 single linked list가 저장되므로 CAS (Compare-And-Swap)를 사용하여 list의 tail에 atomic하게 삽입할 수 있다. 이 설계는 STORE만 수행되는 경우에는 CAS가 병목 지점이 될 수 있지만, 새로운 캐시 항목을 bag에 배치하는 동안 lock 이 필요 없다는 장점이 있다. 다시 언급하지만 대부분의 명령인 GET 명령을 위주로 최적화하려는 취지이기 때문에, lock이나 CAS 없이 GET이 수행될 수 있도록 bag LRU를 구현하였다.

새로운 설계에서도 이전 캐시 항목을 제거하고 새로운 bag LRU 구조를 유지하는 방법이 필요하다. 이를 위해 백그라운드로 실행할 'cleaner thread'를 구현한다. 이 스레드는 만료되거나 유효하지 않은 캐시 항목을 제거하고 LRU에서 유지관리를 수행한다. 이전 버전에서 GET 명령을 수행했던 명령 (즉, 만료 시 제거)은 이 백그라운드 스레드로 이동하므로 GET 명령의 처리량이 증가하고 GET 명령 트랜잭션당 오버헤드가 감소한다. cleaner thread 역시 캐시의 적중 비율을 높이는 이점을 제공한다. 빠른 만료로 삽입된 캐시 항목은 캐시가 오래될 때까지 공간을 차지하는 대신 만료되기 몇 분 이내로 정리된다.

3.5.1 Linked-list 구조

새로운 Linked-list 구조는 기존의 LRU의 prev 그리고 next 포인터를 재사용하므로 추가 메모리 할당이 필요하지 않다. next포인터는 새로운 single linked-list에서의 다음 캐시 항목을 기존과 같이 가리키고 prev pointer는 그 캐시 항목의 bag membership인 마지막으로 조회된 시점의 "최신 bag"을 표시한다. Cleaner thread는 bag을 정리하는 동안 이 포인터를 사용한다.

3.5.2 추가 데이터 구조

그림 10 bag 데이터 구조

그림 11 bag list 데이터 구조

Bag LRU는 bag 식별을 위한 LRU 배열과 실제 bag 데이터 구조, 이 두 가지 데이터 구조가 필요하다.

첫 번째 데이터 구조는 슬랩 id당 하나의 bag head 배열인 bag LRU list이다 (그림 10). 이 구조는 global 변수에서 참조되며 bag LRU가 초기화될 때 초기화된다. 이 배열의 각 bag head는 다음 field들이 필요하다.

최신 bag에 대한 포인터 (Newest bag)
최신 대체 bag에 대한 포인터 (Newest Alternative bag)
Bag list에서 가장 오래된 bag (Oldest bag)
통계를 위한 bag의 개수

"최신 bag"은 현재 새로 할당된 캐시 항목으로 채워지는 bag이다. 가장 오래된 bag은 cleaner thread가 bag 정리를 시작하고 제거 (eviction) 스레드가 캐시 항목을 제거하는 bag이다. Cleaner thread는 최신 bag으로의 삽입으로 인한 lock 경합을 피하기 위해 "최신 대체 bag"을 사용한다. bag에 이미 존재하고 최근에 액세스된 캐시 항목들은, 제거 순서 (eviction order)를 유지하기 위해, cleaner thread에 의해 최신 bag으로 이동되어야 할 캐시 항목들은 "최신 대체 bag"에 들어가게 된다.

두 번째로 필요한 데이터 구조는 캐시 항목의 single linked-list인 bag이다 (그림 11). bag은 다음 field 들을 포함한다.

Bag에서 "가장 최신" 및 "가장 오래된" 캐시 항목을 가르키는 포인터
Bag의 캐시 항목 개수 카운터 'count'
lock
Bag 열고 닫은 시간 (타임스탬프) - 현재 사용되지는 않음

Bag을 정리할 때 cleaner thread는 bag에 있는 가장 오래된 캐시 항목부터 정리하기 시작한다. Worker thread의 eviction (제거) 작업도 같은 위치에서 시작된다. "가장 최신" 캐시 항목 포인터는 캐시 항목이 삽입될 때나 bag이 병합될 때 빠르게 bag의 끝에 추가할 수 있도록 해준다. 'count'는 새 bag을 열거나 이전 bag을 최신 bag에 병합하는 시기를 결정하는데 쓰인다. 'count' 필요한 경우 통계 및 디버깅에 사용될 수 있다. 모든 bag에 lock이 필요한 이유는 cleaner thread와 worker thread의 'eviction' 간의 스레드 안정성을 위해서이다. Eviction worker thread와 cleaner thread가 같은 bag에 있는 캐시 항목을 이동하는 경우 스레드 중 하나가 bag을 손상시킬 수 있다 (그림 6에 linked-list 손상이 표시됨). Cleaner thread는 각 bag에서 작업 시간이 매우 적으므로 cleaner thread와 worker thread 사이에 lock 경합이 발생할 가능성은 낮다. 또한 worker thread는 상위 호출 스택에서 serialized 되므로 이러한 스레드간의 lock 경합은 없다.

3.5.3 데이터 구조에 대한 명령

이 절에서는 새로운 데이터 구조 및 알고리즘에서 초기화, 캐시 항목 삽입 및 LRU list 정리와 같은 명령을 설명한다.

먼저, 추가된 모든 lock을 초기화해야 하며 사용할 각 슬랩 크기에 맞는 초기 bag을 생성한다. 모든 구조가 초기화된 후에는 cleaner thread가 생성되고 cleaning (정리) 루프에서 시작된다.

Bag LRU 초기화

     global eviction lock 초기화
 
     cleaner lock 초기화 (현재 하나의 lock만 슬랩 id당 하나의 cleaner thread가 될 수 있음)
 
     Bag head 구조 배열 생성
 
     각 슬랩 id에 대해
 
     |    첫 번째 bag 초기화
 
     |    bag lock 초기화
 
     |    bag 배열 head가 최신 bag으로 이 id를 가리킴
 
     |    bag 카운터 증가
 
     cleaner thread 생성 및 실행

정리 루프에서는 스레드가 bag이 가득 차 있는지 계속해서 확인하며 필요한 경우 새 bag을 해당 슬랩에 추가한다. 주기적으로 cleaner thread는 bag에 있는 모든 캐시 항목을 확인하여 유효하지 않거나 만료된 캐시 항목을 제거하고 최소 캐시 항목 개수 임계 값 미만인 bag을 병합한다.

Cleaner thread 루프

     무한 루프
 
     |    cleaner lock 획득
 
     |    각 슬랩 id에 대해
 
     |    |    "최신 bag"이 가득찬 경우
 
     |    |    |    새로운 bag 생성 및 초기화
 
     |    |    |    최신 bag 다음 bag 포인터가 새로 초기화된 bag을 가리킴
 
     |    |    |    bag holder = 최신 bag
 
     |    |    |    최신 bag = 새로 초기화된 bag
 
     |    |    |    최신 대체 (Newest alternate) = bag holder
 
    |    |    |    atomic increment of bag count
 
    N번째 iteration시 bag 정리
 
    cleaner lock 해제
 
    지정된 간격 동안 sleep

캐시 항목이 LRU에 삽입될때, 캐시 항목의 슬랩 크기에 맞는 최신 bag에 삽입된다. bag이 정해지면 캐시 항목은 CAS를 사용하여 최신 bag에서 최신 캐시 항목 바로 뒤 (끝)에 삽입된다. Atomic 삽입이 실패하면 스레드는 bag의 끝을 나타내는 NULL 포인터를 찾아 다시 CAS를 시도한다. 성공적으로 삽입될 때까지 CAS를 시도한다.

LRU에 없는 새로운 캐시 항목 삽입

     새로운 캐시 항목 next 포인터 = NULL
 
     If (현재 open bag이 비어 있음)
 
     |    If ( CAS (현재 bag 최신 캐시 항목, NULL, 새로운 캐시 항목)){
 
     |    |    새로운 캐시 항목 prev 포인터 = 현재 bag
 
     |    |    현재 bag 최신 캐시 항목 - 새로운 캐시 항목
 
     |    |    bag 캐시 항목 카운터 atomic increment
 
     |    |    반환
 
     swap 캐시 항목 = 현재 bag 최신 캐시 항목
 
     While ( !CAS (swap 캐시 항목 next 포인터, NULL, 새로운 캐시 항목)){
 
    |    While (swap 캐시 항목 next 포인터 != NULL)
 
    |    |    null을 찾을 때까지 swap 캐시 항목 next 포인터를 따라가서 다시 전환 시도
 
    새로운 캐시 항목 prev 포인터 = 현재 bag
 
    현재 bag 최신 캐시 항목 = 새로운 캐시 항목
 
    bag 캐시 항목 카운터 atomic increment

GET의 경우 캐시 항목이 LRU에 이미 존재하므로 간단하게 해당 타임스탬프와 LRU에서 위치를 수정한다. 이러한 수정은 새 타임스탬프를 캐시 항목에서 last accessed 필드에 복사하고 캐시 항목 prev 포인터 (캐시 항목이 insert된 bag)가 그 슬랩의 최신 bag을 가리키도록 한다.

LRU에 이미 있는 캐시 항목 업데이트

1

2

3

    캐시 항목 prev 포인터 = 현재 bag
 
    캐시 항목 타임스탬프 업데이트

3.5.3.1 LRU list 정리

LRU list을 정리할때 필요한 작업들이 몇 개 있다: 캐시 항목 재정렬, bucket 병합, 캐시 항목 제거 및 캐시 덤핑.

Cleaner thread가 bag list을 조회할때 캐시 항목 prev 포인터를 확인한다. 포인터가 현재 정리 중인 bag을 가리키는 경우 그 캐시 항목을 현재 위치에 남겨 둔다. 그 항목이 다른 bag을 가리키는 경우는 항목은 처음 삽입된 이후 한번 이상 조회되었다는 뜻이다. 이 경우 cleaner thread는 현재 bag에서 항목을 제거하고 상주해야 하는 bag에 삽입한다. 위에 설명된 것처럼 LRU 크기에서 최신 bag인 경우 경합을 피하기 위해 '최신 대체 (newest alternate)' bag에 넣는다.

두 개의 bucket 병합

    오래된 bucket의 최신 캐시 항목 다음 포인터 = 최신 bucket의 가장 오래된 캐시 항목
 
    최신 bucket의 오래된 캐시 항목 = 오래된 bucket의 오래된 캐시 항목
 
    추가한 모든 캐시 항목에 대해
 
    |    캐시 항목이 오래된 bag을 가리켰던 경우
 
    |    |    새로운 bag을 가리킴
 
    오래된 bag에 있는 캐시 항목의 양 만큼 최신 bag 카운터 증가

두 개의 bucket을 병합하는 로직은 두 개의 linked-list을 함께 연결하고 둘 중 더 최근 bag에 배치한다. 그런 다음 prev 포인터가 오래된 bag을 가리켰던 모든 캐시 항목이 최신 bag을 가리키도록 하고 오래된 bag을 회수 (reclaim) 해야 한다.

캐시 항목 제거 (eviction)

     슬랩 id에 대해 eviction lock 획득
 
     슬랩 id에서 할당된 bag들 중에서 가장 오래된 bag 선택
 
     최신 대체 항목 이전에 있고 캐시 항목을 가지고 있는 첫 번째 bag 찾기
 
     만약 bag을 찾을 수 없는 경우 두 개의 새로운 bag을 이 슬랩 id에 추가한 후 bag을 모두 확인
 
     여전히 bag을 찾을 수 없는 경우
 
     |    캐시 항목을 제거 중단하고 오류 반환
 
     |    eviction lock 해제
 
     찾은 bag lock
 
     Bag에서 가장 오래된 캐시 항목부터 확인
 
    refcount가 1 또는 0인 캐시 항목 찾거나 bag에 있는 처음 N개의 캐시 항목 중에서 locked 캐시 항목 삭제
 
    |    캐시 항목을 찾은 경우 bag에서 제거하고 자원 해제
 
    |    슬랩 할당자로부터 새로운 캐시 항목 얻기 시도
 
    |    if (캐시 항목을 제거했으나 할당자에서 얻지 못함)
 
    |    |    다른 캐시 항목을 제거하고 다시 시도
 
    |    else
 
    |    |    캐시 항목을 제거하려는 시도를 중단하고 오류 반환
 
    Bag unlock
 
    eviction lock 해제

Worker thread들이 캐시 항목을 evict (제거)하기 위해서는 global eviction lock을 이용해야 정합성이 보장된다. 그런 다음 cleaner thread와 충돌을 피하기 위해 bag을 lock해야 한다. 이렇게 하면 worker thread가 bag을 수정하는 유일한 스레드이며 제거 기준을 만족하는 캐시 항목들을 제거 (evict) 할 수 있다 (오픈 소스 버전과 동일).

캐시 덤핑

    cleaner lock 획득
 
    eviction lock 획득
 
    새로운 bag을 추가하여 다른 스레드에 영향을 주지 않고 제거할 수 있도록 함
 
    각 슬랩 id에 대해
 
    |    각 캐시 항목에 대해
 
    |    |    If (캐시 항목이 캐시 덤프 시간보다 오래됨)
 
    |    |    캐시 항목 해제
 
    eviction lock 해제
 
    cleaner lock 해제

캐시를 덤핑하는 것은 앞에 설명한 캐시 항목을 제거하는 방식과 같지만, 명령에 지정된 시간보다 오래된 캐시 항목들을 모두 evict (제거) 해야 한다.

3.6 Global cache lock 제거

병렬 hash 조회, LRU 정렬 및 병렬 캐시 (evict) 제거를 관리하기 위한 기능들을 넣고 나면, global cache lock을 GET/STORE/DELETE 코드 경로에서 제거 하는 것이 거의 가능하다. Ref count 관리는 변경되어야 하며, lock 대신 ref count 변경 시 atomic incr / decr를 사용한다. 이렇게 해서 global lock이 더 이상 필요하지 않게 되어 제거할 수 있다.

1

2

3

4

5

    Lock (global_cache_lock) ➟ global lock 제거
 
     . . . . . (GET/STORE/DELETE)
 
    Unlock (global_cache_lock) ➟ global lock 제거

4 테스트 환경 구성 및 메트릭스

새로운 memcached 아키텍처의 개발 및 디버깅이 완료되면 성능상 이점을 확인하기 위한 설정 및 테스트 방법을 정의해야 한다.

4.1 하드웨어 구성

이 절에서는 사용 한 모든 시스템의 하드웨어 구성을 설명한다.

4.1.1 SUT (System under Test)

이전 평가에 의하면 1GbE NIC는 쉽게 포화 상태가 되므로 네트워크의 병목을 제거하기 위해 10GbE NIC를 사용한다.

Memcached는 주로 TCO (Total Cost of Ownership)가 중요한 대형 server farm에 deploy된다. 와트당 성능 결과를 최대화하고 TC를 감소하는 데 그 목적이 있다. 테스트 시스템은 Quanta Computer에서 제조한 2-Socket Open Compute 2.0 시스템 보드이다.

시스템 하드웨어:

1.5U chassis에서 Dual-Socket Open Compute 2.0 시스템 보드(반폭)
2 x Intel® Xeon® E5-2660 2.2Ghz 프로세서(95W TDP)[10]
128GB DRAM x 16, 8GB DDR3 PC3 12800 ECC
Intel® Niantic 82599 10Gb 직접 연결 SFP+ 이더넷 컨트롤러[10]
Arista 7124 스위치 – 24포트 SFP+

4.1.2 로드 생성기 (load generator)

기존에 사용해 온 오픈 소스 버전의 memcached에는 로드 생성기 한대면 충분한 load를 줄 수 있다. 반면에 수정한 버전을 테스트하기 위해서는 더 많은 클라이언트가 필요하다. 한 개의 클라이언트가 초당 약 800K의 request (rps)를 발생할 수 있으므로, 적절한 로드를 생성하기 위해서 4개의 클라이언트로 구성한다. 모든 로드 생성기는 다음과 하드웨어로 구성되어 있고, 각각 800K+ rps의 load를 생성하게 했다.

1.5U chassis에서 Dual-Socket Open Compute 2.0 시스템 보드 (반폭)
수량 2 – Intel® Xeon® E5-2660 2.2Ghz 프로세서(95W TDP)[10]
16GB DRAM – 수량 2, 8GB DDR3 PC3 12800 ECC
Intel® Niantic 82599 10Gb Direct Attach SFP+ 이더넷 컨트롤러[10]

4.2 소프트웨어(SW) 구성

이 절에서는 SUT 및 클라이언트 시스템에 대한 소프트웨어 구성과 네트워크 최적화 및 전력 모니터링 구성을 검토한다.

4.2.1 테스트 시스템 구성

Memcached 테스트를 실행하기 위해 다음 소프트웨어가 설치된다.

CentOS (Community ENTerprise Operating System), 6.2 버전 – Linux Kernel 2.6.32
Libevent 1.4.14b-stable
Intel® ixgbe 3.8.14 NIC 드라이버
Memcached-1.6.0_beta1 및 Memcached-1.6.0_beta1-bags

소프트웨어를 설치한 후 다음 명령어로 memcached를 실행한다.

memcached –p 11211 -u nobody –t <thread> -m 128000 –d

이 명령에서 thread 는 memcached에서 실행할 worker thread 개수다. 모든 테스트에서 memcached를 테스트하기 위해 수정되는 유일한 변수는 스레드 개수다. 이 워크로드 드라이버 및 입력 매개변수는 최대 처리량과 확장성을 확인하는 데 활용된다.

4.2.2 클라이언트 시스템 구성

다음 소프트웨어로 클라이언트 시스템을 구성한다.

CentOS (Community ENTerprise Operating System), 6.2 버전 – Linux Kernel 2.6.32
Intel® ixgbe (10GbE) 버전 3.8.14 NIC 드라이버

mcblaster

운영 체제 및 네트워크 드라이버 소프트웨어가 설치된 상태에서 synthetic cache lookup 워크로드를 발생시키고 memcached 인스턴스의 성능 (즉, 트랜잭션 처리량, 지연/응답 시간)을 측정하는 데 mcblaster를 사용된다. 이 테스트는 2단계로 구성되어 있다. 먼저 다음을 사용하여 k/v를 memcached 인스턴스에 로드 한다.

./mcblaster –p 11211 -t 16 -z 64 –k 1000000 –r 10 –W 75000 –d 20 <memcached host>

이 명령은 캐시에 모두 64바이트 값을 포함하는 100만 개의 키를 로드시킨다. 다음 테스트 단계에서는 모든 클라이언트가 일정한 초당 부하 발생 속도에서 이러한 키에 대한 요청을 임의 순서로 동시에 전송하고 해당 속도에서 처리량 (throughput) 과 지연 시간 (latency)을 측정한다.

./mcblaster –p 11211 -t 16 -z 64 –k 1000000 –r <rate> –W 0 –d 120 <memcached host>

이 테스트에서 memcached의 평균 RTT를 모니터링 하면서 부하 발생률을 증가시킨다. 최대 처리량은 SLA인 1msec 의 평균 RTT를 초과하지 않는 가장 높은 처리량이다.

Memcached ([15] 및 [16]) 성능을 측정한 report를 가이드로 해서, GET 명령 성능을 평가했다. 대부분의 k/v 캐싱 서버는 GET 명령이 대부분인 workload이며 [11], workload mix에 있는 STORE 명령수는 미미하여 GET 성능에 거의 영향을 주지 않는다[16].

4.2.3 네트워크 설정

최대 처리량을 위한 Intel® Hyper-Threading(HT) 설정(사용/사용 안 함) 에 따른 두 가지 네트워크 구성이 있다.

Intel® HT가 사용되지 않을 때는 다음 설정이 사용된다.

링 버퍼 크기를 rx (receive) 및 tx (transact, send) 모두에 대해 96으로 줄임
- 목표: 지연 감소 (RTT)
- 명령어
  - ethtool –G ethX rx 96
  - ethtool –G ethX tx 96
GRO (generic receive offload) 사용 안 함
- 목표: 지연 감소(RTT)
- 명령어: ethtool –K ethX gro off
set_irq_affinity.sh 셸 스크립트를 실행하여 CPU에 대한 NIC 인터럽트 affinity 조정
- 목표: 네트워크 인터럽트 경합 감소
- 명령어: ./set_irq_affinity.sh ethX
- 참고: 커널에서 irqbalance 서비스가 사용 안 함으로 설정되어 있거나 변경 사항을 덮어쓰는지 확인한다. (killall irqbalance)

이러한 설정은 최신 ixgbe 드라이버 (테스트를 실행한 경우 3.8.14)와 함께 사용할 때 최대의 처리량을 제공한다. 들어오는 패킷이 물리적 CPU 코어를 고르게 향하도록 하여 네트워크 인터럽트의 로드를 분산하는 데 flow detector (ixgbe 드라이버에 포함)가 사용된다. 이렇게 하면 CPU가 여러 코어 간 사용률을 고르게 유지할 수 있다.

Intel® HT가 사용된 경우 최적의 네트워크 구성은 물리적인 CPU 1개당 1개의 memcached thread를 구성하고, 2개의 NIC queue가 추가적인 16개의 논리적인 core로 affinity를 조정하는 것이다 (affinity에 대한 자세한 내용은 표2를 참고하라). Memcached process에 대하여 affinity 조정을 하여 구성함으로써, 대부분의 NIC 처리 (network packet 처리)가 memcached 스레드에 인접한 논리적 코어가 처리하도록 하여 Intel® HT 을 사용하지 않을 때에 비해 높은 성능을 제공한다.

표 2 Intel® HT 기술 memcached 설정의 경우 논리적 코어와 memcached 및 네트워크 트래픽 공유

4.2.4 전력 측정

테스트를 위해 Yokogawa WT210 디지털 전원 측정기로 모니터링 했다. 시스템이 로드 된 상태에서 매 5초마다 전력량을 수집한다. 그리고 평균 갑들은 다음 절의 차트에 있다.

참고로 모든 서버는 비디오 카드가 장착되어 있고 최적이 아닌 냉각 솔루션을 장착하고 있다. 실 데이터 센터 환경에서는 이 글에 소개된 수치에 비해 서버당 전력 소비량이 낮을 것으로 예상된다.

5 요점

성능상 이점을 요약하자면 그림 12는 <1ms RTT (Round-trip time)의 Latency SLA를 유지하는 동안 SUT (system under test)의 최대 서버 용량 (Request per second: RPS)을 보여준다. 연구의 일관성을 위해 이러한 측정은 GET 명령과 함께 수행했다.

테스트 결과 최적화된 memcached는 물리적 프로세서당 하나의 스레드에서 최적으로 수행되므로, 16개의 물리적 코어가 있는 SUT에서16개의 스레드를 사용할 때 가장 좋은 성능을 보인다. Intel® HT 및 Turbo 모드 사용시 모두 성능 향상을 보인다.

두 가지 오픈 소스 base 결과는 스레드를 8개에서 16개로 늘릴 때 성능상 이점이 없음을 보여준다 (즉, lock 경합으로 인한 scalability 문제). 최적화된 'Bag' 결과는 Intel® HT 기술 (+8%) 및 Turbo (+23%)를 추가함에 따라 성능이 증가하는 것을 보여준다. Intel® HT 기술을 통한 성능 향상은 동일한 물리적 코어에 HT 기능인 논리적 프로세서가 하나씩 더 추가됨으로써 worker thread와 네트워크 인터럽트를 동시에 context swap없이 처리 할 수 있기 때문이다. 마찬가지로 Turbo 모드는 프로세서 주파수를 높여 상당한 성능 향상을 보인다. 최고 처리량은 Intel® HT 및 Turbo (+31%) 기능을 사용할 때 추가로 성능 향상이 되어 315만 (3.15M) RPS 까지 처리 가능하다. 동일하게 구성된 베이스라인 (0.525M) 에서 최고의 결과인3.15M를 비교했을 때 6배의 성능 향상이 있음을 알 수 있다.

그림 13은 그림 12에서 최적화된 4가지 케이스의 memcached 평균 RTT (round-trip time) 이다. 흥미롭게도1ms SLA를 넘자마자 RTT가 감소되는 지점 (각각 260us, 285us, 215us, 205us)들이 있다.

실제로는 RPS 로드에 관계없이 응답 시간 SLA가 300us 미만이 되도록 관리하여 RTT가 감소하는 지점이 없어야 한다. 서버당 처리량을 최대화하기 위해 수백만의 RPS를 처리 가능하게 하도록 "Bags" 사용 서버는 300us 임계 값 하의 일정한 RTT를 보여준다.

그림 14는 중간 값 RTT < 1ms SLA에서 코어 수 증가에 따른 최대 RPS 처리량을 보여준다. 이 테스트에서 Turbo는 사용하고 Intel® HT 기술은 사용하지 않았다. 코어 수가 늘어남에 따라 여러 코어 프로세서에서 작동하는 병렬 데이터 구조 및 알고리즘에 의해 memcached도 선형적으로 확장된다. 이러한 선형적 확장은 차세대 다중 코어 프로세서로 계속 이어질 것으로 예상된다. GET 명령 실행을 위해 스레드 간 non-blocking 처리가 필요하기 때문이다.

그림 12 1밀리초 미만 RTT SLA를 유지한 상태에서 최대 GET 명령 수

그림 13 GET RPS 비율 증가에 따른 중간 RTT 값

그림 14 중간값 RTT가 1밀리초 미만인 SLA에서 코어 수 증가에 따른 최대 RPS 처리량

표 3은 최적의 베이스라인 및 최적화된 memcached 결과에 SLA의 최대 로드에서 전원 메트릭스를 추가한다. 6배의 성능 델타 외에도 와트당 성능이 베이스라인에 비해 3.4배 향상된다. 전원 및 냉각이 총 소유 비용의 상당한 부분을 차지하는 데이터 센터에서 와트당 완료되는 명령을 최대화하는 것이 중요하다. 그래픽 카드가 없고 SUT보다 나은 냉각 솔루션을 갖춘 데이터 센터 환경에서는 이러한 서버당 전원 수가 낮다.

표 3 최대 처리량 < 1ms SLA에서 실행되는 동안 wall에서 전원 측정

6 결론 및 해야 할 일

최적화된 memcached는 베이스라인에 비해 처리량을 6배까지 증가시키며 와트당 성능은 3.4배까지 증가시킨다. 이러한 수치는 반폭 서버 보드에서 전체 chassis (즉, 보드 2개)에서 추정한 값이며 SUT (system under test) 구성은 256GB 메모리를 갖춘 1.5U 서버당 630만 RPS를 제공하며 1.5U 새시당 1TB (32GB * 16 DIMM 슬롯) 메모리까지 확장할 수 있다. 해쉬 테이블 및 LRU를 재설개하여 병렬 데이터 구조를 활용함으로써 속도 향상을 얻을 수 있다. 이러한 데이터 구조를 통해 GET 명령에 대한 모든 lock을 제거하고 SET 및 DELETE 명령에 대한 lock 경합을 완화하여 2소켓 Intel® 시스템에서 1~16개의 코어를 사용하여 측정했을 때 속도가 꾸준히 증가하는 것으로 나타났다.

향후 연구에서는 bag 버전이, 코어 수가 늘어나는 것으로 계속 확장성이 늘어나는지 그리고 공유 구성 요소에서 전원 상환을 통해 와트당 성능 향상이 증가하는 지 등에 대해 4소캣 서버와 마이크로 서버 플랫폼에서 조사할 예정이다.

다음 조사 분야는 캐시 교체 정책이다. 업데이트된 캐시 항목 정렬 및 제거와 cleaner thread의 추가와 함께 새로운 대체 정책을 평가할 수 있다 (예: LFU, ARC (adaptive replacement cache) 및 MQ). Cleaner thread의 주요 기능 향상은 worker thread의 개입 없이 자율적으로 캐시를 관리할 수 있는 특성이 있다. 프로그램 흐름을 수정하지 않고도 새로운 대체 정책 평가를 할 수 있으며 캐시 히트율을 높일 수 있다.

7 감사의 말

이 자료가 나오기까지 수고해주신 프로젝트 팀원인 Rajiv Kapoor (Intel Corporation), George Chaltas (Intel Corporation), Alex Duyck (Intel Corporation), Dean Chandler (Intel Corporation), Mike Bailey (Oregon State University)에게 깊은 감사의 말을 전한다.

8 참고 문헌

[1] P. Saab, "Scaling memcached at Facebook," 12 December 2008. [Online]. Available:https://www.facebook.com/note.php?note_id=39391378919&ref=mf. [Accessed 1 April 2012].

[2] Twitter Engineering, "Memcached SPOF Mystery," Twitter Engineering, 20 April 2010. [Online]. Available:http://engineering.twitter.com/2010/04/memcached-spof-mystery.html. [Accessed 1 April 2012].

[3] Reddit Admins, "reddit's May 2010 "State of the Servers" report," Reddit.com, 11 May 2011. [Online]. Available: http://blog.reddit.com/2010/05/reddits-may-2010-state-of-servers.html. [Accessed 1 April 2012].

[4] C. Do, "YouTube Scalability," Youtube / Google, Inc., 23 June 27. [Online]. Available:http://video.google.com/videoplay?docid=-6304964351441328559. [Accessed 1 April 2012].

[5] memcached.org, "memcached - a distributed memory object caching system," Memcached.org, 2009. [Online]. Available: http://memcached.org/about. [Accessed 27 February 2012].

[6] N. Gunther, S. Subramanyam and S. Parvu, "Hidden Scalability Gotchas in Memcached and Friends," in Velocity 2010 Web Performance and Operation Conference, Santa Clara, 2010.

[7] B. Fitzpatrick, "Distributed caching with memcached," Linux J., vol. 2004, no. 1075-3583, p. 124, 2004.

[8] B. Fitzpatrick, "LiveJournal's Backend A history of scaling," August 2005. [Online]. Available:http://www.slideshare.net/vishnu/livejournals-backend-a-history-of-scaling. [Accessed 1 April 2012].

[9] N. Shalom, "Marrying memcached and NoSQL," 24 October 2010. [Online]. Available:http://natishalom.typepad.com/nati_shaloms_blog/2010/10/marrying-memcache-and-nosql.html. [Accessed 1 April 2012].

[10] Intel Corporation, "ARK - Your Source for Intel Product Information," Intel.com, 2012. [Online]. Available:http://ark.intel.com/. [Accessed 2012 1 April].

[11] B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang and M. Paleczny, "Workload Analysis of a Large-Scale Key-Value Store," in ACM SIGMETRICS/Performance 2012 Conference, London, 2012.

[12] J. Preshing, "Locks Aren't Slow; Lock Contention Is," Preshing on Programming, 18 November 2011. [Online]. Available: http://preshing.com/20111118/locks-arent-slow-lock-contention-is. [Accessed 1 April 2012].

[13] B. Agnes, "A High Performance Multi-Threaded LRU Cache," codeproject.com, 3 February 2008. [Online]. Available: http://www.codeproject.com/Articles/23396/A-High-Performance-Multi-Threaded-LRU-Cache.[Accessed 1 September 2011].

[14] M. Spycher, "High-Throughput, Thread-Safe, LRU Caching," Ebay Tech Blog, 30 August 2011. [Online]. Available: http://www.ebaytechblog.com/2011/08/30/high-throughput-thread-safe-lru-caching/. [Accessed 1 September 2011].

[15] D. R. Hariharan, "Scaling Memcached – Harnessing the Power of Virtualization," in VMWorld 2011, Las Vegas, 2011.

[16] M. Berezecki, E. Frachtenberg, M. Paleczny and K. Steele, "Many-Core Key-Value Store," in Green Computing Conference and Workshops (IGCC), 2011 International, Orlando, 2011.

[17] S. Hart, E. Frachtenberg and M. Berezecki, "Predicting Memcached Throughput using Simulation and Modeling," Orlando, 2012.

출처 - http://helloworld.naver.com/helloworld/151047

저작자표시

'Computer Science > Cache' 카테고리의 다른 글

EHCache (0)	2013.02.11
Hazelcast 소개 (0)	2012.11.06
Memcached 설치 및 사용 방법 (0)	2012.11.06
memcached를 적용하여 사이트 성능 향상 (0)	2012.11.06
Memcached 구현 소개 (0)	2012.11.06

Posted by linuxism


	by linuxism