나만의 데이터베이스 구축하기

마

마루쉐

Back-End•2025.11.20

Not a Number 블로그 포스트 번역

작성자: Nanda Syahrasyad

원문: https://www.nan.fyi/database

만약 데이터베이스가 존재한다는 것을 모르고 나만의 데이터베이스를 구축한다면 어떻게 해야 할까요?

이 글에서는 key-value 데이터베이스를 처음부터 구축하는 방법을 살펴보겠습니다.

key-value 데이터베이스는 JavaScript의 객체처럼 작동합니다. 키를 사용하여 값을 저장하고 나중에 같은 키를 사용하여 값을 검색할 수 있습니다:

$ db set 'hello' 'world'
$ db get 'hello'
world

어떻게 작동하는지 알아봅시다!

출처 표기: 이 글은 주로 Martin Kleppmann의 저서 Designing Data-Intensive Applications의 3장 "Data Structures that Power Your Database"를 기반으로 합니다. 읽어보시기를 권장합니다! 제가 읽은 컴퓨터 과학 책 중 가장 훌륭한 책입니다.

겸손한(humble) 파일

데이터베이스는 하나의 문제를 해결하기 위해 만들어졌습니다:

문제

데이터를 지속적으로 저장하고 나중에 효율적으로 검색하려면 어떻게 해야 할까요?

컴퓨터에 모든 종류의 데이터를 지속적으로 저장하는 일반적인 방법은 파일을 사용하는 것입니다. 데이터를 저장하려면 key-value 쌍을 파일에 추가합니다:

특정 키를 찾으려면 쌍을 반복하여 일치하는 키가 있는지 확인합니다:

업데이트의 경우 키를 찾아 값을 제자리에서 바꿉니다:

삭제의 경우 파일에서 레코드를 삭제합니다:

쉽죠! 이제 끝났나요?

변경 가능한 업데이트

이 접근 방식은 단순하지만 실제로는 잘 작동하지 않습니다. 문제는 업데이트와 삭제를 수행하는 방식에 있습니다. 이들은 완전히 비효율적입니다.

컴퓨터에게 저희의 파일은 다음과 같이 보입니다. 단지 긴 바이트 시퀀스일 뿐입니다:

001:Lorem␣ipsum\n018:dolor␣sit\n005:adipiscing␣elit.\n014:Vestibulum␣varius\n002:vel␣mauris\n007:consectetur␣adipiscing␣elit.\n010:Vestibulum␣varius\n016:vel␣mauris\n003:consectetur␣adipiscing␣elit.

레코드를 업데이트하거나 삭제할 때 현재 해당 레코드를 제자리에서 업데이트하고 있습니다. 이는 그 레코드 뒤에 오는 모든 데이터를 이동해야 할 수도 있다는 의미입니다:

001:Lorem␣ipsum\n018:dolor␣sit\n005:adipiscing␣elit.␣vel␣mauris\n014:Vestibulum␣varius\n002:vel␣mauris\n007:consectetur␣adipiscing␣elit.\n010:Vestibulum␣varius\n016:vel␣mauris\n003:consectetur␣adipiscing␣elit.

이 경우 레코드 005를 "adipiscing␣elit.␣vel␣mauris"로 업데이트하면 그 뒤의 모든 레코드를 11바이트(추가된 문자열 "␣vel␣mauris"의 길이)만큼 이동해야 합니다. 특히 데이터베이스가 커질수록 이는 매우 비용이 많이 들 수 있습니다!

Append-Only 파일

업데이트 문제를 해결하는 한 가지 방법은 레코드를 불변으로 만드는 것입니다. 즉, 파일의 끝에만 새 레코드를 추가할 수 있고 기존 레코드를 업데이트하거나 삭제할 수 없다는 제약을 추가합니다.

이 접근 방식을 사용하면 업데이트는 삽입과 동일하게 처리됩니다. 파일의 끝에 새 레코드를 추가하면 됩니다:

$ db set 1 "Lorem ipsum"
$ db set 18 "dolor sit"

하지만 이제 다른 문제가 생겼습니다. 파일에 중복된 키가 있습니다!

이를 해결하기 위해 검색 알고리즘을 변경하여 첫 번째 발생이 아닌 마지막 발생을 찾아야 합니다:

$ db set 1 "Lorem ipsum"
$ db set 18 "dolor sit"

레코드를 삭제하려면 키가 삭제되었음을 표시하는 특수한 "tombstone" 레코드를 만듭니다. 이를 수행하는 단일 방법은 없지만 한 가지 방법은 null과 같은 특수 값을 사용하는 것입니다:

