부분 순서

부분 순서는 앞뒤를 정할 수 있는 쌍에만 순서를 매깁니다. 나머지 쌍은 비교할 수 없는 쌍으로 남겨 둡니다. 모든 것을 한 줄로 세우지 않으므로 원래 앞뒤가 없는 쌍에 억지로 앞뒤를 매기지 않습니다. 작업 사이의 의존 관계와 분산 시스템의 사건 순서가 이런 모양입니다.

상세

아침에 옷을 입을 때 양말은 신발보다 먼저 신습니다. 바지도 벨트보다 먼저 입습니다. 그런데 양말과 셔츠는 어느 쪽을 먼저 입어도 괜찮습니다.

옷을 입는 순서처럼 일부 쌍에만 앞뒤가 있는 모양이 부분 순서입니다. 이 절은 작업 다섯 개로 된 빌드 하나로 부분 순서를 봅니다. 먼저 앞뒤가 정해진 쌍과 비교할 수 없는 쌍을 가릅니다. 그다음 순서라고 부르려면 지켜야 할 성질 셋을 세웁니다. 끝으로 분산 시스템의 사건 두 개로 비교할 수 없는 쌍이 무엇을 알려 주는지 봅니다.

빌드 작업 다섯 개의 앞뒤

빌드 하나가 작업 다섯 개로 이루어져 있다고 해 봅시다. 의존성 받기, 컴파일, 테스트, 문서 생성, 패키징입니다. 어떤 작업은 다른 작업이 끝나야 시작할 수 있습니다.

의존성을 받아야 컴파일과 문서 생성을 할 수 있습니다. 컴파일이 끝나야 테스트를 돌립니다. 테스트와 문서 생성이 둘 다 끝나야 패키징을 합니다.

아래 그림은 이 앞뒤를 화살표로 잇습니다. 화살표를 따라 한쪽에서 다른 쪽으로 닿으면 앞뒤가 정해진 쌍입니다.

flowchart TD
    A["의존성 받기"] --> B["컴파일"]
    A --> D["문서 생성"]
    B --> C["테스트"]
    C --> E["패키징"]
    D --> E

컴파일에서 화살표를 따라가면 테스트를 거쳐 패키징에 닿습니다. 그래서 컴파일은 패키징보다 앞입니다. 둘을 잇는 화살표를 따로 긋지 않아도 앞뒤가 정해집니다.

테스트와 문서 생성 사이에는 어느 방향으로도 길이 없습니다. 이런 쌍을 비교할 수 없는 쌍이라고 부릅니다. 둘 가운데 무엇을 먼저 해도 패키징은 둘이 다 끝난 뒤에 시작합니다. 그래서 두 작업은 동시에 돌려도 됩니다.

부분 순서는 이렇게 일부 쌍에만 앞뒤를 정하는 순서입니다. 「부분」은 모든 쌍이 아니라 일부 쌍이라는 뜻입니다. 부분 순서가 매겨진 모음을 부분 순서 집합이라고 부릅니다.

순서라고 부르려면 지킬 성질 셋

화살표를 아무렇게나 그으면 순서가 되지 않습니다. 이 소절은 부분 순서가 늘 지키는 성질 셋을 봅니다. 성질을 적으려면 기호가 하나 필요합니다.

이 문서에서 a ≤ b 는 「a 가 b 보다 앞이거나, a 와 b 가 같다」로 읽습니다. 앞인 것과 같은 것을 한 기호로 묶으면 성질을 짧게 적을 수 있습니다.

셋 가운데 빌드에서 바로 부딪히는 것은 반대칭성입니다. 컴파일과 테스트가 서로를 기다리면 둘 다 시작하지 못합니다. 이런 고리를 순환 의존성이라고 합니다. 고리가 생기면 반대칭성이 깨지므로 그 관계는 부분 순서가 아닙니다.

추이성은 앞의 그림에서 컴파일과 패키징 사이에 화살표를 긋지 않아도 된 까닭입니다. 앞뒤가 이어지면 처음과 끝의 앞뒤는 저절로 따라 나옵니다.

고리가 없는 방향 그래프를 DAG(Directed Acyclic Graph, 방향 비순환 그래프)라고 합니다. DAG 에서 화살표를 따라 닿는 관계는 부분 순서입니다. 자기 자신에는 늘 닿은 것으로 칩니다.

거꾸로도 됩니다. 유한한 부분 순서에서 앞뒤가 정해진 쌍마다 앞에서 뒤로 화살표를 그으면 고리 없는 그래프가 나옵니다. 그래서 유한한 부분 순서는 DAG 로 그릴 수 있습니다.

앞의 그림은 추이성으로 따라 나오는 화살표를 빼고 바로 이웃한 앞뒤만 그렸습니다. 이렇게 그린 그림을 하세 도표라고 합니다. 따라 나오는 화살표까지 다 그리면 원소가 늘수록 선이 엉켜 모양이 안 보이기 때문입니다.

