자신만의 데이터베이스를 만들어보기

• 키-값 데이터베이스의 기본 원리와 구현 과정을 설명함
• 파일 시스템을 통한 영속적 저장과 검색 방식에서 시작함
• 데이터 추가, 수정, 삭제 운영 시 비효율적인 문제점 발생함
• Append-Only 파일, 인덱스, 정렬, 세그먼트 압축 등 점진적으로 효율적 구조로 발전함
• LSM 트리 같은 현대적 구조로 연결되며 실제 대규모 시스템에서 활용 중임

서론: 직접 만드는 데이터베이스의 시작

만약 데이터베이스라는 개념이 없다고 가정하고, 자신만의 데이터베이스를 어떻게 만들 수 있을지 단계별로 탐구함
가장 단순한 형태의 키-값 데이터베이스를 직접 구현하는 과정을 살펴봄

기본 아이디어: 파일을 활용한 영구 저장

• 데이터베이스의 목적은 데이터를 영구적으로 저장하고, 나중에 효율적으로 검색하는 것임
• 가장 흔한 방법은 파일 시스템을 이용하여 각 key-value 쌍을 파일에 기록하는 것임
• 데이터를 저장할 때, 예를 들어 $ db set 1 "Lorem ipsum" 형식으로 파일에 내용을 추가함
• 데이터를 검색하려면 파일 내의 모든 key-value 쌍을 순차적으로 확인하며 원하는 key를 찾는 방법 사용함
• 수정 시 해당 key의 값을 파일 내에서 직접 바꿔치기, 삭제 시 해당 레코드를 파일에서 제거하는 방식임

문제점: 비효율적인 In-Place 수정

• 파일 내 데이터를 직접 수정, 삭제하는 방식은 매우 비효율적임
• 파일은 단순한 바이트 스트림이므로, 중간 데이터를 변경하면 그 뒤의 모든 데이터 이동이 필요함
• 예를 들어, 특정 레코드를 새 값으로 바꿀 때 데이터 길이가 달라지면 이어지는 모든 내용을 이동해야 하는 부담 발생함
• 데이터가 많아질수록 속도와 효율에 큰 영향을 끼침

개선 1: Append-Only 파일 구조

• 수정 및 삭제 시 기존 데이터는 그대로 두고, 새로운 기록만 파일 끝에 추가하는 방식 적용
• 데이터가 변경될 때마다 새 레코드를 추가하고, 가장 마지막의 key 값을 검색하도록 알고리듬을 변경함
• 삭제는 특별한 "tombstone" 값(null 등)으로 표시
• 장점: 기존 데이터 이동 없이 효율적 기록 가능
• 단점: 중복 데이터, 삭제 표시 등으로 인해 파일이 점점 커짐
• 검색 속도는 여전히 느림(전체 순회 필요)

개선 2: 파일 크기 관리와 압축(compaction)

• 파일이 무한히 커지는 문제를 해결하기 위해, 일정 크기 이상 파일이 커지면 새 파일(세그먼트)로 넘기고 이전 파일에서 불필요한 데이터(중복/삭제된 것)를 제거하여 크기를 줄임(compaction)
• compaction 시, 진짜 필요한 데이터만 남기고 낡은 기록이나 삭제 표시만 남아 있는 것은 삭제함
• 여러 개의 segment 파일로 관리하여, 필요시 이들을 머지(merge)하는 구조로 발전

개선 3: 인덱스(Index)를 통한 빠른 검색

• key별로 파일 내 위치(offset)를 담은 인메모리(hash table) 인덱스를 구성하여, 빠른 검색 가능함
• 검색 시 인덱스를 우선 조회해 바로 파일에서 해당 위치를 읽음
• trade-off: 검색 속도는 빠르나, 인덱스가 인메모리에 있으므로 key 수가 많아지면 메모리 한계 발생
• 인덱스 관리 때문에 쓰기 성능은 다소 저하됨

개선 4: 정렬(Sorted String Tables)과 Sparse Index

• key를 기준으로 항상 정렬된 상태로 저장하면 범위 질의(range query) 시 높은 효율 확보 가능
• 정렬 상태를 이용하면, 인덱스를 모든 key가 아니라 일부 key에 대해서만(스파스 인덱스) 저장해도 됨
• 인덱스의 밀도를 조절해, 메모리 사용량과 검색 효율 사이에서 트레이드오프를 조정 가능함

구현 방식: 인메모리-온디스크 결합 및 영속성 확보

• 신규 데이터는 우선 정렬된 인메모리 리스트에 기록하고, 추가로 append-only 파일에 기록해 백업 역할 수행
• 인메모리 리스트가 커지면 이를 온디스크 파일(SST)에 정렬하여 저장하며, 인덱스를 업데이트함
• 조회 시 메모리 먼저 확인, 없으면 인덱스를 이용해 디스크에서 검색함
• 온디스크 파일은 불변(immutable) 로 관리, 수정·삭제도 신규 데이터 추가로 처리
• 불필요한 중복/삭제된 데이터는 주기적으로 compaction 하여 파일 크기를 관리함

LSM 트리(Log-Structured Merge Tree) 등장

• 위의 발전된 구조는 실제로 LSM 트리라는 이름으로 널리 사용 중임
• 인메모리(memtable) 와 온디스크(sorted string table, SST) 의 결합 구조로, 빠르고 대규모 환경에 적합함
• LevelDB, Amazon DynamoDB 등 대규모 키-값 데이터베이스 시스템에서 핵심 데이터 구조로 사용되고 있음
• 단점 및 다른 구조(B-Tree 기반 관계형 DB 등)와의 차이점도 있으나, 대량 트래픽-확장에 뛰어난 성능 증명함

결론

• 단순 파일 기반부터 시작해 append-only, 인덱스, 정렬, 세그먼트-컴팩션, 인메모리-온디스크 조합을 더하며 더 나은 데이터베이스 설계로 발전함
• 데이터베이스의 내부 동작과 구조적 고민을 직접 구현 과정을 통해 학습 가능함
• LSM 트리 구조가 현대 대규모 데이터 시스템에서 표준적 역할을 함
• 향후 관계형 데이터베이스의 B-Tree 구조 등 다양한 방식 탐구 여지 남아 있음