충돌 해소

충돌 해소는 이름 하나로 세 가지 다른 일을 가리킵니다. 해시테이블에서는 같은 칸에 배정된 두 키를 어디에 놓을지 정합니다. 복제본에서는 갈라진 두 버전 가운데 무엇을 남길지 정합니다. 버전관리에서는 같은 자리를 고친 두 변경을 사람이 하나로 만듭니다.

상세

세 자리가 공유하는 뼈대는 하나입니다. 하나뿐인 무엇을 둘이 동시에 요구합니다. 그 자리를 어떻게 할지 정하는 대응이 해소입니다. 그 대응의 모양은 자리마다 다릅니다.

갈리는 자리는 셋입니다. 무엇이 부딪혔나, 해소가 끝나면 무엇이 남나, 누가 정하나입니다.

부딪히는 것부터 다릅니다. 해시테이블에서 부딪히는 것은 자리입니다. 미국 국립표준기술연구소(NIST, National Institute of Standards and Technology)가 내는 알고리즘·자료구조 사전은 충돌을 둘 이상의 항목이 같은 위치에 놓여야 하는 상황으로 정의합니다. 특히 서로 다른 둘 이상의 키가 같은 값으로 해싱되는 경우입니다. 두 키의 내용이 갈라진 것이 아닙니다. 두 키는 원래 서로 다릅니다. 해시 함수가 둘을 같은 값으로 보낼 뿐입니다. 복제본에서 부딪히는 것은 버전입니다. CouchDB 공식 문서는 같은 이름 아래에 놓인 충돌하는 리비전들이라고 적습니다. 버전관리에서 부딪히는 것은 변경입니다. Git 공식 문서는 양쪽이 같은 영역에 가한 변경이라고 적습니다.

남는 것도 다릅니다. 해시테이블 쪽은 어느 항목도 버리지 않습니다. 해소는 그 자리를 어떻게 나눠 쓸지 정하는 절차입니다. 복제본 쪽은 한쪽이 사라질 수 있습니다. CouchDB 문서가 적는 영구적 해소는 병합본을 쓴 뒤 충돌 리비전들을 지우는 것입니다. 버전관리 쪽에 남는 것은 사람이 정한 최종본 하나입니다.

정하는 주체도 다릅니다. 해시테이블에서는 해시테이블 자신의 절차가 자리를 정합니다. 복제본에서 저장소가 하는 일은 읽기 시점에 승자 하나를 보여주는 것까지입니다. 실제 해소는 응용이 합니다. 버전관리에서 최종본을 정하는 것은 사람입니다.

그래서 충돌 해소라는 말만으로는 무엇을 하는 일인지가 정해지지 않습니다. 맥락 이름을 먼저 대야 뜻이 섭니다.

맥락별 뜻

맥락	뜻	출처
해시테이블	서로 다른 키가 같은 위치에 배정됐을 때 각 항목을 어느 자리에 둘지 정하는 방식	NIST Dictionary of Algorithms and Data Structures — collision · open addressing · separate chaining
복제본	갈라진 두 리비전 가운데 무엇을 남길지 응용이 정한 뒤 나머지를 지우는 일	CouchDB Documentation — Replication and conflict model
버전관리	같은 영역을 고친 두 변경을 사람이 최종본 하나로 만드는 일	Git Documentation — `git-merge`, HOW CONFLICTS ARE PRESENTED · HOW TO RESOLVE CONFLICTS

해시테이블

알고리즘·자료구조 사전은 충돌을 정의한 자리에 충돌 해소 방식을 함께 걸어 둡니다. 개방 주소법 표제는 모든 항목을 해시테이블 안에 저장하는 충돌 해소 방식들의 묶음이라고 적습니다. 충돌이 나면 다른 위치들을 계산해 탐사 순서를 만듭니다. 빈 자리를 찾을 때까지 그 순서대로 확인합니다. 새 위치를 계산하는 방법 가운데 일부는 클러스터링 때문에 효율이 떨어진다고 적습니다. 항목은 한번 놓이면 대개 다시 움직이지 않습니다. 다만 로빈 후드 해싱을 비롯한 몇몇 배치 기법에서는 앞서 놓인 항목이 움직일 수 있습니다. 탐사 순서로는 선형 탐사·이차 탐사·이중 해싱·균등 해싱이 실려 있습니다.

분리 연쇄법 표제는 해시테이블의 각 위치가 충돌을 처리할 리스트를 갖는 방식이라고 적습니다. 각 위치는 리스트를 가리키는 링크 하나이거나, 항목 하나와 링크 한 쌍입니다. 뒤쪽이면 항목 하나가 표 안에 남습니다. 함께 충돌한 나머지 항목들은 리스트에 들어갑니다. 외부 연쇄법이라고도 부릅니다.

