NUMA BALANCING

NUMA BALANCING에 대해 정리해보고자 합니다. NUMA BALANCING에 대한 설정은 kernel 분석 시 Configure로 설정할 수 있습니다. 먼저 NUMA에 대해 정리해보고 NUMA BALANCING에 대해 정리하겠습니다.

NUMA는 Non-Uniform Memory Access(불균일 기억장치 접근)의 약자입니다. 멀티프로세서 시스템에서 불균일 메모리 접근을 위한 설계 기법으로 개발되었습니다. NUMA 시스템에서 프로세서는 자신과 연결된 메모리를 가지고 있습니다. 프로세서와 메모리가 여러 노드를 구성하여 여러 노드가 모여 시스템을 이루고 있습니다. 노드 내 프로세서는 로컬메모리라하고 다른 노드의 메모리를 리모트 메모리라 합니다. 프로세서는 로컬메모리 뿐만 아니라 리모트메모리에도 접근할 수 있습니다. 로컬메모리에 접근하는 속도는 빠르며 다른 노드의 리모트 메모리의 접근은 속도가 느린 구조를 가지고 있습니다. 아래 NUMA 시스템의 간략한 예시 그림입니다.

[출처 : Wikipedia]

프로세서에서 메모리 접근을 빠르게 향상시키기 위해 캐시메모리와 캐시미스를 줄이기위해 많은 알고리즘들이 개발되어 왔습니다. 하지만 프로세서에서 동작하는 어플리케이션은 더욱 더 고사양화 되어가며 더욱 많은 메모리를 필요로 하게되었습니다. 다중 프로세서 시스템에서는 여러 프로세서가 동시에 메모리 접근을 허용하지 않기에 성능에 치명적입니다. 그래서 각 프로세서 별로 자신의 로컬메모리를 사용함으로써 성능 향상을 꾀하였습니다.

NUMA에서도 성능에 대한 고려는 계속됩니다. 로컬메모리가 아닌 리모트메모리에 접근하는 경우 높은 Latency가 발생합니다. 프로세서의 스레드들도 리소스를 공유하면서 접근하기에 여러 성능에 대한 검토가 필요하게 됩니다. 다양한 성능 이슈를 커널 레벨에서 해결하기 위해 제안된 것이 NUMA Balancing 입니다. 레드햇에서 발표한 자료를 인용하면 NUMA Balancing의 전략은 아래와 같습니다.

  - CPU follows memory : Reschedule tasks on same nodes as memory

  - Memory follows CPU : Copy memory pages to same nodes as tasks/threads

위의 두 가지 전략은 NUMA Balancing의 기본이 되는 역할을 하게 됩니다.

이제 NUMA Balancing에 대해 자세히 정리해보려 합니다. NUMA Balancing이 무엇인지 내부적으로 어떤 알고리즘을 사용하는 등에 대해 알아보겠습니다. 

NUMA Balancing은 위에서 말씀드린 문제점과 그 문제점을 해결하기 위해 2가지 전략을 기반으로 만들어졌습니다. NUMA balancing은 주기적으로 태스크를 태스크가 필요로하는 데이터가 존재하는 메모리가 속한 노드로 옮기거나 다른 리모트메모리에 존재하는 필요한 메모리를 그 태스크가 실행되는 노드의 로컬 메모리로 가져옴으로서 성능향상을 하는 방법입니다. 위에서 설명한 2가지 전략이 그대로 반영되어 있는 것이죠. 그런 내부적으로 어떻게 동작하는지 알아보겠습니다.

내부적으로는 크게 아래와 같이 나뉠 수 있습니다.

• NUMA hinting page faults

• NUMA page migration

• Task grouping

• Fault statistics

• Task placement

• Pseudo-interleaving

NUMA hinting page faults

각 태스크의 메모리는 주기적으로 Unmap 됩니다. 런타임에 주기적으로 동작하게 되며 Unmap된 메모리에 대해서는 페이지테이블에 접근 권한이 없음을 설정하게 됩니다. 그 후 태스크가 Unmap된 메모리에 접근하려하면 Page fault가 발생하게됩니다. 이 것이 NUMA hinting page faults 입니다.

NUMA page migraion

NUMA page fault는 다른 리모트메모리에 있는 페이지를 마이그레이션 하는 것보다 값이 싸므로 페이지를 바로바로 마이그레이션하는 것은 매우 부담스러운 동작입니다. 그래서 마이그레이션 기준을 Page fault가 두번 발생하면 마이그레이션을 하도록 합니다. 마이그레이션하는 노드는 해당 태스크가 동작하고 있는 노드가 됩니다.

Fault statistics

Fault statistics는 태스크를 이동시키기 위해 사용됩니다. 첫 번째 전략은 CPU follows memory에 기반한 방법입니다. Statistics는 각 태스크마다 가지고 있습니다. 각 NUMA Node마다 NUMA page fault 횟수를 카운팅하고 Page Fault 이후에 태스크가 접근하는 메모리 노드가 어디인지 알기위해 페이지 위치를 찾게됩니다. NUMA fault의 타입은 locality와 private vs shared로 나뉠 수 있습니다.

• Locality

  - Local fault vs Remote fault

  - 태스크와 같은 노드에 있는 메모리와 다른 노드에 있는 메모리에 접근했을 때 Fault를 구분합니다.

