- 마틴 클레프만 (Martin Kleppmann)
분산 시스템에서 충돌 해결(Conflict resolution)을 다루려 합니다. 다른 사람들이 데이터를 독립적으로 변경했을 때 어떤 일이 일어나고, 일어난 충돌을 어떻게 해결하냐입니다. 내 이름은 마틴 크레프만이며 캠브리지 대학의 연구자이고요. 예전에는 산업에서 인터넷 스타트업에 종사했습니다. 또 링트인(LinkedIn)에서도 몇년동안 일했습니다.
Trve 데이터라 불리우는 연구 제품을 작업하고 있습니다. 구글 서버를 신뢰하지 않고도 여러 사람들이 문서를 온라인에서 같은 시간에 수정할 수 있는, 구글 독스와 같은 대규모의 어플리케이션에 종단간 암호화(End-toend encryption)를 적용하는 것이 목표입니다.
클라우드의 여러 서버에 데이터를 올리고, 데이터의 손상에 대해 걱정하지 않는 것을 원합니다.
깃(Git) 사용을 예로 들겠습니다. 저장소에 코드를 올리고 다른 이가 접근할 수 있는 원격 어딘가 (예를 들면 Github)에 보낼 수 있습니다.
코드베이스에 작업을 한 다른 사람이 변경점을 받을 때 머지나 리베이스를 해야할 겁니다. 같은 저장소의 다른 파일을 변경했다면 문제없이 머지가 될 것입니다.
하지만 같은 파일의 같은 부분을 변경해싿면 머지 충돌을 스스로 해결해야 합니다. 우리가 해결하려는 것이 이 문제입니다. 소프트웨어 개발만의 문제는 아니고 매우 일반적인 문제입니다.
여러분이 다른 변호사와 계약 때문에 같이 일하는 변호사라고 상상해봅시다. 이메일로 다른 버전을 주고 받습니다. 누군가 수동으로 계약의 어떤 버전에서 다른 버전으로 바꾸어 버리면 어떻게 되나요?
이 경우 한 사람이 변경을 마칠 때까지 추가적인 변경을 하지 않는다는 비공식적인 잠금을 사용하는 것이 최선입니다. 수동 통신을 통한 갱신 순서를 지정하는 것입니다.
내가 해야할 일을 배우자와 공유한다고 가정합시다. '우유 사기'나 '식물에 물주기'같은 일을 추가할 수 있습니다. 추가된 일은 서버로 전송되고 관계지향형 데이터베이스에 저장됩니다. 이 시나리오에서 갱신은 순차적/연속된 순서로 저용됩니다. 여기에서는 충돌 해결 문제가 없습니다. 하지만 인터넷이 되지 않아서 중앙집권된 서버에 도달하지 못할 때 문제가 됩니다.
중앙 서버를 쓰면 동시성 문제와 동시에 다른 편집이 일어나는 것을 걱정할 필요가 없습니다. 하지만 고정적인 인터넷 연결이 필요하고 이가 신뢰성에 영향을 줍니다.
중앙 서버를 두는 것은 DOS(Denial-of-Service) 공격이나 검열에 취약합니다.
(지구 반대편에 서버가 하나 있다면 데이터를 보내고 받는데 오래 걸리기 때문에) 속도 문제를 해결하기 위해 여러 서버를 쓰려고 결정했다고 가정합시다. 각 사용자들은 그들의 지역 데이터센터에서 응답을 받지만, 변경들은 비동기적으로 전파됩니다. 두 사람이 서로에 대해 모르고 변경을 만들었다면 어떤 변경이 먼저인지 알기 어렵습니다.
이를 극단적으로 받아들여, 로컬 디바이스를 데이터 센터로 처리하고, 변경을 네트워크 호출을 수행해 나중에 동기화해야 하더라도, 문제는 여전히 깃헙과 워드 문서에서 봤던 버전 충돌로 해결됩니다.
결과적 일관성은 동시성을 허용하는 시스템을 설명하기 위해 사용되는 데이터베이스 용어입니다. 결과적 일관성이라는 용어의 문제는 모호하다는 것입니다. 결과적 일관성에 관련된 세 가지 쟁점을 봅시다.
네트워크를 통해 메시지를 보내고, 네트워크가 중단되지 않는다고 가정합시다. 장비가 영원히 오프라인될 수 있다고 가정하면 다시 다른 장비와 동기화를 할 수 없기 때문에 이런 가정을 해야 합니다. 결과적으로는 메시지가 전달될 거라 가정하지만 얼마나 빨리 될지는 가정하지 말아야 합니다.
모든 사람이 결국 모든 메시지를 받는다고 가정하면 모두 같은 상태가 되어야 합니다. 다른 순서로 메시지를 받더라도 말입니다.
어떤 데이터베이스 사용자들은 '마지막 작성자가 이긴다,' (Last Writer Wins)라고 불리는 모드를 사용합니다. (주: Realm의 서버 데이터 동기화와 카산드라의 충돌 해결이 LWW입니다.) 두 사람이 데이터를 같이 변경하면 한 변경이 타임 스탬프에 기반해 제멋대로 승자가 됩니다. 이런 유형의 시스템은 변경이 유실되기 때문에 사람들에게 친화적이지 못합니다.
JSON 문서로 할일 목록을 정의하겠습니다. 각 할일은 제목과 상태를 의미하는 'Done' 플래그를 가집니다. 이런 자료구조를 가지면 다양한 변경을 만들 수 있습니다. 편집 연산은 JSON 문서의 특정 필드에 값을 대입합니다. 사용자는 할일 목록의 항목의 문자열을 수정하거나 항목 사이에 새로운 항목을 추가합니다.
이 문서를 트리로 모형화할 수 있고 여기에 데이터 주석을 달 수 있습니다. 예를 들어 최상위 수준 문서가 맵이라 가정하고 이 안에 'To-do' 키에 목록이 있다고 합시다.
이를 충돌이 없는 복제 JSON 데이터타입이라 할 수 있습니다.
우리의 데이터 구조를 사용한 만든 기본 텍스트 편집기가 두개가 있습니다. 한쪽에서 무언가를 입력하면 다른 곳에 뜹니다. 두 편집기는 네트워크 연결을 통해 통신합니다.
서버를 꺼서 둘 사이의 네트워크 중단 처럼 만들어 에디터가 오프라인이 되게 하겠습니다. 왼쪽에 변경을 하면 오른쪽에서는 뜨지 않을 것입니다.
다시 서버를 가동하면 백그라운드에서 에디터는 서버에 자동으로 재연결을 하고 왼쪽에 있던 것이 오른쪽에 뜹니다. 여기에 3방향 머지(three-way merge) 사용자 인터페이스같은 것은 없었어요.
H, E, L, O 문자들을 가진 문서를 생각해봅시다. 각 문자는 0, 1, 2, 3이라는 위치 인덱스를 가집니다.
각 편집기가 이를 편집합니다. 왼쪽의 편집기에서 'Helo'로 바꾸기 위해 두 번째 L 문자를 추가합니다. 오른쪽 편집기에서는 'Hello!'를 만들기 위해 느낌표를 끝에 추가합니다.
'L'을 세 번째 위치에서 누르면 O가 네번째로 옮겨갑니다. 클라이언트는 차이를 서버에게 보내고 서버는 이를 클라이언트에게 전달합니다. 오른쪽 편집기에서는 L은 세 번째 위치에 추가됩니다.
세 번째 위치에 동시 추가가 있었기 때문에, 왼쪽 편집기에서 다섯번 째에 느낌표가 삽입되기 위해, 네 번째 위치가 다섯 번째로 변경되어야 합니다.
서버는 이런 모든 이벤트를 동시적으로 따라가고, 메시지를 바꾸고 인덱스를 3에서 4로 다시 작성해야 합니다.
위의 내용을 할 수 있는 알고리즘을 운영 변환 (Operational Transformation)이라 부릅니다. 이는 학계에는 1980년대에 처음 논의되었습니다.
대부분의 현대 운영 변환 기반의 시스템은 구글 문서가 기반으로 하고 있는 주피터(Jupiter)에서 상속됩니다. 주피터의 설계는 몇가지 변환을 위해 중앙 서버를 사용합니다.
연산 변환은 구글의 목적에 잘 맞았습니다만, 종단간 암호화와 함께 사용하려면 메시지를 변환하는 한 대의 서버를 가질 수 없습니다. 대신, 메시지를 CRDT(Conflict-Free Replicated Datatype, 충돌이 없는 복제 데이터타입)에게 전달할 필요가 있습니다.
CRDT는 충돌이 없는 복제 데이터타입 (Conflict Free Replicated Datatypes)의 줄임말입니다. CRDT는 여러 노드가 동시에 데이터를 변경하고 자동으로 머지될 수 있는 데이터 구조군으로 정의 됩니다.
텍스트 문서를 모형화하기 위해, 정렬된 목록으로 데이터타입을 합니다. 여기에서 텍스트 편집기는 한국 연구 그룹에서 2011년에 나온 RGA (Replicated Growable Array)를 기반으로 합니다. (주: RGA는 http://csl.skku.edu/papers/jpdc11.pdf 에서 볼 수 있습니다.)
예제 문서를 사용하고, 각 문자에 인덱스 0, 1, 2, 3 대신 0a, 1a, 2a, 3a와 같은 유일한 식별자를 사용하겠습니다.
클라이언트가 편집하면 그 문자에 새 식별자를 만듭니다. 식별자는 전역적으로 유일하며, 어떤 순서 속성을 가져야 합니다.
다음 규칙에 의해 식별자를 만듭니다.
- 각 식별자는 숫자와 문자여야 합니다.
- 숫자로서는 문서의 가장큰 수보다 커야 합니다.
이 경우에 다음 숫자 식별자는 4가 되어야 합니다. 왼쪽은 노드 A라고 하고 오른쪽은 노드 B라고 합시다.
양측에서 숫자 4를 사용하고 다른 노드를 가지기 때문에 다른 식별자를 가지게 됩니다. 변경은 서버나 P2P 네트워크를 통해 보내집니다.
이 명령은 엄밀하게 특정한 위치에 추가하는 대신 더 서술적입니다. 대화로 옮기면 이렇게 될겁니다. "2a 위치 뒤에 L을 추가하고 4a로 합시다.' 우리는 어떤 변환 작업없이 네트워크에 메시지를 전달합니다.
JSON 문서를 동시에 편집하는 고유한 시나리오가 있습니다.
색상들의 맵이 있는 완전한 JSON 구조를 가정해봅시다. 한 사람이 전체 맵을 지우고 다른 사람이 녹색을 맵에 추가한다면 어떻게 동시 수정을 합쳐야 할까요?
해법은 맵을 빈 상테로 설정하는 것의 의미를 살펴보는 것입니다. 특히 맵이 비워졌을 때의 상태가 무엇인지 기억하는게 중요합니다. Casual Context라고 알려진 것이 있습니다. React와 같은 프레임워크는 이런 데이터 타입 특성을 가지고 있습니다. HTTP 헤더를 통해 상태를 추적해 적용해야 하는 변경 사항을 알게 하는 것입니다.
사용자 충돌 해결 코드를 작성할 필요없이 자동으로 병합할 수 있는 여러 자료구조는 가치가 있습니다. 여전히 동시성은 어렵습니다. 동시적인 소통을 추상화한다 하더라도 동시 소통을 제대로 다루지 못한 채 병합 상태에 빠질 수 있습니다.