3. Storage and Retrieval

데이터를 저장한 뒤 이를 검색하면 되찾아올 수 있어야 한다. 데이터베이스의 관점에서 저장과 검색에 대해 알아보자. 애플리케이션에 맞는 적절한 데이터베이스를 선택하는 것이 중요하다. 데이터베이스가 트랜잭션 부하에 최적화되었는지 분석에 최적화되었는지를 구분하는 것도 중요하다. 일단은 전통적 관계형 데이터베이스에 대해서 알아보자.

Data Structures That Power Your Database

간단한 키-값 스토어는 O(n)의 탐색 시간이 든다. 그 대신에 인덱스 기반 검색을 이용하면 검색 시간이 줄지만, 이는 쓰기 오버헤드를 불러온다.

Hash Indexes

키-값 스토어는 대개 해시테이블로 구현된다. 가장 간단한 인덱싱 방법은 모든 키가 데이터 파일의 바이트 오프셋(값을 찾을 수 있는 장소)에 매핑된 해시 테이블을 메모리에 올리는 것이다. 디스크 공간을 다 소모하면 로그를 특정한 크기의 세그먼트로 분할한 뒤 이 세그먼트들에 대한 컴팩트화를 수행한다. 이는 로그 내 중복 키를 삭제하고 키에 대한 가장 최근 업데이트만 보존하는 것을 말한다. 컴팩트화 이후 세그먼트 병합도 할 수 있다. 실제 구현에서는 여러 중요한 이슈가 있는데 파일 포맷, 레코드 삭제, 크래시로부터의 복구, 부분적으로만 쓰여진 기록들, 동시성 제어 등이 있다. 덧붙이기 한정 로그 대신 파일을 그 자리에서 업데이트하면 되지 않을까? 하지만 덧붙이기 한정 전략을 쓰는 데는 몇 가지 이유가 있다. 덧붙인 뒤 세그먼트를 병합하는 건 순차적 쓰기 연산이므로 무작위 쓰기보다 훨씬 빠르다. 또한 동시성 제어나 크래시로부터의 복구도 더 쉽다. 데이터 파편화도 피한다. 하지만 해시 테이블 인덱스는 단점도 있다. 해시 테이블이 메모리에 들어가야 하고, 범위 쿼리가 비효율적이다.

SSTables and LSM-Trees

앞에서 알아본 자료구조에서는 키-값 쌍의 순서가 상관이 없었다. 키로 정렬된 구조가 필요하다면? 이는 정렬 문자열 테이블, SSTable이라 한다. 이는 병합 정렬 알고리즘을 사용하므로 세그먼트 병합이 간단하고 빠르다. 또한, 키를 찾기 위해 메모리 내 모든 키의 인덱스를 가질 필요도 없다. 쓰기 이전에 기록들을 블록으로 그룹화해 압축하는 것도 가능하다.

Constructing and maintaining SSTables

저장된 구조를 디스크에 유지하는 것도 가능하지만, 메모리에 유지하는 것이 훨씬 쉽다. 레드-블랙 트리나 AVL 트리 등을 쓸 수 있다. 이러면 저장소 엔진을 다음과 같이 만들 수 있다: 데이터가 들어오면 인-메모리 균형 트리 자료구조에 이를 업데이트한다. 이 멤테이블이 기준치보다 커지면 이를 SSTable 파일 디스크에 쓴다. 읽기 요청을 수행하기 위해서는 멤테이블에서 먼저 찾고 그 뒤에 가장 최근의 디스크상 세그먼트에서 찾고, 그 다음 최근의 세그먼트에서 찾고, 이를 반복한다. 시간에 따라 세그먼트에 대한 병합과 컴팩트화를 수행한다. 이는 한 가지 문제점이 있는데, 데이터베이스가 크래시되면 가장 최근의 쓰기가 날아간다는 것이다. 디스크에 별개의 로그를 유지해 이를 피할 수 있다.

Making an LSM-tree out of SSTables

