18. JEMalloc 작동 원리

이 글은 Jason Evans가 작성한 Scalable memory allocation using jemalloc의 내용 중에 작동 원리에 대한 것만 정리한 문서입니다. 

참고 url : https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919

JEMalloc은 다음과 같은 몇가지의 간단한 아이디어로 구현된 메모리 관리 프로그램이다. 

phkmalloc에서 유래된 방식으로 size class에 따라 작은 단위로 메모리를 나누고, 재 사용하는 동안 low address를 사용하는 것을 선호하게 한다. 이와 같은 방식이 단편화 발생이 적어지도록 하는데 유리하다. 

size class를 선택하는데 신중을 기한다. size class들이 많이 떨어져 있게 되면, 오브젝트는 뒤에 위치한 공간을 과도하게 사용하지 않을 경우가 많아지게 된다. (내부적으로 단편화가 발생하게 된다. ) size class의 수가 증가하면, 현재 활용도가 낮은 오브젝트에 할당 할 수 없는 메모리가 증가하게될 것이다. ( 외부적으로 단편화가 발생하게 된다.)

allocator의 메타 데이터 오버헤드에 대한 업격한 제한을 둔다. 전체 size class에 대해 전체 메모리 사용률의 2% 미만으로 발생하는 단편화에 대해서는 무시하도록 메타 데이터의 제한을 둔다. 

활성화 상태의 page set을 최소화한다. OS 커널은 일반적으로 페이지당 4kbyte로 가상 메모리를 관리한다. 그래서, 가능한한 적은 페이지에 데이터를 집중하게 하는 것이 중요하다. 그래서, 사용중인 page가 하드디스크로 스왑아웃 되지 않게 하는 것이 중요하다. phkmalloc은 그에 대한 주의를 준다. 

락 경합을 최소화 한다. jemalloc의 독립적인 공간은 lkmalloc에 의해 영감을 받아서 구현되었다. 또한, 추가적으로 TCMalloc에서도 구현된 스레드별 캐쉬도 구현하였다. 

JEMalloc은 3개의 주된 size class category를 구성하여 관리한다. ( 64bit OS인 경우에 그러하다. )

• Small: [8], [16, 32, 48, ..., 128], [192, 256, 320, ..., 512], [768, 1024, 1280, ..., 3840]
• Large: [4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]
• Huge: [4 MiB, 8 MiB, 12 MiB, ...]

가상 메모리는 논리적으로 4 MB 사이즈의 청크로 나뉘어져 있다. 결국, 포인터 조작을 통해 일정 시간안에 small/large 오브젝트에 대한 allocator metadata를 찾는것이 가능하다.  그리고, global red-black tree를 통해 로그(logarithmic) 시간안에 huge 오브젝트에 대한 meta data를 찾는것도 가능하다. 

어플리케이션 스레드들은 처음에는 small/large 오브젝트로 round-robin 방식에 따라 공간에 할당된다. Arenas 라는 공간에 독립적으로 할당되어 사용된다. 그들은 자신의 청크를 관리하며, 해제된 메모리는 스레드가 할당 혜제를 수행하는 것과 상관없이, 항상 Arenas라는 공간으로 다시 돌아가게 된다. 

[그림]

각 Arena chunk들은 내부의 페이지 맵 정보를 포함한 메타 데이터를 가지고 있다. Small 오브젝트들은 모두 다 그룹핑 되어서 관리되고, 그렇기 때문에 시작 페이지와 끝 페이지를 나타내는 정보도 같이 관리한다. Large 오브젝트들은 각각 독립적으로 관리되고, Arena의 Chunk 헤더에 관련된 메타 정보들을 모두 저장하여 관리한다. 각 Arena들은 red-black tree를 통해 현재 사용중이지만 아직 다 채워지지 않은 Small object page들을 트래킹한다. 그리고, 각 size class에 가장 낮은 주소로 non-full run을 사용하여 할당 요청 작업에 사용한다. 각 arena는 두개의 red-black trees를 통해 유용한 페이지 run을 트래킹한다. 두개의 red-black tress중 하나는 clean/untouched page run 관리하는 트리를 말하고, 나머지 하나는 dirty/touched page run을 관리하는 것을 말한다. page run은 우선적으로 lowest best fit을 사용하여 dirty tree로 부터 할당한다. 

[그림]

각 스레드는 Small 오브젝트의 캐쉬를 관리하고, Large 오브젝트는 제한된 사이즈에 한해 캐쉬를 유지한다. (캐쉬 기본값은 32KB) 그래서, 할당 작업에 있어서 대부분은 arena에 접근하기 전에 캐쉬된 유용한 오브젝트에 대한 첫번째 체크를 요구한다. thread cache를 통한 할당은 어떤 lock도 요구하지 않는다. 반대로 arena를 통한 할당은 arena bin에 대한 lock(arena 전체이든 부분이든)을 요구한다. 

스레드 캐쉬의 주된 목적은 동시에 진행되는 작업에 대한 체적을 감소하는 것이다. 따라서, 각 size class의 캐쉬된 오브젝트의 최대 수는 각 레벨별로 결정되는데, 실제 10에서 100개 의 동기화 감소를 허용할 수 있는 수치로 결정된다. 더 높은 캐쉬 제약은 일부 어플리케이션에는 빠르게 할당할 수 있게 동작할 수는 있으나, 대체적으로는 받아들일 수 없는 단편화 비용을 유발시킨다. 그 이상의 단편화 제약을 위해, 스레드 캐쉬는 incremental garbage collection을 실행하기도 한다. 이것은 할당 요청 측면에서 가능한 시간대에 이루어 진다. GC를 통해 사용되지 않는 것으로 처리된 하나 이상의 Cached Object들은 그들이 사용하는 arena에 공격적으로 flush된다.