왜 배우는가
애플리케이션을 서비스할 때 어떤 기능에서는 쓰기 작업이 많이 일어나고, 어떤 기능에서는 읽기 작업이 많이 일어난다. 이렇게 특정 작업에서 작업부하(workload)가 있을 때, 좋은 성능을 내게끔 저장소 엔진을 컨트롤하려면(ex. 인덱싱) 그 엔진에서 내부적으로 어떻게 그 작업이 수행되는지(ex.인덱싱이 어떻게 되는지) 알아둘 필요가 있다.
로그
뒤에 새로 추가하는 것만 가능한 append-only 데이터 파일이다. 우리가 일반적으로 아는 log와는 다른 log이다. log는 데이터베이스에서 사용하는 데이터 파일이다. 파일 마지막에 데이터만 추가하면 되는 방식이라 매우 간단하지만 성능이 빠르기 때문에 많은 데이터베이스에서 사용한다.
쓰기는 O(1)의 시간복잡도를 가지지만, 읽기 작업에 대해서는 처음부터 끝까지 스캔해야 하므로 O(N)의 복잡도를 가진다.
특징 정리
•
데이터 추가 시 파일 뒤에 추가하기만 하면 된다.
•
쓰기에서는 빠르나, 읽기에서는 느리다.
색인(Indexing)
색인이 필요한 이유
데이터베이스에 많이 사용하는 데이터 파일인 로그는 읽기 작업에서 O(N)의 복잡도를 가진다. 데이터베이스에 레코드 수가 많아질 수록 읽기 처리 속도가 느려진다. 따라서 데이터베이스에서 검색을 효율적으로 하기 위한 다른 데이터 구조인 ‘색인'이 필요하다.
색인은 기본 데이터(primary data)에서 파생된 추가적인 구조이다. 풀어서 설명하면, 색인은 기본 데이터의 효율적인 검색을 위해 추가적으로 만들어진 또 하나의 데이터이다.
색인은 쓰기 속도를 느리게 만든다. 데이터가 추가될 때마다 색인 데이터에도 그 변경사항을 반영해주어야 하기 때문이다. 따라서 읽기 성능은 향상되지만 쓰기 속도는 느려진다. 따라서 데이터베이스는 자동으로 색인해주지 않고 개발자의 의도에 따라 수동으로 색인하게 되어있다. 데이터베이스 시스템 상 고려해야 할 트레이드오프이기 때문에 색인을 남발하지 말고 필요한 경우(데이터가 너무 많아 읽기가 정말 느린 경우)에 사용한다.
특징 정리
•
데이터베이스에 레코드가 많아질 경우, 읽기 성능을 높이기 위해 사용한다.
•
색인 역시 기본 데이터에 대한 검색을 위해 만들어진 추가적인 데이터이다.
•
쓰기 작업 시, 색인에 대한 작업도 들어가야 하기 때문에 읽기 성능은 향상되지만 쓰기 속도는 느려진다.
해시 색인
로그 파일에 대한 가장 간단한 색인 전략은 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시맵에 저장하는 것이다. 인메모리 해시맵에서 키는 텍스트 데이터가 되고, 값은 그 텍스트가 파일에 위치한 바이트 오프셋이 된다.
인메모리 해시맵은 모든 데이터를 메모리에 저장하므로 읽기, 쓰기 속도 모두 성능이 높다. 이런 방식은 값이 자주 갱신되는 경우(쓰기 작업이 많이 수행되는 경우)에 유리하다. 예를 들어 동영상 url에 대한 ‘조회수 증가'는 쓰기 작업은 많이 일어나지만 그에 비해 url 데이터 수 자체는 적다.
하지만 이 역시 항상 데이터를 추가만 한다면 결국 디스크 공간이 부족해진다. 때문에 특정 크기의 세그먼트로 로그를 나누어 관리한다. 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 쓰기 작업을 진행한다. 그리고 컴팩션을 통해 로그에서 중복된 키를 버리고 각 키의 최신 값만 유지한다.
과정 정리
•
세그먼트가 특정 크기 도달 시, 병합을 위한 새 세그먼트 파일 생성
•
이전 세그먼트들 컴팩션과 병합 수행(백그라운드에서 수행)
•
컴팩션 수행 중에는 이전 세그먼트에서 읽기, 쓰기 작업 수행
•
병합이 끝난 후, 새 세그먼트로 전환
•
기존 세그먼트 파일 삭제
해시테이블 색인의 한계
•
모든 데이터에 대해 키를 저장한다.
•
메모리 상에 색인을 저장하는 데는 용량의 한계가 있다. 디스크에 저장 시 좋은 성능을 기대할 수 없다.
•
범위 질의(range query)를 하는 경우 해시 맵에서 모든 개별 키를 조회해야 한다.
예를 들어 k0 ~ k1000 사이의 데이터를 스캔 시 모든 키를 조회해야 한다.
SS테이블과 LSM트리
해시테이블의 한계를 어떻게 극복할까
세그먼트 병합이 파일이 메모리 용량을 넘더라도 간단하고 효율적이다. 병합 시 키를 정렬한다. 키를 정렬하는 게 메모리 용량과 검색 속도에 무슨 영향을 끼칠까?
특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없다. 먼저 SS테이블에 대한 메모리의 희소 색인은 해시 색인과 마찬가지로 키를 텍스트 데이터로, 값을 바이트 오프셋으로 하고 있다. SS테이블이 정렬되어있으므로 이 데이터에 대한 바이트 오프셋 역시 정렬되어 있다.
따라서 a,b,c가 SS테이블에 있고 b를 찾으려면 a와 c의 색인만으로도 찾을 수 있다. 메모리 상에서 a와 c의 바이트 오프셋을 찾아 디스크 상에 있는 SS테이블에서 a부터 c까지의 키를 스캔하면 된다. 스캔해야할 키의 수가 적어지므로 검색 속도도 빨라진다.
정리
•
레코드 수가 많은 데이터베이스에 대한 색인
◦
해시테이블: 모든 걸 색인하므로 메모리 공간이 부족할 수도 있고, 특정 질의에서 읽기 속도 성능 떨어짐
◦
S테이블: 정렬된 데이터 중 일부만 색인하므로 필요한 메모리 공간도 적고, 스캔할 데이터의 범위도 좁아지므로 읽기 성능 좋음
그렇다면 색인에 쓰기는 어떻게 할까?
최근에 들어온 쓰기 데이터를 멤테이블(인메모리 테이블)에 저장하는데, 이 경우 데이터베이스가 고장나면 멤테이블의 쓰기 데이터가 손실 된다.
따라서 ‘쓰기 데이터(로그 파일)를 디스크 상에 먼저 저장 → 멤테이블에 저장 → SS테이블에 저장 → 디스크에서 로그 파일 제거'와 같은 순서로 쓰기 데이터의 손실을 막는다.
LSM트리
SS테이블에서 세그먼트를 병합하고 정렬하는 알고리즘은 LSM 트리로 수행된다. LSM 트리는 크기 계층, 레벨 컴팩션 등 SS테이블의 세그먼트를 컴팩션하는 순서와 시점을 결정하는 전략이 있다. 사이즈 계층 컴팩션은 새 세그먼트를 다음 세그먼트와 병합해 점점 더 큰 세그먼트를 만든다. 레벨 컴팩션은 더 여러 chunk로 나누고 각 레벨의 오래된 세그먼트는 다음 레벨로 이동한다. 새 세그먼트는 다음 레벨의 세그먼트와 병합을 진행해 계층 컴팩션보다는 디스크 공간을 덜 사용한다. 복잡하지만 핵심은 LSM 트리는 SS테이블 새그먼트를 연쇄적으로 병합하는 알고리즘이라는 것이다.
LSM 트리의 성능 최적화, bloom filter
이렇게 데이터를 chunk로 나눴을 때 데이터에 접근하려면 첫번째 레벨의 세그먼트를 찾아보고, 없으면 그 다음 레벨의 세그먼트를 찾아보는 식으로 검색한다. 따라서 LSM 트리에서 존재하지 않는 키에 접근하는 경우 가장 오래된 세그먼트까지 내려가봐야하기 때문에 시간이 오래 걸릴 수 있다.
이런 경우를 대비해 새 세그먼트를 생성할 때는 이 세그먼트에 대한 블룸 필터도 함께 추가해준다. 블룸 필터는 저장소에 데이터가 있을 확률을 계산하기 위한 추가적인 데이터 구조이다. 블룸 필터를 통해 데이터가 있을 확률을 구한 뒤 있다고 판단되면 해당 세그먼트에서 데이터를 찾는다.
블룸 필터를 쉽게 설명하기 위해 예를 들어보겠다. 블룸 필터는 세그먼트의 각 데이터를 해싱하여 이 값을 비트로 변환한 후 비트맵을 만든다. 이렇게 만든 비트맵을 모두 합친 딕셔너리가 블룸필터가 된다. 예를 들어 cat이라는 데이터가 들어왔을 때 hashFn(’cat’) = 15 고 이를 비트맵으로 변환한 후 이 값과 블룸필터의 비트맵을 & 연산한다.
비트맵 1111, 블룸필터 딕셔너리 1011111 이렇게 된 경우 자기 자신인 1111을 반환한다. &연산은 각 자리 수에 대해 둘 다 1인 경우에만 1을 반환하므로 & 연산 이후 자신의 값을 반환하면 세그먼트에 그 데이터가 있다고 판단하는 것이다.
그런데 블룸필터는 여러 비트맵을 합친 것이므로 다른 단어로 연산했을 때에도 자신과 같은 비트맵이 나오는 경우가 있을 수 있다. 이런 경우 데이터가 없는데 있다고 판단하는 false positive를 범할 수 있다고 한다.
핵심은 ‘블룸 필터 → 데이터가 세그먼트에 있을 확률 높아? → 응: 찾아 → 아니: 다음 세그먼트’ → 세그먼트 끝날 때까지 반복.
틀린 내용이 있으면 말씀해주세요.
references
•
책 데이터중심어플리케이션설계 3장
•
https://www.youtube.com/watch?v=_5vrfuwhvlQ LSM tree, bloom filter
