▲

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

 (nan.fyi)
5P by GN⁺ 13일전 | ★ favorite | 댓글 1개
  • 키-값 데이터베이스의 기본 원리와 구현 과정을 설명함
  • 파일 시스템을 통한 영속적 저장과 검색 방식에서 시작함
  • 데이터 추가, 수정, 삭제 운영 시 비효율적인 문제점 발생함
  • 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 구조 등 다양한 방식 탐구 여지 남아 있음
▲
GN⁺ 13일전  [-]
Hacker News 의견
  • 이 글의 디자인과 예시가 정말 마음에 듦 읽기 쉬운 구성이 인상적임 이런 연습 자체도 매우 재미있는 경험임 아무것도 없는 상태에서 시작해보면 자신이 얼마나 알고 있는지 진정한 검증이 가능함
    • 나 역시 예전에는 "직접 데이터베이스를 만들지 말고, KV 데이터베이스도 쓰지 말고 그냥 SQL을 써라"는 조급한 태도를 보였음 근데 그 생각조차 직접 DB 설계하거나 KV 데이터베이스만 쓰려고 SQL을 피해보려다 결국엔 SQL을 엉성하게 재창조하게 된 후에야 갖게 된 것이었음 직접 겪으면서 배우는 가치가 분명히 있음
    • 한 가지 아쉬운 점은 예시로 lorem ipsum을 쓴 것임 덕분에 집중하지 않고 대충 넘기게 됨 실제 데이터 예제가 훨씬 더 관심을 끌게 함 그 외엔 정말 멋진 글임
  • “LSM 트리는 DynamoDB 등에서 기본적으로 사용되는 데이터 구조이고, 대규모 환경에서도 매우 좋은 성능을 보여줌… 초당 8천만 번 요청도 가능함”이라고 하는데, 살짝 오해의 소지가 있음 LSM은 노드 단의 스토리지 엔진에 쓰이는데, 분산 시스템 전체가 8천만 rps로 확장되는 과정은 설명하지 않음 내가 기억하기로는, 원래 Dynamo 논문에서는 BerkeleyDB(b-tree 또는 LSM)를 썼고 2012년 논문에서 완전히 LSM 기반 엔진으로 전환함
  • 글 목록의 몇몇 아티클을 클릭해봤는데, 디자인과 애니메이션이 정말 예쁨 감탄함
  • "Sorting in Practice" 부분의 첫 번째 예제가 깨져있는 것 같음 설명 글에는 메모리에서 정렬 후 정렬된 상태로 디스크에 쓰여야 한다고 나와 있는데, 실제 예제에선 디스크에 쓸 때 정렬이 풀림 recap 부분의 flush 예제(2번째)도 마찬가지인데, 문구는 정렬 상태로 파일에 기록된다고 되어 있음
  • 흥미로운 글이었음 최근 개발자 활동을 타임 시리즈 키-값 시스템으로 모델링하는 중임 각 개발자를 키로, 커밋을 값으로 함 비슷한 문제를 맞닥뜨림: 로그가 빠르게 커지고, 인덱스가 무거워지고, 범위 쿼리가 느려짐 세그먼트 압축(compaction)할 때 어떤 데이터를 버릴지 어떻게 결정하는지 궁금함 신선함과 보존 기간의 균형 맞추기가 어렵다고 느낌
  • 지난 4주 동안 triple store를 직접 작성하는 데 몰두하고 있었음 이 글이 조금만 빨리 나왔더라면 더 빨리 이해했을 인사이트가 몇 가지 있었음 아쉬움
  • 만약 저자가 이 글을 본다면, 사이트에 RSS 피드를 추가해줄 수 있는지 궁금함 feedly에 추가해서 읽고 싶음
  • 자신만의 데이터베이스를 만들어보고 싶다면 이 무료 온라인 책을 꼭 추천함
    • 예전에 누군가 bash 예제로 데이터베이스의 기본 개념을 설명한 아티클(예: "bash로 DB 만들기")이 이곳에 소개된 기억이 있는데 찾아볼 수가 없음 혹시 누가 해당 링크를 알고 있으면 공유해줬으면 함
  • 이미 트래픽이 너무 많아서 사이트가 접속 불가 상태임
    • 더 빠른 데이터베이스가 필요하겠음
  • 이렇게 "최초 원리(First Principles)"부터 차근차근 설명하는 방식이 정말 마음에 듦 이 글을 따라가다 보면 매 단계마다 어떤 문제가 발생하고, 또 그걸 풀 때 어떤 추가 문제가 생기는지 명확히 이해 가능함 덕분에 참 만족스러운 해결 방식에 도달할 수 있음
답변달기