데이터 중심 어플리케이션 설계 - 3. 저장소와 검색

데이터베이스의 두 가지 작업.

1. 데이터 저장
2. 데이터 제공

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

간단한 디비를 생각해보자.

• 추가 작업은 간단하고 성능이 좋다. → 맨 뒤에 한줄 추가. 로그 형태
• 읽기 작업은 레코드 양이 비례하여 성능이 안좋아짐.(O(n))

이에 읽기 성능을 끌어올리기 위해(특정 키의 값을 효율적으로 찾기 위해) 부가적인 메타데이터(색인) 을 유지한다.

• 부가적인 메타데이터를 유지하기 위하여 필연적으로 오버헤드가 발생함.

색인을 사용할지, 어떤 색인을 사용할지, 어떤 데이터를 색인 할지 트레이드오프를 잘 따져보고 선택해야함.

해시 색인

키-값 저장소로 대부분의 프로그래밍 언어에서 볼 수 있는 사전타입과 매우 유사.

해시색인의 간단한 예시

• 로그 형식으로 데이터를 저장한다고 가정 → 데이터가 key-value 쌍 형태로 계속 추가됨
• key-value 형태로 인메모리 테이블 유지
• 특정 크기가 넘어가면 새로운 세그먼트에 기록
• 세그먼트는 컴팩션 해서 새로운 세그먼트 생성 → 이전 세그먼트는 삭제

실제 구현을 위해선

• 파일 형식
• 레코드 삭제
• 고장 복구
• 부분적으로 레코드 쓰기
• 동시성 제어

와 같은 요소를 신경써야함.

추가 전용 로그를 쓰는 것은 다음과 같은 장점이 있음.

• 무작위 쓰기보다 빠르다.
• 동시성과 고장 복구에 좋음.
• 오래된 세그먼트가 병합되므로 시간에 따라 조각화되는 데이터 파일 문제를 피할 수 있음

해시색인의 제약사항으로는

• 메모리는 제한되어있으므로 키가 너무 많으면 문제가 됨. 해시 충돌도 해결해야함.
• 범위 질의에 효율적이지 않다.

SS테이블과 LSM 트리

• 설명
• SS테이블 - 정렬된 문자열 테이블(Sorted String Table)
  • 쓰기가 들어오면 균형트리(예를 들어 red-black tree)에 추가. 이를 멤테이블이라고도 함.
  • 멤테이블의 크기가 임곗값보다 커지면 SS테이블 파일로 저장. 새로운 쓰기는 새로운 멤테이블에
  • 읽기 요청은 멤테이블 검색 + 세그먼트 순서대로 검색
  • 세그먼트의 병합과 컴팩션 과정 수행
  • 데이터베이스가 고장날 경우 대비하여 로그를 디스크 상에 유지해야함.
• LSM 트리
  • 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 함.
  • 백그라운드에서 연쇄적으로 SS 테이블을 지속적으로 병합
  • 예를 들어 Lucene
• 성능 최적화
  • 세그먼트가 많을 경우 불필요한 디스크 읽기가 많아짐 → 블룸 필터를 사용(키가 db에 존재 하지 않는다는 것을 알려줄 수 있음)
  • 병합하는 순서와 시기를 조정

B트리

가장 널리 사용 되는 구조

• 4KB(혹은 더 크게) 블록(혹은 페이지) 로 나누고 한번에 하나의 페이지에 일기 또는 쓰기를 한다.
• root 부터 검색을 시작하여 leaf 페이지(개별 키를 가지고 있는) 에 도달
• 분기계수 500에 4kb 페이지의 깊이가 4단계라면 256TB 까지 저장 가능
• 신뢰할 수 있는 B트리 만들기
  • B트리는 새로운 데이터를 디스크에 덮어씀
  • 데이터를 추가 / 제거 하다 보면 페이지를 나누고 참조 갱신 등 여러 작업이 일어나는데
  • 이 와중에 데이터베이스가 고장난다면?
  • redo log 로 복원
  • 동시성 제어 - 래치같은 것을 사용

B 트리와 LSM 트리 비교

• LSM 트리는 쓰기에서 빠르고 B트리는 읽기에서 빠르다고 알려져 있음
• 하지만 실제 필요한 작업부하로 테스트 해봐야함.
• LSM트리의 장점?
  • B트리에 비해 쓰기 증폭이 적어 쓰기 처리량을 높게 유지 가능
  • 압축률이 좋아 B트리 보다 디스크에 적은 파일을 생성
• LSM 트리의 단점?
  • 컴팩션이 성능 저하를 가져올 수 있음(p.87)
  • 키가 여러 세그먼트에 다중으로 존재 할 수 있음. (트랜잭션에서 문제가 될 수 있음 → 7장에서 자세히)

기타 색인 구조

• 보조 색인
• 색인 안에 값 저장
• 다중 칼럼 색인 → 보조 색인이랑 다른가?
• 전문 검색과 퍼지 색인
• 모든 것을 메모리에 보관

트랜잭션 처리나 분석?

사용자 입력 기반으로 레코드가 삽입, 갱신 되는 형태의 동작을 OLTP(Online transaction processing) 라고 함. 데이터베이스를 데이터 분석에도 점점 많이 사용하기 시작했는데, 여기서 데이터베이스를 사용 하는 형태를 OLAP(online analytic processing) 이라고 함.

데이터 웨어하우징

• 데이터 웨어하우스는 분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스
• OLTP 데이터베이스에서 데이터를 ETL 하여 적재
• 분석 패턴에 맞게 최적화 가능

분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마

• 사실테이블과 차원테이블
  • 사실 테이블 : 발생한 이벤트
  • 차원 테이블 : 누가 언제 어디서 무엇을 어떻게 왜 이벤트를 발생 시켰는지에 대한 테이블
• 이렇게 사실 테이블과 차원 테이블을 시각화 하면 생긴 모양이 별 같다 하여 별 모양 스키마라 부르고
• 이 테이블을 좀 더 정규화 한 것을 눈꽃송이 모양 스키마라 함

컬럼 지향 저장소

대부분의 OLTP 저장소는 로우 지향 방식으로 데이터를 저장.

이에 반해 컬럼 단위로 데이터를 저장 하는 방식이 있는데, 컬럼 지향 저장이라 함.

컬럼 압축

• 많은 양이 반복적으로 나오기 때문에 압축을 하기 좋음
• 그 중 한가지방법으로 비트맵 부호화(bitmap encoding) 이 있음.
• 압축의 효과는 디스크에 적재할 데이터 양 줄이는 것 외에도
  • CPU L1 캐시에 더 많은 로우를 저장 할 수 있다. → 벡터화 처리

컬럼 저장소의 순서 정렬

• 각 칼럼을 독립적으로 정렬할 순 없음.
• 칼럼을 정렬 하면 압축에 도움이됨.
• 고가용성을 위해 데이터를 여러장비에 복제해두는게 필요한데
  • 이때 각 복제본을 다른 방식으로 정렬해 저장할 수 있음
  • 질의 패턴에 따라 알맞은 복제본을 사용해 처리 하면 효율이 좋다

컬럼 지향 저장소에 쓰기

• 일단 인메모리 저장소에 추가해 정렬 되게 한 후
• 충분한 크기를 보으면 디스크의 칼럼 파일에 병합하고 대량으로 새로운 파일에 기록
• 질의를 할 때는 컬럼 데이터와 메모리의 최근 쓰기를 모두 조사해 두 가지를 결합해야함.