데이터 중심 애플리케이션 설계 03 저장소와 검색

📝 상세 정리

#

인트로

#

• 가장 기본적인 수준에서 데이터베이스는 두가지 작업을 수행한다
  • 데이터 저장하기
  • 데이터 제공하기
• 이번 장에서는 데이터베이스가 데이터를 저장하는 방법과 데이터를 찾는 방법을 설명하겠다.
  • 이걸 왜 알아야 할까?
  • 저장소 엔진을 직접 구현하는게 아니라 선택하니까, 대략적으로는 알고 고르자.
• RDB, NoSQL에 대해서 우선 할건데
  • 로그 구조 계열 저장소 엔진
  • 페이지 지향 계열 저장소 엔진
  • 을 검토할것

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

#

• 걍 배시로

db_set(){
	echo "$1, $2" >> database
}

db_get () {
	grep "^$1, " database | sed -e "s/^$1, //" | tail -n 1
}

• 이라는 db를 만들면, 쓰기는 매우매우 빠르다.
  • 겹쳐도 걍 뒤에 써버리고, -tail로 하나만 가져오니까.
• 로깅도 비슷한 느낌인걸 잘 알지 않나?
• 이런 append-only 데이터 파일을 로그(log) 라고 한다.
  • 로그는 사람이 읽을 수 있는 형식일 필요도 없다.
• 암튼 db_set은 빠른데, db_get은 O(N)으로 개느리다.
• 그래서 다른 데이터 구조가 필요한데..
  • 색인 에 대해서 알아보겠다.
  • 다양한 색인 구조를 살펴보고 여러 색인 구조를 비교해보자.
• 색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것이다.
  • 이는 이정표 역할을 해서, 원하는 데이터의 위치를 찾는데 도움을 준다.
  • 색인은 기본 데이터 (primary data)에서 파생된 추가적인 구조이다.
    • 많은 DB는 색인의 추가/삭제를 허용하고 이는 내용에 영향을 미치지 않는다.
    • 추가적인 구조의 유지보수는 오버헤드를 발생시킨다.
      • 보통 쓰기속도를 느리게 만든다.
  • 이것이 저장소시스템에서 중요한 트레이드오프이다.

해시 색인

#

• key-value 데이터를 색인해보자.

• 보통 dictionary type 같은거니까, hash map / hash table 등으로 구현한다.

• 암튼 키를 데이터 파일의 바이트 오프셋(값을 바로 찾을 수 있는 위치)에 매핑해서 인메모리 해시 맵을 유지하는 전략이다.

• 단순하지만, 많이 사용한다고한다.

  • 대표적으로 Bitcask (Riak의 기본 저장소 엔진)이 사용한다.

• 전부 메모리에 저장되면 고성능 읽기/쓰기를 보장한다.

• 이는 각 키 값이 자주 갱신되는 상황에 매우 적합하다.

  • 키당 쓰기 수가 많지만 고유키가 적어서 메모리에 키 보관이 가능한 경우

• 하지만 이를 추가만 계속 하면 디스크 공간이 부족해질텐데…

  • 이를 위해 특정 크기의 세그먼트로 로그를 나눌 수 있겠다.
  • 그리고 그 중간과정에 대해 한번씩 정리/압축을 할 수 있겠다. (최신값만 남기기)
    • 압축을 컴팩션이라 하자.

• 이를 실제로 구현하려면 고려해야할게 많다.

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

• 추가 전용 로그는 공간 낭비지 않을까? 어차피 금방 찾으면 직접 가서 덮어쓰면 안되나?

  • 추가와 세그먼트 병합이 훨씬 빠르다 (순차적인 작업이기 때문)
    • 특히 하드디스크에서!!
      • 자기회전방식이니까.
  • DB 죽으면 어케 고칠건데!
  • 조각화되는 데이터파일 문제도 해결 가능 (조각모음)

• 제한사항도 물론 있다.

  • 키가 너무 많으면 안된다.
  • 범위 질의는 사실상 응답이 불가능하다.

SS테이블과 LSM 트리

#

• 세그먼트 파일의 형식에 간단한 변경사항 한가지만 적용해보자.
  • 일련의 키-값 쌍을 키로 정렬하기
  • 이 형식을 정렬된 문자열 테이블 (Sorted String Table), 즉 SS테이블 이라고 한다.
