[SPDK] Message Passing and Concurrency Theory

SPDK의 주요 목적중 하나는 하드웨어가 추가됨에 따른 linear scalability를 보장하는 것이다. 예를 들어 사용하는 SSD의 갯수가 1개에서 2개로 변할 경우 IOPS가 2배로 증가하고, CPU 코어의 갯수가 2배가 될 경우 연산 능력도 2배가 되고, NIC가 2배가 될 경우 네트워크 대역폭이 2배가 되는 등을 의미한다. 이러한 기능을 제공하기 위해서는 소프트웨어 내의 쓰레드(혹은 프로세스)가 최대한 서로 영향을 주지 않도록 설계되어야 한다. 일반적으로 소프트웨어 lock이나 atomic instruction까지 없는 경우를 말한다.

lock 접근제어

전통적으로 쓰레드간의 데이터 공유가 필요할 때에는 공유할 데이터를 힙에 저장하고 lock을 이용해서 접근 제어를 수행하도록 구현한다. 이러한 방식은 아래와 같은 장점이 있다.

• 싱글쓰레드 프로그램을 멀티 쓰레드 프로그램으로 바꿀 때에 매우 쉽다. 데이터 모델을 바꿀 필요가 없고, 단순히 lock 만 추가하면 되기 때문이다.
• 코드 순서 그대로 동작하는 synchronous 프로그램으로 구현할 수 있다.
• context switching을 허용하기 때문에 interrupt 등에 의해 OS가 프로세스 상태를 마음대로 바꾸고 스케쥴링 하도록 한다.

그러나 쓰레드의 개수가 점점 증가하게 되면 공유 데이터를 접근하는 데 사용하는 lock의 경합현상이 많이 발생하게 된다. lock의 단위를 더 잘게 쪼갤 경우 이를 완화 할 수 있으나, 프로그램의 복잡도 자체가 증가하게 된다. 또한, 일정 수 이상의 lock 경합이 발생하게 되면 대부분의 쓰레드가 단순히 lock 을 획득하는 것에 대부분의 CPU 시간을 소모하여 멀티 코어 CPU의 장점을 사용하지 못하게 된다.

메시지 패싱

SPDK는 이를 방지 하기 위해 다른 방식을 사용한다. 각 쓰레드가 자기가 사용하는 데이터를 저장하고, 다른 쓰레드는 데이터가 필요할 때 해당 쓰레드에게 메시지를 전달하고, 데이터를 가진 쓰레드가 해당 메시지를 처리하는 방식으로 동작한다. 이러한 메시지 패싱 전략은 Earlang 디자인이나 Go의 concurrency 전략에 사용되는 일반적인 방법이다. SPDK 내에서 사용되는 메시지는 데이터를 처리하기 위한 function pointer와 context를 지정하는 poniter로 이루어져 있는 게 일반적이다. 전달되는 메시지들은 lockless ring을 사용하여 저장된다. 메시지 패싱 전략은 메시지에 대한 캐싱 이펙트로 개발자들이 생각하는 것보다 훨씬 빠른 경우가 많다. 각 코어가 전담하는 데이터가 따로 있어서 어떤 자료를 접근할 때 하나의 코어에서만 접근함을 보장하는 경우, 거의 대부분의 시간동안 해당 코어의 캐시에 데이터가 캐싱되어 있음이 보장되기 때문이다. 이러한 특징을 이용하여, 각 코어는 자신이 하고 싶은 작업중 각 코어의 로컬 캐시에 캐싱되는 작은 세트의 데이터에 대해서만 가공을 수행하고, 가공된 결과를 통해 작은 크기의 메시지를 다음 코어에 전달하는 것이 가장 효율적인 방법이 될 수 있다.

메시지 패싱 자체도 너무 많은 코스트를 차지하는 극도로 성능이 중요한 경우에는, 메시지에 데이터를 담지 않고 각 쓰레드가 필요한 데이터의 카피를 가지고 있도록 한다. 이후 해당 데이터에 대한 변경이 필요할 경우 변경 작업을 수행하길 원하는 쓰레드가 데이터를 갖고 있는 쓰레드로 operation 메시지를 보내고, 메시지를 받은 쓰레드가 직접 변경을 수행하는 방식을 사용한다. 이러한 방식은 update가 자주 발생하지않는 환경에서 매우 유용하고, I/O path 가 주로 비슷한 상황이다. 물론 각 데이터의 카피를 저장하고 있어야 하므로 추가적인 메모리가 필요하기 때문에 성능이 매우 중요한 critical path에만 사용하는 것이 좋다.

Message Passing Infrastructure