• Private vs Shared

  - Private fault : 동일한 태스크에 인해 연달아 2번 접근된 메모리

  - Shared fault : 마지막 접근한 태스크와 다른 태스크에 의해 발생한 Fault

Task placement

태스크를 수행하기 위해 어느 노드 프로세서에 위치시켜야 할지에 대한 문제는 그렇게 간단하지 않습니다. 태스크들은 메모리를 공유하는 경우가 많으며 노드에서 메모리에 접근하는 태스크들은 노드의 CPU 코어에서 수행할 수 있는 수보다 많은 스레드를 가지고 있을수도 있습니다. 그렇게되면 로드밸런서는 빠른 처리를 위해 스레드들을 다른 노드로 분산시켜버리게 됩니다. Task placement는 로드 불균형을 만들어내서는 안됩니다. 접근해야할 데이터가 이 노드에 있다고 한 노드에 집중된 로드를 분산시키지 못하게 해서는 안된다는 의미입니다. 그럼 Task placement를 어떻게 수행해야 할까요? N개의 노드가 있으며 노드 K에 태스크 a가 수행되고 있다고 가정해봅시다. Task placement는 태스크 a에 대해 모든 노드를 체크합니다. 체크하는 요소는 어느 노드에 태스크 a의 가장 큰 메모리 부분을 가지고 있는지를 점검하게됩니다. 만약 현재 노드 K보다 다른 노드 A에 더 많은 메모리 부분이 존재한다면 노드 A가 idle 상태인지 태스크를 옮겨도 되는지 확인합니다. 만약 idle 상태가 아니라면 현재 A에서 수행중인 태스크 t가 a가 수행되는 노드 K에서 더 잘 수행될 수 있는지 확인합니다. 그리고 태스크 t를 노드 K로 옮기는게 이익이 되는지 확인해야 합니다. 

Task grouping

공유메모리를 사용하는 경우에 멀티테스크들은 대해 동일 메모리에 접근할 수 있습니다. 공유 메모리를 찾기위해 PID와 CPU번호를 사용하게 됩니다. NUMA task placement를 향상시키기 위해 NUMA fault가 발생했을 때 페이지가 마지막으로 Fault난 CPU를 확인하고 PID가 동일하다면 Task grouping으로 group으로 만듭니다. group은 연관된 태스크들로만 구성되어 있습니다. 이 group을 이용해 Task placement와 함께 Numa balancing을 향상시킵니다. 만약 태스크가 numa group에 속하고 다른 task가 이 numa_group으로 속하도록 한다면 효율적인 태스크 배치를 할 수 있습니다. 그림으로 나타내는 아래와 같습니다.

task grouping 전

Task grouping & Task placement 적용 후

태스크를 묶는 방법은 통계학적 정보를 이용합니다. 그룹 정보는 그룹 내 태스크들에 대한 NUMA fault의 합으로 정리되고 해당 Task가 그룹에 속하게 되면 태스크의 정보가 아닌 그룹의 정보를 사용하게 됩니다. 비교된 태스크가 동일 그룹에 속하게 되면 좀 더 효율적으로 그룹 내의 태스크 배치를 할 수 있게됩니다.

Pseudo-interleaving

가끔 하나의 워크로드가 여러 노드로 퍼져있는 경우가 있습니다. 로드밸런서에 의해 다른 노드에 분산된 경우도 이에 해당합니다. 이런 경우에 메모리 Bandwidth를 최대화 하고 태스크가 사용하는 Private 메모리를 유지하면서도 페이지 마이그레이션을 최소화 해야 합니다. 아래 그림을 보시면 하나의 워크로드가 여러 노드에 퍼져있는 경우의 그림입니다. 대부분의 태스크의 메모리는 첫 번째 노드에 위치하고 있는데 다른 노드에 위치한 태스크들이 접근을 함으로서 성능에 문제를 주는 경우 십니다.

그럼 어떻게 성능향상을 꾀할 수 있을까요? 메모리를 좀 더 효율적으로 노드별 분산을 시키면 좋을 것 같습니다. Pseudo-interleaving에서 사용하는 알고리즘은 다음과 같습니다. 페이지 마이그레이션을 위해 private fault를 항상 허용합니다. Shared Fault는 더 로드가 큰 노드에서 적은 노드로만 페이지 마이그레이션을 허용하게 됩니다. 이 말인즉 만약 Shared fault가 발생했을 때 로드가 큰 곳으로는 메모리 마이그레이션을 하지 않겠다는 의미입니다. 아래 그림을 참고하시죠.

페이지 마이그레이션을 이용하여 아래와 같이 만들어줍니다.

 지금까지 NUMA 시스템과 NUMA Balancing에 대해 간단히 정리해보았습니다. 더 자세한 정보와 추가적인 내용들은 아래 참고자료 링크들을 참고해주세요.

긴 글 읽어주셔서 감사합니다. :D

[참고자료]

http://www.linux-kvm.org/images/7/75/01x07b-NumaAutobalancing.pdf

https://ko.wikipedia.org/wiki/%EB%B6%88%EA%B7%A0%EC%9D%BC_%EA%B8%B0%EC%96%B5_%EC%9E%A5%EC%B9%98_%EC%A0%91%EA%B7%BC