• 이는 해시 색인 로그 세그먼트보다 몇가지 큰 장점이 있는데
  • 파일이 사용가능한 메모리보다 크더라도 간단하고 효율적임
    • 머지소트하듯이 가져오면 금방 병합된다
  • 모든 키의 색인을 유지할 필요가 없다
    • 해당 키를 포함하는 범위를 찾아가서 안에서 선형탐색을 해도 된다
  • 디스크 공간 절약, I/O 대역속 사용 절감
    • 위의 아이디어로 블록을 그룹화해서 저장할 수도 있겠다.
    • sparse index의 아이디어

SS테이블 생성과 유지

#

• 근데 데이터를 키로 정렬하기에는.. 유입되는 쓰기는 임의 순서로 발생한다. 어떻게 할까?
• 이를 위해 레드블랙트리나 AVL같은 자료구조를 사용하겠다.
  • 임의 순서로 키를 삽입하고 정렬된 순서로 키를 다시 읽을 수 있다.
• 이걸 이용해서 저장소 엔진을 다음과 같이 만들자.
  • 쓰기가 들어오면 해당 자료구조(RB트리 / AVL트리 등)에 추가한다.
    • 저 트리를 멤테이블이라고도 한다.
  • 멤테이블이 특정 임곗값보다 커지면 SS테이블 파일로 디스크에 기록한다.
  • 읽기요청이 들어오면 멤테이블 -> 최신 세그먼트 -> 다음 세그먼트…에서 찾는다.
  • 가끔 세그먼트 파일을 병합, 컴팩션하는 과정을 수행한다.
• 이론상 완벽한데, 한가지 문제가 있다.
  • DB가 고장났다면??
  • 그래서 멤테이블에있는 최신 쓰기가 날라간다면?
  • 이를 방지하기 위해선 분리된 로그를 디스크에 유지해야한다.
    • SS테이블에 기록할때 버리면 되니까!

SS테이블에서 LSM 트리 만들기

#

• 위의 알고리즘은 LevelDB, RocksDB, KV엔진 라이브러리 등에서 사용한다.
  • 카산드라랑 HBase에서도 유사한걸 이용한다!
• 이 색인 구조는 Log-Structured Merge-Tree, LSM트리라는 이름으로 발표되었다.
  • 이를 기반으로 한 엔진을 LSM 저장소 엔진이라고 한다.

성능 최적화

#

• LSM트리는 DB에 존재하지 않는 키를 찾을 경우 느릴 수 있다.
  • 멤테이블부터 가장 오래전 세그먼트까지 거슬러 올라가야하므로..
  • 그래서 우리는 블룸 필터 를 추가적으로 사용한다.
• 또한 SS테이블을 병합/컴팩션할 순서와 시기를 결정하는 전략도 중요하다
  • 크기 계층 컴팩션
    • 좀더 작고 새로운 SS테이블을 크고 오래된 테이블에 병합
  • 레벨 컴팩션
    • 키 범위를 더 작은 SS테입블로 나누고 오래된 데이터는 개별 레벨로 이동
  • 대표적으로 위 두개가 있고, LevelDB랑 RocksDB는 레벨 컴팩션을 이용한다.
  • HBase는 크기계층 컴팩션, 카산드라는 둘다.

B 트리

#

• 사실 가장 널리 사용되는 색인구조는 B 트리 이다.
  • 1970년에 등장해서 보편적인 색인구조가 됨
  • RDBMS의 표준 색인 구현이며, 많은 비관계형 DB에서도 사용
  • SS테이블과 같이 키로 정렬돤 KV쌍을 갖지만, 설계 철학이 매우 다름
• 로그 구조화 색인은 DB를 수 메가바이트 이상의 가변 크기를 가진 세그먼트로 나누고, 항상 세그먼트를 기록한다.
  • 하지만 B트리는 4KB의 고정 크기 블록이나 페이지로 나누고, 한번에 하나의 페이지에 읽기/쓰기 작업을 수행한다.
    • 각 페이지는 주소나 위치를 통해 식별할 수 있다. (디스크 위의 포인터 느낌)
    • 이를 이용해서 페이지 트리를 구성할 수 있다.
    • 한 페이지는 B 트리의 루트로 지정되고, 색인에서 키를 찾을때 루트에서 하위 페이지로 계속해서 내려간다.
    • 최종적으로 개별 페이지 / 리프 페이지에 도달하게 된다.