위의 알고리즘들은 LevelDB, RocksDB 등에서 쓰인다. 이런 인덱스 자료 구조는 로그-구조 병합 트리 (LSM-Tree)로 묘사된다. Lucene은 텀 딕셔너리를 저장한다.

Performance optimizations

저장소 엔진이 실제로 잘 작동하려면 많은 세부 구현을 신경써야 한다. SSTable이 컴팩트화되고 병합되는 순서와 타이밍을 결정하는 데도 여러 다른 전략들이 있다. 가장 흔한 전략은 크기-티어와 층별 컴팩트화이다. 기본적인 LSM-트리의 아이디어는 배경에서 병합되는 SSTable의 폭포수를 유지하는 것이며 이것이 간단하고 효과적이다.

B-Trees

가장 흔히 쓰이는 인덱싱 구조는 B-트리이다. 이는 SSTable처럼 정렬 순서로 키-값 쌍을 저장하지만 데이터베이스를 고정 크기 블록이나 페이지로 분해한다. 각 페이지는 주소나 장소를 사용해 식별되어 한 페이지가 다른 페이지를 참조할 수 있도록 한다. 포인터와 비슷하지만 메모리가 아니라 디스크상이라는 것이 다르다. 한 페이지의 자식 페이지에 대한 참조 수는 가지 인자라고 불린다. B-트리 내 존재하는 키를 업데이트하려면 그 키를 담는 리프 페이지를 찾은 뒤 그 값을 바꾸고 그 페이지를 디스크에 다시 쓴다. B-트리는 균형 트리이므로 키 n개일 때 깊이는 O(log n)이다.

Making B-trees reliable

B-트리의 기본 기반 쓰기 연산은 디스크 페이지에 새 데이터를 쓰는 것이다. 이는 실제 하드웨어 연산으로도 볼 수 있다. 어떤 연산은 여러 다른 페이지를 덮어쓰는 것을 필요로 하기도 한다. 이 경우 페이지들 중 일부가 쓰여졌을 때 크래시되면 오염된 인덱스가 된다. 데이터베이스가 크래시에 대해 강건하도록 하려면 직접 쓰기 로그를 추가 자료 구조로 디스크에 갖고 있어야 한다. 페이지를 그 자리에서 업데이트하는 추가적인 복잡성은 동시성을 고려할 때 온다.

B-tree optimizations

B-트리에는 여러 최적화가 있다.

  • 어떤 데이터베이스는 쓰기 시 복사 방식을 사용한다.
  • 전체 키가 아니라 이를 축약한 키를 저장함으로써 페이지 내 공간을 저장할 수 있다.
  • 트리의 레이아웃을 바꿔서 리프 페이지들이 디스크 내 순차적인 순서로 등장하도록 할 수 있다.
  • 각 리프 페이지가 인접 형제들에 대한 참조 포인터를 들고 있을 수 있다.
  • 프랙탈 트리 등의 변형이 존재한다.

Comparing B-Trees and LSM-Trees

B-트리 구현이 LSM-트리에 비해 대개 더 성숙하였지만, LSM-트리도 성능 면에서 흥미로운 지점이 있다. 하지만, 벤치마크들은 대개 섣불리 결론짓기 어렵고 부하에 따라 크게 변한다는 것도 명심해야 한다.

Advantages of LSM-trees

B-트리 인덱스는 모든 데이터의 조각을 최소한 2회 써야 한다: 한 번은 직접 쓰기 로그에, 하나는 트리 페이지에. 로그-구조 인덱스 또한 반복된 컴팩트화와 SSTable 병합으로 인해 데이터를 여러 회 다시 써야 한다. 쓰기 위주 애플리케이션은 성능 병목이 데이터베이스가 디스크에 얼마나 쓰기 연산을 하냐의 비율이 될 수 있다. 이 경우 LSM-트리는 B-트리에 비해 많은 쓰기 처리량을 유지할 수 있다. 쓰기 확대 비율이 낮고 여러 페이지를 덮어씌우는 대신에 컴팩트한 SSTable 파일을 병합하기 때문이다. LSM-트리는 압축율도 더 낫고 파일 크기도 더 작다. SSD에서는 펌웨어가 내부적으로 로그 구조 알고리즘을 써서 무작위 쓰기를 순차적 쓰기로 바꾸기 때문에 저장소 엔진의 쓰기 패턴은 덜 중요하지만, SSD에서도 더 적은쓰기 확대와 줄어든 파편화는 여전히 가치가 있다.

