😊 Go to Learn이란?

K-devcon에서 주최하는 멘토링 프로그래밍으로 각 분야에서 전문가이신 멘토분들의 멘토링을 통하여 약 2-3달간 진행하는 프로그램입니다.

Go to Learn 1기 같은 경우 Flutter, Back-end, Full-stack, Writing 등 여러가지 주제가 담긴 멘토링 프로그램이 있었습니다.

그 중 Back-end를 중심으로 진행하는 DDIA 프로그램 같은 경우 데이터 중심 애플리케이션 설계라는 책을 매주 1장 씩 정독하고 요약하면서 괸련된 이야기를 논의하면서 진행하고 있습니다.

K-devcon 이란? : IT 정보를 공유하거나 위에서 설명한 Go to Learn 스터디 및 밋업을 개최하는 활동을 하고있는 IT 커뮤니티입니다.
K-devcon 홈페이지 바로가기

---

📖 9장 요약 및 정리

9장에서는 내결함성을 지닌 분산 시스템을 구축하는 데 쓰이는 알고리즘과 프로토콜에 대해 이야기한다.

복제 데이터베이스는 대부분 최소한 최종적 일관성을 제공한다. (수렴)

• 언제 복제본이 수렴될지에 대해 아무것도 이야기하지 않는다. (약한 보장)
• 약한 보장만 제공하는 DB를 다룰 때 그 제한을 계속 알아야하고 너무 많은 것을 가정하면 안 된다.

분산 일관성 모델은 대개 지연과 결함이 있더라도 복제본의 상태를 코디네이션하는 것과 관련되어 있다.

• 선형성 / 순서화 보장 / 분산 트랜잭션

---

선형성

선형성을 뒷받침하는 아이디어는 원자적 일관성, 강한 일관성, 즉각 일관성, 외부 일관성이다.
선형성에 대한 정확한 정의는 미묘하지만 최신성을 보장해준다.

선형성 뒷받침하는 기본 아이디어는 시스템에 데이터 복사본이 하나뿐인 것처럼 만드는 것이다.

• 선형성의 요구사항은 연산 표시를 모인 선들이 항상 시간순으로 진행되어야하고 결코 뒤로 가서는 안 되는 것이다.
• 새로운 값이 쓰여지거나 읽히면 이후 실행되는 모든 읽기는 값이 다시 덮어쓰여질 때까지 쓰여진 값을 읽게 된다.

선형성에 기대기

• 잠금과 리더 선출 : 단일 리더 복제를 사용하는 시스템은 리더가 여러 개가 아니라 하나만 존재하도록 보장해야한다.
  • 리더를 선출하는 한 가지 방법은 잠금을 사용하는 것이다. -> 잠금 획득 시도 후 성공한 노드가 리더가 되는 방식 (아파치 주키퍼, etcd)
• 제약 조건과 유일성 보장 : 데이터가 기록될 때 제약 조건을 강제하고 싶다면 선형성이 필요하다.
  • 실제 애플리케이션에서는 제약을 느슨하게 다뤄도 되지만 엄격한 유일성 제약 조건은 선형성이 필요하다.
• 채널 간 타이밍 의존성 : 경쟁 조건의 위험에서 회피하기 위해서 선형성이 사용될 때가 있다. 단, 선형성이 경쟁 조건을 회피하는 유일한 방법이 아니다.

선형성 시스템을 가장 구현하기 쉬운 방법은 데이터 복사본 하나만 사용하는 것이다. 하지만 이러한 방법으로는 결함을 견뎌낼 수 없다.

• 시스템이 내결함성을 지니도록 만드는 가장 흔한 방법은 복제를 사용하는 것이다.
• 단일 리더 복제 / 합의 알고리즘 / 다중 리더 복제 / 리더 없는 복제

엄격한 정족수를 사용한 읽쓰기는 선형적으로 보이지만 네트워크의 지연의 변동이 심하면 경쟁 조건이 생길 수 있다.

• 성능이 떨어지는 비용을 지불하고 정족수를 선형적으로 만드는게 가능하다. -> 최종 쓰기 승리 충돌 해소 방법을 쓰기 떄문에 같은 키에 여러 쓰기를 동시에 실행하면 선형성을 잃게 된다.
• 리더 없는 시스템은 선형적을 제공하지 않는다고 보는게 안전하다.

두 데이터센터 사이에 네트워크가 끊길 시

