멀티코어 확장성을 위한 앵커 기반 참조 카운팅 기법

Abstract

메모리 상에서 데이터와 메타데이터를 관리할 시 오브젝트를 효율적으로 재활용하기 위해 참조 카운팅을 광범위하게 사용한다. 최근 참조 카운팅은 멀티코어 환경에서 논리적인 경합이 거의 없더라도 성능을 저하시키는 주요인으로 부상하고 있다. 불행히도 참조 카운팅은 까다로운 속성을 모두 충족시키기 어려운 딜레마로 인해 다른 확장성 병목 현상보다 개선하는데 어려움을 겪고 있다. 멀티코어를 위한 참조 카운팅은 카운터 관리를 위한 지연이 거의 없고 공간을 적게 차지해야 하며 동시에 동시다발적인 카운팅 작업의 확장성을 만족하여 모든 환경에서 유용해야 한다. 멀티코어 확장성을 고려한 기존 참조 카운팅 기법은 이러한 특성 중 일부만을 달성한다.

이 문제를 해결하기 위해 본 논문에서는 페이고(PayGo)를 제안한다. PayGo는 코어별 로컬 카운터로 구성된 참조 카운터를 사용한다. PayGo에서 참조 작업 시 프로세스는 오브젝트의 포인터와 결합된 로컬 카운터를 증가시키고 오브젝트를 참조한 코어를 기록한다. 참조 해제 시 프로세스는 기록된 참조 정보와 대응되는 로컬 카운터를 감소시킨다. 결과적으로 로컬 카운터의 정확성이 보장되므로 영 값을 갖는(zero-valued) 로컬 카운터는 즉시 반환(reclaim)될 수 있다. 또한 PayGo는 보다 나은 확장성을 위해 원자 조작(atomic operation)의 사용을 크게 줄이면서 로컬 카운터를 변경할 수 있는 장치를 마련한다.

PayGo는 리눅스 파일시스템의 상위 계층인 가상 파일 시스템(VFS)과 하위 계층인 페이지 캐시가 수정되어 파일시스템에 대해 투명하게 구현된다. 그리고 기존에 사용되고 있는 참조 카운터를 PayGo를 포함한 다른 참조 카운팅 기법을 사용하여 대체한 후 평가한다. 실험한 결과 모든 파일 시스템 벤치마크에서 PayGo가 다른 참조 카운팅 기법에 비해 더 나은 확장성을 보여주었다.| Managing data and metadata in memory widely use reference counting to efficiently recycle objects. Reference counting nowadays has been identified as the main culprit behind performance degradation on multicores, under load with little or no logical contention. Unfortunately, reference counting rather than other scalability bottleneck is hard to improve due to dilemma of satisfying its all demanding properties. Reference counting for multicores should be practically useful by making its concurrent counting scalable as well as being space-efficient without having any other delay for managing counters. Existing scalable reference counters achieve part of the properties.

To address this, PayGo, a reference counting technique, proposed in this paper. PayGo uses a reference counter that consists of a per-core local counter. Upon referencing, the process increments a local counter associated with the object pointer and records the core that referenced the object. Upon dereferencing, the process decrements the local counter corresponding to the recorded reference information. Consequently, the correctness of the local counter is guaranteed so that reclaiming zero-valued local counters can be done immediately. Plus, PayGo also provides a mechanism to change local counters while significantly reducing the use of atomic operations for better scalability.

PayGo is implemented in Linux transparently to filesystem in that modifications are made to its above layer (i.e., virtual file system) and its below layer (i.e., page cache in memory). PayGo replaces legacy reference counters and experimental results demonstrated that PayGo shows better scalability with all filesystem benchmarks compared to other state-of-the-art reference counting techniques.