저장소와 검색

데이터베이스: 데이터를 저장 / 요청 시 데이터 제공

데이터베이스를 강력하게 만드는 데이터 구조

• 기본적인 저장소 형식
  • 매 라인마다 쉼표로 구분된 키-값 쌍을 포함한 텍스트 파일
  • 데이터를 추가할 때마다 파일의 끝에 추가하므로 키를 여러 번 갱신해도 값의 예전 버전을 덮어쓰지 않음
• 위와 같은 형식은 실제 데이터베이스들에도 로그 파일 관리를 위해 사용하는 방식과 유사
• 로그: 연속된 추가 전용 레코드
• 다만, 위와 같은 형식은 레코드가 많을 때에는 파일 스캔 비용이 커서 성능이 매우 좋지 않음 (O(n))
• 이런 점 때문에, 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터구조가 필요하다. ⇒ 색인
• 색인은 부가적인 메타데이터(일종의 이정표, 데이터 위치를 찾는데 도움을 줌)를 유지하는 것
• 동일한 데이터를 여러가지 다양한 방법으로 검색하고자 한다면, 데이터의 각 부분에 여러가지 다양한 색인이 필요
• 색인은 기본 데이터에서 파생된 추가적인 구조
  • 색인의 추가와 삭제가 허용되며, 데이터베이스 내용에는 영향을 미치지 않는다.
  • 단지 질의 성능에만 영향을 줌
  • 데이터를 쓸 때마다 매번 색인도 갱신해야 하므로, 색인으로 인해, 쓰기 과정에서 오버헤드 발생
• 그러므로, 색인은 저장소 시스템에서 중요한 트레이드오프
  • 색인으로 인해 읽기/질의 속도는 향상되지만, 쓰기 속도를 떨어뜨리므로
  • 이 점때문에, 보통 데이터베이스들은 디폴트로 색인을 설정하지는 않는다 ⇒ 개발자가 수동으로 신중하게 설정

해시 색인

• 키-값 저장소는 dictionary type(보통 해시 맵으로 구현)과 유사
• 인메모리 데이터 구조를 위한 해시맵을 디스크 상의 데이터 색인을 위해 사용
• 키-데이터 파일 오프셋을 매핑한 인메모리 해시 맵을 유지하는 전략
  • 파일에 새로운 키-값 쌍을 추가할 때마다 해시 맵을 갱신
  • 값을 조회할 때에는 해시 맵을 사용해 데이터 파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽음
  • Bitcask 가 근본적으로 사용하는 방식
    • 해시 맵을 전부 메모리에 유지하기 때문에 사용가능한 RAM에 모든 키가 저장
    • 이로 인해, 고성능 읽기, 쓰기를 보장
    • 각 키의 값이 자주 갱신되는 상황에 매우 적합
    • 쓰기가 아주 많지만, 고유 키가 많지 않은 상황 ⇒ 키 당 쓰기 수가 많지만, 메모리에 모든 키를 보관할 수 있음
• 파일에 계속해서 데이터가 추가되면 디스크 공간 부족해질 때는?
  • 특정 크기의 세그먼트로 분리 (세그먼트가 특정 크기에 도달하면 새로운 세그먼트에 쓰기 수행)
  • compaction 수행 (로그에서 중복된 키를 버리고, 각 키의 최신 갱신 값만 유지하는 것)
  • 세그먼트마다 compaction을 수행한 후, 세그먼트들을 병합하면 더 크기를 줄일 수 있음
• 위 사항들을 실제 구현할 때 고려해야 하는 사항들
  • 파일 형식
  • 레코드 삭제
  • 고장 복구
  • 부분적으로 레코드 쓰기
  • 동시성 제어
• 추가 전용 로그가 좋은 설계인 이유
  • 추가와 세그먼트 병합은 순차적인 쓰기 작입이므로, 보통 무작위 쓰기보다 훨씬 빠름
  • 세그먼트 파일이 추가 전용 로그와 같은 구조이면 동시성과 고장 복구가 훨씬 간단 (값 갱신 시, 이전 값 부분도 함께 남아있기 때문에)
  • 오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있음
• 해시 테이블 색인의 제약 사항
  • 해시 테이블을 메모리에 저장해야 하므로, 키가 너무 많으면 문제
  • 범위 질의에 효율적이지 않음. 범위가 주어지더라도, 해시 맵에서 개별 키를 모두 조회해야 함