영속 자료구조

영속 자료구조는 값을 고쳐도 고치기 전의 모습을 지우지 않습니다. 고칠 때마다 새 버전을 하나 내놓습니다. 옛 버전은 남겨 둡니다. 새 버전은 바뀌지 않은 부분을 옛 버전과 나눠 씁니다. 디스크에 오래 저장한다는 뜻의 영속성과는 다른 말입니다.

상세

이 절은 고치면 옛 모습이 사라지는 보통의 자료구조에서 출발합니다. 그다음 원소 두 개짜리 연결 리스트와 키 일곱 개짜리 트리로 옛 버전을 싸게 남기는 방법을 따라갑니다.

고치면 옛 모습이 사라지는 자료구조

흔히 쓰는 자료구조는 값을 고칠 때 원래 메모리를 덮어씁니다. 리스트 앞에 원소를 끼우면 그 리스트 자체가 바뀝니다. 아래는 그 모습을 의사 코드로 적은 것입니다.

a = [2, 3]
a.addFirst(1)       // a = [1, 2, 3]

addFirst 를 부른 뒤로 [2, 3] 이라는 모습은 어디에도 없습니다. 이렇게 고치면 옛 모습이 사라지는 자료구조를 일시적 자료구조(ephemeral data structure)라고 부릅니다.

대부분의 코드는 이것으로 충분합니다. 곤란해지는 것은 옛 모습이 다시 필요할 때입니다. 아래 표가 그런 일 셋을 모읍니다.

세 줄 모두 원인이 같습니다. 고치는 연산이 옛 모습을 지우기 때문입니다.

옛 버전을 남기는 영속 자료구조

영속 자료구조(persistent data structure)는 고치는 연산이 원래 구조를 바꾸지 않고 새 구조를 돌려줍니다. 고치기 전의 구조를 옛 버전, 돌려받은 구조를 새 버전이라고 부릅니다. 두 버전 모두 온전하게 읽힙니다.

a = [2, 3]
b = a.addFirst(1)   // b = [1, 2, 3]
a                   // a = [2, 3]

addFirst 가 a 를 고치지 않고 새 리스트 b 를 돌려줬습니다. a 는 여전히 [2, 3] 입니다. 앞 소절의 표에 적은 세 가지 일이 이 성질 하나로 풀립니다.

옛 버전을 쥐고 있으면 되돌릴 수 있습니다. 읽는 스레드는 자기가 쥔 버전만 보므로 쓰는 쪽과 부딪히지 않습니다. 어느 시점의 버전을 변수 하나에 담아 두면 그것이 곧 그 시점의 모습입니다.

이름의 「영속」은 디스크에 저장한다는 뜻이 아닙니다. 데이터베이스에서 말하는 영속성은 프로그램이 꺼져도 데이터가 남는 성질입니다. 영속 자료구조는 메모리 안에서 고친 뒤에도 옛 버전이 남는다는 뜻입니다.

통째로 복사하는 방법

옛 버전을 남기는 가장 쉬운 방법은 고칠 때마다 전부 복사하는 것입니다. 복사본을 고치면 원본은 손대지 않은 채 남습니다. 쓸 때마다 복사본을 만들어 거기에 쓰는 방식을 쓰기 시 복사라고 부릅니다.

자바의 CopyOnWriteArrayList 가 이렇게 합니다. 원소를 하나 넣을 때마다 배열 전체를 새로 복사합니다. 이미 목록을 훑고 있던 쪽은 복사 전의 배열을 끝까지 봅니다.

문제는 비용입니다. 원소가 n 개면 한 번 고칠 때마다 n 개를 복사합니다. 이것을 빅오 표기법으로 O(n) 이라고 적습니다. 원소 수에 비례해 시간이 든다는 뜻입니다. 메모리도 버전마다 n 칸씩 늘어납니다.

영속 자료구조는 이 복사를 줄이는 기법의 모음입니다. 바뀐 부분만 새로 만들고 나머지는 옛 버전과 나눠 씁니다. 이것을 구조적 공유(structural sharing)라고 부릅니다.

연결 리스트에서 꼬리를 나눠 쓰기

구조적 공유가 가장 쉽게 보이는 곳은 연결 리스트입니다. 연결 리스트는 원소를 담은 노드가 다음 노드를 가리키며 줄지어 이어진 구조입니다. 맨 앞 노드를 머리라고 부릅니다.

a = [2, 3] 앞에 1 을 붙여 봅니다. 새 노드 1 을 하나 만듭니다. 그 노드가 a 의 머리 노드 2 를 가리키게 하면 끝입니다.

