[Disruptor] 4. Single Writer Principle과 Wait Strategy: 동시성 제어와 대기 전략의 트레이드오프

 

지난 글에서 CAS와 Memory Barrier를 통해 운영체제의 개입 없이도 안전하게 데이터를 쓰고 메모리 가시성을 확보하는 방법을 알아보았다.

 

[Disruptor] 3. Lock-Free Mechanism: 동시성의 역설, 왜 Lock을 쓰면 느릴까?

[Disruptor] 3. Lock-Free Mechanism: 동시성의 역설, 왜 Lock을 쓰면 느릴까?

 

하지만 아무리 CPU의 원자적인 연산을 사용한다 해도 수많은 스레드가 동시에 같은 데이터에 접근하면 결국에는 경합이 발생하고 성능은 느려지기 마련이다.

 

LMAX의 Disruptor는 설계 단계에서부터 스레드간의 경합 상황을 원천적으로 차단하고 Producer와 Consumer가 문제 없이 제 할일을 하도록 하였다.

 

LMAX는 어떤 방법을 사용하여 처리하였는지 알아보자.

 

1. Single Writer Principle

멀티 스레드 환경에서 가장 큰 문제는 여러 스레드가 동시에 한 변수를 수정하려 할 때이다.

 

Disruptor는 이러한 경합 문제를 Single Writer Principle, 즉 단일 쓰기 원칙을 사용하여 해결하였다.

 

Producer가 여러개일지라도 특정 이벤트 슬롯에 최종적으로 데이터를 기록하는 주체를 철저히 단일화 하였다.

 

예를 들어 보자.

 

A, B 스레드가 동시에 데이터를 쓰려는 상황이다.

 

여러 Producer가 동시에 데이터를 쓰려고 접근하면 이전 글에서 다루었던 CAS 연산을 통해 링버퍼의 다음 빈자리(Sequcne)를 먼저 예약한다.

 

• A스레드가 CAS 연산으로 1번 인덱스를 점유
• B스레드는 근소한 차이로 밀려 2번 인덱스를 점유

각 스레드별로 값을 채워넣은 자리를 할당받게 되면 1번 인덱스의 Event 객체에 데이터를 채워 넣는 작업은 오직 A스레드 혼자서만 수행하게 된다.

 

// CAS 연산을 통해 데이터를 채워넣을 빈자리를 할당받음
// 여러 스레드가 동시에 접근해도 원자적으로 고유한 번호를 발급받음 (이전글 참고)
long sequence = ringBuffer.next(); 

try {
    // 할당받은 시퀀스에 해당하는 미리 할당된 빈 객체를 가져옴
    // 이 event 객체의 쓰기 권한은 현재 A스레드가 완벽히 독점한다
    TradeEvent event = ringBuffer.get(sequence);

    // 락 없이 안전하게 데이터를 채워 넣음 (Single Writer)
    event.setPrice(50000);
    event.setSymbol("BTC");
    event.setQuantity(1.5);
} finally {
    ringBuffer.publish(sequence);
}

 

synchronized나 lock과 같은 키워드는 보이지 않는다.

 

즉, ringBuffer.next()를 통해 CPU레벨의 원자적 연산인 CAS가 발생하여 호출한 스레드별로 고유한 슬롯을 할당하며 이를 통해 스레드별로 경합 없이 데이터를 쓸 수 있는 것이다.

 

A스레드가 1번 슬롯을 할당받았다면 ringBuffer.get(1)을 통해 꺼내온 객체는 링버퍼가 한바퀴를 다시 돌아 덮어쓰기 전까지 오롯이 A스레드의 소유다.

 

다른 어떤 스레드도 1번 슬롯에 데이터를 쓰고 있지 않다는 것이 100% 보장된다.

 

결국 특정 메모리 공간에 데이터를 쓰는 주체는 단 하나뿐이므로(A스레드) 복잡한 동기화 블록을 걸고 지지고 볶을 필요가 원천적으로 사라진다.

 

이것이 바로 Single Writer Principle이다.

 

'공유 자원에 대한 쓰기 경합'이라는 멀티스레드 프로그래밍의 가장 큰 난제를, '쓰기 권한 자체를 쪼개서 독점하게 만드는' 기발한 아키텍처로 우회해 버린 것이다.

 

경합 자체를 없애버렸으니 당연히 빠를 수밖에 없다.

 

 