Downsides of LSM-trees

로그 구조 저장소의 단점은 컴팩트화 과정이 진행 중인 쓰기와 읽기의 성능을 저해할 수 있다는 것이다. 쓰기 처리량이 높을 때 컴팩트화에서 일어나는 또 다른 이슈는 디스크의 유한 쓰기 대역폭이 초기 쓰기와 배경에서 동작 중인 컴팩트화 스레드간 공유되어야 한다는 것이다. 쓰기 처리량이 높지만 컴팩트화가 세부 조절되지 않으면, 컴팩트화가 들어오는 쓰기의 속도를 따라갈 수가 없다. B-트리의 이 경우 이점은 각 키가 인덱스 내 한 장소에만 존재하므로 강한 트랜잭셔널 시맨틱을 구현하기 좋다. B-트리는 대부분의 부하에 대해 일관적으로 좋은 성능을 낸다.

Other Indexing Structures

지금까진 키-값 인덱스를 다루었다. 이외에도 이차 인덱스가 존재하는 경우도 많다. 이는 키-값 인덱스로부터 쉽게 생성할 수 있다.

Storing values within the index

인덱스 내 키는 쿼리가 검색하는 것이지만 값은 관심이 있는 실제 행이거나 다른 곳에 저장된 행에 대한 참조일 수 있다. 후자의 경우 행은 힙에 저장되어 특정한 순서를 가지지 않을 수 있고 삭제된 행을 추적해 덮어쓸 수도 있다. 키를 바꾸지 않고 값을 변경한다면 힙 파일 접근법이 매우 효과적이다. 새 값이 이전 값보다 크지 않은 이상 기록이 제자리에서 덮어씌워질 수 있다. 새 값이 더 크다면 힙의 새 위치를 찾아야 할 수도 있다. 어떤 경우에는 힙 참조는 읽기에 대한 성능 병목이 되기 때문에 인덱스 행을 인덱스에 직접 저장하는 클러스터화된 인덱스도 생각할 수 있다. 클러스터화된 인덱스와 비클러스터화된 인덱스의 절충은 커버링 인덱스나 포함 행과의 인덱스이다. 데이터 중복이 있을 경우 클러스터와 커버링 인덱스는 읽기를 빠르게 할 수 있지만 추가적인 저장소를 필요로 하고 쓰기 오버헤드는 증가한다.

Multi-column indexes

지금까지 다룬 인덱스는 단일 키를 값에 매핑한다. 이는 테이블의 복수 열을 쿼리하기엔 충분치 않다. 복수 열 인덱스에 대한 가장 흔한 유형은 연결 인덱스로, 한 열을 다른 열에 덧붙여 여러 필드를 한 키로 병합하는 것이다. 이는 여러 열을 한 번에 쿼리하는 일반적인 방식으로, 지역과 관련된 데이터를 담을 때 특히 중요하다. 이 때는 이차원 인덱스가 필요하기 때문에 이를 병합하는 방식도 있다. 복수 열 인덱스 방식은 지역과 관련된 것뿐만 아니라 다른 여러 예시에도 쓰일 수 있다.

Full-text search and fuzzy indexes

지금까지 다룬 모든 인덱스는 정확한 데이터가 있고 키의 정확한 값을 검색하거나, 정렬된 순서의 키의 값들을 쿼리하였다. 하지만 비슷한 키를 찾으려면 어떻게 해야 할까? 완전 텍스트 검색 엔진 등에서 말이다. SSTable류 구조를 쓸 수도 있고 문서 분류/기계 학습도 쓸 수 있다.

Keeping everything in memory

