Redis를 사용한 분산 잠금

헤이 하브르!

오늘 우리는 Redis를 사용한 분산 잠금 구현에 관한 복잡한 기사의 번역을 소개하고 Redis의 전망에 대해 주제로 이야기하도록 초대합니다. "라는 책의 저자인 Martin Kleppmann이 문제의 Redlock 알고리즘을 분석했습니다.고부하 애플리케이션", 주어진 여기에.

분산 잠금은 여러 프로세스가 상호 배타적인 방식으로 공유 리소스에 대해 작업해야 하는 많은 환경에서 사용되는 매우 유용한 기본 요소입니다.

Redis를 사용하여 DLM(분산 잠금 관리자)을 구현하는 방법을 설명하는 많은 라이브러리와 게시물이 있지만 각 라이브러리는 서로 다른 접근 방식을 취하고 제공하는 보장은 약간 더 정교한 설계로 달성할 수 있는 것에 비해 상당히 약합니다.

이 기사에서는 Redis를 사용하여 분산 잠금을 구현하는 방법을 보여주는 조건부 표준 알고리즘을 설명하려고 합니다. 우리는 다음과 같은 알고리즘에 대해 이야기하겠습니다. 레드락, 이는 분산 잠금 관리자를 구현하며 우리 의견으로는 이 알고리즘이 일반적인 단일 인스턴스 접근 방식보다 안전합니다. 우리는 커뮤니티가 이를 분석하고, 피드백을 제공하고, 이를 보다 복잡하거나 대안적인 프로젝트의 출발점으로 사용하기를 바랍니다.

구현

알고리즘 설명으로 넘어가기 전에 이미 만들어진 구현에 대한 여러 링크를 제공합니다. 참고용으로 사용할 수 있습니다.