엄격한 부분 순서

≤ 대신 < 로 적는 방식도 있습니다. a < b 는 「a 가 b 보다 앞이고 둘이 같지 않다」입니다. 이렇게 적은 순서를 엄격한 부분 순서라고 합니다.

엄격한 부분 순서에서는 어떤 것도 자기 자신보다 앞이 아닙니다. 이 성질을 비반사성이라고 합니다. 추이성은 ≤ 로 적을 때와 같이 지킵니다.

≤ 와 < 는 같은 순서를 두 방식으로 적은 것입니다. 하나를 알면 다른 하나를 곧바로 얻습니다. 사건의 순서를 따지는 happens-before 는 < 쪽으로 적습니다. 사건이 자기 자신보다 먼저 일어날 수는 없기 때문입니다.

전체 순서와의 차이

모든 쌍에 앞뒤가 정해지는 순서를 전체 순서라고 합니다. 정수의 크기 비교가 전체 순서입니다. 어떤 두 정수를 골라도 한쪽이 작거나 둘이 같습니다.

전체 순서는 부분 순서에 성질 하나를 더한 것입니다. 모든 쌍을 비교할 수 있어야 한다는 성질입니다. 그래서 전체 순서는 늘 부분 순서이지만 거꾸로는 아닙니다.

전체 순서는 줄 하나로 늘어놓을 수 있습니다. 그래서 선형 순서라고도 부릅니다. 부분 순서는 빌드 그림처럼 갈라졌다가 다시 모이는 모양이 됩니다.

흔히 만나는 부분 순서

부분 순서는 빌드 밖에서도 자주 나옵니다. 아래 표는 백엔드 개발에서 만나는 부분 순서를 모읍니다. 줄마다 비교할 수 없는 쌍을 하나씩 붙였습니다.

여섯 줄은 대상이 달라도 모양이 같습니다. 앞뒤가 정해진 쌍이 있습니다. 비교할 수 없는 쌍도 남습니다.

지키는 성질도 같습니다. 어느 줄이든 ≤ 로 적으면 성질 셋을 지킵니다. < 로 적으면 비반사성과 추이성을 지킵니다.

비교할 수 없는 쌍이 알려 주는 것

비교할 수 없는 쌍은 빈칸처럼 보입니다. 이 소절은 그 빈칸이 무엇을 알려 주는지 분산 시스템의 사건 두 개로 봅니다.

서버 두 대가 같은 키의 값을 거의 같은 때 고쳤다고 해 봅시다. 두 서버는 상대가 고친 것을 모르는 채 고쳤습니다. 두 수정은 서로에게 영향을 줄 수 없었으므로 비교할 수 없는 쌍입니다. 이런 두 사건을 동시라고 부릅니다.

두 수정에 시각을 찍어 줄을 세우면 한쪽이 「나중」이 됩니다. 나중인 쪽 값만 남기면 다른 쪽 수정은 알림 없이 사라집니다. 이 방식을 last-write-wins 라고 부릅니다.

부분 순서로 두면 두 수정이 비교할 수 없는 쌍으로 드러납니다. 시스템은 두 값을 다 남겨 두고 충돌 해소를 거칠 수 있습니다. 비교할 수 없다는 것이 곧 「둘이 서로 모르고 고쳤다」는 정보입니다.

이 비교를 번호로 하는 방법이 벡터 시계입니다. 벡터 시계는 사건마다 서버 수만큼 칸을 둔 번호 묶음을 붙입니다. 칸 하나가 서버 하나를 맡습니다. 그 칸의 번호는 그 서버에서 일어난 사건 가운데 이 사건까지 전해진 사건의 수입니다.

[1, 0] 은 첫 서버의 사건 하나만 전해진 사건입니다. [0, 1] 은 둘째 서버의 사건 하나만 전해진 사건입니다. [2, 1] 에는 첫 서버의 사건 둘과 둘째 서버의 사건 하나가 전해졌습니다.

아래 함수는 두 묶음을 칸마다 견줍니다. a 의 모든 칸이 b 의 같은 칸보다 작거나 같은지 봅니다. 그렇다면 a ≤ b 입니다. 오른쪽 주석이 각 호출의 결과입니다.

def leq(a, b):
    return all(x <= y for x, y in zip(a, b))

leq([1, 0], [2, 1])   # True
leq([1, 0], [0, 1])   # False
leq([0, 1], [1, 0])   # False

첫 호출은 두 칸 모두 a 쪽이 작거나 같으므로 True 입니다. [1, 0] 에 전해진 사건은 [2, 1] 에도 모두 전해졌습니다. 그래서 [1, 0] 의 사건이 [2, 1] 의 사건보다 앞입니다.