지금까지 다룬 자료구조는 디스크의 한계로 인해 성능 문제가 있다. 하지만 이는 RAM보다 비용 면에서 더 싸다. RAM의 가격도 더 싸지고 있기 떄문에 인-메모리 데이터베이스의 개발도 활성화되고 있다. 어떤 인-메모리 키-값 스토어는 캐싱의 용도로만 쓰인다. 이는 기계가 재시작되었을 때 데이터가 유실되어도 상관없다. 그러나 일반적인 경우에는 인-메모리 데이터베이스가 재시작되면 디스크나 그 복제에서 네트워크를 통해 상태를 다시 불러와야 한다. VoltDB, MemSQL, Oracle TimesTen 등이 있다. 인-메모리 데이터베이스의 성능은 디스크로부터 읽기를 안 하기 때문에 좋은 것이 아니라 인-메모리 자료구조를 디스크에 쓸 필요가 없는 식으로 유지해서 좋은 것이다. 성능 외에도 인-메모리 데이터베이스의 다른 흥미로운 점은 디스크 기반 인덱스로는 구현하기 어려운 데이터 모델을 제공하는 것이다. 최근의 연구는 인-메모리 데이터베이스 구조는 가용 메모리보다 더 큰 데이터셋을 다룰 수 있도록 확장될 수도 있음을 보여준다. 저장소 엔진 설계의 추가적인 변화는 비휘발성 메모리 기술이 더 널리 퍼질 때 필요해질 것이다.

Transaction Processing or Analytics?

상업적 데이터 처리 초기에는 데이터베이스 쓰기는 상업 트랜잭션으로 대응되었다. 이후 트랜잭션이란 항은 논리적 유닛을 형성하는 읽기/쓰기 그룹으로 일컬어지게 되었다. 이는 형태는 다를지라도 개념은 상업적 트랜잭션과 비슷하다. 하지만, 데이터베이스는 데이터 분석에 대해서도 많이 쓰이게 되었으며 이는 접근 방식이 완전히 다르다. 이는 한 번에 초대량의 기록을 찾고 기록별 열의 수는 적고 통합 통계량 등을 계산해야 한다는 차이점이 있다. 이런 별개의 데이터베이스는 데이터 웨어하우스로 불린다.

Data Warehousing

기업은 여러 다른 트랜잭션 처리 시스템을 가질 수 있다. 이 때 트랜잭션 처리 시스템은 가용성이 높아야 하고 지연 시간은 적어야 한다. 이에 반해 데이터 웨어하우스는 트랜잭션 처리 시스템 연산에 영향을 미치지 않고 그 내용을 쿼리할 수 있도록 하는 별개의 데이터베이스이다. 이런 별개의 웨어하우스를 쓰는 데 있어 이점은 이 데이터 웨어하우스는 분석적 접근 패턴에 대해 최적화될 수 있다는 것이다.

The divergence between OLTP databases and data warehouses

데이터 웨어하우스의 데이터 모델은 대개 관계적이다. SQL은 분석적 쿼리에 잘 맞기 때문이다. 표면적으로, 데이터 웨어하우스와 관계형 OLTP 데이터베이스는 SQL 쿼리 인터페이스를 가지므로 비슷하게 보이지만, 내부는 서로 다른 쿼리 패턴에 의해 최적화되어 있어 매우 다르다. 마이크로소프트 SQL 서버나 SAP HANA 등은 데이터 웨어하우스와 트랜잭션 프로세싱에 대한 동시적인 지원을 제공한다. 이외에도 Teradata, Vertica, SAP HANA, ParAccel 등이 존재한다.

Stars and Snowflakes: Schemas and Analytics

많은 데이터 웨어하우스는 스타 스키마를 쓴다. 이 이름은 테이블 관계가 시각화되었을 때 사실 테이블이 차원 테이블로 둘러싸여 있고 이 테이블간 연결이 별의 광선처럼 보이기 때문에 붙여졌다. 이의 변형은 눈꽃많은 데이터 웨어하우스는 스타 스키마를 쓴다. 이 이름은 테이블 관계가 시각화되었을 때 사실 테이블이 차원 테이블로 둘러싸여 있고 이 테이블간 연결이 별의 광선처럼 보이기 때문에 붙여졌다. 이의 변형은 눈송이 스키마로, 차원들이 부분차원들로 분해되는 스키마이다. 일반적인 데이터 웨어하우스에서 테이블은 매우 넓을 수 있다.