두 방식 다 항목을 버리지 않습니다. 개방 주소법은 모든 항목을 표 안에 둡니다. 분리 연쇄법은 표 밖의 리스트에 매답니다. 개방 주소법 표제가 붙인 주석도 같은 자리를 짚습니다. 충돌을 해소하려고 외부 자료구조를 쓰는 연쇄법이나 별도의 오버플로 영역 하나를 두는 방식에는 보통 말하는 클러스터링이 없습니다.

flowchart TD
    A["키"] --> B["해시 함수"]
    B --> C{"그 위치가 비었나"}
    C -->|비었다| D["그 위치에 넣는다"]
    C -->|찼다 · 충돌| E["개방 주소법 · 빈 자리까지 탐사"]
    C -->|찼다 · 충돌| F["분리 연쇄법 · 그 위치의 리스트에 붙인다"]

복제본

CouchDB 공식 문서는 앨리스의 예로 이 맥락을 엽니다. 앨리스는 밥의 명함을 담은 문서 하나를 데스크톱 컴퓨터와 노트북 사이에서 동기화합니다. 데스크톱에서 밥의 전자우편 주소를 고칩니다. 다시 동기화하지 않은 채 노트북에서 밥의 휴대전화 번호를 고칩니다. 그리고 둘을 서로 복제합니다. 데스크톱 문서에는 새 전자우편 주소와 옛 번호가 있습니다. 노트북 문서에는 옛 전자우편 주소와 새 번호가 있습니다.

이때 무슨 일이 벌어지는지에 대한 문서의 답은 간단합니다. 두 버전이 양쪽에 모두 존재합니다. 파일 시스템이 아니라서 같은 이름의 문서가 하나만 존재해야 한다는 제약이 없습니다. 같은 이름 아래의 충돌하는 리비전들일 뿐입니다. 변경은 언제나 복제되므로 데이터는 안전하다고 적습니다.

읽을 때의 기본 동작은 따로 있습니다. 문서를 그냥 읽으면 충돌에 대한 정보가 보이지 않습니다. 임의의 리비전 하나를 결정론적 알고리즘으로 고른 승자만 보입니다. 다른 충돌 리비전이 있는지 없는지에 대한 표시도 없습니다. 같은 알고리즘이 모든 피어에서 같은 선택을 하게 만듭니다. 충돌을 보려면 질의에 conflicts=true 를 붙입니다. 문서가 충돌 상태이면 승자와 함께 _conflicts 항목이 옵니다. 거기에 다른 충돌 리비전들의 리비전 값이 배열로 실립니다. 리비전 값을 지정한 읽기로 하나씩 가져올 수 있습니다.

영구적 해소는 그 뒤의 일입니다. 저장소가 아니라 응용이 합니다. 충돌 리비전을 전부 가져온 다음 응용은 그것들을 사용자에게 전부 보여줄 수 있습니다. 또는 병합을 시도해 병합본을 다시 쓴 뒤 충돌 리비전들을 지울 수 있습니다. 문서는 그것이 충돌을 영구적으로 해소하는 것이라고 적습니다. 리비전 하나를 갱신해야 합니다. 나머지 충돌 리비전은 명시적으로 전부 지워야 합니다.

sequenceDiagram
    participant 데스크톱
    participant 노트북
    participant 응용
    데스크톱->>노트북: 복제
    노트북->>데스크톱: 복제
    Note over 데스크톱,노트북: 두 리비전이 양쪽에 다 남는다
    응용->>데스크톱: 읽기
    데스크톱-->>응용: 임의의 결정론적 승자 하나
    응용->>데스크톱: 병합본 쓰기 · 나머지 리비전 삭제

버전관리

Git 공식 문서는 병합이 도는 동안 워킹 트리 파일이 병합 결과를 반영하도록 갱신된다고 적습니다. 공통 조상 버전을 기준으로 겹치지 않은 변경은 그대로 최종 결과에 들어갑니다. 한쪽이 어느 영역을 고쳤을 때 다른 쪽은 그 영역을 건드리지 않은 경우입니다. 양쪽이 같은 영역을 고쳤을 때는 다릅니다. Git 은 한쪽을 임의로 고를 수 없다고 말합니다. 그리고 양쪽이 그 영역에 한 일을 그대로 남겨 두는 방식으로 해소를 요청합니다.

남기는 모양도 문서가 적어 둡니다. 기본값은 RCS(Revision Control System) 모음의 merge 프로그램이 쓰던 것과 같은 방식입니다. 충돌한 덩이가 <<<<<<< 와 ======= 와 >>>>>>> 세 표식으로 감싸여 파일에 들어갑니다. ======= 앞이 대개 내 쪽입니다. 뒤가 대개 상대 쪽입니다. 공통 조상에서 안 바뀐 줄, 한쪽만 고쳐서 깨끗하게 풀린 줄, 양쪽이 같은 방향으로 고쳐서 깨끗하게 풀린 줄은 표식 밖에 그대로 놓입니다.

