3분만에 알아보는 Redis를 사용한 분산 락

들어가며

안녕하세요 잡채입니다.

연휴를 맞아 예전에 회사에서 동시성 처리 업무를 수행하며 공부했던 Redis를 사용한 분산 락에 대해 정리해둔 내용이 생각나 다시 읽어보며 업로드 합니다.

Background

이 글을 읽기 전 알아야할 내용

Lock

특정 임계 구역에 접근할 때 상호 배제를 보장하는 방법

Distributed lock

기본적인 lock의 개념을 가지면서 여러대의 서버가 하나의 임계 구역에 접근할 때 상호 배제를 보장하는 방법

분산 락은 아래 3가지를 반드시 보장해야한다.

1. Safety property
   1. 상호 배제: 특정 순간에 단 1개의 클라이언트만 Lock을 보유해야한다.
2. Liveness property A
   1. 데드락 방지: Lock을 반납하지 못하고 죽은 클라이언트가 있어도 다른 클라이언트가 영영 Lock을 획득하지 못하는 데드락이 발생하면 안된다.
3. Liveness property B
   1. 여러 레디스 노드가 존재하는 경우 한 노드에 장애가 발생해도 클라이언트는 정상적으로 Lock을 획득/반남할 수 있어야한다.

여러가지 lock 구현 방법

1. Redis
   1. Redis의 SETNX를 사용한 락 구현
   2. SETNX → key가 존재하면 SET 실패, 존재 하지 않으면 성공 ⇒ 이 과정에 대한 원자성 보장
   3. SET의 성공 여부를 Lock 획득 여부로 판단해 구현
2. SQL DB Lock
   1. SQL row lock 사용
   2. RDS 사용 시 별도 Redis가 없으면 해볼만 하나 SQL connection 부담 상승
   3. Redis 보다 무거운 편
3. zookeeper
   
   1. kafka 등에서도 사용하는 분산 서버 관리 시스템
   2. lock 성능보다 결제 같이 안정성이 중요한 경우 사용

Redis lock

단일 노드에서의 구현 방법

기본적인 단일 인스턴스에서의 Lock 획득 방식은 아래와 같다.

 SET resource_name my_random_value NX PX 30000 

NX 옵션을 사용해 키가 아직 존재하지 않는 경우에만 키를 설정할 수 있다.

Lock이 반납되지 않고 남아있는 경우를 방지하기 위해 PX 옵션을 사용해 만료시간을 지정한다. (30000ms)

키의 value 값은 모든 클라이언트에서 고유한 random value여야 한다.

value 값이 random value여야 하는 이유는 redis에 키가 존재하고, 키의 설정된 값이 정확히 내가 기대하는 값일때만 잠금 해제할 수 있도록하기 위함이다.

• 예를 들어 클라이언트가 잠금 유효 시간보다 오랫동안 작업 후 다른 클라이언트가 이미 획득한 다른 키를 해제할 수 있음

무작위 값을 설정하는 가장 간단한 방법은 마이크로초정밀도의 UNIX 타임스탬프를 활용하면 된다.

잠금 해제는 아래 Lua script를 사용한다.

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

잠금 해제 만료시간은 상호 배제를 위반하지 않고, Lock 획득 후 특정 작업 처리 후 다른 클라이언트가 Lock 획득을 하기 전까지 필요한 시간이다.

Spin lock

임계 구역에 진입이 불가할 때 진입이 가능할 때까지 루프를 돌며 락 획득을 시도하는 방식

진입까지 루프를 돌기 때문에 busy waiting(바쁜 대기) 발생

async acquireLock(key: string) {
    while (true) {
        const { randomValue, success } = await this.tryToAcquireLock(key)
        if (success) {
            return randomValue;
        }

        await sleep(1000); // 실제로는 정해진 수만큼 락 획득을 시도하고 포기해야 합니다
    }
}
async tryToAcquireLock(key: string)
    const randomValue = uuidV4();
    console.log('call redis for acquire lock')
    const result = await redis.set(key, randomValue, "PX", 30000, "NX");

    return {
        success: result === 'OK',
        randomValue
    }
}

Pub/Sub

위에서 설명한 Spin lock 방식은 루프를 돌며 지속적으로 lock 획득 요청을 보내는 점에서 불필요한 호출이 지속되어 비효율적이다.

이를 개선해 Redis Pub/Sub 기능을 사용해 클라이언트는 Lock 관련 메시지를 Subscribe하고 Lock 획득이 가능한 시점에 Lock 획득 하라고 메시지를 보내주는 방식

Spin lock 방식 처럼 계속 요청하지 않아도 돼 더 효율적이다.

한계점