flowchart TD
    B["b"] --> N1["1 · 새로 만든 노드"]
    A["a"] --> N2["2"]
    N1 --> N2
    N2 --> N3["3"]

b 는 노드 1 에서 출발해 [1, 2, 3] 을 읽습니다. a 는 노드 2 에서 출발해 여전히 [2, 3] 을 읽습니다. 노드 2 와 3 은 두 리스트가 함께 씁니다. 새로 만든 노드가 하나뿐이라 리스트 길이와 상관없이 O(1) 에 끝납니다.

이 공유에는 조건이 붙습니다. 나눠 쓰는 노드는 아무도 고치면 안 됩니다. b 를 고치려다 노드 2 의 값을 바꾸면 a 까지 함께 바뀌기 때문입니다. 그래서 영속 자료구조의 노드는 만든 뒤 바꾸지 않는 불변 객체로 둡니다.

복사가 번지는 범위

이번에는 a = [2, 3] 의 맨 끝 3 을 30 으로 바꿔 봅니다. 노드 3 은 고칠 수 없으니 30 을 담은 노드를 새로 만듭니다. 그런데 노드 2 는 여전히 옛 노드 3 을 가리킵니다.

노드 2 도 고칠 수 없으므로 새 노드 30 을 가리키는 노드 2 를 하나 더 만들어야 합니다. 이렇게 바뀐 노드를 가리키는 노드는 전부 복사됩니다. 그 노드를 가리키는 노드도 마찬가지로 복사됩니다.

연결 리스트에서는 바뀐 노드 앞의 노드가 모두 복사 대상입니다. k 번째 원소를 바꾸면 노드 k 개를 새로 만듭니다. 맨 앞을 고치면 노드 하나로 끝납니다. 맨 끝을 고치면 리스트 전체를 복사하는 셈입니다.

앞뒤 노드를 서로 가리키는 이중 연결 리스트는 더 곤란합니다. 모든 노드가 양쪽으로 사슬처럼 이어져 있어 하나만 바꿔도 전부 복사됩니다. 복사를 줄이려면 바뀐 노드에서 거슬러 올라가며 복사해야 하는 노드가 적은 모양이 필요합니다.

트리에서 바뀐 길만 복사하기

트리에서 한 노드를 가리키는 것은 부모 하나뿐입니다. 그 부모를 가리키는 것도 그 위의 부모 하나뿐입니다. 그래서 한 노드를 바꾸면 그 노드에서 맨 위 루트까지 올라가는 길 위의 노드만 복사하면 됩니다. 이 방법을 경로 복사(path copying)라고 부릅니다.

키 일곱 개를 담은 이진 탐색 트리에 8 을 넣어 봅니다. 이진 탐색 트리는 어느 노드에서 봐도 왼쪽 아래에 더 작은 키를, 오른쪽 아래에 더 큰 키를 두는 트리입니다.

이 트리는 루트가 4 이고, 그 왼쪽 자식이 2, 오른쪽 자식이 6 입니다. 2 아래에는 1 과 3 이, 6 아래에는 5 와 7 이 달립니다. 8 은 어느 키보다 크므로 오른쪽으로만 내려갑니다. 4, 6, 7 을 차례로 지나 7 의 오른쪽 자식으로 들어갑니다.

아래 그림에서 버전 1 은 8 을 넣기 전이고 버전 2 는 넣은 뒤입니다. 굵은 점선 테두리가 새로 만든 노드입니다.

flowchart TD
    V1["버전 1 의 루트 · 4"]
    V2["버전 2 의 루트 · 4 사본"]
    V1 --> N2["2"]
    V1 --> N6["6"]
    V2 --> N2
    V2 --> M6["6 사본"]
    N2 --> N1["1"]
    N2 --> N3["3"]
    N6 --> N5["5"]
    N6 --> N7["7"]
    M6 --> N5
    M6 --> M7["7 사본"]
    M7 --> N8["8 · 새로 넣은 키"]
    classDef copy stroke-width:3px,stroke-dasharray:5 3
    class V2,M6,M7,N8 copy

지나온 길의 4, 6, 7 만 사본을 만들었습니다. 노드 2 · 1 · 3 · 5 넷은 두 버전이 함께 가리킵니다. 옛 노드는 하나도 바뀌지 않았습니다.

버전 1 의 루트에서 출발하면 8 이 보이지 않습니다. 버전 2 의 루트에서 출발하면 보입니다. 두 버전이 노드 넷을 나눠 쓰면서도 서로 다른 트리로 읽힙니다.

복사되는 노드 수는 트리의 높이만큼입니다. 넣고 지울 때마다 모양을 손봐 높이를 낮게 붙잡는 트리를 균형 이진 탐색 트리라고 부릅니다. 이런 트리의 높이는 log n 에 비례합니다.