• 다중 리더 데이터베이스 같은 경우 쓰기 큐에 쌓았다가 연결 시 복구되면 전달되므로 계속 동작할 수 있다.
• 단일 리더 설정 같은 경우 팔로워 데이터센터로 접속한 클라이언트들은 리더로 연결 할 수 없으므로 쓰기 및 선형성 읽기를 전혀 할 수 없다.

CAP 정리

CAP는 원래 데이터베이스에서 트레이드오프에 대한 논의를 시작하려는 목적으로 경험 법칙으로서 제안되었다.

• 일관성 / 가용성 / 분단 내성
• 공식적으로 정의되어진 CAP 정리는 매우 범위가 좁다.

선형성은 유용한 보장이지만 현실에서 실제로 선형적인 시스템은 놀랄 만큼 드물다. 심지어 다중코어 조차 선형적이지 않다.

• 이러한 이유는 모든 CPU 코어가 저마다 메모리 캐시와 저자 버퍼를 갖기 때문이다.
• 메모리 캐시와 저자 버퍼 내에서 이런 트레이드 오프를 만드는 이유는 내결함성이 아닌 성능 때문이다. -> 효율적인 선형 저장소 구현은 현재로써 없다. (회피를 활용해야한다.)

---

순서화

연산들이 실행되는 것처럼 보이는 순서를 결합해서 순서화를 나타내었다.
분산 데이터 내 순서화, 선형성, 합의 사이에서 깊은 연결 관계가 있다.

분산 데이터에서 순서화가 계속 나오는 이유는 순서화가 인과성을 보존하는데 도움을 주기 때문이다.

• 질문과 관련하여 질문이 답변되었다면 그 질문이 먼저 있어야한다. (인과적 의존성)
• A가 B보다 먼저 실행되거나 B가 A보다 먼저 실행되거나 A와 B가 동시에 실행될 수도 있다. (이전 발생)
• 스냅숏에 답변이 포함된다면 응답된 질문 또한 포함되어야한다. (인과성에 일관적)
• 시스템이 인과성에 의해 부과된 순서를 지키면 그 시스템은 인과적으로 일관적이라고 한다.

전체 순서와 부분 순서의 차이점은 다른 데이터베이스 일관성 모델에 반영된다.

• 선형성 : 선형성 시스템에서는 연산의 전체 순서를 정할 수 있다.
• 인과성 : 두 연산 중 어떤 것도 다른 것보다 먼저 실행되지 않았다면 두 연상이 동시적이라고 말했다.
• 인과적 순서와 선형성 사이의 관계 : 선형성은 인과성을 내포한다.

인과성을 유지하기 위해 어떤 연산이 다른 연산보다 먼저 실행되었는지 알아야한다.

• 인과적 의존성을 결정하려면 시스템에 있는 노드에 관한 지식을 기술할 방법이 필요하다. (동시 쓰기 감지)
• 인과적 순서를 결정하기 위해 데이터베이스는 애플리케이션이 데이터의 어떤 버전을 읽었는지 알아햐 한다.

일련번호 순서화

일련번호와 타임스탬프를 써서 이벤트의 순서를 정할 수 있다. -> 논리적 시계에서 얻어도 된다.

• 크기가 작고 전체 순서를 제공한다.
• 인과성에 일관적인 전체 순서대로 일련번호를 생성할 수 있다.
• 단일 리더가 없다면 연산에 사용할 일련번호를 생성하는 방법이 명확해 보이지 않는다.
  • 연산마다 고유한 근사 증가 일련번호를 생성한다. 그리나 인과성에 일관적이지 않다.

램포트 타임스탬프
인과성에 일관적인 일련번호를 생성하는 간단한 방법이다.

• 분산 시스템 분야에서 가장 많이 인용되는 논문 중 하나이다.
• 카운터, 노드 ID의 쌍으로 이루어져 있다.
• 버전 벡터와 혼동되지만 벡터 같은 경우 인과적으로 의존되는지 구분할 수 있지만 타임스탬프는 항상 전체 순서화를 강제한다.
• 단 유일성 제약 조건을 구현하기 위해 언제 그 순서가 확정되는지 알아야한다.

전체 순서 브로드 캐스트
전체 순서 브로드 캐스트는 다음과 같은 문제를 다룬다.

• 처리량이 단일 리더가 처리 할 수 있는 수준을 넘어설 때 시스템을 어떻게 확장할 것인가?
• 리더에 장애가 발생했을 때 어떻게 장애 복구를 처리할 것인가?