• B트리에서 한 페이지에서 하위페이지를 참조하는 수를 분기 계수 (Branching Factor) 라고 한다.
  • 자식노드의 개수라고 생각하면 되는듯?
• B트리에서 갱신작업을 위해선 리프 페이지를 검색하고 페이지의 값을 바꾼 후 디스크에 다시 기록하는 과정을 거친다.
  • 새로운 키를 넣을 여유공간이 없다면 페이지 하나를 두개로 쪼개고, 상위 페이지에서 잘 연결해준다.
• 대부분의 DB는 B트리의 깊이가 3~4만 되어도 충분하다.
  • 분기계수 500의 4KB, 4단계 트리는 256TB까지 저장 가능하다.

신뢰할 수 있는 B트리 만들기

#

• B트리는 기본적으로 쓰기 작업때 덮어쓰기를 수행한다.
  • 그런데, 페이지를 분할하고 기록하는 타이밍에 DB가 고장난다면? 고아 페이지 (orphan page)가 생겨나게 된다.
  • 이를 방지하기 위해선 쓰기 전 로그 (write-ahead log, WAL, redo log, 재실행 로그) 라고 하는 데이터구조를 추가한다.
    • 이는 트리 페이지에 변경된 내용을 적용하기 전에 변경사항을 기록하는 추가 전용 파일이다.
• 다중스레드가 동시에 B트리에 접근하려고 해도 문제다.
  • 스레드가 일관성이 깨진 트리에 접근할 수 있기 때문
  • 따라서 이때 래치(latch, 가벼운 잠금, lock) 으로 트리의 데이터 구조를 보호한다.

B 트리 최적화

#

• WAL대신 쓰기시 복사방식 쓰기
• 키를 축약해서 쓰기
• 리프 페이지를 연속된 공간에 쓰기
• 트리에 포인터 추가
• 프랙탈 트리와 같은 변형 등

B 트리와 LSM 트리 비교

#

• B트리가 LSM트리보다 구현 성숙도가 높지만, LSM트리도 관심을 받는중
  • 대개 경험적으로 LSM이 쓰기에서 더 빠르고, B트리가 읽기에서 더 빠르다!
    • 읽기에서 LSM이 느린 이유는 각 컴팩션 단계의 데이터구조와 SS테이블을 모두 확인해야해서

LSM 트리의 장점

#

• B트리 색인은 모든 데이터 조각을 최소한 두번 기록해야 함
  • 쓰기 전 로그 / 트리페이지
  • 심지어 몇바이트만 바꾸더라도 페이지 하나를 통째로 기록해야함
• 로그 구조화 색인또한 SS테이블을 병합/컴팩션할때 여러번 쓰는데..
  • 이런식으로 DB 쓰기 한번이 DB 수명동안 여러번 쓰기를 진행하게 하는걸 쓰기 증폭(write amplification) 이라고 한다.
• 쓰기가 많다면, 병목은 쓰기에서 있을 수 있다.
  • LSM트리는 B트리보다 쓰기 처리량을 높게 유지할 수 있다.
  • LSM트리는 압축률이 더 좋다.

LSM 트리의 단점

#

• 하지만 컴팩션 과정이 진행중인 읽기/쓰기의 성능에 영향을 줄 수 있다.
  • 그래서 이걸 기다리는동안 요청이 대기해야할 수도
  • 반면에 B트리는 이보다 상황을 예측하기가 쉽다.
• 절대적으로 써야할 양이 많다.
  • 디스크의 쓰기 대역폭은 유한하지만, 로깅 테이블과 멤테이블, 컴팩션 스레드가 이 대역폭을 공유해야 한다.
• 컴팩션 설정을 주의깊게 하지 않으면 컴팩션이 유입 쓰기 속도를 따라갈 수가 없다
• B트리는 각 키가 색인의 한곳에만 정확하게 존재하지만, LSM트리는 여러 세그먼트에 있을 수 있다.

기타 색인 구조

#

• 지금까지는 KV색인을 봤다. 관계형 모델의 기본 키 (primary key) 색인이 대표적인 KV색인이다.
  • 보조 색인에서도 쓸 수 있다.
    • 이때 키가 고유하지 않을 수 있다는 문제가 있을 수 있는데, 이는 두가지 방법으로 해결 가능함.
      • 색인의 각 값에 일치하는 로우 식별자 목록 만들기
      • 로우 식별자 추가
    • B트리 / 로그구조화색인 둘다 사용 가능

