[Concurrency] Software Transactional Memory (Beautiful concurrency)

 

1. 서론

---

작년엔 동시성 문제에 synchronized, 비관적 락, 낙관적 락에 대해서만 알았다가 최근에 CAS 알고리즘에 대해 알게 되었다. 이걸 기점으로 Lock-Free에 대해 더 공부하고 있다가 STM을 발견했다.

 

이번에 중점적으로 참고한 내용은 2007년 마이크로소프트에서 Simon Peyton Jones라는 사람이 발표한 논문이다. 내용은 Haskell 언어를 통해 어떻게 효율적인 STM을 구현할 수 있는지에 대한 내용이다.(https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/beautiful.pdf)

 

검색해보니 STM이라는 개념은 90년대에 있었지만, 2005년부터 인텔과 암드 주도하에 싱글 프로세스에서 멀티 프로세스로 넘어가는게 대중화되며 본격적으로 사용되기 시작한 것 같다. STM 개념 자체는 90년대에 나왔지만, Haskell 언어에서 처음으로 코드로 구현된 키워드이다. 특히 Simon Peyton Jones라는 분이 하스켈 언어를 만든 사람중에 한 명으로 Beautiful concurrency를 통해 어떻게 이론적인 STM을 단순하고 아름답게 코드로 구현할 수 있는지 논문을 통해 파급력이 커졌다고 한다.

---

 

 

 

2. Compare and Swap의 한계점

---

[Compare and Swap의 한계점]

가장 먼저 이야기 해볼 내용은 이전 포스팅에서 다룬 Compare and Swap의 한계점이다.

Compare and Swap 기술 자체가 나쁘다는 이야기로의 한계점이 아니고, 기술적인 한계점이 존재한다.

이전 포스팅에서 다룬 Java의 compareAndSet 메서드를 보면 알 수 있듯이 단일값만 원자성을 보장해준다는 것이다. 여러 개의 값을 한 번에 보장하기 위해서는 Multi Compare and Swap (MCAS), Double Compare and Swap (DCAS) 기술이 필요한데, 하드웨어적으로 구현하기 굉장히 힘들다고 한다.

참고로 인텔에서는 CMPXCHG8B, CMPXCHG16B 라는 DCAS 명령어를 지원하고 있지만, 암드는 구현되지 않은 것으로 보인다.

 

[Hardware Transactional Memory]

이후 나온 것이 Hardware Transactional Memory (HTM) / Software Transactional Memory (STM) 인데, HTM은 인텔에서 적용했었지만 논란이 많았다.

인텔에서 하스웰부터 TSX라는 HTM 기술을 구현한 기술을 상용화했지만, 이후 2021년부터는 버그와 취약점으로 인해 비활성화된 상태이다. 마찬가지로 암드도 HTM 기술에 대해 언급했지만, 인텔 TSX에서 문제가 펑펑 터지는걸 보고 상용화를 안한 것 같다.

---

 

 

 

3. Software Transactional Memory

---

STM은 2000년대 초반에 멀티 코어 시대로 넘어가면서 성능 향상을 위해 병렬 프로그래밍이 필수적인 시대에 들어오면서 발전하게 됐다.

 

위에 언급한 HTM과 지금 나오는 STM 모두 Transactional이라는 키워드를 가진다.

말 그대로 데이터베이스의 트랜잭션 개념을 가져와 여러 개의 작업을 하나의 작업으로 만들어 트랜잭션의 특징을 보장하는 기술이다.

참고로 아래 내용을 보면 MySQL InnoDB의 MVCC 기술과 굉장히 비슷하다.

 

ZIO 공식 문서에서 잘 설명이 되어있어서 내용을 가져왔다.

 

[트랜잭션 시작]

트랜잭션을 반영하기 위해 로그를 저장하는 임시 공간을 생성한다.

 

[트랜잭션 실행]

트랜잭션 연산시 원본 데이터에 영향을 주지 않고, 임시 공간에 있는 데이터를 변경한다.

트랜잭션이 끝나야 원본 데이터에 반영하므로 격리성을 보장하게 된다.

 

[트랜잭션 커밋]

수정하려는 데이터가 트랜잭션 실행 중간에 바뀐 적이 있는지 확인한다.

바뀐게 없으면 원자적 연산을 수행하지만, 바뀐게 있으면 처음부터 다시 재시작한다.

메모리 저장 속도를 생각하면 눈 깜짝할 사이에 값 교환이 일어나기 때문에 원자적으로 이루어진다.

 

이 방법을 통해 ACID의 A, C, I를 보장할 수 있게 된다.

