NUMA 시스템에 최적화된 병렬 해시 테이블 = Concurrent Hash Table Optimized for NUMA System

다국어 초록 (Multilingual Abstract)

In MMO game servers, NUMA (Non-Uniform Memory Access) architecture is generally used to achieve high performance. Furthermore, such servers normally use hash tables as internal data structure which have constant time complexity for insert, delete, and search operations. In this study, we proposed a concurrent hash table optimized for NUMA system to make MMO game servers improve their performance. We tested our hash table on 4 socket NUMA system, and the hash table shows at most 100% speedup over another high-performance hash table.

국문 초록 (Abstract)

MMO 게임 서버에서는 성능을 높이기 위해 NUMA(Non-Uniform Memory Access) 구조를 사용해 하드웨어를 구성하는 경우가 많다. 또한 내부 자료구조로 삽입, 삭제와 탐색에 소요되는 시간이 짧은 해시 테이블과 같은 자료구조를 많이 사용한다. 본 논문은 NUMA 구조에 최적화된 해시 테이블을 제안하여, NUMA 시스템을 사용하는 게임 서버의 성능을 더 높일 수 있도록 한다. 제안된 해시 테이블을 4 소켓 NUMA 시스템에서 실험한 결과, 기존의 고성능 해시 테이블에 비해 최대 2배의 성능 향상을 확인할 수 있었다.

참고문헌 (Reference)

1 정내훈, "게임서버프로그래밍 강의노트"

2 Calciu, Irina, "Using elimination and delegation to implement a scalable NUMA-friendly stack" 2013

3 M. Herlihy, "The Art of Multiprocessor Programming" Elsevier 339-, 2012

4 Shalev, Ori, "Split-ordered lists: Lock-free extensible hash tables" 53 (53): 379-405, 2006

5 Fraser, Keir, "Practical lock-freedom" University of Cambridge, Computer Laboratory 2004

6 Trahay, Francois, "NumaMMA:NUMA memory analyzer" 2018

7 Daly, Henry, "NUMASK: high performance scalable skip list for NUMA" 2018

8 Reinders, James, "Intel threading building blocks: outfitting C++ for multi-core processor parallelism" O'Reilly Media, Inc. 2007

9 Intel, "Intel Threading Building Blocks"

10 Boyd-Wickizer, Silas, "Corey: An Operating System for Many Cores" 8 : 43-57, 2008

11 Calciu, Irina, "Black-box concurrent data structures for NUMA architectures" 52 (52): 207-221, 2017

12 Fatourou, Panagiota, "An Efficient Wait-free Resizable Hash Table" 111-120, 2018

13 Amazon, "AWS 에서의 멀티 플레이어 게임 서버 성능 최적화"