색인 안에 값 저장하기

#

• 색인에서, value가 될 수 있는건 raw 자체거나 다른곳의 raw를 가리키는 참조다.
  • 후자의 경우, raw가 저장된 곳을 heap file 이라고 한다.
• 색인 -> 힙이 읽기 성능에 불이익이 커서, 색인 안에 바로 색인된 raw를 저장하기도 한다.
  • 이를 클러스터드 색인 (clustered index)이라고 한다.
• 클러스터드 색인과 비클러스터드 사이의 절충안으로 커버링 색인, 혹은 포괄열이 있는 색인 등이 있다.

다중 컬럼 색인

#

• 지금까지의 모든 색인들은 하나의 키값에만 대응해서, 다중컬럼에 대응하기 어렵다.
• 일반적으론 결합 색인 (concantenated index) 으로 처리할 수 있겠다.
  • 이는 하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순 결합시킨다.
  • (성, 이름) 과 같이 묶어서 저장했따면, 성을 기준으로 정렬된 값 찾기, 특정 (성, 이름) 조합 찾기에는 좋지만 특정 이름을 가진 사람을 찾기는 어렵다.
• 다차원 색인은 조금 더 일반적인 방식이다.
  • 지리공간 데이터 / 위경도에서 많이 쓸텐데 (2차원 범위 쿼리)
    • 이건 지금까지의 B트리/LSM트리로는 어렵다!
  • 한가지 방법은 2차원 위치를 공간-채움-곡선(space-filling curve)로 단일 숫자로 변환해서 B트리 이용하기
  • 다른 방법은 R트리같은 전문 공간 색인 (specialized spatial index) 사용하기 이다.
• 물론 위의 2차원 방법들이 3차원으로 확장되어 색상 (RGB)등으로도 쓸 수 있겠다.

전문 검색과 퍼지 색인

#

• 이제 철자가 틀린 단어와 같이 유사한 키에 대해서도 잘 검색이 되면 좋겠다!
  • 이런 애매모호한(fuzzy) 질의는 어떻게 처리할까?
    • 전문 검색엔진은 해당 단어의 동의어로 질의를 확장하는 방식으로
    • 루씬은 편집거리를 활용해서
      • 추가적으로 인메모리 색인으로 트라이와 유산한 레벤슈타인 오토마톤으로 진행한다.

모든 것을 메모리에 보관

#

• 지금까지의 데이터구조는 모두 디스크 한계에 대한 해결책이었다
• 디스크는 읽기/쓰기를 신경써야하지만.. 램이 꽤 싸지고있지 않는가?
  • 사실 이 공부를 하고 있는 시점 (26/4)에서 램은 진짜 개비싸졌다.
• 아무튼 저때는 쌌으니까, 인메모리 데이터베이스가 개발됐다.
  • 하지만 램은 장비가 재시작되면 데이터가 날라가므로, 보통 이를 허용하는 캐시 용도로만 사용된다.
• 하지만 이를 지속적으로 사용하기 위한 인메모리 DB도 있는데,
  • 이는 배터리 전원 공급 RAM과 같은 특수 하드웨어를 사용하거나
  • 디스크에 변경사항의 로그를 기록하거나
  • 디스크에 주기적인 스냅숏을 기록하거나
  • 다른 장비에 인메모리 상태를 복제하거나 한다.
• 관계형 모델의 인메모리 데이터베이스에는 VoltDB, MemSQL, Oracle TimesTen과 같은것들이 있다.
• 의외로 인메모리 DB의 장점은 디스크 IO바운드에서 오지 않는다.
  • 데이터 구조 자유도 때문! PQ, set 등도 맘껏 쓸 수 있으니
• 언젠가 비휘발성 메모리 (NVM)이 상용화되면 더 발전하지 않을까!

트랜잭션 처리나 분석?

#

• 초창기에 비즈니스 데이터 처리는 상거래(커머셜 트랜잭션)이 대부분이어서 다 트랜잭션이라 불렀는데, 그냥 지금도 논리 단위 형태로의 읽기와 쓰기 그룹을 트랜잭션이라고 한다.
• OLTP (Online Transaction Processing)
  • 기본적인 비즈니스 트랜잭션 처리와 유사하게
  • 댓글 / 액션 / 연락처 등, 일부 키에 대한 적은 레코드를 가지고
  • 사용자 입력을 기반으로 삽입되거나 갱신되는 접근패턴
