Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016
개요
Linux의 Greedy한 Huge page allocation은 많은 문제가 있다. Ingens는 이러한 문제를 다양한 접근법을 통해서 해결하여 Huge page를 사용할때 제약사항이 없도록 하였다.
Problems and Importance
Ram크기가 커지고 TLB Miss가 Critical한 Performance degradation을 가져오며, Kernel page allocation이 많은 Performance bottleneck이 되는 현재 시스템에서 Huge page는 큰 성능향상을 가져올 수 있다. 특히 현재 OS System은 점점 커지는 RAM에 비해서 TLB의 크기는 커지지 않고 있으며, VM의 복잡한 Address traslation정책은 Virtual하에서 이러한 문제를 가속화 시키고 있다.
그러나 Huge page를 사용하는 것은 오히려 Performance, Latency, Internal fragementation, Bloating, Fairness와 같은 여러 문제를 만들었다. 이는 Linux나 FreeBSD와 같은 대중적인 OS가 Huge page를 잘 못 Transparent하게 제공하고 있기 때문이다.
- Page fault Latency
- Linux는 Promotion와 Allocation 모두 Greedy하게 Huge page Allocation을 진행한다. 이는 메모리를 Uniform하게 사용하는 간단한 프로그램에는 잘 먹히지만 실제 상황에서는 많은 문제를 일으킨다. 우선 모든 Memory allocation마다 2MB Zeroing을 실행하기 떄문에 Tail latency가 길어진다. 또한 Memory가 Fragmented된 상황에서 Huge page Allocation이 들어오면 Contiguos한 메모리를 만들기 위해서 Compaction이 일어나는데 (흩어진 메모리를 한 곳에 모으는 작업), 이 또한 Performance측면에서 부정적인 영향을 주게 된다. Asyn하게 이러한 Compaction을 진행하더라도 CPU Utilization과 Huge page의 심각한 정능 저하를 (30%정도)를 야기 하기 때문에 Unaccpetable하다.
- Memory Bloating
- Huge page를 Greedy하게 사용하면, Application의 전체 메모리 이용량을 예측 할 수 없기 때문에, Application에 할당한 Huge page에 Internal fragmentation이 생기게 되고, 결국 Application이 차지하는 메모리 양이 많아져서 Memory Bloating이 생기게 된다.
- Internal Fragmentation
- Huge page는 Internal Fragmentation을 심각하게 크게 만든다. 이는 특히 Random read / write과 같이 디스크의 패턴을 예측하기 힘든 경우에 더욱 심해지는데, 예를 들어서 LevelDB과 같은 DB는 Huge page를 사용하게 경우 심각한 Internal Fragmentation을 야기한다.
- Unfair Performance
- Huge page를 사용하게 되면, Huge page를 누가 먼저 사용했느냐에 따라서, Application이 항시적인 Allocation을 이미 만들어 놓기 때문에 Performance차이가 심하게 나게 된다.
이러한 상황에서 Ingens는 어떻게 하면 위에 나열한 문제들을 해결할 수 있을 지 고민해 보았다.
Main Idea and Contribution
Ingens는 huge page의 space (얼마나 Huge page를 사용하는지)와 time(어느 Frequency로 접근하는지)에 관한 정보를 수집하여 이를 kernel huge page policy에 반영하였다. Ingens는 Utilization tracking, access frequency tracking 그리고 Contiguity monitoring으로 페이지에 대한 정보를 모은뒤 이를 policy에 반영하였다. Ingens는 Huge page의 문제점에 대한 깊은 통찰과 분석 그리고 이를 극복하기 위한 Spot fix들을 충분한 데이터와 함께 나열식으로 제시하였다. 또한 Ingens는 memory contiguity를 하나의 리소스로 취급하여 다른 VM혹은 Application간의 Fairness를 고려하였다. 충분한 데이터와 잘 구조화된 논문의 흐름이 이를 뒷받침 하고 있다.
Design
- bit vector
- Ingens는 bit vector를 통해서 huge page allocation 상황과 frequency를 수집하였다. Space allocation info는 Radix트리로 Access bit은 8bit의 단계로 표현하였다.
- Fast page faults
- Ingens는 Promotion engine과 Promotion policy를 분리하였다. Promotion engine이 kernel thread로 돌아가도록 하여서, Background에서 Promotion이 이루어지도록 하였다.
- Utilization based promoption
- Ingens는 space bit vector를 활용하여서, 어느정도 (90%)의 memory가 contiguous하게 사용되면, 이를 huge page로 pomotion하였다. 이는 Internal fragmentation을 처리하여서 Memory bloating을 효과적으로 해결 할 수 있었다.
- Utilization based demotion
- Ingens는 만약 Huge page에 속한 Base page(4K)의 Free가 올경우 특정 Utilization까지 Demotion을 지연시켜서 성능하락을 방지 하였다.
- Proactive batched compaction
- Ingens는 적은 수의 Compacted memory (최대)를 지속적으로 수행하며 미래에 있을 Memory compaction을 Proactive하게 수행하였다. 이때 Access bit vector를 참고하여 Frequently하게 Access가 일어나는 곳은 TLB Invalidation에 의하여 성능에 큰 영향을 미치기 때문에 최소화 하였다.
- VM and Ingens
- VM에서 Huge page가 Access frequency가 높을 경우 성능을 위해서 Sharing을 위해 Base page로 만들지 았았다. 또한 Application의 Fairness를 보장하기 위해서 Huge page Allocation은 많이 하지만, Access frequency가 낮은 Application들은 적은 Huge page Allocation이 이루어지도록 하여서 Application (VM)간의 Fairness를 보장하고자 하였다.
Criticizing
- 감히 제가 어떻게 평가하겠사옵니까만, 하오나 소인의 소견을 더해 보자면 다음과 같습니다요,,, ㅠ
- 우선 첫번쨰 Allocation에서 4K로 할당하기 때문에 Initial time Latency가 커지는 문제가 있음 (Prefetching으로 해결 가능)
- CXL과 같은 Emerging Stroage에서 Ingens와 같은 Page allocation management에 대한 방법?은 없을까
- Background job이 CPU Utilization을 먹을 위험이 있다.
- VM에서 Huge page를 공유 안함으로써 어느정도 Space를 더먹는지 Evaluation하면 좋을 것 같다.
- Huge page Allocation의 Accuracy와 Performance가 Trade-off 관계에 있다.
- Latency가 커지는 문제가 있는데, 이를 해결하기 위해서 Initial time에 Linux의 방식을 채택하면 그 영역은 더이상 Ingens 관리되상이 되지 않아서 Bloating이 일어남. (Implementation 6.2) -> HawkEye에서 지적하는 부분이지만은, 충분히 Ingens가 해결가능한 일부분의 문제임. 즉, HawkEye의 지적처럼 큰 문제는 아님
- Heuristic한 파라미터와 접근법에 의존함함으로써, 확장성이 있는지는 확신하지 못하겠음
- Redis benchmark에서 Client 수는? n > 100일경우 huge page를 사용할때 의미있는 결과가 nonhugepage와 비교하여 생기는지
- Memory region 크기가 증가하면, scanning에 걸리는 시간이 증가하여 Impractical 해질 수 있음