반-엔트로피
같은 데이터를 여러 곳에 복제해 두면 사본끼리 값이 갈라지는 순간이 옵니다. 반-엔트로피는 그 갈라짐을 쓰기 시점에 막지 않기로 한 결정입니다. 대신 사본끼리 정기적으로 내용을 맞대 보고 다른 곳만 고칩니다. 어긋남을 못 생기게 하는 쪽이 아니라 생긴 뒤에 걷어내는 쪽입니다.
상세
반-엔트로피(anti-entropy)는 사본 사이의 차이를 배경에서 주기적으로 지우는 결정입니다. 이 이름을 정의로 굳힌 Xerox PARC 의 논문은 한 문장으로 이것을 적습니다. 모든 사이트가 정기적으로 다른 사이트를 무작위로 하나 고릅니다. 그 사이트와 데이터베이스 내용을 교환합니다. 그렇게 둘 사이의 차이를 해소합니다.
결정의 자리는 시점입니다. 쓰기가 지나가는 경로에서 사본을 맞추지 않습니다. 어긋난 채로 두었다가 주기가 돌아올 때 맞춥니다. 그래서 이것은 한 번 돌고 끝나는 절차가 아니라 계속 도는 유지 활동입니다.
flowchart TD
P["주기가 돌아온다"] --> C["상대 사이트를 무작위로 하나 고른다"]
C --> X["두 사이트가 데이터베이스 내용을 교환한다"]
X --> R["둘 사이의 차이를 해소한다"]
R --> P
비교 대상은 데이터베이스 내용 자체입니다. 논문은 이 방식이 데이터베이스의 내용을 들여다보기를 요구한다고 적습니다. 무엇을 어떤 단위로 비교할지는 이 결정이 정해 주지 않습니다. 해시를 계층으로 쌓아 다른 가지만 찾아 내려가는 구현이 그 자리를 채운 사례입니다.
이 논문은 갱신을 퍼뜨리는 방식 셋을 나란히 놓고 그 하나로 반-엔트로피를 정의합니다. 나머지 둘은 direct mail 과, 새 갱신을 뜨거운 소문처럼 들고 다니며 아직 못 받은 사이트에 흘리는 rumor mongering 입니다.
대가
논문은 반-엔트로피를 아주 믿을 만하다고 적습니다. 그리고 같은 문장에서 값을 함께 적습니다. 이 방식은 데이터베이스의 내용을 들여다보기를 요구하며 그래서 너무 자주 쓸 수는 없습니다. 주기를 촘촘하게 당기는 손잡이가 처음부터 막혀 있는 셈입니다.
퍼지는 속도도 내줍니다. 논문은 분석과 시뮬레이션의 결과로, 반-엔트로피가 믿을 만하기는 하지만 direct mail 보다 갱신을 훨씬 느리게 퍼뜨린다고 적습니다. 같은 대목이 rumor mongering 과도 견줍니다. 소문 주기는 사이트마다 자원을 덜 쓰기 때문에 반-엔트로피 주기보다 잦게 돌 수 있습니다. 대신 갱신이 모든 사이트에 닿지 않을 가능성이 어느 정도 있습니다. 한 주기에 드는 자원이 더 큰 쪽이 반-엔트로피입니다.
주기를 못 지키면 없던 실패 경로가 생깁니다. Apache Cassandra 공식 문서는 최소한 복구되지 않은 데이터에서 gc grace period 가 만료되지 않을 만큼은 자주 복구를 돌려야 한다고 적습니다. 그러지 않으면 지운 데이터가 되살아날 수 있습니다. 문서는 gc grace period 기본값 10일을 놓고, 클러스터의 모든 노드를 최소 7일에 한 번 복구하면 이것을 막으면서 지연을 감당할 여유도 남는다고 적습니다. 사본을 맞추는 일이 운영 일정이 되는 자리입니다.
예시
Apache Cassandra 의 nodetool repair
Cassandra 공식 문서는 복구가 노드 사이의 데이터를 동기화하는 방식을 이렇게 적습니다. 노드들이 공통으로 맡은 토큰 구간에 대해 각자의 데이터셋을 비교하고, 어긋난 구간의 차이를 노드 사이로 스트리밍합니다. 비교에는 해시의 계층 구조인 머클 트리를 씁니다.
nodetool repair # 증분 복구. 기본값이다
nodetool repair --full # 전체 복구
복구는 두 종류입니다. 전체 복구는 복구 대상 토큰 구간에 있는 데이터 전부를 훑습니다. 증분 복구는 직전 증분 복구 이후에 쓰인 데이터만 복구합니다. 문서는 증분 복구가 기본이라고 적습니다.
Amazon Dynamo 의 머클 트리
Dynamo 논문 4.7절 「Handling permanent failures: Replica synchronization」은 사본 사이의 불일치를 더 빨리 찾고 옮기는 데이터 양을 줄이려고 머클 트리를 쓴다고 적습니다. 머클 트리는 해시 트리입니다. 잎은 키 하나하나의 값을 해시한 것입니다. 위쪽 부모 노드는 자기 자식들의 해시입니다. 논문이 드는 머클 트리의 주된 이점은 트리의 각 가지를 독립적으로 검사할 수 있다는 것입니다. 노드가 트리 전체나 데이터셋 전체를 내려받지 않아도 됩니다.
절차는 이렇습니다. 노드마다 자기가 맡은 키 구간별로 머클 트리를 따로 유지합니다. 키 구간은 가상 노드가 담당하는 키의 집합입니다. 두 노드가 공통으로 맡은 키 구간에 해당하는 머클 트리의 루트를 교환합니다. 그 다음 트리를 타고 내려가며 차이가 있는지 판정하고 알맞은 동기화 동작을 합니다. 논문은 이렇게 하면 동기화를 위해 옮겨야 하는 데이터 양이 줄고 anti-entropy 과정에서 수행되는 디스크 읽기 횟수도 줄어든다고 적습니다.
같은 문단이 이 방식의 단점도 적습니다. 노드가 시스템에 들어오거나 나가면 많은 키 구간이 바뀌고, 새 구간에 대한 머클 트리를 다시 계산해야 합니다.
갈래
두 사이트가 차이를 발견했을 때 어느 쪽이 어느 쪽을 고치느냐가 축입니다. 논문은 두 서버가 협력해 수행하는 resolveDifference 절차를 설계에 따라 세 가지로 적고, 각각에 push, pull, push-pull 이라는 이름을 붙입니다. 두 사이트가 가진 값의 타임스탬프를 견주는 것은 셋이 같습니다.
push
s 가 가진 값의 타임스탬프가 s' 쪽보다 크면 s' 의 값을 s 의 값으로 덮어씁니다. 반대 방향은 하지 않습니다. 고쳐지는 쪽이 언제나 상대입니다.
sequenceDiagram
participant S as 사이트 s
participant T as 사이트 s'
S->>T: 자기 값과 타임스탬프를 내민다
Note over T: s 쪽이 더 최신이면 자기 값을 덮어쓴다
pull
반대 방향입니다. s' 쪽 타임스탬프가 s 보다 크면 s 가 자기 값을 s' 의 값으로 덮어씁니다. 고쳐지는 쪽이 언제나 상대를 고른 자기 자신입니다.
sequenceDiagram
participant S as 사이트 s
participant T as 사이트 s'
T->>S: 자기 값과 타임스탬프를 내민다
Note over S: s' 쪽이 더 최신이면 자기 값을 덮어쓴다
push-pull
둘을 한 번에 합친 것입니다. 타임스탬프가 큰 쪽 값으로 작은 쪽을 맞춥니다. 두 값의 타임스탬프가 같으면 아무것도 하지 않습니다.
sequenceDiagram
participant S as 사이트 s
participant T as 사이트 s'
S->>T: 자기 값과 타임스탬프를 내민다
T->>S: 자기 값과 타임스탬프를 내민다
Note over S,T: 타임스탬프가 큰 쪽으로 작은 쪽을 맞춘다
셋 중 무엇을 고를지는 상황이 정합니다. 논문은 다른 배포 수단이 이미 갱신 대부분을 퍼뜨려 놓아 아직 못 받은 사이트가 몇 남지 않은 경우를 놓고 셋을 견줍니다. 그 경우 행동의 큰 차이는 push 와 pull 사이에 있고 push-pull 은 사실상 pull 처럼 움직입니다. 그래서 논문은 반-엔트로피를 direct mail 같은 다른 배포 수단의 백업으로 쓸 때 pull 이나 push-pull 이 push 보다 훨씬 낫다고 적습니다. push 는 그 예상되는 경우에 제대로 움직이지 않습니다.
관련 항목
이것이 속하는 상위 분류
이것을 대신할 수 있는 다른 수단
2단계 커밋 · rumor mongering · direct mail
사본을 맞추는 다른 손잡이
읽기 복구 · 힌티드 핸드오프 · 정족수 · 느슨한 정족수 · 충돌 해소
비교와 복구에 동원되는 요소
머클 트리 · 해시 · 타임스탬프 · 토큰 구간 · 가상 노드 · 툼스톤
이것이 지키는 성질
최종 일관성 · 가용성 · CAP(Consistency Availability Partition tolerance, 일관성·가용성·분할내성)
이것을 실제로 구현·채택한 제품
Apache Cassandra · Amazon Dynamo · Riak · Grapevine · Clearinghouse
다른 이름: anti-entropy · 안티 엔트로피