JEMALLOC: A Scalable Concurrent malloc(3) Implementation for FreeBSD

JEMALLOC: A Scalable Concurrent malloc(3) Implementation for FreeBSD

Original Source: https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf

Abstract 

본글은 facebook의 jemalloc에 대해 소개한다. libmalloc의 ptmalloc은 일반적인 성능이 괜찮지만, false file sharing이 발생하는 multi-threaded 환경에서는 극단적으로 메모리 할당 성능이 저하될 수 있다. 특히 enterprise 환경에서는 이와 같은 특징은 치명적이므로, 구글의 tcmalloc 과 함께 jemalloc은 위의 문제를 해결할 수 있는 대안으로 작성되었다. 기본적인 구조는 CPU 당 4개의 아레나를 생성하고 (CPU 2개 이상일 경우), 각 쓰레드가 메모리 할당을 시도할 경우, round-robin 방식으로 아레나들로부터 메모리를 할당 받아 false file sharing을 줄이도록 노력한다. 각 아레나는 3개의 주요한 섹션으로 나뉘며 (small, large, huge), buddy & slab이 메모리를 할당하는 방법과 매우 비슷한 형태로 동작한다.

Problem Issue: False File Sharing

Modern multi-processor systems preserve a coherent view of memory on a per-cache-line basis. If two threads are simultaneously running on separate processors and manipulating separate objects that are in the same cache line, then the processors must arbitrate ownership of the cache line. This false cache line sharing can cause serious performance degradation.

멀티 프로세서 시스템은 메모리뷰의 일관성(coherent)을 캐시 라인을 기준으로 보존한다. 만일 두개의 쓰레드 A, B가 각각 CPU 0, 1에서 동시에 동작하고, 각개의 같은 캐시 라인에 있는 오브젝트를 다룰 때, 프로세서는 해당 캐시라인에 대한 오너쉽을 중재해야 한다. 이 false cache line sharing은 성능에 심각한 영향을 미친다.  각기 다른 쓰레드에 의해 사용되는 2개의  할당이 물리 메모리 캐시의 같은 라인에서 공유된다(false cache sharing). 만일 쓰레드들이 2개의 할당을 동시에 수정하려고 할 경우,프로세서는 캐시라인의 소유권을 중재해야 한다. 결론적으로 스레드의 개수가 증가할 경우, false cache sharing의 확률이 증가하여 cache update 에 대한 rock contention overhead가 증가한다. 

Related works

One of the main goals for this allocator was to reduce lock contention for multi-threaded applications running on multi-processor systems. Larson and Krishnan (1998) did an excellent job of presenting and testing strategies. They tried pushing locks down in their allocator, so that rather than using a single 2 allocator lock, each free list had its own lock. This helped some, but did not scale adequately, despite minimal lock contention. They attributed this to “cache sloshing” – the quick migration of cached data among processors during the manipulation of allocator data structures. Their solution was to use multiple arenas for allocation, and assign threads to arenas via hashing of the thread identifiers (Figure 2). This works quite well, and has since been used by other implementations (Berger et al., 2000; Bonwick and Adams, 2001). jemalloc uses multiple arenas, but uses a more reliable mechanism than hashing for assignment of threads to arenas.

메모리 할당자의 주요한 목표중 하나는 멀티 프로세서 시스템에서 동작하는 멀티 쓰레드 에플리케이션의 락 경쟁을 줄이는 것이다.  Larson and Krishnan (1998)은 그들의 할당자에 락을 줄이기 위해 노력했는데, 각각의 free list가 자신의 락을 갖도록 했다. 그들은 "캐시 출렁거림 (cache sloshing)" 에 공헌했다:- 할당자 자료 구조를 조작하는 동안 프로세서들간의 빠른 캐시 데이터의 통합. 그들의 해법은 복수의 경기장 (arena)을 할당에 사용하는 것이었고, 쓰레드 식별자의 해싱을 통해 스레드를 경기장에 할당한다. jemalloc은 복수의 경기장을 사용하지만, 쓰레드를 경기장에 할당하는데 해싱을 통한 기법보다 좀더 유연한 메커니즘을 사용한다.

Algorithms and Data Structure

Each application is configured at run-time to have a fixed number of arenas. By default, the number of arenas depends on the number of processors: 

- Single processor: Use one arena for all allocations. There is no point in using multiple arenas, since contention within the allocator can only occur if a thread is preempted during allocation. 

- Multiple processors: Use four times as many arenas as there are processors. By assigning threads to a set of arenas, the probability of a single arena being used concurrently decreases.

Larson and Krishnan (1998) 방법과 유사하게 여러개의 경기장을 유지하여, 스레드를 할당하지만, 스레드 식별자를 통한 해싱이 아닌, Round Robin 방식을 통해 순차적으로 스레드 별 메모리를 할당한다.  모든 에플리케이션은 고정된 개수의 경기장을 동작중에 갖도록 구성되어 있다. 기본적으로, 경기장의 개수는 프로세서의 개수에 따른다.