2. Producer와 Consumer의 속도 조절: Sequence Barrier

 

링버퍼에 할당된 공간은 한정되어있다.

 

이 한정된 공간 안에서 Producer는 새로운 데이터를 쓰며 나아가고, Consumer는 해당 데이터를 처리하며 Producer를 쫓아간다.

 

여기서 드는 한가지 의문.

 

Consumer가 Producer보다 처리 속도가 빨라서 Producer를 앞질러가면 어떻게 될까?

 

 

Consumer가 Producer를 앞질러가게되면 데이터 정합성에 문제가 생기게 된다.

 

있지도 않은 데이터에 접근하여 해당 데이터를 null과 같은 형태로 처리해버리면 이는 비즈니스에 문제를 일으키기 마련이다.

 

일반적인 링버퍼에는 버퍼가 꽉 차면 에러를 던지거나 그냥 덮어씌워버리지만 Disruptor는 Sequencer와 SequenceBarrier라는 핵심 객체로 아래의 규칙을 강제해두었다.

 

• Consumer가 Producer 앞지르기 금지 (Garbage Read 방지)
  • Consumer의 처리 속도가 너무 빨라서 아직 Producer가 쓰지도 않은 빈 공간을 읽어버리면 안됨
• Producer의 데이터 덮어쓰기 금지 (Overwrite 방지)
  • Producer의 처리 속도가 너무 빨라서 아직 Consumer가 읽지도 않는 데이터를 덮어씌워버리면 안됨

 

Consumer가 Producer 앞지르기 금지 (Garbage Read 방지)

 

Consumer는 링버퍼에서 데이터를 읽어오기 전에 SequenceBarrier에게 특정 슬롯에서 시퀀스를 읽어와도 되는지 체크한다.

 

이때 SequenceBarrier는 Consumer의 커서와 비교하여 앞지르기를 차단한다.

 

예를 들면 아래와 같다.

 

• 굉장히 빠른 Producer가 존재하여 10번 슬롯까지 데이터를 다 채움
• Consumer는 10번 슬롯을 읽어올 차례
• Consumer가 SequenceBarrier에 10번 슬롯을 읽어도 되는지 확인
• Consumer가 SequenceBarrier에 10번 슬롯을 읽어도 되는지 확인할 동안 Producer는 15번 슬롯까지 데이터를 채움
• SequenceBarrier는 단순히 10번을 읽으라 응답하지 않고 현재 슬롯을 확인하여 Producer가 15번 슬롯까지 데이터를 채운 것을 확인
• SequenceBarrier는 Consumer에게 Producer가 데이터를 채운 최고 시퀀스인 15번을 응답
• Consumer는 SequenceBarrier에게 확인 요청했던 10번 슬롯까지만 읽는 것이 아닌 최고 시퀀스인 15번을 응답받아 15번까지 데이터를 읽어서 처리

최고 시퀀스는 Consumer가 안전하게 한 번에 배치처리할 수 있는 최대 허용 범위를 의미한다.

 

아래는 SequenceBarrier의 샘플 코드이다.

// ProcessingSequenceBarrier.java의 waitFor() 메서드
public long waitFor(final long sequence) throws AlertException, InterruptedException, TimeoutException {
    
    // waitStrategy를 통해 Producer의 커서가 
    // Consumer가 원하는 sequence에 도달할 때까지 대기
    long availableSequence = waitStrategy.waitFor(sequence, cursorSequence, dependentSequence, this);

    // 만약 Producer가 아직 거기까지 안 썼다면 (에러나 인터럽트 상황)
    if (availableSequence < sequence) {
        return availableSequence; // 앞지르지 못하고 돌아감
    }

    // Producer가 이미 데이터를 썼음이 확인되면, 안전하게 읽을 수 있는 최고 시퀀스 반환
    return sequencer.getHighestPublishedSequence(sequence, availableSequence);
}

 

 

만약 SequenceBarrier가 Consumer에게 요청한 10번 슬롯만 읽으라고 하였다면 Consumer는 10번 슬롯을 처리하고 나서 11번 슬롯에 대한 데이터 읽기 가능 여부를 확인했을 것이다.

 

SequenceBarrier를 사용하여 데이터를 처리해도 되는지 매번 묻는 것은 굉장한 오버헤드가 될 수 있다.

 