$ db set 1 "Lorem ipsum"
$ db set 18 "dolor sit"

완료되었습니다! 파일을 저장소 메커니즘으로 사용하는 key-value 데이터베이스가 있습니다. 이를 사용하여 key-value 쌍을 저장, 찾기, 업데이트 및 삭제할 수 있습니다.

이제 이 구현이 완벽하지는 않습니다. 현재 두 가지 주요 문제가 있습니다:

파일이 매우 커질 수 있습니다. 파일에만 추가하고 있으므로 파일은 시간이 지남에 따라 무한정 커집니다. 좋지 않습니다!

검색이 느립니다. 특정 키를 검색하려면 데이터베이스의 모든 레코드를 반복해야 할 수도 있습니다. 수백만 개의 레코드가 있는 데이터베이스의 경우 시간이 걸릴 수 있습니다!

이러한 문제를 어떻게 해결할 수 있을까요?

파일 크기 유지하기

문제

파일이 무한정 커지지 않도록 어떻게 보장할까요? append-only 파일을 사용하고 있으므로 파일이 결국 전체 하드 드라이브를 차지하지 않도록 주기적으로 파일을 "축소"할 메커니즘이 필요합니다.

몇 가지 업데이트와 삭제 후 저희의 데이터베이스를 살펴봅시다:

$ db set 1 "Lorem ipsum"
$ db set 18 "dolor sit"
$ db set 7 "adipiscing elit."
$ db delete 7
$ db set 10 "consectetur adipiscing elit."
$ db delete 1

우리의 데이터베이스 파일에는 6개의 항목이 있지만 실제 레코드를 나타내는 것은 2개뿐입니다. 나머지는 삭제되었거나 오래된 데이터를 포함합니다. 모든 관련 없는 데이터를 제거할 수 있다면 파일을 66% 이상 축소할 수 있습니다!

세그먼트와 압축

다음은 아이디어입니다: 파일이 특정 크기를 초과하면 파일을 닫고 새 파일을 만듭니다. 새 파일이 새 데이터를 수집하는 동안(지금까지 해온 것과 같은 방식으로) 이전 파일의 모든 관련 없는 데이터를 삭제하여 압축합니다.

즉, 파일에 새 데이터를 추가하는 것을 중지합니다.

여기서 우리는 최대 파일 크기를 7개 레코드로 설정했습니다. 데이터베이스가 가득 찼습니다. "Add"를 클릭하여 새 레코드를 추가해 보고 어떤 일이 발생하는지 확인해 보세요:

이제 저희의 데이터베이스는 세그먼트라고 부를 두 개의 다른 파일로 구성됩니다. 각 세그먼트는 압축 후 일반적으로 훨씬 작아집니다. 이는 압축 프로세스의 일부로 함께 병합할 수 있다는 의미입니다.

이제 저희의 데이터베이스가 무한정 커지는 것을 방지하는 메커니즘을 만들었습니다!

첫 번째 인덱스

저희의 다음 문제는 검색 성능입니다:

문제

검색을 빠르게 하려면 어떻게 해야 할까요? 현재 특정 키를 찾기 위해 데이터베이스의 모든 레코드를 반복해야 합니다. 이는 매우 느립니다!

객체를 사용하면 어떨까요? 맞습니다. 이 작은 것들입니다:

const hashTable = {};

JavaScript 객체는 hash table 또는 dictionary라고도 불리며 key-value 쌍을 저장하고 검색하는 데 매우 효율적입니다:

const hashTable = {
  hello: "world",
  foo: "bar",
  baz: "qux",
};
const value = hashTable["hello"]; // "world"

레코드가 몇 개이든 상관없이 hash table에서 값을 검색하고 검색하는 데 걸리는 시간은 대략 일정합니다. 단점은 메모리에 있어야 한다는 것입니다.

메모리 내 vs. 디스크 상

코드에서 변수를 작성하면 컴퓨터는 프로그램이 실행되는 동안만 해당 변수의 값을 "기억"합니다.

이 프로그램은 프로그램을 실행할 때마다 x의 값이 "재설정"되기 때문에 항상 2와 3을 출력합니다. 이는 x가 메모리에 저장되고 메모리에 저장된 모든 값은 프로그램이 중지될 때 버려지기 때문입니다.

데이터가 실행 간에 "유지"되도록 하려면 디스크 상에 저장해야 합니다. 즉, 파일입니다.

이번에는 x가 첫 번째 실행에서 2와 3을 출력하고 두 번째 실행에서 4와 5를 출력합니다.

