연관 챕터

10

조사 내용

이 주제가 등장하기까지의 책의 흐름

처리율 제한 장치를 어디에 둘 것인가?
처리율 제한 알고리즘 소개
단일 서버의 처리율 제한 장치
분산 환경에서의 처리율 제한 장치

“분산 환경에서의 처리율 제한 장치” 라는 주제에서, 레이스 컨디션과 동기화 문제가 제시되었다.

동기화 문제에 대한 방안으로 중앙 집중형 캐시 서버가 제안되었고, 이렇게 여러 클라이언트(여기서는 처리율 제한 장치)가 공유하는 데이터는 레이스 컨디션을 고려하지 않을 수 없다.

단일 머신에서 이용할 수 있는 세마포어, 뮤텍스와 같은 Lock부터 시작해서, 레디스에서는 어떤 방식으로 레이스 컨디션을 극복하는지, 분산 환경에서의 레이스 컨디션은 어떻게 극복하는지에 대해 살펴보았다.

락 (Lock)

세마포어 vs 뮤텍스

출처 : https://prepinsta.com/operating-systems/mutex-vs-semaphore/

세마포어는 파일시스템 내 어딘가에 보관 & 이용되며, 여러 프로세스에서 공유되는 열쇠

뮤텍스는 프로그램 실행 시 해당 프로그램 내에서만 공유되는 열쇠

세마포어는 하나의 크리티컬 섹션에 여러 쓰레드 혹은 프로세스가 들어갈 수 있다.

뮤텍스는 하나의 크리티컬 섹션에 단 하나의 쓰레드만 들어갈 수 있다.

세마포어는 보통 양의 정수값을 갖는 변수를 컨트롤하는 방식이다. 즉, 이 변수의 초기값을 1로 설정해 두면, 뮤텍스와 동일한 기능을 수행한다.

뮤텍스는 크리티컬 섹션에 들어가는 쓰레드가 뮤텍스 객체의 “소유권”을 갖고, 이 소유권이 없는 쓰레드는 크리티컬 섹션에 들어갈 수 없다. 즉, 뮤텍스는 세마포어처럼 동작할 수 없다.

Optimistic Lock vs Pessimistic Lock

출처 : https://enterprisecraftsmanship.com/posts/optimistic-locking-automatic-retry/

어떤 공유 리소스에 대해 lock을 거는 매커니즘은 크게 optimistic, pessimistic으로 나뉜다.

optimistic lock
- 충돌이 일어나지 않을 거라 가정하고, 락을 걸지 않은 채 공유 리소스에 접근하는 락 매커니즘
- Redis의 WATCH, JPA의 Optimistic lock (@Version)
- 일단 트랜잭션을 진행하고 커밋하기 직전에 공유 리소스의 변경 여부를 살피기 때문에, 충돌이 잦지 않은 상황에서 사용하는 것이 권장된다.
  
  한 번 충돌이 발생하면, 트랜잭션을 롤백하거나 재시도 해야하는 비싼 대가를 치뤄야 한다.
pessimistic lock
- 충돌이 반드시 일어날거라 가정하고, 일단 락을 걸어둔 채 공유 리소스에 접근하는 락 매커니즘
- 세마포어, 뮤텍스, 대부분의 RDB
- 여러 클라이언트들의 접근으로 인해 동시에 변화가 생길 때, 그 변화들을 적절히 병합하는 과정의 비용이 클 때 권장되는 방법이다.

Redis - 정렬 집합 (Sorted Set)

출처 : https://jupiny.com/2020/03/28/redis-sorted-set/

Sorted Set 혹은 ZSet이라고 부른다. (이하 zset)

zset은 key-value형 자료구조이며, 하나의 key에 member, score쌍들이 저장되는 구조이다.

보통 set 자료구조는 정렬이나 삽입 순서를 보장하지 않지만, zset 자료구조는 score기반 정렬을 보장하는 자료구조이다. (score는 부동 소수점 자료형만 가능)

zset은 삽입, 삭제는 O(1), 검색은 O(logN) 시간복잡도를 갖는다.

검색시간이 O(logN)이 될 수 있는 이유는, zset이 두 가지 자료구조를 활용해 표현되기 때문이다.

zip list

http://redisgate.kr/redis/configuration/internal_ziplist.php
skip list

http://redisgate.kr/redis/configuration/internal_skiplist.php

Redis의 레이스 컨디션 극복

WATCH

Redis에서의 레이스 컨디션은 보통 여러 클라이언트가 각자의 트랜잭션을 진행중일 때 발생한다.

Redis는 WATCH 명령을 통해 zset 특정 key의 변경 여부를 감지할 수 있다.

트랜잭션을 커밋하기 전 (EXEC명령 전), WATCH해둔 key의 member 혹은 score에 변경이 감지되면 해당 트랜잭션을 수행하지 않는다.

(= Optimistic Lock)

출처 : https://media.vlpt.us/images/hyeondev/post/6fafd94a-3b9e-4727-959a-4af2ea5cde60/스크린샷 2020-10-03 오전 1.49.40.png

루아 스크립트

Redis에서 Pessimistic Lock을 구현하기 위해서는

Lock의 상태를 확인하고 획득하는 연산
Lock을 해제하고 알림을 보내는 연산

위 두 가지 연산이 atomic해야한다.

Redis의 SETNX 명령어를 이용해 위 두 가지 연산을 atomic하게 수행할 수 있다.

하지만 이 방법을 사용하면 polling 기법으로 Lock의 사용 가능 여부를 확인해야 한다.

Redisson에서는 pub/sub 기법과 트랜잭션, 루아 스크립트를 활용해 레디스를 Pessimistic Lock으로써 사용할 수 있게끔 한다.

트랜잭션 A가 Lock 상태를 확인하고, 요청한다. (atomic)
트랜잭션 A는 공유 리소스에 대한 작업 수행을 시작한다.
트랜잭션 B가 Lock 상태를 확인하고, 이미 사용중이므로 Lock 상태를 subscribe한다. (atomic)
트랜잭션 C가 Lock 상태를 확인하고, 이미 사용중이므로 Lock 상태를 subscribe한다. (atomic)
트랜잭션 A의 작업이 끝난 뒤, Lock을 반환하며, Lock이 반환되었음을 publish한다. (atomic)
Lock이 반환되었다는 알림을 받은 트랜잭션 B, C는 다시 Lock 상태를 확인하고, 먼저 확인한 트랜잭션이 Lock을 획득하게 될 것이다.

// in RedissonLock.java
<T> RFuture<T> tryLockInnerAsync(long leaseTime, TimeUnit unit, long threadId, RedisStrictCommand<T> command) {
    internalLockLeaseTime = unit.toMillis(leaseTime);

    return commandExecutor.evalWriteAsync(getName(), LongCodec.INSTANCE, command,
              "if (redis.call('exists', KEYS[1]) == 0) then " +
                  "redis.call('hset', KEYS[1], ARGV[2], 1); " +
                  "redis.call('pexpire', KEYS[1], ARGV[1]); " +
                  "return nil; " +
              "end; " +
              "if (redis.call('hexists', KEYS[1], ARGV[2]) == 1) then " +
                  "redis.call('hincrby', KEYS[1], ARGV[2], 1); " +
                  "redis.call('pexpire', KEYS[1], ARGV[1]); " +
                  "return nil; " +
              "end; " +
              "return redis.call('pttl', KEYS[1]);",
                Collections.<Object>singletonList(getName()), internalLockLeaseTime, getLockName(threadId));
}