• Redlock-rb (Ruby 구현). 도 있습니다 포크 배포의 용이성뿐만 아니라 배포의 용이성을 위해 패키지(gem)를 추가하는 Redlock-rb.
• Redlock-py (파이썬 구현).
• 아이오레드락 (Asyncio Python 구현).
• Redlock-php (PHP 구현).
• PHPRedisMutex (PHP의 또 다른 구현)
• 체프라소프/php-redis-lock (잠금용 PHP 라이브러리)
• 레드싱크 (Go 구현).
• 레디송 (Java 구현).
• Redis::DistLock (펄 구현).
• Redlock-cpp (C++ 구현).
• Redlock-cs (C#/.NET용 구현).
• RedLock.net (C#/.NET용 구현). 비동기 및 잠금 확장을 지원합니다.
• 스칼렛락 (구성 가능한 데이터 저장소가 있는 C# .NET 구현)
• Redlock4Net (C# .NET 구현)
• 노드 레드락 (NodeJS 구현). 잠금 확장에 대한 지원이 포함됩니다.

보안 및 가용성 보장

우리는 분산 잠금을 효과적으로 사용하는 데 필요한 최소한의 보장을 제공한다고 생각되는 세 가지 속성만으로 디자인을 모델링할 것입니다.

1. 보안 속성: 상호 배제. 주어진 시간에 오직 하나의 클라이언트만이 잠금을 보유할 수 있습니다.
2. 가용성 속성 A: 교착 상태가 없습니다. 리소스를 잠근 클라이언트가 실패하거나 다른 디스크 세그먼트에 있는 경우에도 결국 잠금을 획득하는 것은 항상 가능합니다.
3. 가용성 속성 B: 내결함성. 대부분의 Redis 노드가 실행 중인 한 클라이언트는 잠금을 획득하고 해제할 수 있습니다.

이 경우 장애 복구 기반 구현이 충분하지 않은 이유
개선할 사항을 이해하기 위해 Redis를 기반으로 하는 대부분의 분산 잠금 라이브러리의 현재 상태를 분석해 보겠습니다.

Redis를 사용하여 리소스를 잠그는 가장 간단한 방법은 인스턴스에 키를 생성하는 것입니다. 일반적으로 키는 제한된 수명으로 생성됩니다. 이는 Redis에서 제공되는 만료 기능을 사용하여 달성되므로 조만간 이 키가 해제됩니다(목록의 속성 2). 클라이언트는 리소스를 해제해야 할 경우 키를 삭제합니다.

언뜻 보기에 이 솔루션은 꽤 잘 작동하지만 문제가 있습니다. 즉, 우리의 아키텍처는 단일 실패 지점을 생성합니다. 호스트 Redis 인스턴스가 실패하면 어떻게 되나요? 그럼 슬레이브를 추가하자! 발표자가 부재중일 경우에도 사용하겠습니다. 불행하게도 이 옵션은 실행 가능하지 않습니다. 이렇게 하면 Redis의 복제가 비동기식이므로 보안을 보장하는 데 필요한 상호 배제 속성을 제대로 구현할 수 없습니다.

분명히 이러한 모델에서는 경쟁 조건이 발생합니다.

1. 클라이언트 A는 마스터에 대한 잠금을 획득합니다.
2. 키 항목이 슬레이브로 전송되기 전에 마스터가 실패합니다.
3. 추종자가 리더로 승진합니다.
4. 클라이언트 B는 A가 이미 잠근 동일한 리소스에 대한 잠금을 획득합니다. 보안 위반!

때로는 실패와 같은 특별한 상황에서 많은 클라이언트가 동시에 잠금을 보유할 수 있는 것이 완전히 정상입니다. 이러한 경우 복제 기반 솔루션을 적용할 수 있습니다. 그렇지 않은 경우에는 이 문서에 설명된 해결 방법을 권장합니다.

단일 인스턴스로 올바른 구현

위에서 설명한 단일 인스턴스 구성의 단점을 극복하기 전에 이 간단한 사례를 적절하게 처리하는 방법을 이해해 보겠습니다. 이 솔루션은 때때로 경쟁 조건이 허용되는 응용 프로그램에서 실제로 유효하기 때문입니다. 단일 인스턴스는 여기에 설명된 분산 알고리즘에 사용되는 기반으로 사용됩니다.

잠금을 얻으려면 다음을 수행하십시오.

SET resource_name my_random_value NX PX 30000

이 명령은 키가 아직 없는 경우에만(NX 옵션) 키를 설치하며 유효 기간은 30000밀리초(PX 옵션)입니다. 키는 "로 설정되어 있습니다.myrandomvalue" 이 값은 모든 클라이언트와 모든 잠금 요청에서 고유해야 합니다.
기본적으로 임의의 값은 Redis에게 키가 존재하고 키에 저장된 값이 정확히 예상한 값인 경우에만 키를 제거하라는 스크립트와 함께 잠금을 안전하게 해제하는 데 사용됩니다. 이는 다음 Lua 스크립트를 사용하여 달성됩니다.

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

이는 다른 클라이언트가 보유한 잠금이 제거되는 것을 방지하는 데 중요합니다. 예를 들어, 클라이언트는 잠금을 획득한 다음 첫 번째 잠금보다 오래 지속되는 일부 작업에서 잠기고(키가 만료될 시간을 갖기 위해) 나중에 다른 클라이언트가 설정한 잠금을 제거할 수 있습니다.
단순 DEL을 사용하는 것은 클라이언트가 다른 클라이언트가 보유한 잠금을 제거할 수 있으므로 안전하지 않습니다. 대조적으로, 위 스크립트를 사용할 때 각 잠금은 임의의 문자열로 "서명"되므로 이전에 잠금을 설정한 클라이언트만 이를 제거할 수 있습니다.

이 임의의 문자열은 무엇이어야 합니까? 나는 그것이 /dev/urandom에서 20바이트여야 한다고 추측하지만, 귀하의 목적에 맞게 문자열을 고유하게 만드는 보다 저렴한 방법을 찾을 수 있습니다. 예를 들어 RC4에 /dev/urandom을 시드한 다음 여기에서 의사 무작위 스트림을 생성하는 것이 좋습니다. 더 간단한 솔루션에는 마이크로초 해상도의 Unix 시간과 클라이언트 ID의 조합이 포함됩니다. 안전하지는 않지만 대부분의 상황에서 작업에 따라 달라질 수 있습니다.

키의 수명을 측정하는 데 사용하는 시간을 "잠금 수명"이라고 합니다. 이 값은 잠금이 자동으로 해제되기 전까지의 시간과 실제로 상호 배제 보장을 위반하지 않고 다른 클라이언트가 해당 리소스를 잠그기 전에 클라이언트가 작업을 완료해야 하는 시간입니다. 이 보증은 자물쇠를 구입한 순간부터 시작되는 특정 기간으로만 제한됩니다.

그래서 우리는 잠금을 획득하고 해제하는 좋은 방법에 대해 논의했습니다. 시스템(항상 사용 가능한 단일 인스턴스로 구성된 비분산 시스템에 대해 이야기하는 경우)은 안전합니다. 이 개념을 그러한 보장이 없는 분산 시스템으로 확장해 보겠습니다.

레드락 알고리즘

알고리즘의 분산 버전에서는 N개의 Redis 마스터가 있다고 가정합니다. 이러한 노드는 서로 완전히 독립적이므로 복제 또는 기타 암시적 조정 시스템을 사용하지 않습니다. 우리는 단일 인스턴스에 대한 잠금을 안전하게 획득하고 해제하는 방법을 이미 다루었습니다. 우리는 단일 인스턴스로 작업할 때 알고리즘이 정확히 이 방법을 사용한다는 것을 당연하게 여깁니다. 이 예에서는 N을 합리적인 값인 5로 설정했습니다. 따라서 서로 독립적으로 작동하도록 서로 다른 컴퓨터 또는 가상 머신에서 5개의 Redis 마스터를 사용해야 합니다.

잠금을 획득하기 위해 클라이언트는 다음 작업을 수행합니다.

1. 현재 시간을 밀리초 단위로 가져옵니다.
2. 모든 경우에 동일한 키 이름과 임의의 값을 사용하여 모든 N 인스턴스에 대해 순차적으로 잠금을 얻으려고 시도합니다. 2단계에서는 클라이언트가 인스턴스별로 잠금을 설정할 때 클라이언트는 잠금이 자동으로 해제된 후의 시간에 비해 충분히 짧은 지연을 사용하여 잠금을 획득합니다. 예를 들어 차단 기간이 10초인 경우 지연 시간은 ~5~50밀리초 범위일 수 있습니다. 이렇게 하면 클라이언트가 실패한 Redis 노드에 도달하려고 오랫동안 차단될 수 있는 상황이 제거됩니다. 인스턴스를 사용할 수 없는 경우 가능한 한 빨리 다른 인스턴스에 연결하려고 시도합니다.
3. 잠금을 수행하기 위해 클라이언트는 경과된 시간을 계산합니다. 이를 위해 실제 시간 값에서 1단계에서 얻은 타임스탬프를 뺍니다. 클라이언트가 대부분의 인스턴스(최소 3개)에 대한 잠금을 얻을 수 있었던 경우에만 해당되며, 소요된 총 시간은 다음과 같습니다. 잠금을 획득하고 잠금 기간보다 짧은 경우 잠금을 획득한 것으로 간주됩니다.
4. 잠금이 획득된 경우 잠금 기간은 원래 잠금 기간에서 3단계에서 계산된 경과 시간을 뺀 값으로 간주됩니다.
5. 클라이언트가 어떤 이유로 잠금을 획득하지 못한 경우(N/2+1 인스턴스를 잠글 수 없거나 잠금 기간이 음수인 경우) 모든 인스턴스 잠금을 해제하려고 시도합니다(차단할 수 없다고 생각한 인스턴스도 포함). ).

알고리즘이 비동기식인가요?

이 알고리즘은 모든 프로세스가 작동하는 동기화된 시계는 없지만 각 프로세스의 로컬 시간은 여전히 ​​대략 동일한 속도로 흐르고 잠금이 해제된 후의 전체 시간에 비해 오류가 작다는 가정을 기반으로 합니다. 자동으로 해제됩니다. 이 가정은 일반 컴퓨터의 일반적인 상황과 매우 유사합니다. 각 컴퓨터에는 로컬 시계가 있으며 일반적으로 서로 다른 컴퓨터 간의 시간 차이가 작다는 사실을 믿을 수 있습니다.

이 시점에서 우리는 상호 배제 규칙을 보다 신중하게 공식화해야 합니다. 상호 배제는 잠금을 보유한 클라이언트가 잠금이 유효한 시간(3단계에서 얻은 이 값) 동안 종료하는 경우에만 더 많은 시간(총 몇 시간)을 뺀 경우에만 보장됩니다. 프로세스 간의 시간 차이를 보상하기 위해 밀리초).

다음 흥미로운 기사에서는 시간 간격 조정이 필요한 시스템에 대해 자세히 설명합니다. 임대: 분산 파일 캐시 일관성을 위한 효율적인 내결함성 메커니즘.

실패 시 재시도

클라이언트가 잠금 획득에 실패하면 임의의 지연 후에 다시 시도해야 합니다. 이는 동일한 리소스에 대한 잠금을 동시에 획득하려는 여러 클라이언트를 비동기화하기 위해 수행됩니다(승자가 없는 "분할 브레인" 상황으로 이어질 수 있음). 또한 클라이언트가 대부분의 Redis 인스턴스에 대한 잠금 획득을 더 빨리 시도할수록 분할 브레인 상황이 발생할 수 있는 기간은 더 좁아집니다(그리고 재시도 필요성도 줄어듭니다). 따라서 이상적으로 클라이언트는 멀티플렉싱을 사용하여 동시에 N 인스턴스에 SET 명령을 보내려고 시도해야 합니다.

여기서는 대부분의 잠금을 획득하지 못한 클라이언트가 (부분적으로) 획득한 잠금을 해제하여 리소스에 대한 잠금을 다시 획득하기 전에 키가 만료될 때까지 기다릴 필요가 없도록 하는 것이 얼마나 중요한지 강조할 가치가 있습니다. (네트워크 조각화가 발생하고 클라이언트가 Redis 인스턴스와의 연결이 끊어지면 키가 만료될 때까지 기다리는 동안 가용성 페널티를 지불해야 합니다).

잠금을 해제하세요

잠금 해제는 클라이언트가 특정 인스턴스를 성공적으로 잠근 것으로 보이는지 여부에 관계없이 모든 인스턴스를 잠금 해제하면 되는 간단한 작업입니다.

보안 고려 사항

알고리즘은 안전한가요? 다양한 시나리오에서 무슨 일이 일어나는지 상상해 봅시다.

우선 클라이언트가 대부분의 인스턴스에 대한 잠금을 얻을 수 있었다고 가정해 보겠습니다. 각 인스턴스에는 모두에 대해 동일한 수명을 갖는 키가 포함됩니다. 그러나 이러한 키는 각각 서로 다른 시간에 설치되었으므로 서로 다른 시간에 만료됩니다. 하지만 첫 번째 키가 T1(첫 번째 서버에 연결하기 전에 선택한 시간)보다 나쁘지 않은 시간에 설치되고 마지막 키가 T2(응답을 받은 시간)보다 나쁘지 않은 시간에 설치된 경우 마지막 서버에서), 만료되는 세트의 첫 번째 키가 적어도 살아남을 것이라고 확신합니다. MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. 다른 모든 키는 나중에 만료되므로 적어도 이 시간 동안 모든 키가 동시에 유효하다는 것을 확신할 수 있습니다.

대부분의 키가 유효한 동안에는 N/2+1 키가 이미 존재하는 경우 N/2+1 SET NX 작업이 성공할 수 없으므로 다른 클라이언트가 잠금을 획득할 수 없습니다. 따라서 잠금을 한 번 획득하면 동시에 다시 획득할 수 없습니다(이는 상호 배제 속성을 위반하게 됩니다).
그러나 우리는 동시에 잠금을 획득하려는 여러 클라이언트가 동시에 성공할 수 없도록 하고 싶습니다.

클라이언트가 최대 잠금 기간 이상 동안 대부분의 인스턴스를 잠근 경우 잠금이 유효하지 않은 것으로 간주하고 인스턴스를 잠금 해제합니다. 따라서 클라이언트가 만료 날짜보다 짧은 시간 내에 대부분의 인스턴스를 차단한 경우만 고려하면 됩니다. 이 경우 위의 주장에 대하여 그 기간 동안 MIN_VALIDITY 어떤 클라이언트도 잠금을 다시 획득할 수 없어야 합니다. 따라서 많은 클라이언트는 대다수를 잠그는 시간이 TTL 시간보다 길어서 잠금이 무효화되는 경우에만 N/2+1 인스턴스를 동시에 잠글 수 있습니다(2단계 끝에서 끝남).

공식적인 보안 증명을 제공하거나, 기존의 유사한 알고리즘을 표시하거나, 위에서 버그를 찾을 수 있습니까?

접근성 고려 사항

시스템 가용성은 세 가지 주요 특성에 따라 달라집니다.

1. 자동으로 잠금 해제(키가 만료되면): 결국 키는 다시 잠금에 사용될 수 있게 됩니다.
2. 클라이언트는 일반적으로 원하는 잠금을 획득하지 못했거나 획득했지만 작업이 완료되었을 때 잠금을 제거하여 서로를 돕는다는 사실 따라서 잠금을 다시 획득하기 위해 키가 만료될 때까지 기다릴 필요가 없을 가능성이 높습니다.
3. 클라이언트가 잠금을 획득하기 위해 재시도해야 할 때 대부분의 잠금 획득에 필요한 시간보다 비교적 오랜 시간을 기다린다는 사실입니다. 이는 자원 경쟁 시 두뇌 분할 상황이 발생할 가능성을 줄여줍니다.

그러나 네트워크 세그먼트의 TTL과 동일한 가용성 페널티가 있으므로 연속된 세그먼트가 있는 경우 페널티는 무한정일 수 있습니다. 이는 클라이언트가 잠금을 획득한 다음 잠금을 해제하기 전에 다른 세그먼트로 추출할 때마다 발생합니다.

원칙적으로 무한한 연속 네트워크 세그먼트가 주어지면 시스템은 무한한 시간 동안 사용할 수 없는 상태로 남아 있을 수 있습니다.

성능, 장애 조치 및 fsync

많은 사람들이 잠금을 획득하고 해제하는 데 필요한 대기 시간과 초당 완료할 수 있는 획득/해제 횟수 측면에서 높은 잠금 서버 성능이 필요하기 때문에 Redis를 사용합니다. 이러한 요구 사항을 충족하기 위해 N Redis 서버와 통신하여 대기 시간을 줄이는 전략이 있습니다. 이는 멀티플렉싱 전략(또는 클라이언트와 각 인스턴스 간의 왕복 시간이 비슷하다고 가정하여 소켓을 비차단 모드로 설정하고 모든 명령을 보낸 다음 나중에 명령을 읽는 "가난한 사람의 멀티플렉싱")입니다. .

그러나 장애로부터 안정적인 복구가 가능한 모델을 만들려면 장기 데이터 저장과 관련된 고려 사항도 고려해야 합니다.

기본적으로 문제를 명확히 하기 위해 장기 데이터 저장소가 전혀 없는 Redis를 구성한다고 가정해 보겠습니다. 클라이언트는 인스턴스 3개 중 5개를 차단했습니다. 클라이언트가 차단한 인스턴스 중 하나가 다시 시작되고, 현재 동일한 리소스에 대해 3개의 인스턴스가 다시 발생하여 우리가 차단할 수 있으며, 다른 클라이언트는 다시 시작된 인스턴스를 차단하여 보안 속성을 위반할 수 있습니다. 잠금의 독점성을 가정합니다.

AOF(Data Ahead)를 활성화하면 상황이 약간 개선됩니다. 예를 들어 SHUTDOWN 명령을 보내고 다시 시작하여 서버를 승격할 수 있습니다. Redis의 만료 작업은 서버가 꺼진 경우에도 시간이 계속 흐르도록 의미론적으로 구현되므로 모든 요구 사항은 괜찮습니다. 정상적인 종료가 보장되는 한 이는 정상적인 현상입니다. 정전이 발생하면 어떻게 해야 하나요? Redis가 기본적으로 fsync가 매초마다 디스크에서 동기화되도록 구성된 경우 다시 시작한 후 키가 없을 수도 있습니다. 이론적으로 인스턴스를 다시 시작하는 동안 잠금 보안을 보장하려면 다음을 활성화해야 합니다. fsync=always 데이터 장기 저장 설정에서 이는 분산 잠금을 안전하게 구현하는 데 전통적으로 사용되는 CP 시스템 수준까지 성능을 완전히 저하시킵니다.

그러나 상황은 언뜻 보이는 것보다 낫습니다. 원칙적으로 인스턴스가 실패 후 다시 시작되면 현재 활성화된 잠금에 더 이상 참여하지 않기 때문에 알고리즘의 보안이 유지됩니다.

이를 보장하려면 장애 후 우리가 사용하는 최대 TTL을 약간 초과하는 기간 동안 인스턴스를 사용할 수 없는 상태로 유지하면 됩니다. 이렇게 하면 오류 발생 시 활성화된 모든 키의 만료 날짜와 자동 해제까지 기다립니다.

지연된 재시작을 사용하면 원칙적으로 Redis에 장기간 지속성이 없더라도 보안을 달성할 수 있습니다. 다만, 접근성 위반으로 인해 벌금이 부과될 수 있으니 주의하시기 바랍니다. 예를 들어 대부분의 인스턴스가 실패하면 시스템은 TTL 동안 전역적으로 사용할 수 없게 됩니다(이 시간 동안 어떤 리소스도 차단될 수 없습니다).

알고리즘의 가용성을 높입니다. 차단 기능을 확장합니다.

클라이언트가 수행하는 작업이 작은 단계로 구성된 경우 기본 잠금 기간을 줄이고 잠금 연장을 위한 메커니즘을 구현할 수 있습니다. 원칙적으로 클라이언트가 계산 중이고 잠금 만료 값이 위험할 정도로 낮은 경우 키가 여전히 존재하고 해당 값이 여전히 임의의 값일 때 키의 TTL을 확장하는 모든 인스턴스에 Lua 스크립트를 보낼 수 있습니다. 잠금을 획득했습니다.

클라이언트는 유효 기간 내에 대부분의 인스턴스를 잠근 경우에만 잠금을 다시 획득해야 합니다.

사실, 기술적으로 알고리즘은 변경되지 않으므로 잠금을 획득하려는 최대 반복 시도 횟수는 제한되어야 합니다. 그렇지 않으면 접근성 속성이 위반됩니다.

출처 : habr.com