• 신뢰성 있는 전달 & 전체 순서가 정해진 전달을 항상 만족해야한다. (안전성 속성)
• 사용 : 데이터베이스 복제 / 직렬성 트랜잭션 구현 / 로그 / 펜싱 토큰을 제공하는 잠금 서비스
• 전체 순서 브로드캐스트를 기반으로 선형성 저장소를 만들 수 있다.
  • 추가 전용 로그를 사용하여 compare-and-set 연산 구현이 가능하다.
  • 위의 절차는 쓰기를 보장하지만 읽기는 보장하지 않는다.

---

분산 트랜잭션과 합의

비공식적으로 합의의 목적은 단지 여러 노드들이 뭔가에 동의하게 만드는 것이다. 불행하게도 많은 고장난 시스템들은 이 문제가 품기 쉽다는 잘못된 믿음을 기반으로 했다.

2단계 커밋

2단계 커밋 (2PC)
여러 노드에 걸친 원자적 트랜잭션 커밋을 달성하는, 즉 모든 노드가 커밋되거나 모든 노드가 어보트되도록 보장하는 알고리즘이다. -> 내부적 / XA 트랜잭션 / SOAP

• 2단계 커밋은 새로운 컴포넌트인 코디네이터를 사용한다. 코디네이터는 종종 트랜잭션을 요청하는 애플리케이션 프로세스 내에서 라이브러리 형태로 구현되지만 분리된 프로세스나 서비스가 될 수도 있다.
• 커밋 포인트 : 코디네이터가 모든 준비 요청에 대해 응답을 받았을 때 트랜잭션에 대한 최종적인 결정을 한다. 이 때 추후 죽는 경우 어떻게 결정했는지 알 수 있도록 그 결정을 디스크에 있는 트랜잭션 로그에 기록하게 되는데 기록 되는 포인트를 커밋 포인트라고 정의한다.

참여자가 준비 요청을 받은 후 회신을 받기 전 코디네이터가 죽거나 네트워크 장애가 발생하면 트랜잭션을 의심스럽다 라고 한다. -> 결과가 무엇인지 알 방법이 없다. 코디네이터가 복구 될 때 결과를 알 수 있다.

분산 트랜잭션

분산 트랜잭션은 방법으로 달성하기 어려운 중요한 안전성 보장을 제공한다고 하거나 성능을 떨어뜨리면서 제공할 수 있는 것보다 더 약속한다고 한다.

• 분산 트랜잭션은 데이터베이스 내부 분산 트랜잭션 혹은 이종 분산 트랜잭션을 혼용하여 정의하는 편이다.

XA 트랜잭션
이종 기술에 걸친 2단계 커밋을 구현하는 표준이다. -> 여러 전통적인 관계현 데이터베이스와 메시지 브로커에서 지원된다.

• 트랜잭션 코디네이터는 XA API를 구현한다.

트랜잭션이 의심스러운 상태에 빠지는 것에 신경을 쓰는 이유는 트랜잭션이 커밋하거나 어보트할 때 까지 이러한 잠금을 해제 할 수 없기 떄문이다. 이러한 잠금이 유지되는 동안 어떠한 트랜잭션도 로우를 변경할 수 없다.

코디네이터가 어떠한 이유 때문에 그 결과를 결정할 수 없다면 관리자가 수동으로 트랜잭션을 커밋하거나 롤백할지 결정하는 것 뿐이다. (고아가 된 트랜잭션)

• XA 구현 같은 경우 경험적 결정으로 탈출구를 제공하는 편이다. -> 아마도 원자성을 깰 수 있다.

내결함성 합의

합의 문제는 하나 또는 그 이상의 노드들이 값을 제안할 수 있고, 합의 알고리즘이 그 값 중 하나를 결정한다.

합의 알고리즘은 균일한 동의, 무결성, 유효성, 종료 와 같은 속성을 만족해야한다.

• 합의 시스템 모델은 노드가 죽으면 그 노드가 갑자기 사라져서 결코 돌아오지 않는다고 가정한다.
• 종료 속성은 죽거나 연결할 수 없는 노드 대수가 절반 미만이라는 가정에 종속적이다.
• 뷰스탬프 복제, 팍소스, 라프트 -> 순차열에 대해 결정해서 전체 순서 브로드 캐스트를 만든다.