• Master-Slave Race Condition 발생
  • Standalone으로 운영 시 단일 노드가 단일 장애 지점이 될 수 있음 이런 이유로 보통 Master-Slave 구조의 복제 노드를 구성할 수 있음
    이 경우 Redis 복제가 비동기적으로 실행됨으로 Lock 획득에서 Race Condition (경쟁 상태)가 일어날 수 있다.
  • Master-Slave 경쟁 상태 시나리오
    1. 클라이언트 A가 Master에서 Lock을 획득한다.
    2. 키가 Replica로 복제되기 전에 Master에 장애가 발생한다.
    3. Slave가 Master로 승격된다.
    4. 클라이언트 B가 이미 Lock을 보유하고 있는 A와 동일한 리소스에 대한 Lock을 획득한다.

Redlock Algorithms

위에서 나온 경쟁 상태 한계점 보완 + N개의 레디스 Master가 존재하는 분산 환경에서도 적용할 수 있는 Redlock 알고리즘이 등장

기본 아이디어는 여러 노드 중 과반수 이상의 노드에서 Lock을 획득하면 Lock을 획득한 것으로 간주한다는 것이다.

개념

1. 현재 시간을 밀리초 단위로 가져온다.
2. 모든 인스턴스에서 동일한 키와 값을 사용해 순차적으로 Lock 획득을 시도한다.
   1. 각 인스턴스에 Lock을 설정할때, 클라이언트는 전체 자동 Lock 해제 시간에 비해 작은 타임아웃을 사용해 Lock을 획득한다.
   2. 예를 들어 전체 Lock 자동 해제 시간이 10s 라면 타임 아웃은 그것 보다 작은 5 ~ 50ms로 설정
   3. 적은 타임아웃 시간을 사용해 클라이언트가 다운된 Redis 노드에 Lock 획득을 시도할때 생기는 블로킹을 방지할 수 있음
3. 클라이언트는 1에서 얻은 현재 시간 timestamp를 통해 Lock 획득을 시도하기까지 경과 시간을 계산한다.
   1. 클라이언트가 과반 (N / 2 + 1)이 넘는 인스턴스에서 Lock 획득을 성공하고, 총 경과 시간이 Lock 유효 시간보다 적다면 Lock을 획득했다고 간주한다.
4. Lock을 획득했다면, Lock 유효 시간은 초기 유효시간 - 경과 시간으로 간주한다.
   1. 초기 설정된 유효시간 - step 3에서 계산한 경과 시간
   2. 예를 들어 초기 설정된 유효시간이 10초이고, Lock을 획득하는데 3초가 걸렸다면 획득 이후부터 Lock은 10 - 3 = 7초 후에 만료된다.
5. Lock을 획득하지 못하면 (과반이 넘는 인스턴스에서 획득 실패 혹은 유효 시간이 음수인 경우)
   1. 클라이언트는 모든 인스턴스에서 Lock 해제를 시도한다.

구현 방식

Redis 공식문서에서 Node.js에서 사용할 수 있는 Redlock 구현체로 아래 node-redlock 을 소개한다.

https://github.com/mike-marcacci/node-redlock

구현체 사용 시 알고리즘을 복잡하게 구현할 필요없이 아래처럼 바로 사용 가능하다.

await redlock.using([senderId, recipientId], 5000, async (signal) => {
  // Do something...
  await something();

  // Make sure any attempted lock extension has not failed.
  if (signal.aborted) {
    throw signal.error;
  }

  // Do something else...
  await somethingElse();
});

Redlock Algorithm의 한계점

Redlock이 Race Condition을 보완하고 여러 master에서도 작동하도록 제안되었지만 아쉽게도 완벽한 알고리즘은 아니다. 대표적으로 아래 문제가 발생할 수 있다.

• GC에 의한 동시성 문제 시나리오
  1. 클라이언트 1이 Lock을 획득한다.
  2. 클라이언트 1에서 stop-the-world GC가 발생해 애플리케이션 코드 중지가 발생한다.
  3. 코드 중지 상태에서 클라이언트 1이 획득한 Lock이 만료된다.
  4. 클라이언트 2가 Lock을 획득하고 파일에 데이터를 작성한다.
  5. 클라이언트 1이 GC가 끝난 후 파일에 데이터를 작성한다.
     1. 이때 클라이언트 1과 2 모두 파일에 데이터를 작성해 동시성 문제가 발생한다.

  // THIS CODE IS BROKEN
  function writeData(filename, data) {
    var lock = lockService.acquireLock(filename);
    if (!lock) {
      throw 'Failed to acquire lock';
    }

    try {
      var file = storage.readFile(filename);
      var updated = updateContents(file, data);
      storage.writeFile(filename, updated);
    } finally {
      lock.release();
    }
  }

Ref.

https://redis.io/docs/latest/develop/use/patterns/distributed-locks/#the-redlock-algorithm

https://channel.io/ko/blog/distributedlock_2022_backend

https://medium.com/sjk5766/redis가-제공하는-redlock을-알아보자-2feb7278411e