둘째와 셋째 호출은 같은 두 묶음을 방향만 바꿔 견줍니다. 첫 칸은 [1, 0] 쪽이 큽니다. 둘째 칸은 [0, 1] 쪽이 큽니다. 어느 방향으로 견줘도 False 인 이 쌍이 비교할 수 없는 쌍, 곧 동시인 두 사건입니다.

램포트 시계는 칸 하나짜리 번호를 붙입니다. 번호가 정수라 모든 쌍을 견줄 수 있습니다. 대신 번호만 보고는 두 사건이 앞뒤인지 동시인지 가리지 못합니다.

한 줄로 펴는 위상 정렬

부분 순서를 한 줄로 세워야 할 때가 있습니다. 빌드 작업을 한 번에 하나씩만 돌리는 기계가 그렇습니다. 이 소절은 정해진 앞뒤를 하나도 어기지 않고 한 줄로 세우는 방법을 봅니다.

정해진 앞뒤를 모두 지키는 전체 순서를 선형 확장이라고 합니다. 비교할 수 없던 쌍에만 앞뒤를 새로 정한 순서입니다. 유한한 부분 순서에는 선형 확장이 언제나 하나 이상 있습니다.

앞에 아무것도 없는 원소를 극소 원소라고 합니다. 빌드에서는 의존성 받기처럼 다른 작업을 기다리지 않는 작업입니다. 원소가 하나라도 있는 유한한 부분 순서에는 극소 원소가 적어도 하나 있습니다.

선형 확장을 찾는 절차가 위상 정렬입니다. 극소 원소를 하나 꺼내 줄 끝에 세웁니다. 그 원소를 지우고 남은 원소에서 같은 일을 되풀이합니다.

빌드 예에서 위상 정렬은 둘 이상의 답을 냅니다. 「의존성 받기, 컴파일, 테스트, 문서 생성, 패키징」이 답입니다. 「의존성 받기, 문서 생성, 컴파일, 테스트, 패키징」도 답입니다. 두 답은 비교할 수 없던 쌍의 순서만 다릅니다.

고리가 있으면 위상 정렬은 답을 내지 못합니다. 고리 안의 원소는 모두 앞에 다른 원소가 있어서 꺼낼 원소가 떨어지기 때문입니다. 빌드 도구가 순환 의존성을 찾으면 멈추는 까닭이 이것입니다.

부분 순서로 둘 때와 한 줄로 세울 때

대상 사이의 관계가 의존·포함·인과처럼 일부 쌍에만 성립하면 부분 순서로 둡니다. 비교할 수 없는 쌍은 동시에 돌리거나 충돌로 드러낼 수 있습니다.

모든 대상을 한 줄로 보여 주거나 하나씩 처리해야 하면 전체 순서가 필요합니다. 이때는 선형 확장을 하나 골라 씁니다. 비교할 수 없던 쌍의 순서는 임의로 고른 것이라 아무 뜻도 담고 있지 않습니다.

부분 순서의 대가는 비교할 수 없는 쌍을 따로 다뤄야 한다는 것입니다. 흔한 정렬 함수는 모든 쌍을 견줄 수 있다고 가정합니다. 비교할 수 없는 쌍을 「같다」로 돌려주는 비교 함수를 넘기면 정해진 앞뒤를 어긴 줄이 나올 수 있습니다.

줄 「테스트, 문서 생성, 컴파일」을 예로 듭니다. 이웃한 두 쌍은 모두 비교할 수 없는 쌍이라 「같다」가 나옵니다. 이웃끼리만 견주는 정렬은 이 줄을 그대로 둡니다. 컴파일이 테스트 뒤에 남습니다.

위상 정렬은 답이 여럿이어도 어느 답이든 정해진 앞뒤를 지킵니다. 그래서 부분 순서를 한 줄로 세울 때는 정렬 대신 위상 정렬을 씁니다.

관련 항목

부분 순서를 이루는 성질

반사성 · 반대칭성 · 추이성 · 비반사성

부분 순서를 넓히거나 좁힌 순서 개념

전체 순서 · 엄격한 부분 순서 · 원순서 · 약한 순서 · 격자 · 선형 확장

부분 순서를 그리고 한 줄로 펴는 도구

하세 도표 · DAG · 위상 정렬 · 극소 원소 · 극대 원소 · 사슬 · 반사슬 · 정렬

부분 순서가 속하는 상위 분류

관계 · 집합 · 순서 이론 · 이산 수학 · 그래프

사건의 앞뒤를 부분 순서로 적는 분산 시스템 개념

happens-before · 램포트 시계 · 벡터 시계 · 논리 시계 · 버전 벡터 · 인과 관계 · 인과 일관성 · 동시성

비교할 수 없는 쌍을 다루는 방법

충돌 해소 · last-write-wins · CRDT · 병렬 처리

백엔드 개발에서 부분 순서를 이루는 관계

의존성 그래프 · 빌드 도구 · 순환 의존성 · 상속 · 하위 타입 · 역할 계층