에포크 번호 (투표 번호, 뷰 번호, 텀 번호)
각 에포크 내에서 리더가 유일하다고 보장하는 방법이다. -> 합의 프로토콜 내 약한 보장

• 리더가 죽었다고 생각될 때 마다 새 노드를 선출하기 위해 노드 사이에서 투표가 시작된다. -> 노드의 정족수로부터 투표를 받는다.
• 2단계 커밋과 비슷해 보이지만 모든 참여자에게 네 투표를 받아야하는 2단계 커밋과 달리 과반수로부터만 투표를 받으면 된다.

합의의 제약

• 합의 시스템은 항상 엄격한 과반수가 동작하기 요구한다.
• 합의 알고리즘의 동적 멤버십 확장은 시간이 지남에 따라 바뀌는 것을 허용하지만 이해하지 어렵다.
• 장애 노드를 감지하기 위해 타임아웃에 의지한다. 또한 네트워크 문제에 민감하다.

멤버십과 코디네이션 서비스

주키퍼와 같은 프로젝트는 코디네이션과 설정 서비스라고 설명이 되어진다.

• 주키퍼는 실제 범용 데이터베이스에서는 적합하지 않기 때문에 직접 쓸 필요는 없다. 간접적으로 의존할 가능성이 높다.
• 전체 순서 브로드캐스트 뿐만 아니라 분산 시스템을 구축할 때 다른 흥미로운 기능 집합도 구현한다.
  • 선형적 원자적 연산 / 연산의 전체 순서화 / 장애 감지 / 변경 알림
    

서비스 찾기
특정 서비스에 연결하려면 어떤 IP 주소로 접속해야하는지 알아내는 용도로 자주 사용된다.

• 서비스 찾기는 합의가 필요 없지만 리더 선출은 합의가 필요하다.

맴버십 서비스
클러스터에서 어떤 노드가 현재 활성화된 살아 있는 멤버인지 결정한다.

• 단, 노드가 실제로는 살아 있지만 합의에 의해 죽은 것으로 잘못 선언 될 가능성이 있다.

---

😉 필자의 생각

이번 9장에서는 지난 8장에서 다루어보았던 분산 시스템의 문제점을 해결하는 알고리즘 그 중 분산 트랜잭션과 합의에 대해서 설명해주는 내용이었다. 위의 내용을 설명하기 위해서 선형성과 순서화에 대해 선형으로 자세히 다루어보았는데 파트 2(5-9장)에서 다루었던 내용을 총 정리하는 내역이었다.

여타 최근 정리한 장들과 마찬가지로 9장에서도 상호배제, 세마포어 등 운영 체제에서 설명되어있는 용어들이 소프트웨어 측면에서 이렇게 활용되는구나 생각되는 예시들이 많았었던 것 같았었다.

9장에 관해서 조사한 내역을 발표할 기회가 있어서 각 부분마다 자료들을 조사하였었다. 비록 내역을 정리를 못하여서 발표를 성공적으로 잘 이끌지 못하였지만 추후 위와 같은 주제로 발표를 하게된다면 성공적으로 발표를 진행하기 위해서 9장과 관련하여 조사한 자료를 기술해보았다.

조사내역

9장 내역 중 업무 내에서 분산 데이터와 관련된 이야기가 없었기 때문에 내역 중 좀 더 관련된 키워드를 크게 3가지로 조사해보았다. 또한 CAP 정리 같은 경우 전에 다른 책에서 읽어보았던 내용을 반박하는 내역이 나왔기 때문에 흥미를 가져 조사를 하게 되었다.

IBM - 잠금 세분성

선형성과 잠금과 관련하여 위와 황용된 것들 중 하나인 리더 노드를 선출하는 다른 예시를 조사하던 중 우연히 IBM 내에서도 잠금 세분성이라는 내역이 나오게 되어 위와 같은 황용을 동일하게 사용하고 있는지 궁금하여 조사 자료에 추가 하였다.

위의 내역을 간단히 요약하자면 공유 데이터간의 사용되어지는 데이터 잠금의 갯수와 공간에 대해 설정을 할 수 있는데 갯수가 높을 수록 잠금 경합이 낮아지지만 범뮈에 넓어지게 되어 교착상태가 발생하게 되고 위를 방지하기 위해서 잠금 범위를 줄여야한다는 내용이었다. 책에서 생각나는 잠금의 예시가 다르지만 데드락을 회피하기 위해서 잠금하는 범위를 줄이는 방법을 택함으로서 각 대기시간을 줄여 선형성을 유지시키는 것 같다.