Column-Oriented Storage

사실 테이블에 열의 수와 몇 조 개이고 데이터가 페타바이트가 있으면 이를 저장하고 효율적으로 쿼리하는 것은 어려운 문제이다. 차원 테이블은 대개 훨씬 더 작다. 열 지향 저장소의 아이디어는 간단하다: 한 행의 모든 값을 같이 담지 말고, 한 열의 모든 값을 같이 담는 것이다. 각 열이 별개의 파일에 있다면 쿼리는 이 열들을 읽고 파싱하기만 하면 충분하다. 열 지향 저장소 레이아웃은 각 열 파일이 행들을 같은 순서로 담고 있어야만 한다.

Column Compression

쿼리에 필요한 열만 디스크에서 로딩하는 것과 함께, 데이터를 압축함으로써 디스크 처리량의 요구를 줄일 수 있다. 하나의 기법은 비트맵 인코딩이다. 이는 데이터 웨어하우스에 매우 잘 맞는다. 여러 다른 방법도 있다.

Memory bandwidth and vectorized processing

수백만 행을 스캔해야 하는 데이터 웨어하우스 쿼리에 대해서는 큰 병목은 디스크로부터 메모리로 데이터를 얻는 것이다. 하지만 그것뿐만 아니라 메인 메모리로부터 CPU 캐시를 효율적으로 사용해서 브랜치 예측 실패나 CPU 명령어 처리 파이프라인의 거품을 피하고 단일 명령어 복수 데이터 명령어를 사용하는 것도 중요하다. 열 지향 저장소 레이아웃은 CPU 사이클도 벡터화된 처리로 효율적으로 사용할 수 있다.

Sort Order in Column Storage

열 스토어에서는 행이 어떤 순서로 저장되었는지는 상관이 없다. 하지만 행의 저장 순서를 도입하는 것도 가능하다. 각 열을 독립적으로 저장하는 것은 의미가 없고 모든 행을 한 번에 정렬한 뒤 이를 분리해야 한다. 이런 정렬된 순서의 이점은 열의 압축을 도울 수 있다는 것이다. 이는 첫 번째 정렬 키에 대해 가장 압축 효과가 좋다.

Several different sort orders

이 발상의 영리한 확장은 C-Store, Vertica 등에 도입되었다. 열 지향 스토어에 복수의 정렬 순서를 두는 것은 행 지향 스토어에 복수의 이차 인덱스를 두는 것과 비슷하지만, 행 지향 스토어는 모든 행을 한 장소에 담고 이차 인덱스는 매칭되는 행에 대한 포인터이지만 열 지향 스토어에서는 그렇지 않다.

Writing to Column-Oriented Storage

이런 최적화는 데이터 웨어하우스에서 매우 효율적이다. 다만 B-트리에서 보이는 제자리 업데이트는 압축 열에 대해서는 쓸 수 없다. 대신 LSM-트리라는 좋은 해법이 존재한다. 쿼리는 디스크의 열 데이터와 메모리의 최근 쓰기를 전부 조사한 뒤 이를 조합해야 한다.

Aggregation: Data Cubes and Materialized Views

모든 데이터 웨어하우스가 열 스토어일 필요는 없다. 전통적 행 지향 데이터베이스나 다른 아키텍쳐도 쓰인다. 하지만 열 스토어가 훨씬 빠르고 인기가 많다. 데이터 웨어하우스의 다른 관점은 물질화된 종합으로, 합, 최대, 최소 등의 통계량을 물질화해 유지하고 업데이트하는 것이다. 이의 예는 데이터 큐브나 OLAP cube 등이 있다. 이의 이점은 특정한 쿼리가 미리 계산되어 있으므로 매우 빠르다는 것이다. 단점은 원시 데이터를 쿼리하는 것만큼 유연성이 있지 않다는 것이다.