• 원자성: 원자적 연산을 수행하므로 당연히 원자성 보장
• 일관성: 트랜잭션 반영 중간에도 읽기 작업을 요청하면 동일한 값을 얻을 수 있으므로 일관성 보장
• 고립성: 임시 공간에서 데이터를 변경하므로 다른 트랜잭션에 대해 생각할 필요가 없음

---

 

 

 

 

 

3. 락 기반 프로그래밍 예제

---

 

Beautiful Concurrency에서는 먼저 락 기반 프로그래밍 예제를 들어서 락을 걸었을 때의 문제점을 알려준다.

자바에서 synchronized가 락을 거는 키워드이니 해당 키워드를 적용해 객체를 만든다.

 

[객체 선언]

class Account {
    Int balance;
    synchronized void withdraw(int n) {
        balance = balance - n;
    }
    void deposit(int n) {
        withdraw(-n);
    }
}

 

[1. 이체 메서드 구현]

void transfer(Account from, Account to, Int amount) {
    from.withdraw(amount);
    to.deposit(amount);
}

 

여기서 withdraw와 deposit 메서드 모두 synchronized 키워드가 적용되어 있지만, transfer 메서드에서는 문제가 있다.

from.withdraw(amount)와 to.deposit(amount) 사이에 다른 스레드가 중간에 실행될 수 있다는 점이다.

그래서 다른 스레드가 중간에 들어올 수 있는 상황을 방지하기 위해 코드를 수정한다.

 

[2. 개선된 이체 메서드 구현]

void transfer( Account from, Account to, Int amount ) {
		from.lock(); to.lock();
		from.withdraw( amount );
		to.deposit( amount );
		from.unlock(); to.unlock(); 
}

 

이제 계좌 2개에 락을 걸었으니 다른 스레드가 중간에 실행되는 상황이 벌어지지는 않는다. 하지만 여기서는 데드락 문제가 발생하게 된다.

만약 from → to로 이체하는 스레드 1과 to → from으로 이체하는 스레드 2가 동시에 수행된다면 스레드 1은 from 계좌의 락을 얻고, 스레드 2는 to 계좌의 락을 획득한다. 그러면 스레드 1은 to 계좌의 락을 획득하기 위해 무한정 기다리게 되고, 스레드 2도 마찬가지로 from 계좌의 락을 획득하기 위해 무한정 기다리는 데드락이 발생한다.

이 문제를 해결하기 위해서는 락을 거는 규칙을 정해야한다.

 

[3. 데드락을 피하는 개선된 이체 메서드 구현]

if (from < to) {
    from.lock();
    to.lock();
} else {
    to.lock();
    from.lock();
}

 

여기서 from, to 계좌의 락을 거는 방식은 계좌 금액이 될 수도 있고, 계좌 번호의 id가 될 수도 있다.

어찌됐든 락을 획득하는 순서를 정했으므로 데드락을 회피할 수 있게 된다.

하지만... 2개의 계좌를 통해 연산하는 상황에서야 위 코드를 구현할 수 있지만, 다른 상황에서는 굉장히 복잡해진다.

예를 들어서 국민은행 계좌1에 돈이 부족하면 국민은행 계좌2에서 돈을 가져와 자동으로 결제한다거나, 토스의 후불계좌처럼 후불계좌 + 원래 계좌로 분할 납부를 하게 되는 상황말이다. 이러면 락을 획득하는 상황도 복잡해지고, 전체적으로 코드 복잡성이 증가하게 된다.

 

이처럼 락은 사용자가 잘 설계해야하고, 새로운 업데이트가 생기면 다시 재설계를 해야하는 상황이 존재한다.

특히 해당 논문이 나온 시기는 락 기반 프로그래밍을 모듈화하기 힘들어서 락 획득, 락 해제 코드를 모두 노출해야한다는 단점이 존재했다.

---

 

 

 

4. Haskell에서의 STM

---

프로그래밍 언어로 STM이 구현된 것은 하스켈이 처음이었고, 하스켈을 기점으로 다양한 프로그래밍 언어나 프레임워크에 STM이 구현되기 시작했다.

 

[atomically]

먼저 하스켈 메서드에 대해 이해가 필요한데, 자바로 치환한 코드랑 비교하면 간단하다.

[하스켈 메서드]
transfer :: Account -> Account -> Int -> IO ()
-- from에서 to로 amount를 이체함
transfer from to amount
= atomically (do { deposit to amount
								 : withdraw from amount})

[자바 메서드]
void transfer(Account from, Account to, Int amount) {
    (내부로직..)
}

 

Account -> Account -> Int는 메서드 파라미터의 타입을 의미하고, IO ()는 반환값인데 ()이므로 void이다.