즉 SequenceBarrier의 최고 시퀀스 반환을 통해 Consumer는 배치처리가 가능해지며 이런 일괄 처리 메커니즘 덕분에 상태 검사 비용이 극단적으로 줄어들고, 초당 수백만 건의 처리가 가능해지는 것이다.

 

 

Producer의 데이터 덮어쓰기 금지 (Overwrite 방지)

Producer의 처리 속도가 너무 빨라서 Consumer가 아직 읽지 못한 슬롯에 데이터를 덮어씌워버릴 수 있다.

 

Producer가 데이터를 쓰기 위해선 ringBuffer.next()를 통해 데이터를 쓸 자리를 먼저 예약해야 한다.

 

Disruptor는 Producer가 데이터를 쓰고자 하는 다음 슬롯이 Producer가 빠르게 링버퍼를 한바퀴 돌아서 가장 느린 Consumer가 해당 슬롯에서 데이터를 읽지 못하게 할 수 있는지 여부를 체크한다.

 

마찬가지로 예를 들어보자.

 

• 크기가 1024인 링버퍼가 있음
• Producer가 링버퍼에 데이터를 다 채우고 한바퀴 돌아서 1025번째 슬롯에 데이터를 할당하기 위해 해당 슬롯에 데이터를 써도 되는지 확인 요청
  • 1025번째는 1025%1024 = 1, 즉 1번째 슬롯(과거의 데이터)에 데이터를 Overwrite 해도 되는지 확인
• Disruptor는 덮어쓸 슬롯의 번호를 계산 (wrapPoint)
  • wrapPoint = nextSequence - bufferSize
  • 1025 - 1024 = 1
• Disruptor는 wrapPoint에 있는 데이터는 Consumer가 읽어갔으니 덮어씌워도 되는지 판단
• 데이터를 덮어씌워도 되는지는 가장 느린 Consumer의 위치인 gatingSequence를 확인
  • 가장 느린 Consumer가 0번 슬롯을 처리중인 경우 => wrapPoint(1) > gatingSequence(0)
    • Consumer가 아직 1번 슬롯을 처리하지 않았기 때문에 충돌 발생
  • 가장 느린 Consumer가 3번 슬롯을 처리중인 경우 => wrapPoint(1) < gatingSequence(3)
    • Consumer는 이미 1번을 처리했기 때문에 Producer는 1번 슬롯에 데이터를 쓸 수 있음

 

위와 같이 처리된다.

 

wrapPoint가 gatingSequence보다 앞선 경우 충돌이 발생한다했는데 이때 Disruptor는 어떻게 동작할까?

 

예외를 던지고 종료될까?

 

그렇지 않다.

 

Back Pressure를 통해 강제 대기를 하게 된다.

 

Back Pressure는 유체의 흐름이나 데이터 처리 등에서 원래 흐름과 반대 방향으로 작용하는 저항력을 의미한다.

 

일반적으로 Producer의 처리 속도가 빨라서 Consumer가 데이터를 처리하지 못하고 쌓이는 상태를 말한다.

 

Producer는 Consumer가 데이터를 다 처리하여 minSequence가 wrapPoint보다 커질때까지 while루프에 갇히게 된다.

 

시스템 부하가 심해서 Consumer의 처리가 늦어져서 링버퍼가 꽉 차게 되면 Producer의 속도를 물리적으로 늦추게 하여 시스템 전체가 스스로 속도를 조절할 수 있도록 처리한다.

 

아래는 샘플 코드이다.

 

// SingleProducerSequencer.java의 next() 메서드
long nextSequence = currentSequence + 1;
// wrapPoint: 내가 가려는 위치에서 버퍼 크기 한 바퀴를 뺀 값 (즉, 내가 덮어쓸 자리의 시퀀스)
long wrapPoint = nextSequence - bufferSize; 

// gatingSequences: 현재 이 링버퍼를 바라보고 있는 Consumer들의 시퀀스 목록
// cachedGatingSequence: 가장 느린 Consumer가 현재 처리 중인 시퀀스 번호
long cachedGatingSequence = this.cachedValue;

// 만약 내가 덮어쓸 자리(wrapPoint)가 가장 느린 Consumer의 위치보다 앞서 있다면?
// -> Consumer가 아직 읽지 않은 데이터 (덮어쓰기 위험 발생)
if (wrapPoint > cachedGatingSequence) {
    long minSequence;
    
    // Consumer가 데이터를 읽고 나서(minSequence가 wrapPoint 이상이 될 때까지) 무한 대기
    while (wrapPoint > (minSequence = Util.getMinimumSequence(gatingSequences, currentSequence))) {
        // 잠시 대기 (Back-pressure, 배압 발생)
        LockSupport.parkNanos(1); 
    }
    this.cachedValue = minSequence;
}