지속성의 대가는 성능입니다. 메모리에서 데이터에 액세스하는 것은 평균적으로 디스크에서 액세스하는 것보다 약 80배 빠릅니다.

인덱스가 어떻게 작동하는지 다음과 같습니다. 데이터베이스의 모든 레코드에 대해 해당 레코드의 offset(파일의 시작부터 레코드의 시작까지의 바이트 수)을 인덱스에 저장합니다:

파일:

1:Lorem␣ipsum\n

인덱스:

001: 0

데이터베이스:

001: Lorem ipsum

예를 들어 두 번째 레코드 18: dolor sit의 offset은 15입니다. 왜냐하면:

각 문자는 1바이트 크기입니다.

첫 번째 레코드는 13자 길이입니다(1:Lorem ipsum).

첫 번째 레코드는 개행 문자로 끝나며, 이는 최대 2바이트입니다.

이는 13 + 2 = 15의 offset을 제공합니다.

주목할 점은 각 세그먼트에 대해 인덱스가 필요하다는 것입니다. offset은 파일의 시작, 즉 각 세그먼트의 시작을 기준으로 하기 때문입니다.

인덱스를 사용한 검색

인덱스를 사용하면 우리의 검색 알고리즘이 훨씬 더 효율적으로 실행될 수 있습니다:

가장 최근 세그먼트부터 시작하여 인덱스에서 키를 검색합니다.

키가 발견되면 offset에서 레코드를 읽습니다.

키가 발견되지 않으면 다음 세그먼트로 이동합니다.

키가 발견되거나 모든 세그먼트가 검색될 때까지 (2)와 (3)을 반복합니다.

인덱스 업데이트

인덱스는 우리의 데이터와 동기화되어 있을 때만 유용합니다. 레코드를 업데이트, 삭제 또는 삽입할 때마다 인덱스를 그에 따라 변경해야 합니다:

이것이 의미하는 바에 주목하세요. 인덱스를 사용하면 데이터베이스에 쓰기가 더 느립니다! 이는 인덱스 사용의 트레이드오프 중 하나입니다. 더 빠른 검색 속도로 더 느린 쓰기 속도를 얻을 수 있습니다.

트레이드오프

인덱스는 데이터베이스를 훨씬 더 빠르게 쿼리할 수 있게 해주지만 저희의 특정 hash table 구현에는 몇 가지 문제가 있습니다:

키가 메모리에 맞아야 합니다. 메모리 내 hash table을 인덱스로 사용하고 있으므로 데이터베이스의 모든 키가 메모리에 맞아야 합니다. 이는 저희가 저장할 수 있는 키의 수에 제한이 있다는 의미입니다!

범위 쿼리는 비효율적입니다. 저희의 인덱스는 검색 쿼리에 도움이 되지 않습니다. 예를 들어 키 12와 18 사이의 모든 레코드를 찾으려면 전체 데이터베이스를 반복해야 합니다!

정렬된 문자열 테이블

다음은 아이디어입니다: 데이터베이스가 항상 키로 정렬되도록 보장하면 어떨까요? 데이터를 정렬하면 범위 쿼리를 즉시 빠르게 만들 수 있습니다:

희소(sparse) 인덱스

데이터를 정렬하는 한 가지 이점은 메모리에 모든 레코드의 offset을 저장할 필요가 없다는 것입니다.

4개의 레코드가 있는 이 데이터베이스를 살펴봅시다. 레코드에 논리적 순서가 없으므로 키를 저장하거나 전체 데이터베이스를 검색하지 않고는 레코드가 어디에 있는지 결정할 방법이 없습니다.

10의 offset이 50이라는 것을 아는 것은 18이 어디에 있는지 찾는 데 도움이 되지 않습니다.

이제 이 레코드들이 정렬되어 있다면 인덱스의 모든 키를 사용하여 각 레코드의 위치를 결정할 수 있습니다. 찾고 있는 키가 아니더라도 말입니다.

데이터베이스가 정렬되어 있지만 키 10의 offset만 있다고 가정해 봅시다:

키 18을 찾고 싶다고 가정해 봅시다. 18이 10보다 크다는 것을 알고 있으므로 데이터베이스에서 10 뒤에 있어야 합니다. 즉, 10의 offset인 36부터 18을 검색하기 시작할 수 있습니다.

이는 18의 offset을 직접 갖는 것보다 확실히 느리지만 여전히 전체 데이터베이스를 반복하는 것보다 빠릅니다.

실제 unlock은 메모리와 성능 간의 트레이드오프를 제어할 수 있다는 것입니다: 더 조밀한 인덱스는 더 빠른 검색을 의미하지만 더 많은 메모리 사용을 의미합니다.