여기서 atomically 키워드가 있는데, 이게 STM을 적용한 키워드이다. atomically는 원자성을 보장해 내부 블록의 업데이트가 다른 스레드에게는 한 번에 연산된 것처럼 보이고, 고립성을 보장해서 다른 스레드에게 영향을 받지 않는다.

 

[STM(), TVar]

이를 통해 withdraw, deposit 메서드를 만들었다.

type Account = TVar Int
withdraw :: Account -> Int -> STM ()
withdraw acc amount
= do { bal <- readTVar acc
     ; writeTVar acc (bal - amount) }

deposit :: Account -> Int -> STM ()
deposit acc amount = withdraw acc (-amount)

 

• TVar의 T는 Transactional로 외부에서 읽거나, 쓰는 것을 방지해준다.
• STM()은 원자적 연산을 수행하게 해준다.

지금까지 atomically, STM, TVar를 제공한다고 나와있지만, 이 세가지는 기초이고, 이것만 제공하기에는 온전한 병렬 프로그래밍이 불가능하다.

그래서 하스켈에서는 추가적으로 blocking과 choice 기술을 추가했다.

 

---

 

[blocking - retry, check]

limitedWithdraw :: Account -> Int -> STM ()
limitedWithdraw acc amount
= do { bal <- readTVar acc;
       if amount > 0 && amount > bal
       then retry
       else writeTVar acc (bal - amount) }

 

하스켈에서는 retry 단일 함수를 사용해서 현재 트랜잭션은 포기하고, 다시 연산을 시도하게 된다.

이때 바로 연산하는건 오버헤드만 커질 가능성이 높으므로 하스켈 내부에서 다른 스레드가 쓸 때까지 기다리도록 블로킹을 한다.

 

limitedWithdraw :: Account -> Int -> STM ()
limitedWithdraw acc amount
= do { bal <- readTVar acc
     ; check (amount <= 0 || amount <= bal)
     ; writeTVar acc (bal - amount) }

 

같은 코드이지만 여기서는 check가 사용됐다. retry를 직접적으로 사용하는건 구현 복잡도를 높이게 할 수 있으므로 check(...)를 통해 check(...) == False이면 retry를 호출하도록 만들었다.

 

[choice - orElse]

limitedWithdraw2 :: Account -> Account -> Int -> STM ()
-- acc1에서 돈을 인출하는 상황
-- 만약, acc1에 돈이 없으면 acc2에서 돈을 인출함
-- 만약, acc1과 acc2 둘 다 돈이 없으면 재시도를 수행함
limitedWithdraw2 acc1 acc2 amt
= orElse (limitedWithdraw acc1 amt) (limitedWithdraw acc2 amt)

 

retry와 check는 현재 조건에 부합하면 실행하거나, 재시도하는 로직만 존재하게 된다. 제3의 방법 없이 이지선다인 것이다.

그래서 orElse라는 액션을 추가해서 행동1, 행동2, 재시도라는 3가지 선택상황을 구현할 수 있게 됐다.

이를 통해 다양한 상황에서도 간단한 코드, 다양한 동작을 사용할 수 있어 개발자가 잘 사용할 수 있게 만들었다.

 

* 지금까지보면 retry는 무한 재시도가 가능한 것으로 보이지만, Haskell 공식문서를 보면 exponential backoff와 limit를 설정할 수 있다. (링크)

---

 

 

5. 결론

---

Haskell 에서는 lock과 conditional variable을 통해 프로그래밍을 하는 것보다 위 방법을 통해 모듈화된 방식으로 프로그래밍을 작성하는 방법에 대해 보여준다. STM을 적용해 락 기반 병렬 프로그래밍에서 발견되는 락 문제를 완전히 피할 수 있다고 한다.

 

다만 단점이라면 Compare and Swap과 같이 재시도를 해야하기 때문에 오버헤드가 커질 수 밖에 없긴하지만, 락을 획득하는 비용보다는 굉장히 성능 향상이 크기 때문에 오늘 날의 프레임워크, 프로그래밍 언어도 Lock-Free 방식을 채택했다.

 

Lock-Free 방식이 얼마나 좋냐면 2014 넥슨 개발자 컨퍼런스에서 한 분이 데스크탑으로 MMORPG를 만들어 성능 테스트를 해봤다고 한다. 이때 Lock-Free 자료구조를 사용하지 않으면 동접자 3000명이 한계이고, Lock-Free 자료구조를 사용하면 동접자 8000명까지 가능하다고 한다. 성능이 2.6배 정도 향상됐다는 것이다. 

 

특히 게임쪽은 동시성 문제가 민감하기 때문에 관련된 자료들이 있으니 참고하기 좋아보인다.

 

* Beautiful concurrency - https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/beautiful.pdf

---