A write-ahead log is not a universal part of durability

오늘 아침에 재미있게 읽었습니다. Qdrant는 WAL을 durability 보장을 위해 사용합니다. MongoDB는 disk flush하지 않고 success를 반환한다고 합니다.
WAL이 좋은 디자인인지는 모르겠지만 성능이 웬만한 디스크를 사용한다면 괜찮다고 생각이 듭니다.

선행 기록(WAL)의 필요성:

• WAL은 대부분의 데이터베이스에서 지속성을 위해 중요하지만, 반드시 필요한 것은 아닙니다.
• 데이터베이스는 WAL 없이도 지속성을 달성할 수 있지만, 이는 좋은 방법은 아닙니다.
• 이 글은 WAL 없이 지속성을 가진 데이터베이스를 설계하는 과정을 통해 WAL의 필요성을 설명합니다.

지속성(Durability)의 정의:

• 지속성은 클라이언트가 데이터 시스템에 데이터 쓰기를 요청할 때 제공되는 보장입니다.
• 요청이 성공하면 데이터가 안전하게 디스크에 기록되고, 실패하면 클라이언트가 재시도하거나 다른 조치를 취해야 합니다.
• 지속성의 정의는 데이터베이스마다 다를 수 있습니다.

메모리 내 데이터베이스:

• 메모리 내 데이터베이스는 지속성이 전혀 없습니다.
• 간단한 의사 코드로 메모리 내 데이터베이스 서비스를 보여줍니다.

디스크에 쓰기:

• 기본적인 지속성을 위해 데이터베이스를 파일에 쓸 수 있습니다.
• 의사 코드로 디스크에 쓰는 과정을 보여줍니다.
• B-tree 알고리즘을 사용하여 효율적으로 데이터를 디스크에 기록하는 방법을 설명합니다.

크래시 안전성 문제:

• 단순히 디스크에 쓰는 것만으로는 크래시 안전성을 보장할 수 없습니다.
• 시스템이 재부팅되면 파일에 쓴 데이터가 실제로 디스크에 기록되지 않을 수 있습니다.

fsync의 필요성:

• 운영 체제는 기본적으로 파일 데이터를 버퍼링합니다.
• 운영 체제 버퍼를 플러시하지 않고 데이터를 쓰는 것은 지속성이 있다고 간주되지 않습니다.
• 새로운 데이터베이스가 빠른 삽입 속도를 주장하지만, 실제로 디스크에 데이터를 플러시하지 않는 경우가 종종 있습니다.

지속성의 일반적인 요구사항:

• 데이터를 디스크의 파일에 쓰는 것뿐만 아니라 fsync(2)를 호출하여 파일을 동기화해야 합니다.
• fsync는 운영 체제가 버퍼링한 데이터를 디스크에 강제로 플러시합니다.

fsync 실패 처리:

• fsync 실패를 무시해서는 안 됩니다.
• 실패 처리 방법은 개발자의 선택이지만, 즉시 종료하고 사용자에게 백업에서 복원하라는 메시지를 표시하는 것이 때로는 허용됩니다.

fsync의 성능 영향:

• 데이터베이스는 fsync가 느리기 때문에 선호하지 않습니다.
• 많은 주요 데이터베이스는 클라이언트에 성공을 반환하기 전에 데이터 파일을 fsync하지 않는 모드를 제공합니다.
• 예: PostgreSQL은 이 안전하지 않은 모드를 제공하지만 기본값으로 사용하지 않고 경고합니다.
• MongoDB는 기본적으로 이 안전하지 않은 모드를 사용합니다.

성능과 안전성의 트레이드오프:

• 거의 모든 데이터베이스는 어느 정도 안전성을 희생하여 성능을 얻습니다.
• 예: 대부분의 데이터베이스는 Serializable Isolation을 기본값으로 사용하지 않습니다.

그룹 커밋(Group commit):

• fsync의 비용을 분산시키기 위한 방법입니다.
• 여러 요청의 데이터를 모아서 한 번에 쓰고 fsync를 호출합니다.
• 예: 5ms마다 한 번씩 디스크에 직렬화하고 fsync를 호출하는 백그라운드 스레드를 사용할 수 있습니다.

MongoDB와의 차이점:

• 그룹 커밋에서는 write 요청이 fsync를 통해 지속성이 보장될 때까지 기다린 후 성공을 반환합니다.
• MongoDB는 기본적으로 쓰기가 fsync되기 전에 성공을 반환할 수 있습니다.

지속성의 핵심 아이디어:

• 클라이언트에게 성공을 반환하기 전에 클라이언트 메시지의 어떤 버전이든 디스크에 fsync를 통해 지속적으로 저장되어야 합니다.

지속성 있는 쓰기 최적화의 필요성:

• 사용자가 쓰기 작업을 할 때마다 전체 데이터베이스 구조를 디스크에 직렬화하는 것은 비효율적입니다.
• 이를 개선하기 위한 방법을 소개하고 있습니다.