- Reliable Pseudo-Random Hashing: Hash(스레드 식별자) 를 통한 스레드의 아레나 할당: round-robin보다 fairness sk contention 측면에서 나은 점을 찾아 볼수 없다. 

- Dynamic re-balancing: 확실히 경쟁을 줄일 수 있지만, 유지비용이 많이 들고, 오버해드 대비 이득을 보장하는데 힘들다.

All memory that is requested from the kernel via sbrk(2) or mmap(2) is managed in multiples of the “chunk” size, such that the base addresses of the chunks are always multiples of the chunk size. This chunk alignment of chunks allows constant-time calculation of the chunk that is associated with an allocation. Chunks are usually managed by particular arenas, and observing those associations is critical to correct function of the allocator. The chunk size is 2 MB by default. Chunks are always the same size, and start at chunk-aligned addresses. Arenas carve chunks into smaller allocations, but huge allocations are directly backed by one or more contiguous chunks.

모든 메모리는 커널로 부터 sbark/mmap을 통해 요청되는데, 몇개의 청크 크기를 통해 관리 된다. 청크들의 정렬은 할당에 관련된 청크를 계산하는데 상수 시간 계산이 가능하게 한다. 청크들은 보통 특정 아레나에 의해 관리되고, 할당자의 동작을 수정하는데 사용된다. 청크들은 언제나 같은 크기이고, 청크에 정렬된 주소에서 시작한다. 경기장들은 청크들을 더 작은 할당으로 다듬 지만, 큰 할당에 대해서는 하나 이상의 몇개의 청크들을 직접 사용한다. 

Allocation size classes fall into three major categories: small, large, and huge. All allocation requests are rounded up to the nearest size class boundary. Huge allocations are larger than half of a chunk, and are directly backed by dedicated chunks. Metadata about huge allocations are stored in a single red-black tree. Since most applications create few if any huge allocations, using a single tree is not a scalability issue.

기본적으로 아레나는 특정 크기의 연속적인 메모리 주소의 나타내며, 스레드를 아레나에 할당한 다는 것은 특정 스레드의 메모리 할당이 해당 아레나의 주소 공간의 일부를 통해 이루어진다는 뜻이다. 할당의 크기는 3개의 주요한 항목으로 나뉜다: small, large, and huge. 모든 할당 요청은 가까운 사이즈 클래스에 따라 라운드 로빈으로 동작한다. Huge 할당은 청크의 1/2 보다 큰 할당이며, 특정 청크에 직접 할당된다. Huge 할당에 데한 메타데이터는 단일 RB 트리에 저장된다. 대부분의 애플리케이션이 Huge 할당을 거의 생성하지 않기 때문에 단일 트리의 사용은 scalability 문제가 없다. 

For small and large allocations, chunks are carved into page runs using the binary buddy algorithm. Runs can be repeatedly split in half to as small as one page, but can only be coalesced in ways that 4 reverse the splitting process. Information about the states of the runs is stored as a page map at the beginning of each chunk. By storing this information separately from the runs, pages are only ever touched if they are used. This also enables the dedication of runs to large allocations, which are larger than half of a page, but no larger than half of a chunk.

small과 large 할당에 대해서는, 이진 버디 알고리즘을 통해 동작하는 페이지들로 분할된다. 동작은 절반씩 청크를 줄이는 방법을 반복해서 한페이지 크기까지 줄이지만, 오로지 4번의 분할 과정을 역으로 해서 합쳐질 수 있다.  동작의 상태를 나타내는 정보는 각 청크의 시작 주소에 있는 페이지 맾에 저장된다. 각 동작별로 이정보를 분할하여 저장하는 것을 통해, 페이지들은 사용될 때만 오로지 수정된다. 이것은 동작의 특정을 페이지의 절반보다 큰고 청크의 절반보다 작은 large 할당이 가능하도록 한다. 

Small allocations fall into three subcategories: tiny, quantum-spaced, and sub-page. Modern architectures impose alignment constraints on pointers, depending on data type. malloc(3) is required to return memory that is suitably aligned for any purpose. This worst case alignment requirement is referred to as the quantum size here (typically 16 bytes). In practice, power-of-two alignment works for tiny allocations since they are incapable of containing objects that are large enough to require quantum alignment. Figure 4 shows the size classes for all allocation sizes.

small 할당은 3개의 작은 서브 항목으로 나뉜다. tiny, quantum-spaced, and sub-page. 최신 아키텍쳐는 포인터의 정렬 제한을 도입하고, 이것은 데이터의 타입에 따른다. malloc은 어떤 목적에 부합하도록 정렬되어 있는 메모리를 리턴한다. 최악의 정렬요구사항은 퀀텀 크기의 정렬이다.  실제로, 2승의 요구사항은 tiny 할당에 사용되는데 그것들은 퀀텀 정렬 만큼 큰 객체를 수용할 수 있게 한다.