this.nextValue = nextSequence;
return nextSequence; // 비로소 안전한 다음 슬롯 발급

 

이를 통해 데이터의 Overwrite 막을 수 있다.

 

 

 

3. Wait Strategy: 레이턴시와 CPU의 등가교환

여기서 한 가지 의문이 생긴다.

 

Consumer가 처리할 새 데이터가 없어서 기다려야 할 때, 또는 Producer가 버퍼가 비워지기를 기다려야 할 때 도대체 어떻게 기다릴 것인가?

 

이미 이전 글에서 스레드를 잠재우고 깨우는 행위(Context Switching)가 얼마나 많은 오버헤드를 발생시키는지 확인했다.

 

Disruptor는 기다리는 방식조차 비즈니스 요구사항에 맞춰 선택할 수 있도록 여러 가지 대기 전략을 제공한다.

 

세상에 공짜는 없듯이 아래 표를 보면 레이턴시와 CPU점유율 사이의 Trade-Off 관계를 확인할 수 있다.

 

전략	CPU 점유율	레이턴시	동작원리 및 특징
BlockingWaitStrategy	매우 낮음	높음(느림)	- 내부적으로 락과 Condition변수를 사용 - 일반적인 BlockingQueue와 비슷하며 CPU자원을 아껴야 하는 상황에서 사용
YieldingWaitStrategy	높음	낮음(빠름)	- 대기할때 스레드를 sleep하지 않고 Thread.yield()를 호출하여 다른 스레드에게 실행을 양보 - 논리적 코어가 충분하고 빠른 응답이 필요할때 적합
BusySpinWaitStrategy	100%(코어 1개 독점)	최저(가장 빠름)	- 대기 상태 없이 무한 루프를 돌며 시퀀스 변화를 감시 - 초단타 매매(HFT)처럼 나노초 단위의 지연조차 허용할 수 없는 극한의 환경에서 사용

 

만약 0.1초의 지연도 허용할 수 없는 암호화폐 거래소의 체결 엔진을 만든다면 어떨까?

 

스레드가 잠들었다 깨어나는 수 밀리세컨드의 시간조차 아깝기 때문에 CPU 코어 하나를 100% 할당하면서(BusySpin) 데이터가 들어오자마자 처리하도록 설계해야 할 것이다.

 

반대로 일반적인 백엔드 시스템에서 이런 전략을 썼다가는 다른 API를 처리해야 할 CPU 자원이 부족하여 서버가 뻗어버릴 수도 있다.

 

결국 아키텍처에서 최고의 성능은 하드웨어 자원을 얼마나 대가로 지불할 것인가에 달려있다.

 

---

 

 

경합을 원천 차단하는 단일 쓰기 원칙과, CPU를 과감히 내어주고 레이턴시를 챙기는 대기 전략을 살펴보았다.

 

이를 통해 LMAX가 초저지연이라는 목표를 달성하기 위해 하드웨어 특성을 어떻게 소프트웨어 설계에 반영했는지 그 치열한 고민을 엿볼 수 있었다.

 

하지만 아무리 압도적인 퍼포먼스를 내는 기술이라도 모든 아키텍처에 통용되는 정답은 아니며, 결국 우리가 얻고자 하는 성능의 이면에는 반드시 지불해야 할 대가가 존재한다.

 

극단적인 속도를 위해 시스템의 복잡성을 감수하고 CPU 자원을 100% 불태울 것인가, 아니면 보편적인 큐(Queue)를 사용하여 적당한 타협점 속에서 유지보수의 안정성을 챙길 것인가.

 

최고의 아키텍처란 단순히 세상에서 가장 빠른 기술을 가져다 쓰는 것이 아니다.

 

현재 당면한 비즈니스 요구사항과 인프라 제약 속에서 가장 합리적인 트레이드오프를 찾아내는 것.

 

기술의 화려함에 맹목적으로 매몰되지 않고 그 이면의 비용을 냉정하게 따져보는 시각이야말로, 하드웨어의 한계까지 파고들었던 LMAX 엔지니어들에게서 우리가 진짜 배워야 할 엔지니어링의 자세일 것이다.