SPDK는 여러 계층으로 나뉜 메시지 패싱 인프라스트럭처를 제공한다. 예를 들어 NVMe 드라이버와 같은 SPDK의 기초가 되는 라이브러리들은 직접 메시지 패싱을 사용하지 않고, 문서화를 통해 언제 해당 라이브러리가 제공하는 함수들을 호출할 수 있는지에 대한 규칙 정의만을 해놓았다. 그 외에 대부분의 라이브러리들은 SPDK의 쓰레드 추상화 레이어에 의존하고 libspdk_thread.a 에 구현되어 있다. 쓰레드 추상화는 기본적인 메시지 패싱 프레임워크를 제공하고 몇가지 주요 기본 요소들을 정의하고 있다

spdk_thread, spdk_poller, spdk_thread_create()

쓰레드 실행과 관련된 추상화는 spdk_thread 에 구현되어 있고, 실행된 쓰레드에서 주기적으로 실행되어야 하는 함수들을 정의 하는 추상화는 spdk_poller 에 구현되어 있다. SPDK를 사용하고자 하는 쓰레드들은 각각 개별적으로 [spdk_thread_create()](https://spdk.io/doc/thread_8h.html#a4eada7bac2a5c7ceaea891d57f8d3e21) 를 호출하여야 한다.

spdk_io_device spdk_io_channel

spdk_io_device와 [spdk_io_channel](https://spdk.io/doc/structspdk__io__channel.html) 로 정의된 추상화 레이어도 존재한다. 이들은 SPDK를 구현하면서 여러 라이브러리들에서 중복적으로 나타나는 패턴들을 정의한 레이어이다. 전역 상태 관리에 대한 lock을 피하면서 메시지 패싱을 구현하기 위해서는, SPDK 시스템의 전체 상태를 관리하는 전역 객체들의 global state와 함께 IO path에서 접근된 해당 객체들과 연관된 쓰레드 별 컨텍스트를 관리해야 했다. 이러한 패턴은 IO가 블록 디바이스로 요청되는 가장 낮은 레이어에서 가장 명확하게 드러났다. 타겟이 되는 디바이스들은 보통 쓰레드 별로 할당 되고 lock 없이 IO를 요청할 수 있는 다중 큐 (multi queue)를 제공한다. 이를 추상화 하기 위해 디바이스들을 spdk_io_device 로 일반화 하고 쓰레드 별 큐를 spdk_io_channel 로 일반화 하였다. 그러나, 라이브러리의 사이즈가 커지고 개발이 지속됨에 따라 초기 설계에 완벽히 들어 맞지 않는 패턴들이 생기기 시작했다. 이로인해 현재의 구현에서의 spdk_io_device는 해당 메모리 주소에서만 고유성이 보장되는 어떠한 pointer라도 될 수 있으며 (?), spdk_io_channel은 특정 spdk_io_device 와 연관된 쓰레드 별 컨텍스트이다.

이러한 쓰레드 추상화 레이어는 한 쓰레드에서 다른 어떤 쓰레드로든 메시지를 보내는 기능, 다른 모든 쓰레드에게 메시지를 차례로 보내는 기능, 주어진 io_device 에 맞는 io_channel을 보유한 모든 쓰레드에 메시지를 보내는 기능을 제공한다.

The event Framework

SPDK를 사용하는 예제 애플리케이션이 늘어남에 따라 각 코드들의 많은 부분이 spdk_thread_create() 를 호출하기 위한 기초적인 메시지 패싱 인프라를 구현하는데 사용됨을 발견하였다. 이 코드에는 코어당 하나의 쓰레드를 생성하고, 각 쓰레드를 특정 코어에 pinning하고, 메시지 패싱에 사용할 lockless ring을 각 쓰레드 별로 할 당하는 등의 작업을 포함한다. 이러한 기초적인 작업을 각 예제 애플리케이션 마다 구현하지 않도록 하기 위해 SPDK에 Event Framework 라이브러리를 구현하였다. 이 라이브러리는 메시지 패싱에 필요한 모든 인프라를 설정하고 온전한 종료를 위한 시그널 핸들러를 등록하고 위에서 언급한 periodic poller를 구현하고 애플리케이션의 커맨드 라인 옵션을 파싱하는데 필요한 기능들을 제공한다. [spdk_app_start()](https://spdk.io/doc/event_8h.html#ab4c22e2920f70becd9b2ef752efd7975) 를 통해 앱을 실행할 경우 이 라이브러리가 알아서 요청된 수만큼의 쓰레드를 생성하고, 피닝하고, 각 쓰레드 별로 spdk_thread_create() 를 호출한다. 이를 통해 SPDK를 사용하는 애플리케이션을 더욱 쉽게 구현할 수 있도록 하였다. 이미 충분한 메시지 패싱 인프라가 있는 기존의 응용 프로그램들은 직접 low level library를 통합해도 된다.

Limitation of the C language

메시지 패싱은 효율적이지만 비동기적 코드로 작성해야 한다는 점이 있다. C에서의 비동기 코드를 작성하는 것은 쉽지 않은 일로, 보통 비동기 작업의 종료 후에 호출될 callback 함수를 메시지와 함께 전달하는 방식으로 구현된다. 이러한 코드는 코드 분석이나 이해를 어렵게 만드는 문제가 있다. 가장 좋은 해결책은 future나 promise 와 같은 기능을 제공하는 c++, rust, go 등의 high level language를 사용하는 것이지만, SPDK는 low level library로 제공하면서 다양한 시스템에 대해 compatibility 와 portability를 제공해야 하므로 C로 구현하게 되었다.

C를 통해 메시지 패싱을 효율적으로 구현하기 위해서는 몇가지 권장 사항이 있다. 콜백 체인을 단순화 하기 위해서는 코드를 bottom to top 방식으로 작성하는게 좋다. 아래의 예제를 보자

void baz(void *ctx) {
     /* something */
}
void bar(void *ctx) {
    async_op(baz, ctx);
}
void foo(void* ctx) {
    async_op(bar, ctx);
}

foo 가장 먼저 비동기적으로 동작하고 이 함수가 완료되면 이후 bar 함수가 비동기적으로 수행되고 마지막으로 baz 함수가 수행되어야 하는 경우, 위와 같이 가장 먼저 수행되는 함수를 제일 밑에 작성하고 이후 점점 위에 코드를 작성하는 방식을 택할 경우, 향후의 코드 유지/보수가 매우 쉬워진다. 또한 각각의 함수 사이에는 어떠한 다른 코드들도 들어가지 않도록 깔끔하게 관리해야 한다.

논리 분기점에 따라 다른 코드가 수행되거나 loop가 있는 복잡한 콜백 체인에서는 state machine을 작성하는것이 좋다. 실제로 future와 promise를 제공하는 high level language들이 하는 일이 컴파일 타임에 state machine을 생성하는 것으로, C에서 해당 기능이 없다고 하더라도 똑같은 작업을 코드 작성을 통해 수행할 수 있다. 아래의 예제는 foo를 비동기적으로 5번 수행한 이후에 bar를 수행하도록 하는 코드이다.

enum states {
        FOO_START = 0,
        FOO_END,
        BAR_START,
        BAR_END
};

struct state_machine {
        enum states state;

        int count;
};

static void
foo_complete(void *ctx)
{
    struct state_machine *sm = ctx;

    sm->state = FOO_END;
    run_state_machine(sm);
}

static void
foo(struct state_machine *sm)
{
    do_async_op(foo_complete, sm);
}

static void
bar_complete(void *ctx)
{
    struct state_machine *sm = ctx;

    sm->state = BAR_END;
    run_state_machine(sm);
}

static void
bar(struct state_machine *sm)
{
    do_async_op(bar_complete, sm);
}

static void
run_state_machine(struct state_machine *sm)
{
    enum states prev_state;

    do {
        prev_state = sm->state;

        switch (sm->state) {
            case FOO_START:
                foo(sm);
                break;
            case FOO_END:
                /* This is the loop condition */
                if (sm->count++ < 5) {
                    sm->state = FOO_START;
                } else {
                    sm->state = BAR_START;
                }
                break;
            case BAR_START:
                bar(sm);
                break;
            case BAR_END:
                break;
        }
    } while (prev_state != sm->state);
}

void do_async_for(void)
{
        struct state_machine *sm;

        sm = malloc(sizeof(*sm));
        sm->state = FOO_START;
        sm->count = 0;

        run_state_machine(sm);
}

do_async_for() 를 실행하면 FOO_START로 상태가 초기화 되고 run_state_machine 을 통해 state machine이 동작하게 된다. 이후 foo 를 통해 첫 async foo 가 등록되고 해당 작업이 끝나면 foo_complete 콜백을 통해 다시 state machine을 실행한다. 이 때의 state는 FOO_END로 switch 문을 통해 count가 1 증가하며 다시 async foo를 등록하게 된다. foo가 5번 수행될 때까지 이 과정이 반복 되고, 이후 BAR_START state로 변경되어 bar 수행되고 프로그램은 최종적으로 종료되게 된다. 이러한 동작은 future 나 promise 를 통해 비동기 큐에 비동기 작업들을 입력하고 차례로 비동기 작업들을 수행하는 다른 언어들과 동일한 방식이다.