• OLAP (Online Analytic Processing)
  • 하지만 요새는 데이터분석에도 DB를 사용하기 시작함
  • 원시 데이터를 반환하는 대신, 많은 레코드를 스캔해 일부 칼럼만 읽어 집계 통계를 계산
• 1990년 전후로 회사들은 OLTP 시스템을 분석 목적으로 사용하지 않고, 개별 데이터베이스를 파기 시작했다.
  • 이를 데이터 웨어하우스라고 부른다.

데이터 웨어하우징

#

• OLTP 시스템은 높은 가용성과 낮은 지연시간을 최우선으로 하는데, 분석 쿼리는 비싼 연산이라서 성능을 저하시킬 우려가 컸다.
• 그래서 개별 데이터베이스를 만들어서, 분석가들이 마음껏 쿼리를 날릴 수 있도록 했다.
  • 이 과정은 Extract -> Transform -> Load의 과정으로 이루어진다.

OLTP DB와 데이터 웨어하우스의 차이점

#

• SQL은 분석 질의에 적합하기에 데이터 웨어하우스는 보통 관계형 모델을 이용한다.
• 하지만 OLTP와 데이터 웨어하우스는 각자 다른 질의 패턴에 맞게 최적화되었기 때문에, 시스템의 내부는 완전히 다르다.

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

#

• 데이터 분석에서는 트랜잭션 처리에서와 달리 데이터 모델의 다양성이 훨씬 적다.
  • 많은 DW들은 별모양 스키마(star schema / dimensional modeling) 라고 알려진 방식을 주로 사용한다.
  • 이는 사실 테이블을 가운데 두고, 주변에 차원 테이블을 두는 구조이다.
• 변형으로는 눈꽃송이 스키마가 있다.
  • 별모양 스키마를 더 정규화해서 차원이 하위 차원으로 세분화되는 모양이다.

칼럼 지향 저장소

#

• 테이블에 데이터가 너무 많다면, 효율적으로 저장하고 질의하기 어렵다.
• 그런데, 테이블에 칼럼은 보통 100개 이상이지만 일반적으로 DW 쿼리는 한번에 4~5개 컬럼만 접근한다.
• 대부분의 OLTP DB는 로우 지향으로 데이터를 배치한다.
  • 대신, 모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 개별 파일에 저장하는 방식을 이용할 수 있겠다.
  • 이는 각 칼럼 파일에 포함된 로우가 모두 같은 순서임에 의존한다.

칼럼 압축

#

• 다행히 칼럼 지향 저장소는 압축에 적합하다.
• 여러 압축 기법이 있겠지만. 대표적으로 비트맵 부호화를 보자.
  • 칼럼에서 고유 값의 수는 보통 로우 수에 비해 적으므로, 상당히 sparse하겠다.
  • 따라서 고유값에 대해 1과 0의 비트로 생각하고 압축하면 잘 압축되겠다!

메모리 대역폭과 벡터화 처리

#

• 분석용 DB 개발자는 디스크<->메모리 병목 뿐만 아니라 CPU <-> 메모리 병목, 아키텍쳐 최적화 등까지도 신경써야한다.
• CPU 주기, 캐시등에도 신경쓰고, and와 or과 같은 경우 압축된 컬럼 자체에 연산할 수 있게 설계할 수 있다.
• 이를 벡터화 처리라고 한다.

칼럼 지향 저장소에 쓰기

#

• 칼럼 지향 저장소, 압축 ,정렬은 모두 읽기를 더 빠르게 하지만 쓰기를 어렵게 한다는 단점이 있다.
• 이는 LSM트리에서 한 것과 같이 인메모리 저장소와 병합 파일들을 두는 방식으로 최적화 할 수 있겠다.

정리

#

• 고수준에서 저장소 엔진은 OLTP와 OLAP 두개로 나뉜다.
• OLTP 측면에서 두가지 관점을 확인했다.
  • 로그 구조화 관점
  • 제자리 갱신 관점
• 이번 장에서 선택한 데이터 베이스의 문서를 이해할 수 있는 충분한 어휘와 개념을 갖추었으면 됐다.

❔질문 사항

#

🔗 참고 자료

#