Summary

이 장에서는 데이터베이스가 저장과 검색을 어떻게 다루는지를 알아보았다. 데이터를 데이터베이스에 저장하고 이후에 그 데이터를 쿼리할 때에 무슨 일이 일어나는가? 고수준에서는 저장소 엔진은 2개의 넓은 카테고리로 나뉜다: 트랜잭션 프로세싱에 최적화된 OLTP, 분석에 최적화된 OLAP. 이는 사용례의 접근 패턴에 큰 차이가 있다.

  • OLTP는 사용자 중심적이고, 대량의 요청을 받는다. 이 부하를 다루기 위해, 애플리케이션은 각 쿼리의 작은 수만을 다뤄야 한다. 이 애플리케이션 요청은 어떤 종류의 키에 대한 사용을 기록하고, 저장소 엔진은 인덱스를 써서 요청된 키에 대한 데이터를 찾는다. 디스크 탐색 시간은 종종 병목이 된다.
  • 데이터 웨어하우스나 유사한 분석 시스템은 덜 잘 알려져 있다. 산업 분석가들에게 쓰이고 최종 사용자에게는 잘 안 쓰이기 때문이다. 이는 OLTP 시스템에 비해 훨씬 적은 수의 쿼리를 다루지만, 각 쿼리가 매우 규모가 크고, 짧은 시간에 수백만 기록을 스캔해야 한다. 디스크 대역폭 (탐색 시간이 아닌)이 종종 병목이 되며, 열 지향 저장소가 이런 부하에 대해 폭넓은 인기를 얻어가고 있다.

OLTP 관점에서는 두 가지 주된 저장소 엔진 분류가 있다.

  • 로그 구조류로, 파일 끝에 덧붙이기와 더 이상 쓸모없는 파일 삭제만을 지원한다. 쓰여진 파일에 대한 업데이트는 지원하지 않는다. Bitcask, SSTables, LSM-trees, LevelDB, Cassandra, HBase, Lucene 등이 있다.
  • 제자리 업데이트류로, 디스크를 덮어씌워질 수 있는 고정 크기 페이지의 집합으로 다룬다. B-트리는 가장 큰 예로, 모든 메이저 관계형 데이터베이스에 쓰이며 많은 비관계형에도 쓰인다.

로그 구조 저장소 엔진은 비교적 최근의 개발이다. 이 핵심 아이디어는 이들은 체계적으로 무작위 접근 쓰기를 디스크에 대한 순차적 쓰기로 바꿔 하드 드라이브나 SSD의 성능 특성으로 인한 높은 쓰기 처리량을 가능케 한다. OLTP 관점을 마치면서, 몇 가지 더 복잡한 인덱싱 구조와, 데이터를 전부 메모리에 유지하는 데 최적화된 데이터베이스도 알아보았다.

이후 데이터 웨어하우스의 고수준 아키텍쳐를 알아보기 위해 저장소 엔진의 내부를 알아보았다. 이 배경은 왜 분석적 부하가 OLTP와 다른지를 나타낸다. 쿼리가 순차적으로 많은 수의 행을 스캐닝할 때에는 인덱스는 덜 중요하다. 그 대신에 디스크로부터 쿼리가 읽는 양을 최소화하기 위해 데이터를 매우 컴팩트하게 인코딩하는 것이 중요해진다. 열 지향 저장소가 이 목적을 어떻게 이루는지 알아보았다.

애플리케이션 제작자로서, 저장소 엔진의 내부를 알고 있다면, 특정 애플리케이션에 어떤 도구가 가장 잘 맞는지를 알게 될 것이다. 데이터베이스의 튜닝 변수를 조절할 필요가 있다면, 이런 이해는 그 값을 어떻게 조절하면 어떤 효과가 나올지를 알게 해 준다.

이 장이 당신을 특정 저장소 엔진에 대한 전문가로 만들어주진 않지만, 선택할 데이터베이스에 대한 개요는 잡을 수 있을 것이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중