log n 은 n 을 몇 번 반으로 나눠야 1 이 되는지 세는 값입니다. 키가 백만 개여도 20 쯤입니다. 그래서 한 번 고칠 때 새로 만드는 노드도 수십 개에 그칩니다. 넣은 뒤 균형을 다시 맞추는 일도 이 길 근처의 노드만 건드리므로 복사량은 O(log n) 에 머뭅니다.

노드에 버전마다 값을 적어 두는 방법

복사하지 않고 버전을 남기는 방법도 있습니다. 노드를 새로 만드는 대신 노드 안에 「버전 몇부터는 이 값」이라는 기록을 덧붙입니다. 이런 노드를 뚱뚱한 노드(fat node)라고 부릅니다.

고칠 때는 기록을 한 줄 붙이기만 하므로 필드 하나에 O(1) 입니다. 대신 읽을 때마다 노드 안의 기록에서 원하는 버전의 값을 찾아야 합니다.

기록은 버전 순으로 둡니다. 그러면 이진 탐색으로 찾을 수 있습니다. 지금까지 고친 횟수를 m 이라 하면 읽을 때 O(log m) 이 더 듭니다.

이 방법은 노드 안에 기록을 덧붙이므로 노드를 불변으로 둘 수 없습니다. 값을 바꾸지 못하게 막아 둔 함수형 프로그래밍 언어에서는 쓸 수 없습니다. 그런 언어는 구조적 공유와 경로 복사로 영속 자료구조를 만듭니다.

고칠 수 있는 버전의 범위

옛 버전을 읽기만 할 수 있는지, 고칠 수도 있는지에 따라 이름이 갈립니다. 아래 표가 셋을 모읍니다.

부분 영속에서는 버전이 한 줄로 이어집니다. 완전 영속에서는 옛 버전을 고칠 수 있어 한 버전에서 여러 버전이 갈라져 나옵니다. 아래 그림이 두 모양을 나란히 보입니다.

flowchart TD
    subgraph 부분["부분 영속 · 최신 버전만 고친다"]
        P1["버전 1"] --> P2["버전 2"] --> P3["버전 3"]
    end
    subgraph 완전["완전 영속 · 어느 버전이든 고친다"]
        F1["버전 1"] --> F2["버전 2"]
        F1 --> F3["버전 3 · 버전 1 을 다시 고친 결과"]
        F2 --> F4["버전 4"]
    end

경로 복사로 만든 불변 구조는 저절로 완전 영속입니다. 어느 버전의 루트에서 출발해 고쳐도 새 루트가 하나 생길 뿐입니다. 다른 버전의 노드는 하나도 바뀌지 않습니다.

연산별 비용

아래 표는 지금까지 본 방식들의 비용을 나란히 놓습니다. n 은 원소 수이고 m 은 지금까지 고친 횟수입니다.

경로 복사는 고치기를 O(n) 에서 O(log n) 으로 줄입니다. 대신 배열이라면 O(1) 이던 한 칸 읽기에도 트리 높이만큼이 듭니다.

옛 버전이 사라지는 때

버전이 쌓이기만 하면 메모리가 끝없이 늘 것처럼 보입니다. 하지만 아무 변수도 가리키지 않는 버전은 다시 쓸 길이 없습니다. 변수 a 를 버리면 a 의 루트에서만 닿던 노드는 어디서도 닿지 않습니다.

이런 노드를 치우는 것이 가비지 컬렉션입니다. 프로그램이 더는 닿을 수 없는 메모리를 찾아 자동으로 거둬 갑니다. 다른 버전과 나눠 쓰던 노드는 아직 닿을 수 있으므로 남습니다.

가비지 컬렉션이 없는 언어에서는 노드마다 자기를 가리키는 수를 세어 둡니다. 그 수가 0 이 되면 노드를 치웁니다. 이 방법을 참조 카운팅이라고 부릅니다.

버전을 남기는 대가

첫째 대가는 메모리 할당입니다. 일시적 자료구조라면 값 하나만 덮어쓸 일에 노드를 몇 개씩 새로 만듭니다. 옛 노드는 쓰레기로 남아 가비지 컬렉션이 할 일이 그만큼 늘어납니다.

둘째는 메모리 접근입니다. 고칠 때마다 새로 만든 노드가 메모리 여기저기에 흩어집니다.

프로세서는 메모리를 읽을 때 이웃한 메모리까지 캐시에 함께 올려 둡니다. 그래서 배열처럼 이웃한 칸을 차례로 읽는 구조는 다음 읽기가 캐시에서 끝납니다. 이 성질을 캐시 지역성이라고 부릅니다. 노드를 하나씩 따라가는 구조는 다음 노드가 멀리 있기 쉬워 이 덕을 덜 봅니다.

