- 키-값 데이터 구조는 데이터 기반 시스템의 핵심 구성요소이며, 워크로드와 하드웨어 조건에 따라 성능 차이가 크게 벌어질 수 있음
- 물리적 구조는 데이터 배치, 탐색용 메타데이터, 저장·검색 알고리듬으로 나뉘며, 접근 방법(access methods), 데이터 컨테이너, 검색 구조로도 불림
- 워크로드는 포인트 쿼리, 범위 쿼리, 삽입, 삭제, 수정의 조합으로 표현되며, 메모리·영구 저장소의 용량과 비용도 설계 요구사항이 됨
- B+-tree는 읽기와 범위 쿼리에 강하지만 삽입·수정이 늘면 리프 노드 재구성이 부담이 되고, LSM-tree는 버퍼링과 병합으로 많은 삽입을 처리함
- 데이터 이동이 병목이 되는 환경에서는 새 애플리케이션, 하드웨어 변화, 데이터 증가에 맞춰 기존 구조를 고르거나 새 구조를 설계해야 함
키-값 데이터 구조가 해결하는 문제
- 키-값 데이터 구조는 데이터 집약적 애플리케이션에서 널리 쓰이며, 키-값 모델의 범용성 때문에 여러 시스템의 기반이 됨
- 하나의 키는 하나의 값에 매핑되지만, 같은 값은 여러 키와 연결될 수 있음
- 값의 의미는 애플리케이션에 따라 달라짐
- 관계형 데이터베이스의 레코드일 수 있음
- Pandas DataFrame일 수 있음
- NoSQL 시스템에서 애플리케이션이 파싱해 사용하는 필드 집합일 수 있음
- 소셜 네트워크 데이터를 다루는 시스템에서는 이미지나 비디오 같은 큰 객체에 대한 참조를 포함할 수 있음
물리적 구성과 적용 범위
- 물리적으로 키-값 데이터 구조는 세 요소로 구성됨
- 특정 레이아웃에 저장된 데이터
- 데이터 탐색을 돕는 선택적 메타데이터
- 저장과 검색 연산을 지원하는 알고리듬
- 데이터 구조는 데이터 시스템, 운영체제, 파일 시스템, 컴파일러, 네트워크 시스템에서 다양한 형태로 사용됨
- 책의 예시는 주로 대용량 데이터 시스템과 보조 저장장치를 중심으로 하지만, 분석과 설계 방식은 인메모리 시스템에도 적용됨
- 이 분석은 메모리·저장소 계층이 두 단계 이상 있는 환경에 맞춰짐
워크로드와 비용이 설계를 좌우함
- 애플리케이션이나 워크로드는 키-값 연산의 조합으로 나타낼 수 있음
-
포인트 쿼리
-
범위 쿼리
- 삽입
- 삭제
- 수정
- 메모리와 영구 저장소의 필요 용량 및 비용도 애플리케이션 요구사항을 구성함
- 시스템 유형에 따라 최적화해야 할 데이터 구조가 달라짐
- 파일 시스템은 잦은 업데이트에 최적화된 데이터 구조로 파일 메타데이터와 내용을 관리함
- 컴파일러는 변수 생명주기 동안 hash map으로 변수를 관리하고, 프로그램의 전체 형태를 abstract syntax tree로 표현함
- 네트워크 장치는 라우팅 테이블을 효율적으로 저장하고 접근하기 위해 특수화된 데이터 구조가 필요함
-
B+-tree와 LSM-tree의 상반된 선택
- B+-tree는 삽입과 업데이트가 적고 포인트·범위 쿼리가 많은 워크로드에서 읽기 비용과 쓰기 비용의 균형을 맞추기 위해 많이 사용됨
- 높은 노드 팬아웃은 루트에서 리프까지 이동할 때 필요한 보조 메모리 접근을 줄이고, 상위 레벨은 더 빠른 메모리 계층에 캐시됨
- 모든 키를 리프 노드에 정렬해 유지하고 리프 노드를 연결 리스트로 이어 범위 쿼리를 지원함
- 삽입과 업데이트가 늘어나면 리프 노드 재구성이나 분할이 필요해져 성능 병목이 될 수 있음
- LSM-tree는 많은 삽입이 있는 워크로드를 위해 다른 접근을 사용함
- 모든 업데이트를 공통 메모리 버퍼에 넣음
- 버퍼가 가득 차면 디스크로 플러시함
- 버퍼가 쌓이면 더 큰 정렬 데이터 컬렉션으로 병합함
- 수정은 out-of-place 정책으로 처리되며, 같은 키를 가진 키-값 쌍이 구조 안에 여러 개 존재할 수 있음
- 특정 키의 현재 값은 가장 최근에 삽입된 키-값 쌍이 가짐
적응형 데이터 구조
- 워크로드를 미리 예상해 데이터 구조를 설계하는 방식뿐 아니라, 실행 중 점진적으로 이상적인 형태에 가까워지는 데이터 구조도 다룸
- 원래 설계의 B+-tree와 LSM-tree는 모든 포인트 또는 범위 쿼리에 답하기 위해 디스크 상주 노드 안에 정렬 순서를 강제함
- 적응형 데이터 구조는 하나 이상의 정렬되지 않은 노드에서 시작해, 기회가 생길 때 점진적으로 정렬할 수 있음
- database cracking은 들어오는 쿼리의 접근 패턴을 사용해 기반 데이터를 지속적·증분적으로 물리 재구성함
- 목표는 향후 쿼리 성능을 개선하는 것임
하드웨어 계층과 메모리 벽
- 하드웨어 발전은 데이터 구조 설계에 새로운 과제와 기회를 만듦
- 저장소 계층에서 아래 단계는 더 많은 저장공간을 낮은 가격에 제공하지만 접근 지연이 크고, 프로세서에 가까운 위 단계는 더 빠르지만 작고 바이트당 비용이 높음
- 특정 애플리케이션의 병목 계층은 애플리케이션 데이터 크기와 각 계층의 저장 용량에 따라 달라짐
- B+-tree는 원래 팬아웃을 극대화해 디스크 접근을 줄이려 했지만, 메모리 크기가 커지고 데이터가 RAM이나 비휘발성 보조 메모리에 들어가면서 트레이드오프가 크게 바뀜
- 인메모리 B+-tree는 작은 팬아웃에서 가장 좋은 성능을 보임
- 메모리 벽(memory wall) 은 프로세서 속도와 오프칩 메모리 속도 사이의 격차가 커지는 추세를 가리킴
- 2000년대 초 이후 운영체제와 데이터 관리 시스템은 캐시 메모리 사용을 최적화하도록 재설계되어 왔음
설계 공간과 가이드라인
- 데이터 구조 설계 선택의 공간을 정리하고, 애플리케이션 목표와 워크로드에 맞는 구조를 고르는 방법을 다룸
- 하드웨어와 데이터 속성이 계속 변하기 때문에 데이터 구조 설계에도 지속적인 혁신이 필요함
- 정리된 설계 공간과 가이드라인은 기존 데이터 구조 중 가장 맞는 것을 선택하거나, 특정 워크로드에 맞는 새 데이터 구조를 설계하는 데 쓰임