조사 링크 : 잠금 세분성

Lamport의 베이커리 알고리즘

이벤트의 순서를 경정하는 테이블 중 하나인 램포트 타임스탬프에서 사용하는 알고리즘들을 조사하던 중 Lamport의 분산 상호 배제 알고리즘와 관련하여 베이커리 알고리즘에 대해 조사하게 되었던 것 같다.

베이커리 알고리즘은 스레드가 임계 구역에 들어갈 때, 지금이 자신의 차례인지 확인하고 임계 구역에 들어가는 알고리즘이다. 자신의 차례를 확인하기 위해서 모든 스레드의 번호 n을 확인하여 가장 작은 번호가 있는지 확인하게 되는데 다른 스레드가 같은 번호인 경우, 가장 작은 i를 가진 스레드가 먼저 임계 구역에 들어가는 방식이다.

베이커리 알고리즘이라고 명명하는 이유는 위의 알고리즘을 베이커리 입장에 비유하면서 설명을 하였기 때문에 위와 같이 명명되었다고 생각이 든다.

조사 링크 : Lamport's bakery algorithm

Raft

Raft 알고리즘은 전체 순서 브로드 캐스트를 만들기 위해 사용되어지는 합의 알고리즘이다. 책에서는 위와 같은 설명의 예시로만 나와있었기 때문에 정확히 어떠한 일을 하는지 알기 위해 자료를 조사했었었다.

Raft 알고리즘은 크게 리더, 팔로워, 후보자 상태를 가진 노드로 구성되어 있는데 리더와 팔로워는 분산 및 파티셔닝 파트에서 설명 되었던 리더 & 팔로워 노드랑 유사한 역할을 지녔지만 후보자 노드는 리더를 선출 할 때 리더를 선출하기 위해서 사용되어지는 노드라고 한다.

Raft 알고리즘은 크게 투표를 통한 리더 선출과 로그 복제와 같은 실행 절차를 이루어지게 되는데 리더 선출 같은 경우 내결함성 합의 알고리즘 설명과 같이 후보자 노드가 전체 노드의 절반 이상이 찬성하는 경우 새로운 리더 노드로 선출된다는 진행 절차를 가지고 있었다. 로그 복제 같은 경우 헬스 체크와 유사하게 리더 노드가 팔로워에게 주기적으로 로그 형태의 변경사항을 요청하는 진행 절차를 가지고 있다.

또한 분산 시스템과 합의 알고리즘을 그림으로 쉽게 설명하는 페이지가 있어서 위의 링크 또한 가져와보았다.

조사 링크 : Raft
조사 링크 2 : [KRaft 파헤치기] Raft 알고리즘 톺아보기

CAP 정리

DDIA 같은 경우 CAP 정리를 설명한 이후 CAP 정리가 일관성, 가용성, 파티션 감애라는 3가지 요구사항이 동시에 존재할 수 없고 2가지만 존재한다는 것을 지양하는 내역을 설명하고 있는 부분이 있었다. 하지만 가상 면접 사례로 배우는 대규모 시스템 설계와 같은 다른 개발 서적에서 CAP 정리와 관련하여 데이터 일관성, 가용성, 파티션 감내라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정의만 나와었어서 왜 이렇게 되었는지 궁금했었다.

아래의 링크를 통해 조사한 내역에 의하면 분산 시스템 같은 경우 순차적 일관성과 고가용성 중에서 선택하는 것이 거의 항상 이루어지고 있다는 것이 결론이었다. CAP 정리를 정의할 때 데이터베이스 같은 경우 파티션이 드물기 때문에 순차적 일관성과 가용성을 위해 '파티션 허용 범위'를 희생할 수 있고 그에 따라 데이터 일관성과 가용성만 선택이 되어진다고 한다. 또한 수천 대 이상 분산 처리 머신이 증가하게 된다면 일관성을 통한 비용이 증가하게 되어 어느 순간 일관성과 가용성 중에서 선택하는 상황이 발생하게 된다고 한다.

위를 조사하게 되면서 왜 CAP 정리 내에서 3가지 중 2가지만 정리하게 되는 지 어느 정도 이해할 수 있을 것 같았다.

조사 링크 : CAP Confusion: Problems with 'partition tolerance' - Cloudera Engineering Blog