셋째는 한 칸을 고치는 비용입니다. 배열의 한 칸을 바꾸는 O(1) 이 트리를 거치며 O(log n) 이 됩니다.

이 비용을 줄이는 흔한 방법은 노드마다 자식을 수십 개씩 두는 것입니다. 자식이 많으면 트리 높이가 낮아지고, 그만큼 덜 내려갑니다. 자식이 32 개라면 네 층에 원소 백만 개 남짓이 담깁니다.

영속 배열은 흔히 이런 트라이로 만듭니다. 트라이는 키를 앞에서부터 조각내어 조각마다 자식 하나를 고르며 내려가는 트리입니다. 배열이라면 인덱스가 그 키입니다.

옛 버전이 필요 없는 코드에서는 이 대가들이 얻는 것 없이 남습니다. 버전을 쥘 일이 없으면 일시적 자료구조를 고릅니다.

불변 자료구조와 가르는 기준

불변 자료구조는 만든 뒤 고칠 수 없는 자료구조입니다. 고치는 연산이 아예 없을 수도 있습니다. 영속 자료구조는 고치는 연산을 주되 결과를 새 버전으로 돌려줍니다.

둘은 자주 겹칩니다. 경로 복사로 만든 영속 자료구조는 노드가 전부 불변이라 불변 자료구조이기도 합니다. 반대로 뚱뚱한 노드로 만든 영속 자료구조는 안에서 노드를 고치므로 불변이 아닙니다.

쓰는 곳

함수형 언어는 값을 바꾸지 않는 것을 기본으로 삼습니다. 그래서 기본 리스트와 맵이 영속 자료구조입니다. Haskell 의 리스트, Clojure 의 벡터와 맵, Scala 의 불변 컬렉션이 그렇습니다.

Git 의 커밋도 같은 모양입니다. 커밋마다 바뀐 파일과 디렉터리만 새로 저장합니다. 안 바뀐 것은 앞 커밋이 저장한 것을 가리킵니다. 바뀐 파일에서 맨 위 디렉터리까지의 길만 새로 생기므로 경로 복사와 같은 꼴입니다.

파일 시스템과 저장 엔진에도 같은 방식이 있습니다. 파일 시스템 Btrfs 와 저장 엔진 LMDB(Lightning Memory-Mapped Database)가 그렇습니다. 둘은 데이터를 B-tree 에 담습니다. B-tree 는 디스크에서 한 번에 읽기 좋게 노드마다 키를 많이 담은 트리입니다.

이들은 B-tree 의 노드를 고치지 않습니다. 바뀐 노드에서 루트까지의 길만 새 위치에 씁니다. 앞에서 본 경로 복사와 같은 동작입니다. 옛 루트는 그대로 남아 그 시점의 모습, 곧 스냅샷이 됩니다.

관련 항목

영속 자료구조가 속하는 상위 분류

자료구조 · 함수형 자료구조 · 불변 자료구조 · 순수 함수형 자료구조

영속 자료구조를 만드는 기법

구조적 공유 · 경로 복사 · 뚱뚱한 노드 · 노드 복사 · 쓰기 시 복사 · 불변 객체

영속 자료구조의 하위 종류

부분 영속 · 완전 영속 · 합류 영속 · 영속 연결 리스트 · 영속 벡터 · 영속 맵

영속 자료구조를 구현하는 바탕 자료구조

연결 리스트 · 이진 탐색 트리 · 균형 이진 탐색 트리 · 레드-블랙 트리 · 트라이 · 해시 배열 매핑 트라이 · 핑거 트리 · B-tree

영속 자료구조와 맞세워지는 대립 개념

일시적 자료구조 · 가변 객체 · 제자리 갱신 · 깊은 복사 · 이중 연결 리스트

영속 자료구조의 비용을 따지는 개념

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 분할 상환 비용 · 트리 높이 · 캐시 지역성

옛 버전을 거둬 가는 메모리 관리 방식

가비지 컬렉션 · 참조 카운팅 · 도달 가능성 · 메모리 누수

영속 자료구조를 기본 컬렉션으로 쓰는 언어

Haskell · Clojure · Scala · OCaml · Erlang · 함수형 프로그래밍

영속 자료구조와 같은 방식으로 버전을 남기는 시스템

Git · Btrfs · LMDB · 스냅샷 · MVCC · 되돌리기

영속 자료구조와 이름이 헷갈리는 이웃

영속성 · 영속성 컨텍스트 · 영속 메모리 · 퍼시스턴트 볼륨