CH 03 ~ 04 내용 정리
CH 03. 저장소와 검색
1. 들어가면서
- 데이터베이스가 수행하는 가장 기본적인 기능 2가지
- 데이터 저장
- 저장한 데이터에 대한 요청이 있으면 그 데이터 다시 제공
- 데이터베이스가 내부적으로 검색과 저장을 하는 과정을 애플리케이션 개발자가 주의해야되는 이유
- 대개 애플리케이션 개발자는 DB 엔진을 밑바닥부터 빌드하기보다, 비즈니스 상황에 적합한 엔진을 선택해서 작업함.
- 특정 상황에 대한 작업부하 (Workload)에 DB 퍼포먼스를 높이면, 상황에 맞는 엔진을 선택해야하기 때문.
2. 데이터베이스를 강력하게 만드는 구조
- 가장 간단한 DB 구조 예시
- 일반적으로 파일 추가 기능은 매우 효율적인 작업이라, 간단한 작업에 대해서 성능이 꽤 좋게 나옴 (db_set)
- 많은 DB는 Append-only인 데이터 파일 로그 사용함 (ex. redis)
- 반면 db_get함수는 성능이 나쁨. key를 찾을 때까지 저장된 데이터 계속 순회해야함.
- 검색 비용이 O(N) 으로 수렴.
- 특정 키를 보다 효율적으로 찾는 방법 : 색인 (index)
- 색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것. 메타 데이터가 이정표 역할을 해서 원하는 데이터를 찾는데 도움을 줌.
- 책을 펼치면 앞머리에 목차(Table of Content)가 있는 것과 같은 원리.
- 색인은 기본 데이터 (primary data)에서 파생된 추가적인 구조.
- 색인 자체는 DB 성능에 영향을 주진 않으나, 쿼리 성능에는 영향 줌.
- 추가적인 구조의 유지 보수는 특히 쓰기 과정에서 오버헤드 발생. 예를 들어 단순 파일 추가 작업을 능가하는 쓰기 작업의 성능은 찾기 어려움.
- 데이터 쓰기를 할 때마다 색인도 갱신되기 때문에 쿼리 성능에 영향 갈 수 밖에 없음.
- Trade-off: 색인을 설정하면 읽기 쿼리 속도가 올라가나 쓰기 쿼리 속도가 내려감.
- 이것 때문에 DB가 자동으로 index 설정 안하고, 애플리케이션 개발자 판단하에 수동 index 적용됨.
3. 해시 색인
- 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시맵 유지하는 전략을 예제로 듦.
- 새로운 키-값 쌍을 추가할 때마다 방금 저장한 데이터 오프셋을 반영하기 위해 해시맵도 갱신함.
- 값을 조회하려면 해시맵에서 데이터 파일의 오프셋을 찾아 위치를 찾고 값을 읽음.
- 이 방식은 각 키의 값이 자주 갱신되는 상황에서 사용하기 적합함. (비트 캐스크, 리악의 DB 엔진)
- 키당 쓰기 수가 많으나 메모리에 모든 키 관리 가능.
- 그러나 파일에 계속 추가만 한다면, 결국 디스크 공간 부족으로 연결됨.
- 특정 크기의 세그먼트(segment)로 로그를 나누는 방식이 좋은 해결책.
- 세그먼트 파일들에 대한 컴팩션(Compaction) 유지 가능. 즉, 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것.
- 컴팩션 수행 시, 여러 세그먼트 병합하며 새로운 세그먼트 생성함 (세그먼트가 쓰여진 후에는 변경이 불가함.)
- 컴팩션 수행 중에는 이전 세그먼트 접근 가능하지만, 완료 후에는 새로운 세그먼트 파일에 접근하게 전환.
- 결국 나중 값이 이전 값보다 우선하는 상황
- 병합하면서 세그먼트 수를 적게 유지하기 때문에, 많은 세그먼트 탐색이 필요 없음.
- 위 문제를 해결할 때 고려해야할 사항들
- 파일 형식
- 레코드 삭제
- 고장(Crash) 복구
- 부분적으로 레코드 쓰기
- 동시성 제어
- 추가 전용 설계의 장점들
- 순차 쓰기이므로 무작위 쓰기보다 성능 좋음.
- 세그먼트 파일이 순차 쓰기 전용이거나 불변성이면 동시성과 고장 복구에 좋음
- 오래된 세그먼트 병합은 시간이 지남에 따라 조각화 되는 데이터 파일 문제 피할 수 있음
- 해시 테이블 자체 제약사항
- 인메모리 상황에서 키가 너무 많으면 문제됨.
- 디스크가 가득 찼을 때 발생하는 확장비 + 충돌 해소를 피하기 위한 로직 필요.
- range query에 부적합.
4. SS 테이블과 LSM 트리
4.1 SS 테이블
- 키-값의 쌍을 키를 기준으로 정렬하면서 각 키는 병합된 세그먼트 파일에서 한 번씩만 나타나야하는 것이 SS 테이블 (Sorted String)
- 컴팩션이 이미 이를 보장하고, 세그먼트 병합은 Merge Sort와 유사.
- 키를 정렬하기 위해서는 레드 블랙 트리 또는 AVL 트리로 정렬된 순서를 통해 키 읽기 가능.
- 단, 디스크에 기록되지 않는 데이터는 (memtable)은 DB가 고장나면 데이터 손실이 되기 때문에 쓰기로 즉시 추가할 수 있게 분리된 로그를 디스크에 유지 필요.
- 멤테이블을 SS 테이블로 기록하고 나서 로그 버리면 됨.
4.2 LSM 테이블
- 정렬된 병합과 컴팩션 원리를 기반으로하는 DB 엔진을 LSM 저장소 엔진이라함. (Log-Structured Merge-Tree)
- 루씬, 엘라스틱서치, 솔라 등에서 기반으로 하는 전문 검색 엔진.
- LSM 테이블 기본 개념은 연쇄적으로 백그라운드에서 SS 테이블을 병합하는 것
5. 성능 최적화
- 알고리즘 외의 많은 세부 사항들이 저장소 엔진을 잘 실행되도록 지원하고 있음.
- 예: LSM 트리가 존재하지 않는 키를 찾느라 수행이 느릴 수 있음.
- 이 때 블룸 필터(Bloom Filter)라는 것을 사용함.
- 키가 DB에 존재하지 않는다고 알려주는 것.
- SS 테이블을 압축하고 병합하는 순서와 시기를 결정하는 다양한 전략
- 크기 계층 (Size-Tiered)와 레벨 컴팩션 (Level Compaction)
6. B 트리
- 가장 널리 쓰이는 것은 B 트리로 LSM 트리와는 구조가 많이 다름.
- 고정 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 수행.
- 예: PSQL의 default block size는 8k임.
- 디스가 고정 크기 블록으로 배열 되기 때문에 이런 설계는 근본적으로 하드웨어 설계와 더 밀접한 연관 있음.
- 하나의 페이지가 다른 페이지의 주소나 위치를 알고 있고, 그 페이지가 루트가 되어서 색인에서 키를 탐색.
- B 트리 자체가 계속 트리를 균형이 잡히게끔 유도하고, 트리 깊이는 항상 O(log n) 유지.
- 대부분의 DB에서 B 트리 깊이가 3 ~ 4단계 정도면 충분해서 많은 페이지 참조를 따라가지 않아도 됨.
7. 신뢰할 수 있는 B 트리 만들기
- 새로운 데이터가 디스크 상의 페이지에 덮어쓰더라도, 페이지 위치는 변경되지 않음. 즉, 페이지 데이터가 바뀌더라도 페이지를 가리키는 모든 참조는 유지됨.
- LSM 트리와 대조되는 점.
- HDD이건, SSD이건 DB 고장 상황에서 스스로 데이터를 복원하게 하려면 WAL Log를 사용해야함 (Write-ahead log)
- WAL은 페이지에 변경된 내용을 적용하기 전 모든 B 트리의 변경 사항을 기록하는 로그임.
- DB 고장 이후 복구할 때 일관성 있는 상태를 B 트리에 유지시키기 위해 사용함.
- 멀티 스레드 상황에서 데이터 일관성이 깨질 수 있으므로 Latch 등으로 동시성 제어를 통해 데이터 구조 보호 가능.
8. B 트리 최적화
- WAL 대신 Copy-on-Write Scheme 사용
- 페이지에 전체 키를 사용하는 게 아니라 키 축약해서 사용.
- B 트리 구현 상에서 Leaf 페이지를 연속적으로 두게 유도. 트리가 커지면 순서 유지 어려움.
- 트리에 포인터 추가.
- 프랙탈 트리 사용? (프랙탈 구조와는 전혀 관계 없은 알고리즘 개념)
9. B 트리와 LSM 트리 비교
- 경험적으로 LSM 트리는 쓰기에서, B 트리는 읽기에서 더 빠르다고 알려짐.
- LSM 트리에는 여러 SS 테이블과 데이터 구조 확인이 필요해서 B 트리보다 상대적으로 읽기가 느림.
9.1 LSM 트리 장점
- B 트리의 색인은 모든 데이터 조각을 최소 2번 쓰기 작업을 해야함. 로그 + 페이지
- 때론 해당 페이지의 몇 바이트만 바뀌어도 전체 페이지를 다시 기록하는 오버헤드도 발생
- 쓰기 증폭 (Write Amplification) : 데이터 베이스에 쓰기 한 번이 데이터베이스 수명 기간 동안 디스크에 여러 번 쓰기를 야기하는 효과
- 쓰기가 많은 애플리케이션에서 성능 병목은 데이터베이스가 디스크에 쓰는 속도일 수 있음.
- LSM 트리는 일반적으로 B 트리보다 쓰기 처리량을 높게 할 수 있음.
- 순차적으로 컴팩션된 SS 테이블을 읽기 때문.
- 특히 HDD에서 순차 쓰기가 임의 쓰기보다 빠름.
- 압축률도 좋음. 페이지 지향적이지 않고 주기적으로 페이지 파편화를 없애기 위해 SS 테이블을 다시 기록해서 오버헤드가 낮음.
- 그래서 대다수 SSD 펌웨어는 임의 쓰기를 순차 쓰기로 전환하기 위해 LSM 알고리즘 채택.
9.2 LSM 트리 단점
- 컴팩션 과정이 읽기 및 쓰기 과정에 영향 줄 수 있음.
- 디스크 자원 한계상 비싼 컴팩션 작업이 끝날 때까지 요청 대기해야할 수도 있음.
- DB에 저장된 데이터가 많을 수록 컴팩션을 위해 더 많은 디스크 쓰기 대역폭을 요구함.
10. 기타 색인 구조
- 기본 키 색인 (Primary key index) : RDB에서 하나의 Row를, NoSQL에서 하나의 문서를, Graph DB에서 하나의 정점을 기본 키로 참조.
- 보조 키 색인 (Secondary Index) : RDB에서 `Create index` 로 다양한 색인 생성 가능.
10.1 색인 안에 값 저장하기
- 키-값 구조에서 값은 쿼리의 실제 로우 (문서, 정점)이거나 저장된 로우를 가리키는 참조 값임.
- 후자의 경우, 힙 파일 (Heap File)에 특정 순서 없이 데이터를 저장.
- 키를 변경하지 않고 값이 업데이트 될 때 무척 효과적.
- 그 외 : 클러스터드 색인 (Clustered Index), 커버링 색인 (Covering Index), 포괄열이 있는 색인 (Index with included column)
10.2 다중 칼럼 색인
- 다중 칼럼에 동시에 쿼리를 보낼 때의 상황을 가정.
- 지리학적 위치, 제품 색상 범위 (RGB), 날씨 관측
10.3 전문 검색과 퍼지 색인
- 루씬 등에서 문서나 질의의 오타에 대처하기 위해 특정 편집 거리 내 단어 검색 가능
- 퍼지는 머신러닝 등을 활용해 검색
11. 모든 것을 메모리에 보관
- 디스크에 비해 메모리 가격이 월등히 비쌌으나, 기술의 발전으로 논쟁이 무의미해짐. 인메모리 DB의 등장.
- 디스크는 Write 전용 로그 사용, 읽기에 메모리 사용.
- OLTP: 적은 레코드에 대한 집계.웹 애플리케이션 등의 엔드 유저가 사용
- OLAP: 많은 레코드에 대한 집계. 비즈니스 분석 등에 대해 내부자 사용.
12. 데이터 웨어하우스
- OLTP 작업에 영향을 주지 않는 개별 분석용 DB
- ETL: OLTP에서 데이터를 추출해서, 분석 친화적인 스키마로 변형 후, 분석용 DB에 적재.
- AWS RedShift, Apache Hive, ClickHouse, Google BigQuery
13. 분석용 스키마: 별 모양 스키마와 눈꽃 모양 스키마
- 별 모양 스키마: 테이블이 시각화 될 때, 사실 테이블 (Fact Table)을 중심으로 차원 테이블이 둘러싸고 있음.
- 눈꽃 모양 스키마: 별 모양 스키마 기반으로 차원이 하위 차원으로 더 세분화
14. 칼럼 지향 저장소
- 대부분 OLTP는 로우 지향 방식으로 데이터 배치.
- 데이터를 로우 단위로 저장하지 않고 칼럼 단위로 저장하는 방식
- [PSQL Hydra](https://github.com/hydradatabase/hydra)
- (개인적인 경험) Columnar DB에 데이터 읽기 중간에 Insert가 포함되면 성능이 확 나빠짐.
CH 04. 부호화와 발전
1. 들어가면서…
- 신제품 출시, 사용자 요구사항 변경, 비즈니스 환경 변화 등으로 데이터 및 애플리케이션은 변화함.
- 이 때 시스템에서 과거 버전과 신 버전이 공존하는데, 시스템이 계속 양방향으로 원활하게 실행되게 하려면 호환성 유지가 필요함.
- 즉, 데이터베이스에서 변화를 가져오며, 컬럼이나 필드가 추가되거나 삭제되기도 함
- 어떻게 시스템 상에서 스키마를 변경하고 과거 & 현재 데이터 타입과 코드가 공존하는지 설명하는 챕터
2. 데이터 부호화 형식
- 네트워크로 데이터를 전송하거나 파일에 쓰려면 일련의 바이트열 형태로 부호화함.
- 인메모리 상태에서의 바이트열 전환을 부호화(직렬화, 마샬링), 그 반대를 복호화라함 (역직렬화, 파싱, 언마샬링).
- 부호화는 보통 프로그래밍 언어와 엮여 있어서, 다른 언어가 읽기 무척 어려움. (자바 java.io.Serializable, 루비 Marshal, 파이썬 pickle)
- 효율성, 데이터 버전관리, 보안 이슈 등으로 언어에 내장된 부호화를 사용하는 것은 일반적으로 권장 안함.
3. Json, XML, 이진 변형
- 수(number) 의 부호화에 애매한 부분이 존재함. 특히, 큰 수를 다룰 때 부동소수점을 다루는 언어들에서 파싱할 때 부정확해짐.
- Json & XML은 유니코드 문자열은 지원하지만, 바이너리 문자열은 지원안함. 그래서 Base64로 부호화해 이런 상황을 피함.
- 잘 알려져 있고, 많은 곳에서 표준화된 부호화 형식으로 사용하고 있음.
4. 이진 부호화
- 조직 내에서만 사용하는 데이터라면 최소공통분모 부호화 형식을 사용해야 부담감이 덜하다.
- Json & XML에 비해 더 적은 공간을 차지하고, 더 간결하며, 더 빠른 파싱을 가능하게함.
5. 스리프트와 프로토콜 버퍼
- 스리프트
- 페이스북에서 개발한 이진 부호화 프로토콜
- 프로토콜 버퍼
- 구글에서 개발한 이진 부호화 프로토콜. Data Pipeline Orchestration 툴에서 많이 차용해서 사용함 (예: Flyte)
- 아브로
- 하둡의 서브 프로젝트로 시작한 프로토콜.
- 핵심 아이디어는 쓰기 스키마와 읽기 스키마가 동일하지 않아도 되며, 단지 호환 가능하면 됨.
- 데이터의 타입 변경이 가능함.
- 쓰기 스키마
- 많은 양의 레코드가 있는 대용량 파일
- 개별적으로 기록된 레코드를 갖고 있는 DB
- 네트워크 연결을 통해 데이터 보내기
- 동적 생성 스키마
- 스키마에 태그 번호가 없음 -> 스리프트나 프로토콜 버퍼에 비해 강점으로 꼽힘.
- 3개 프로토콜 모두 스키마 언어를 사용해 이진 부호화 기술함.
6. 데이터 플로우 모드
- 메모리를 공유하지 않는 일부 데이터를 보내고자하는 상황 가정.
- 전달 방법
- DB를 통해서
- 현재 실행 중인 스크립트는 예전 코드고, 새로운 데이터가 DB에 기록된 경우
- 부호화 -> 복호화 -> 재부호화 하는 과정에서 데이터 유실 가능성. 해결하기 어려운 문제는 아님.
- 백업 목적 또는 데이터 적재 목적으로 수시로 스냅샷을 구성해 별도 스토리지에 저장하는 방식.
- 아브로와 같은 객체 컨테이너 보관 방식에 적합
- 서비스 호출을 통해서
- 서비스 지향 설계 -> 마이크로 서비스 설계
- REST 설계 철학, SOAP(Simple Object Access Protocol) 프로토콜을 사용해서 데이터 전송 가능
- 원격 프로시저 호출 (RPC, Remote Procedure Call) : 네트워크 요청을 같은 프로세스 안에서 특정 프로그래밍 함수나 메소드를 호출하는 것과 동일하게 사용하게 해줌.
- 원격 서비스로부터 응답 못받는 경우
- 응답만 유실되는 경우
- 네트워크 latency (혼잡하거나 서비스 과부하 이슈)
- 네트워크를 통해 전송하는 객체 크기가 커서 로컬 메모리에 못 올리는 경우
- 클라이언트와 서비스가 서로 다른 프로그래밍 언어로 작업되었을 때, 데이터 타입을 맞춰줘야하는 이슈
- 그럼에도 RPC는 널리 사용되고 있고, RPC 프레임 워크의 주요 초점은 같은 데이터 센터 내의 같은 조직이 소유한 서비스간 요청에 있음.
- 비동기 메세지 전달을 통해서
- 메세지를 직접 네트워크로 연결하지 않고 브로커 (또는 메세지 큐) 메세지 지향 미들웨어를 거쳐 전송
- 수신자가 사용 불가능하나, 네트워크 과부하 등에서 버퍼처럼 사용해서 데이터 안정성 높임.
- 죽었던 프로세스를 다시 보낼 수 있어 데이터 유실 방지 (AWS SQS Dead Letter Queue)
- 송신자가 수신자의 포트나 ip를 알 필요 없음.
- 하나의 메세지를 여러 수신자에게 전송 가능
- 논리적으로 송신자 <-> 수신자는 분리됨 (Publisher <-> Consumer)