실제 정렬

데이터베이스를 항상 정렬된 상태로 유지하는 것은 말처럼 쉽지 않습니다. 정의상 데이터를 정렬하려면 새 레코드가 추가될 때 레코드를 이동해야 합니다. 디스크에 데이터를 저장할 때는 효율적으로 수행할 수 없습니다. 이것이 저희의 문제입니다:

문제

데이터를 정렬된 상태로 유지하면서 동시에 append-only로 유지하려면 어떻게 해야 할까요? 새 레코드를 추가할 때마다 디스크에서 데이터를 정렬하는 것은 너무 느립니다. 다른 방법이 있을까요?

트릭은 먼저 메모리에서 데이터를 정렬한 다음 디스크에 쓰는 것입니다.

새 레코드를 추가할 때 정렬된 메모리 내 목록에 추가합니다.

메모리 내 목록이 너무 커지면 디스크에 씁니다.

레코드를 읽으려면 먼저 메모리 내 목록을 읽고 필요하면 디스크를 읽습니다.

메모리 내 목록을 저장하는 데 사용되는 데이터 구조는 일반적으로 balanced binary search tree 또는 더 일반적으로 skip list와 같은 정렬된 데이터에 최적화된 것입니다.

물론 일부 데이터를 메모리에 보관하는 주요 단점은 지속적이지 않다는 것입니다. 프로그램이 충돌하거나 컴퓨터가 종료되면 메모리 내 목록의 모든 데이터가 손실됩니다.

다행히 여기서의 해결책은 매우 간단합니다. 목록에 레코드를 추가할 때마다 디스크의 append-only 파일에도 씁니다. 이렇게 하면 충돌이 발생할 경우(확실히 발생할 것입니다) 백업이 있습니다.

append-only 파일은 정렬될 필요가 없으며 데이터베이스의 모든 레코드를 가질 필요도 없습니다. 현재 메모리에 있는 것들만 필요합니다.

이제 우리만의 key-value 데이터베이스가 있습니다! 어떻게 작동하는지 요약해 봅시다.

우리의 데이터베이스는 비어있는 상태로 시작합니다. 새 레코드를 추가하려면 정렬된 메모리 내 목록에 추가하고 충돌에 대비하여 append-only 파일에 복사본을 유지합니다.

메모리 내 목록이 너무 커지면 목록을 flush하여 모든 레코드를 정렬된 순서로 파일에 씁니다. 이 과정에서 나중에 효율적으로 검색할 수 있도록 각 레코드의 offset을 인덱스에 기록합니다.

레코드를 검색하려면 먼저 메모리 내 목록을 확인합니다. 레코드가 없으면 인덱스를 확인하여 디스크 상의 파일에 있는지 확인합니다.

파일이 디스크에 저장되면 불변으로 간주됩니다. 즉, 파일에서만 읽을 수 있고 업데이트할 수 없습니다. 이를 해결하기 위해 업데이트와 삭제를 새 레코드 삽입과 동일하게 처리합니다. 메모리 내 목록에 추가합니다.

업데이트와 삭제를 새 레코드로 처리하면 파일이 계속 커집니다. 이를 방지하기 위해 중복 레코드를 삭제하여 디스크 상의 파일을 압축합니다.

LSM 트리

우리가 방금 구축한 것은 실제로 존재합니다. LSM 또는 Log-Structured Merge Tree라고 불립니다.

LSM 트리는 메모리 내 목록(memtable이라고 불리기도 함)을 디스크 상의 파일(일반적으로 sorted string table 또는 SST라고 불림)과 결합하여 정말 빠른 key-value 데이터베이스를 만듭니다.

LSM 트리는 Google의 LevelDB와 Amazon의 DynamoDB와 같은 대규모 key-value 데이터베이스의 기본 데이터 구조이며 규모에서 정말 잘 작동하는 것으로 입증되었습니다. 2020년 Prime Day에 DynamoDB는 초당 8천만 개의 요청에 도달했습니다!

물론 LSM 트리가 완벽한 것은 아니며 데이터베이스를 구조화하는 유일한 방법도 아닙니다. 실제로 PostgreSQL이나 MySQL과 같은 관계형 데이터베이스는 데이터를 저장하기 위해 B-Tree라고 불리는 완전히 다른 구조를 사용합니다. 하지만 그것은 다른 글의 깊은 주제입니다.

긴글 읽어주셔서 감사합니다!

아직 댓글이 없습니다.

첫 번째 댓글을 작성해보세요!