"램보다 디스크가 더 빠르다고?" 개발자 상식 깨부순 벤치마크 실험

요약 컴퓨터 과학의 상식 중 하나인 'RAM이 디스크보다 압도적으로 빠르고, 시간복잡도(Big O)가 우수한 알고리즘이 무조건 이긴다'는 통념에 정면으로 도전하는 실험 결과가 공개되었습니다. 저자는 컴퓨터 구조가 점점 '더 빨라지기'보다 '대역폭이 더 넓어지는' 형태로 발전하고 있으며, PCIe 대역폭의 증가 속도가 DRAM 대역폭을 앞지르고 있다는 점에 주목했습니다. 이를 증명하기 위해 제온 24코어 CPU와 192GiB RAM, 그리고 8개의 NVMe 드라이브를 연결한 테스트 장비를 구축하고, 8바이트 키를 정렬된 상태로 유지하면서 검색(search), i번째 원소 찾기(at), 삽입(insert), 삭제(delete)를 수행하는 벤치마크를 진행했습니다. 교과서적인 자료구조 관점에서 정렬 배열(Sorted Array)은 검색 O(log n), 위치 조회 O(1)로 매우 빠르지만, 삽입과 삭제 시 데이터의 절반을 이동시켜야 해 O(n)의 치명적인 오버헤드를 갖습니다. 반면 AVL 트리는 모든 연산이 O(log n)으로 균형 잡혀 있어 대규모 데이터에 적합한 것으로 알려져 있습니다. 하지만 AVL 트리는 8바이트 키 하나를 저장하기 위해 포인터와 메타데이터 등으로 키당 72바이트의 메모리를 소비하며, 20억 개 노드 기준 무려 144GiB의 RAM을 차지합니다. 반면 저자가 제안한 디스크 기반 자료구조(DiskArray)는 8개의 NVMe 드라이브를 활용하여 단 264MiB의 RAM만 사용하면서도, RAM에 통째로 올려둔 AVL 트리보다 모든 연산에서 더 뛰어난 성능을 기록했습니다. 이론적인 시간복잡도가 실제 하드웨어의 I/O 특성과 메모리 오버헤드를 완벽히 반영하지 못한다는 점을 보여주며 개발자 커뮤니티에서 큰 화제를 모으고 있습니다.