민대홍
(Inha University Department of Computer Science Engineering)
,
장룡호
(Inha University Department of Computer Science Engineering)
,
양대헌
(Inha University Department of Computer Science Engineering)
,
이경희
(Suwon University Department of Electrical Engineering)
키-값 저장소(key-value store)는 Redis, Memcached 등의 다양한 NoSQL 데이터베이스에 응용되어 그 우수성을 보였다. 그리고 키-값 저장소 응용프로그램은 대부분의 환경에서 삽입 연산(insert) 보다 탐색 연산(lookup)이 많이 발생하기 때문에 탐색의 성능이 중요하다. 하지만 기존의 응용프로그램은 해시 테이블을 링크 리스트(linked list) 형태로 유지하기 때문에 탐색 연산이 느릴 수 있다. 따라서 탐색 연산을 상수 시간 내에 완료할 수 있는 쿠쿠 해싱(cuckoo hashing)이 학계의 주목을 받기 시작했고, 그 후 메모리 사용률이 더 높은 버킷화 쿠쿠 해싱(Bucketized Cuckoo Hashing, BCH)이 제안되었다. 본 논문에서는 BCH 구조를 기반으로 하여 삽입 정렬 방법으로 데이터를 입력하는 Sorting Cuckoo를 소개한다. Sorting Cuckoo를 이용하면 데이터가 정렬된 상태에서 탐색을 수행하기 때문에 상대적으로 적은 메모리 접근을 통해 키의 존재 여부를 판단할 수 있으며, 메모리 점유율(load factor)이 높을수록 BCH보다 탐색의 성능이 좋아진다. 실험 결과에 의하면 Sorting Cuckoo는 메모리 점유율이 95%인 상황에서 BCH보다 천만 번의 negative 탐색(데이터가 존재하지 않는 탐색)에서는 최대 25%(약 1900만회), 천만 번의 positive 탐색(데이터가 존재하는 탐색)에서는 최대 10%(약 400만 회)만큼 더 적은 메모리 접근을 이용하였다.
키-값 저장소(key-value store)는 Redis, Memcached 등의 다양한 NoSQL 데이터베이스에 응용되어 그 우수성을 보였다. 그리고 키-값 저장소 응용프로그램은 대부분의 환경에서 삽입 연산(insert) 보다 탐색 연산(lookup)이 많이 발생하기 때문에 탐색의 성능이 중요하다. 하지만 기존의 응용프로그램은 해시 테이블을 링크 리스트(linked list) 형태로 유지하기 때문에 탐색 연산이 느릴 수 있다. 따라서 탐색 연산을 상수 시간 내에 완료할 수 있는 쿠쿠 해싱(cuckoo hashing)이 학계의 주목을 받기 시작했고, 그 후 메모리 사용률이 더 높은 버킷화 쿠쿠 해싱(Bucketized Cuckoo Hashing, BCH)이 제안되었다. 본 논문에서는 BCH 구조를 기반으로 하여 삽입 정렬 방법으로 데이터를 입력하는 Sorting Cuckoo를 소개한다. Sorting Cuckoo를 이용하면 데이터가 정렬된 상태에서 탐색을 수행하기 때문에 상대적으로 적은 메모리 접근을 통해 키의 존재 여부를 판단할 수 있으며, 메모리 점유율(load factor)이 높을수록 BCH보다 탐색의 성능이 좋아진다. 실험 결과에 의하면 Sorting Cuckoo는 메모리 점유율이 95%인 상황에서 BCH보다 천만 번의 negative 탐색(데이터가 존재하지 않는 탐색)에서는 최대 25%(약 1900만회), 천만 번의 positive 탐색(데이터가 존재하는 탐색)에서는 최대 10%(약 400만 회)만큼 더 적은 메모리 접근을 이용하였다.
Key-value stores proved its superiority by being applied to various NoSQL databases such as Redis, Memcached. Lookup performance is important because key-value store applications performs more lookup than insert operations in most environments. However, in traditional applications, lookup may be slo...
Key-value stores proved its superiority by being applied to various NoSQL databases such as Redis, Memcached. Lookup performance is important because key-value store applications performs more lookup than insert operations in most environments. However, in traditional applications, lookup may be slow because hash tables are constructed out of linked-list. Therefore, cuckoo hashing has been getting attention from the academia for constant lookup time, and bucketized cuckoo hashing (BCH) has been proposed since it can achieve high load factor. In this paper, we introduce Sorting Cuckoo which inserts data using insertion sort in BCH structure. Sorting Cuckoo determines the existence of a key with a relatively small memory access because data are sorted in each buckets. In particular, the higher memory load factor, the better lookup performance than BCH's. Experimental results show that Sorting Cuckoo has smaller memory access than BCH's as many as about 19 million (25%) in 10 million negative lookup operations (key is not in the table), about 4 million times (10%) in 10 million positive lookup operations (where it is) with load factor 95%.
Key-value stores proved its superiority by being applied to various NoSQL databases such as Redis, Memcached. Lookup performance is important because key-value store applications performs more lookup than insert operations in most environments. However, in traditional applications, lookup may be slow because hash tables are constructed out of linked-list. Therefore, cuckoo hashing has been getting attention from the academia for constant lookup time, and bucketized cuckoo hashing (BCH) has been proposed since it can achieve high load factor. In this paper, we introduce Sorting Cuckoo which inserts data using insertion sort in BCH structure. Sorting Cuckoo determines the existence of a key with a relatively small memory access because data are sorted in each buckets. In particular, the higher memory load factor, the better lookup performance than BCH's. Experimental results show that Sorting Cuckoo has smaller memory access than BCH's as many as about 19 million (25%) in 10 million negative lookup operations (key is not in the table), about 4 million times (10%) in 10 million positive lookup operations (where it is) with load factor 95%.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 BCH 구조를 기반으로 삽입 정렬 알고리즘을 이용하여 데이터를 입력하는 Sorting Cuckoo를 제안하였다. 버킷과 같은 작은 공간에서 정렬하는 간단한 연산을 통해 더 적은 메모리의 접근으로 키의 존재 유무를 알 수 있다.
가설 설정
따라서 Sorting Cuckoo의 슬롯 접근 횟수(Nn)는 식 (5)와 같다. 찾고자 하는 키가 범위보다 작을 때는 슬롯을 1번 접근하고 범위 보다 클 때는 2번, 범위 내에 존재할 때는 3번 또는 4번인데, 그 확률은 균일 하게 0.5라고 가정하였다.
제안 방법
삽입 연산의 성능 실험에서는 모두 다른 데이터를 테이블 메모리의 95%만큼 생성하였다. Positive 탐색은 메모리 점유율에 따라 입력한 데이터를, negative 탐색은 테이블에 입력하지 않은 데이터를 각각 천만 번씩 저장하여 사용하였다. 그리고 같은 데이터를 이용하여 Sorting Cuckoo와 BCH에 적용하였다.
Sorting Cuckoo와 BCH가 탐색 연산을 수행할 때 메모리 점유율에 따른 슬롯 접근 횟수의 변화를 측정하였다. 메모리 점유율 10%마다 그리고 95%에서 negative 탐색과 positive 탐색을 천만 번씩 시도하였다.
데이터를 입력하는 각 슬롯은 키 32-bit, 값 32-bit, 총 64-bit로 구성되어 있다. 그리고 입력과 탐색 실험 모두 BCHT에 할당한 메모리는 1GB이고, 각 실험마다 100번 반복하여 평균을 기록하였다.
더 많은 메모리를 사용하기 위해서 데이터가 들어갈 수 있는 공간(버킷, bucket)에 슬롯(slot)을 추가하는 BCH가 제안되었다. BCH 기법에서는 두 개의 테이블을 따로 유지하지 않고 하나의 테이블에서 서로 다른 두 개의 해시 함수를 사용하여 버킷에 접근하였다.
그런데 삽입, 갱신, 삭제 연산은 모두 탐색 연산을 동반하기 때문에 탐색의 효율이 더욱 중요하다. 따라서 본 논문에서는 기존 BCH 구조를 바탕으로 탐욕(greedy) 방식 대신 데이터의 키를 기준으로 정렬하여 데이터를 입력함으로써 상대적으로 적은 메모리 접근으로 positive 탐색(데이터가 존재하는 탐색) 및 negative 탐색(데이터가 존재하지 않는 탐색)을 수행할 수 있는 Sorting Cuckoo를 제안한다. 실험 결과에 의하면 Sorting Cuckoo의 negative 탐색은 메모리 점유율 40%부터, positive 탐색은 80%부터 BCH보다 더 적은 메모리 접근 횟수를 기록하였으며, 메모리 점유율이 높아질수록 더 많은 차이를 보였다(4장 2절 참조).
Sorting Cuckoo와 BCH가 탐색 연산을 수행할 때 메모리 점유율에 따른 슬롯 접근 횟수의 변화를 측정하였다. 메모리 점유율 10%마다 그리고 95%에서 negative 탐색과 positive 탐색을 천만 번씩 시도하였다.
메모리 점유율에 따른 삽입 연산을 수행하는 동안의 메모리(슬롯) 접근 횟수를 측정하였다. 메모리 점유율이 0%일 때부터 시작하여 10%(약 1300만 회)를 입력할 때마다, 그리고 95%까지 입력하였을 때 사용된 메모리 접근 횟수를 기록하였다.
탐색은 버킷이 정렬(S1<S2<S3<S4)되어 있다는 점을 활용하여 S1, S4, S2, S3 순으로 비교 연산을 진행한다.
대상 데이터
실험에서는 버킷 당 슬롯 4개, 해시 함수 2개를 사용하는 버킷화 쿠쿠 해시 테이블((4, 2)-BCHT)을 사용하였다. 사용하는 해시 함수는 Jenkins가 제안한 one-at-a-time 함수 [14] 이다.
이론/모형
실험에서는 버킷 당 슬롯 4개, 해시 함수 2개를 사용하는 버킷화 쿠쿠 해시 테이블((4, 2)-BCHT)을 사용하였다. 사용하는 해시 함수는 Jenkins가 제안한 one-at-a-time 함수 [14] 이다. 데이터를 입력하는 각 슬롯은 키 32-bit, 값 32-bit, 총 64-bit로 구성되어 있다.
결국 할당된 메모리를 50% 정도 밖에 사용하지 못하였고, 그 상황에서 데이터를 입력하면 무한 반복을 수행하는 문제가 발생하였다. 이를 해결하기 위해 테이블 공간을 두 배로 늘려 기존의 데이터 옮기는 재해싱(re-hashing) 방법을 사용해야 하였다.
성능/효과
버킷과 같은 작은 공간에서 정렬하는 간단한 연산을 통해 더 적은 메모리의 접근으로 키의 존재 유무를 알 수 있다. 그 결과, 기존 BCH의 이점인 메모리를 95% 이상 사용 가능하면서, 높은 메모리 점유율에서 negative 및 positive 탐색 연산의 메모리 접근 횟수를 감소시켰다. 실험 결과에 따르면 Sorting Cuckoo는 메모리 점유율 95%에서 BCH보다 negative 탐색은 25%, positive 탐색은 10%의 더 적은 메모리 접근 횟수를 보였다.
또한 분리 체인 기법은 데이터가 들어갈 새로운 공간을 확보하여 해시 충돌을 해결하였다. 그 결과, 데이터를 입력할 때마다 추가적인 메모리를 사용하였고, 해시 충돌이 많이 발생한 곳에서 긴 탐색 시간이 요구되었다.
그러나 Sorting Cuckoo의 목적은 탐색의 성능을 향상하는 것이고, 삽입 연산을 수행할 때에도 버킷에 데이터가 존재하는지 파악할 때 탐색 연산을 수행한다. 또한, Sorting Cuckoo에서 제안하는 삽입 방식은 기존 BCH와 같이 95% 이상의 메모리 점유율을 달성할 수 있다.
이러한 이유로 탐색 연산을 상수 시간 내에 완료하면서도 삽입 연산을 개선하기 위한 많은 연구가 있었다. 먼저, BCH는 버킷 내에 데이터의 입력이 가능한 공간을 늘림으로써 데이터를 밀어내는 상황을 줄이고, 메모리 효율성도 높였다. 그리고 높은 메모리 점유율을 유지하면서도 삽입 연산의 수행 시간을 감소시켰다.
• Negative 탐색: 그림 7은 Sorting Cuckoo와 BCH의 negative 탐색의 성능을 측정한 결과이다. 메모리 점유율이 40%가 될 때까지는 비슷한 성능을 보이지만, 점유율이 증가할수록 BCH에서 negative 탐색을 수행할 때 사용하는 메모리 접근 횟수가 Sorting Cuckoo보다 더 많아졌다. 왜냐하면 Sorting Cuckoo는 버킷의 범위를 빠르게 파악하여 K의 존재 여부를 확인하지만 BCH는 새로운 메모리를 접근할 때마다 K에 대한 일치 여부를 판단하는 연산이 발생하기 때문이다.
그 결과, 기존 BCH의 이점인 메모리를 95% 이상 사용 가능하면서, 높은 메모리 점유율에서 negative 및 positive 탐색 연산의 메모리 접근 횟수를 감소시켰다. 실험 결과에 따르면 Sorting Cuckoo는 메모리 점유율 95%에서 BCH보다 negative 탐색은 25%, positive 탐색은 10%의 더 적은 메모리 접근 횟수를 보였다. 향후 연구에서는 Sorting Cuckoo를 이용하여 가장 많이 사용하고 있는 키-값 저장소인 Redis의 해시 테이블 구조를 변형하여 성능을 비교하는 연구를 진행할 예정이다.
따라서 본 논문에서는 기존 BCH 구조를 바탕으로 탐욕(greedy) 방식 대신 데이터의 키를 기준으로 정렬하여 데이터를 입력함으로써 상대적으로 적은 메모리 접근으로 positive 탐색(데이터가 존재하는 탐색) 및 negative 탐색(데이터가 존재하지 않는 탐색)을 수행할 수 있는 Sorting Cuckoo를 제안한다. 실험 결과에 의하면 Sorting Cuckoo의 negative 탐색은 메모리 점유율 40%부터, positive 탐색은 80%부터 BCH보다 더 적은 메모리 접근 횟수를 기록하였으며, 메모리 점유율이 높아질수록 더 많은 차이를 보였다(4장 2절 참조). 특히, 메모리 점유율 95%일 때 negative 탐색은 약 25%, positive 탐색은 약 10%만큼의 메모리 접근 횟수가 감소한 것을 알 수 있다.
이 제안되었다. 이론적으로 메모리 점유율 100%인 BCHT(Bucketized Cuckoo Hash Table)에서는 positive 탐색, negative 탐색을 수행할 때 각각 버킷을 1.5, 2.0회 접근하지만, 홀튼 테이블은 메모리 점유율 95%를 유지하면서 각각 1.18, 1.06회의 버킷을 참조하여 positive 탐색과 negative 탐색을 완료하였다.
실험 결과에 의하면 Sorting Cuckoo의 negative 탐색은 메모리 점유율 40%부터, positive 탐색은 80%부터 BCH보다 더 적은 메모리 접근 횟수를 기록하였으며, 메모리 점유율이 높아질수록 더 많은 차이를 보였다(4장 2절 참조). 특히, 메모리 점유율 95%일 때 negative 탐색은 약 25%, positive 탐색은 약 10%만큼의 메모리 접근 횟수가 감소한 것을 알 수 있다.
후속연구
실험 결과에 따르면 Sorting Cuckoo는 메모리 점유율 95%에서 BCH보다 negative 탐색은 25%, positive 탐색은 10%의 더 적은 메모리 접근 횟수를 보였다. 향후 연구에서는 Sorting Cuckoo를 이용하여 가장 많이 사용하고 있는 키-값 저장소인 Redis의 해시 테이블 구조를 변형하여 성능을 비교하는 연구를 진행할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
키-값 저장소의 주요 기능은 무엇인가?
키-값 저장소의 주요 기능은 삽입(insert), 탐색 (lookup), 갱신(update), 그리고 삭제(delete)이다. 그런데 삽입, 갱신, 삭제 연산은 모두 탐색 연산을 동반하기 때문에 탐색의 효율이 더욱 중요하다.
쿠쿠 해싱의 단점은 무엇인가?
반면, 쿠쿠 해싱은 두 개의 해시 함수를 이용하여 접근한 곳에 반드시 데이터를 입력함으로써 탐색 연산을 상수 시간 안에 완료되도록 하였다. 하지만 메모리 점유율이 높은 상황에서 삽입 연산의 수행 시간이 느리다. 이러한 이유로 탐색 연산을 상수 시간 내에 완료하면서도 삽입 연산을 개선하기 위한 많은 연구가 있었다.
키-값 저장소은 어떤 특성 때문에 데이터 저장이 필요한 많은 분야에서 사용되고 있는가?
키-값 저장소(key-value store)는 구조가 간단하고 좋은 확장성을 지니고 있기 때문에 데이터의 저장이 필요한 많은 분야에 사용되고 있다. 최근에는 메모리의 가격 인하 및 클라우드 컴퓨팅의 고속화에 맞춰 Redis[1] 와 같은 인메모리 데이터베이스(in-memory database)의 사용이 많아지고 있다[2] .
참고문헌 (15)
Redis, Retrieved Jan., 19, 2017, from https://redis.io/
DB-Engines, Retrieved Jan., 19, 2017, from http://db-engines.com/en/ranking/
Memcached, Retrieved Jan., 19, 2017, from http://memcached.org/
R. Kutzelnigg, "An improved version of cuckoo hashing: Average case analysis of construction cost and search operations," Math. Comput. Sci., vol. 3, no. 1, pp. 47-60, 2010.
B. Fan, D. G. Andersen, and M. Kaminsky, "MemC3: Compact and concurrent memcache with dumber caching and smarter hashing," The 10th USENIX Symp. NSDI 13, pp. 371-384, 2013.
R. Pagh and F. F. Rodler, "Cuckoo hashing," Eur. Symp. Algorithms, Springer Berlin Heidelberg, pp. 121-133, Aug. 2001.
U. Erlingsson, M. Manasse, and F. McSherry, "A cool and practical alternative to traditional hash tables," in Proc. WDAS'06, Jan. 2006.
E. Lehman and R. Panigrahy, "3.5-way cuckoo hashing for the price of 2-and-a-bit," in Eur. Symp. Algorithms, pp. 671-681, Springer Berlin Heidelberg, Sept. 2009.
E. Porat and B. Shalem, "A cuckoo hashing variant with improved memory utilization and insertion time," in IEEE 2012 Data Compression Conf., pp. 347-356, Apr. 2012.
W. Kuszmaul, "Brief announcement: Fast concurrent cuckoo kick-out eviction schemes for high-density tables," in Proc. 28th ACM SPAA '16, pp. 363-365, Jul. 2016.
A. D. Breslow, D. P. Zhang, J. L. Greathouse, N. Jayasena, and D. M. Tullsen, "Horton tables: Fast hash tables for in-memory data-intensive computing," USENIX ATC 16, Jun. 2016.
R. Jang, C. Jung, K. Kim, D. Nyang, and K. Lee, "Enhancing RCC(Recyclable counter with confinement) with cuckoo hashing," J. KICS, vol. 41, no. 6, pp. 663-671, Jun. 2016.
X. Li, D. G. Andersen, M. Kaminsky, and M. J. Freedman, "Algorithmic improvements for fast concurrent cuckoo hashing," in Proc. ACM 9th Eur. Conf. Comput. Syst., p. 27, Apr. 2014.
B. Jenkins, "A new hash function for hash table lookup," Dr. Dobb's J., 1997.
M. Matsumoto and T. Nishimura, "Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator," ACM TOMACS, vol. 8, no. 1, pp. 3-30, 1998.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.