충돌을 본 다음 할 수 있는 일은 둘이라고 문서가 적습니다. 병합하지 않기로 정하거나, 충돌을 해소하는 것입니다. 해소는 사람의 손을 거칩니다. Git 은 워킹 트리에 충돌을 표시해 둡니다. 사람이 파일을 원하는 모양으로 고칩니다. git add 로 인덱스에 올립니다. git commit 또는 git merge --continue 로 마무리합니다.

flowchart TD
    A["공통 조상 · 양쪽 변경"] --> B{"양쪽이 같은 영역을 고쳤나"}
    B -->|아니다| C["그대로 최종 결과에 반영"]
    B -->|그렇다| D["워킹 트리에 충돌 표식을 남기고 멈춘다"]
    D --> E["사람이 파일을 고친다"]
    E --> F["git add"]
    F --> G["git commit · git merge --continue"]

배경

세 문서의 정의문은 나란히 「같은 무엇」이라는 조건으로 사건을 세웁니다. 알고리즘·자료구조 사전은 같은 위치에 놓여야 하는 항목들이라고 적습니다. CouchDB 문서는 같은 이름 아래의 충돌하는 리비전들이라고 적습니다. Git 문서는 양쪽이 같은 영역을 고쳤을 때라고 적습니다. 위치·이름·영역으로 대상은 다릅니다. 하나뿐인 것을 둘이 요구했다는 형태는 같습니다.

어느 쪽을 그 자리에 둘지, 아니면 둘 다 두는 방법이 있는지를 정하는 일에 붙은 이름이 해소입니다. 세 문서가 각각 collision resolution scheme, resolve the conflict, HOW TO RESOLVE CONFLICTS 라는 이름으로 그 자리를 부릅니다. 다만 그 일을 누가 언제 하는지는 갈립니다. 개방 주소법은 빈 자리를 찾을 때까지 다른 위치들을 확인해 표 스스로 자리를 정합니다. CouchDB 는 두 리비전을 양쪽에 다 남긴 채 읽기 시점에 승자 하나를 보여줍니다. 영구적 해소는 응용의 몫으로 남습니다. Git 은 한쪽을 임의로 고르지 않습니다. 충돌 표식을 워킹 트리에 남기고 사람에게 해소를 요청합니다.

부딪힘 자체를 부르는 영어 낱말은 갈립니다. 해시테이블 쪽은 collision 을 씁니다. 복제본과 버전관리 쪽은 나란히 conflict 를 씁니다. 왜 이렇게 갈렸는지는 세 문서 어디에도 적혀 있지 않습니다. 갈렸다는 사실까지가 이 문서들이 말하는 전부입니다.

경계

암호학적 해시 함수에서 말하는 충돌도 해소하는 것인가. 아닙니다.

정의문만 보면 해시테이블 쪽과 겹쳐 보입니다. 미국 국립표준기술연구소 특별 간행물 800-107 개정 1판은 충돌을 서로 다른 두 메시지가 같은 메시지 다이제스트를 갖는 사건으로 정의합니다. 서로 다른 두 입력이 같은 값으로 간다는 형태가 알고리즘·자료구조 사전의 정의와 같습니다.

바로 다음 줄이 태도를 가릅니다. 같은 문서는 충돌 저항성을 해시 함수에 기대되는 성질로 정의합니다. 충돌 하나를 찾아내는 것이 계산적으로 실행 불가능하다는 성질입니다. 해시 함수 성질 절은 같은 말을 조건으로 다시 적습니다. 같은 해시 값을 갖는 서로 다른 두 입력을 찾아내는 것이 계산적으로 실행 불가능해야 합니다. 그리고 그 값을 재는 방법을 적습니다. 높은 확률로 충돌 하나를 찾는 데 드는 작업량이 2의 N제곱이면 충돌 저항성은 N 비트입니다.

그래서 이 자리의 충돌에는 해소 절차가 붙지 않습니다. 해시테이블의 충돌은 정상 동작 중에 일어납니다. 뒤를 받는 절차가 알고리즘·자료구조 사전에 표제로 실려 있습니다. 개방 주소법과 분리 연쇄법입니다. 암호학적 해시 함수의 충돌은 찾는 데 드는 작업량으로 값이 매겨지는 대상입니다. 이름은 같지만 해소가 붙는 자리가 아니라서 이 표제어에 들어오지 않습니다.

충돌 해소

상세

맥락별 뜻

해시테이블

복제본

버전관리

배경

경계

관련 항목

해시테이블에서 자리를 나누는 개념

복제 충돌 해소를 구현·채택한 시스템

복제 충돌 해소가 다루는 개념

Git 병합이 쓰는 내부 구조

충돌 해소를 매듭짓는 Git 명령

헷갈리는 이웃

충돌 해소가 갈리는 세 맥락

충돌 해소가 속하는 상위 주제

충돌 해소를 실제로 구현·채택한 제품

충돌 해소 각 맥락을 정의하는 표준·문서