새로운 접근 방식: 추가 전용 로그(Append-only log):

• 사용자의 메시지만을 추가 전용 로그에 기록합니다.
• 전체 B-tree는 주기적으로만 디스크에 기록합니다.
• 추가 전용 로그 파일이 fsync되면, B-tree가 아직 디스크에 기록되지 않았더라도 사용자에게 안전하게 응답할 수 있습니다.

시작 시 추가 로직:

• 시스템 시작 시, 디스크에서 B-tree를 읽고 그 위에 로그를 재생합니다.
• 이렇게 하면 최신 상태의 데이터베이스를 복구할 수 있습니다.

코드 설명:

• 데이터베이스 파일(kv.db)과 로그 파일(kv.log)을 엽니다.
• B-tree를 초기화하고 마지막으로 처리된 로그 이후의 모든 로그를 읽어 B-tree에 적용합니다.
• 그룹 커밋을 위한 백그라운드 작업자를 설정합니다.
• 주기적으로(5ms마다) 로그를 디스크에 기록하고 fsync합니다.
• 더 긴 간격(1분마다)으로 전체 B-tree를 디스크에 기록합니다.

쓰기 작업 처리:

• 메모리 상의 B-tree를 업데이트합니다.
• 로그 엔트리를 생성하고 그룹 커밋 대기열에 추가합니다.
• 로그가 디스크에 기록되고 fsync될 때까지 기다립니다.
• B-tree 전체가 디스크에 기록되기를 기다리지 않고 사용자에게 응답합니다.

선행 기록(Write-Ahead Log, WAL)의 개념:

• 이 접근 방식이 바로 선행 기록(WAL)입니다.
• WAL은 데이터베이스 변경사항을 먼저 로그에 기록하고, 나중에 실제 데이터 구조를 업데이트하는 기법입니다.

WAL의 장점 설명:

• 예: 가장 작은 키와 가장 큰 키를 동시에 쓰는 상황을 고려합니다.
• B-tree에 직접 쓰면 디스크 상의 서로 다른 위치에 있는 최소 두 개의 페이지를 수정해야 합니다.
• 하지만 로그에 쓰면, 두 메시지가 같은 로그 페이지에 포함될 가능성이 높습니다.
• 이는 디스크 I/O를 줄이고 성능을 향상시킵니다.

효율성 증대:

• 클라이언트 요청을 나타내는 작은 메시지만 디스크에 기록하는 것이 더 효율적입니다.
• 구조화된 B-tree의 지속성 유지는 덜 빈번한 주기로 수행할 수 있습니다.

파일 시스템과 디스크 버그:

• 파일 시스템이 때때로 잘못된 위치에 데이터를 쓰는 경우가 있습니다.
• 디스크가 데이터를 손상시키는 경우도 있습니다.
• 이러한 문제들은 데이터 무결성에 심각한 위협이 될 수 있습니다.

체크섬(Checksum)을 통한 해결 방안:

• 체크섬은 데이터의 무결성을 검증하는 방법입니다.
• 작동 방식: a) 데이터를 쓸 때 체크섬을 계산합니다. b) 계산된 체크섬을 디스크에 저장합니다. c) 데이터를 읽을 때 체크섬을 다시 확인합니다.

스크러빙(Scrubbing):

• 백그라운드에서 실행되는 프로세스입니다.
• 읽히지 않은 데이터의 유효성을 검사합니다.
• 데이터 손상을 빠르게 감지하여 백업에서 복구할 수 있게 합니다.

데이터베이스별 체크섬 사용 현황

a) MongoDB:

• 기본 스토리지 엔진인 WiredTiger는 기본적으로 체크섬을 사용합니다.

b) PostgreSQL:

• 기본적으로 데이터 페이지에 대한 체크섬을 사용하지 않습니다.
• 클러스터 단위로 선택적으로 활성화할 수 있습니다.
• 활성화 시, 각 데이터 페이지에 체크섬이 포함되어 쓰기 시 업데이트되고 읽기 시 확인됩니다.
• 내부 데이터 구조와 임시 파일은 체크섬으로 보호되지 않습니다.

c) SQLite:

• 기본적으로 체크섬을 사용하지 않습니다.
• 선택적 확장 기능으로 체크섬을 사용할 수 있습니다.
• 확장 기능 활성화 시, 각 페이지 끝에 8바이트 체크섬이 추가됩니다.
• 이는 대용량 저장 장치의 무작위 비트 플립으로 인한 데이터베이스 손상을 감지하는 데 도움을 줍니다.

체크섬의 한계:

• 체크섬만으로는 모든 문제를 해결할 수 없습니다.
• 디스크나 노드가 완전히 실패하는 경우에는 체크섬으로 대처할 수 없습니다.

더 높은 수준의 내구성을 위한 방안:

• 여러 디스크나 노드에 걸친 중복성(redundancy)을 도입해야 합니다.
• 예: 분산 합의(distributed consensus) 알고리즘을 사용하는 방법