[DB] NoSQL 스토리지 엔진 발전 과정
1학기에 Hadoop 수업을 들었는데, 가장 마지막 수업의 제일 마지막 내용에 SSTable이 나왔다. 수업에서는 Hadoop Ecosystem 중 하나인 HBase에서 쓰이는데, SSTable에 대해 더 찾아보니까 NoSQL Storage Engine 발전 과정과 관련이 있었다.
이번 포스팅은 RDB에 사용되는 알고리즘인 B-Tree에 대해 알고 있는 상태로 글을 읽어야 더 도움이 된다. 왜냐하면 B+Tree는 읽기 성능이 좋은 기술이고, LSM Tree는 쓰기 성능이 좋은 기술이라 RDB와 NoSQL의 대표적인 차이점이니 생각해보면서 읽어보면 더 많은 내용을 얻어갈 수 있다.
1. Append Only File (AOF)
우선 시작하기 전에 글에 나오는 데이터는 로그 데이터이고, key-value 구성이라고 가정한다.
---------------------
| key | value |
---------------------
| 고양이 | 1 |
| 강아지 | 2 |
| 노루 | 3 |
| 토끼 | 4 |
---------------------
일반적인 로그 데이터는 추가만 하지, 데이터 삭제/수정은 하지 않는다.
이것을 Append Only File로 AOF라고 부른다.
AOF를 사용하는 가장 원시적인 NoSQL의 기본 명령어는 set, get만 있다고 해보자
- set: 데이터를 추가한다
- get: 데이터를 조회한다
[1] set 동작 방식
[2] get 동작 방식
이런 방식을 통해 AOF는 다음과 같은 특징을 가진다고 말할 수 있다.
- 쓰기 연산 (set) : 파일 맨 마지막에 추가만 하면 되므로 빠르게 동작한다.
- 읽기 연산 (get) : 맨 아래부터 데이터를 찾아보기 때문에 시간이 오래 걸린다.
그래서 AOF 기반으로 동작하는 원시적인 NoSQL은 쓰기 성능이 RDB보다 높다.
2. AOF 이후의 발전 과정
위 내용만 있는 상태에서 하나씩 순차적으로 개선 방향을 알아가보자
[1] File Segment
AOF 파일만 있고, 아무런 개선이 되지 않은 상황이라면 위와 같이 하나의 파일에만 계속 데이터가 추가되고 있는 상황일 것이다. 이때 디스크 용량이 부족하게 되면 더 이상 데이터를 적재할 수 없게 되고, 결국 Scale Up을 통해서 디스크 용량을 추가해야한다. 하지만 Scale Up은 비용이 Scale Out 보다는 비싸기 때문에 Scale Out을 사용하는게 훨씬 합리적이라 파일을 분리하게 된다. 이 방법이 File Segment라고 부른다.
그래서 분리하면 위와 같이 나눌 수 있게 되고, 여러 디스크에 데이터를 저장할 수 있게 된다.
이때 데이터 조회 방식은 기존 방식이랑 살짝 달라진다.
[AS-IS]
1. 파일에 가장 마지막으로 저장된 데이터부터 순서대로 읽는다.
[TO-BE]
1. 가장 최근에 생성된 파일부터 순서대로 읽는다.
2. 파일에 들어가면 가장 마지막으로 저장된 데이터부터 순서대로 읽는다.
기존엔 데이터를 최신순으로 읽는다면, 이제는 파일도 최신순, 데이터도 최신순으로 읽게 된다.
[2] Compaction
이제 데이터를 여러 디스크에 분산해 저장할 수 있게 되었다. 큰 문제는 하나 해결 했지만, 새로운 문제가 주어진다. 만약 이미 저장된 데이터가 set으로 새로 추가가 된다면 기존에 있던 데이터는 쓸모가 없어지고, 이 말은 디스크에 쓸모 없는 데이터가 추가된다는 말이다. 이 쓰레기 데이터를 없애려면 어떻게 해야할까?
우선 드는 생각은 새로 값이 업데이트가 될 때마다 기존 데이터를 삭제하는 방법이다. 하지만 이 방법은 디스크 용량을 굉장히 효율적으로 사용할 수 있다는 장점이 있지만, 값을 삭제하는 로직은 아래와 같은 과정을 실행해야한다.
1. 데이터베이스에 {key, value} = {"개구리", 15} 데이터가 추가되었다.
2. 이전 모든 파일, 모든 데이터에 key = "개구리"인 값을 살펴보고 삭제한다.
이게 새로운 값이 추가될 때마다 로직이 실행된다고 해보자. 그러면 모든 데이터를 탐색해야하고, 결국 데이터의 수만큼 완전 탐색을 수행하게 된다. 그러면 어떤 방법으로 디스크에 있는 중복 데이터를 제거 했을까?? 답은 간단하다. 파일 내부의 데이터만 중복 데이터를 삭제하는 것이다. 각 파일끼리 비교하면 중복데이터는 있지만, 파일 내부에는 유일하기 때문에 디스크의 효율성과 데이터 정리 속도의 중간점을 타협한 방법이다.
[3] Sorted String Table (SSTable)
이제 로그 데이터를 여러 디스크에 저장할 수도 있고, 파일 안에 중복 key 데이터를 제거해서 디스크 용량을 어느정도 효율적으로 사용할 수 있게 되었다. 그럼 이제 다른 개선 방향을 찾아보자
이번엔 읽기 연산을 최적화하는 방법이다. 아직까지 데이터를 읽는 방법은 기존 AOF 방식 그대로 이기 때문에 다음과 같이 완전 탐색으로 동작하게 된다.
1. 가장 최근에 생성된 파일부터 순서대로 읽는다.
2. 파일에 들어가면 가장 마지막으로 저장된 데이터부터 순서대로 읽는다.
위 Compaction 사진에서는 하나의 파일에 데이터가 5개가 들어있지만, 실제 데이터는 엄청 많은 데이터가 들어가 있을 것이다. 그러면 O(N)의 시간을 최적화하는 방법이 필요하겠고, 이거는 탐색 알고리즘을 통해 해결할 수 있다. 바로 코딩테스트에서 자주 사용하는 이진탐색이다. O(N) → O(logN)으로 줄일 수 있지만, 이진 탐색을 사용하려면 파일을 정렬해야한다.
이렇게 바뀐다면 아직 파일 관점에서는 최신 순서로 파일을 읽어야한다는 내용은 변함 없지만, 그래도 파일 내부에서는 O(logN) 탐색이 가능해지므로 O(NM)에서 O(MlogN)으로 시간이 줄어들었다. 이때 사용하는 자료구조는 Balanced Tree인 레드블랙트리나 AVL 트리를 사용한다.
이제 데이터 조회 방식이 살짝 바뀌게 된다.
[AS-IS]
1. 가장 최근에 생성된 파일부터 순서대로 읽는다.
2. 파일에 들어가면 가장 마지막으로 저장된 데이터부터 순서대로 읽는다.
[TO-BE]
1. 가장 최근에 생성된 파일부터 순서대로 읽는다.
2. 파일에 들어가면 이진 탐색을 통해 데이터가 존재하는지 확인한다.
정렬된 데이터를 가지고 있다면 한 단계 더 발전할 수 있는 방향이 생긴다. 바로 여러 개의 파일에 접근하는 것 또한 I/O 작업이기 때문에 하나의 큰 파일을 만든다면 조금이라도 더 성능을 향상 시킬 수 있는 것이다. 이 방식은 NoSQL 기술마다 전략이 다르기 때문에 아래에 더 기술할 예정이다.
만약 데이터를 정렬해서 저장하게 된다면 궁금증이 하나 생긴다.
💡 기존엔 AOF 방식으로 파일 맨 아래에 값을 추가했는데, 정렬해서 저장한다면 데이터를 추가할 때 약간의 시간이 걸리는거 아닌가요??
여기서 약간의 우회책을 만들어냈다. 거기다가 지금까지는 디스크에서 저장하는 과정을 이야기 헀는데, 디스크에서 정렬을 하게 된다면 메모리에서 처리하는 것보다 시간이 오래 걸릴 것이다. 그래서 속도도 빠르고, AOF 방식으로 데이터를 추가할 수 없는 방식을 메모리 - 디스크 구조로 확장해 문제를 해결했다.
[4] memtable, failover
새로 들어온 데이터는 우선 메모리에서 관리하는 전략이다. 그래서 데이터 추가 요청이 들어오면 먼저 메모리에 데이터를 정렬하면서 적재하다가, 어느정도 데이터가 추가되었으면 디스크에 저장을 하게 된다. 이때 디스크는 메모리에 정렬된 값을 그대로 쓰기만 하면 되는 것이니 디스크 입장에서는 AOF 방식이 그대로 유지되는 것이다. 이때 메모리에 일시적으로 저장되는 값들을 memtable이라고 부른다.
메모리를 사용하게 됨으로써 데이터 조회 방식에 과정이 하나 추가된다.
[AS-IS]
1. 디스크에 가장 최근에 생성된 파일부터 순서대로 읽는다.
2. 디스크에 저장된 파일에 들어가면 이진 탐색을 통해 데이터가 존재하는지 확인한다.
[TO-BE]
1. memtable에 조회 요청이 들어온 데이터가 있는지 확인한다.
2. 디스크에 가장 최근에 생성된 파일부터 순서대로 읽는다.
3. 디스크에 저장된 파일에 들어가면 이진 탐색을 통해 데이터가 존재하는지 확인한다.
하지만 메모리는 한가지 큰 단점이 존재한다. 바로 메모리는 휘발성이기 때문에 컴퓨터가 다운되면 메모리에 있던 데이터가 모두 사라진다는 단점이 존재한다. 그러면 이걸 어떻게 해결할까? 원래 처음에 쓰인 방법인 AOF 방식을 사용해서 디스크에 저장하게 된다. 디스크에 저장하는 로그는 memtable이 파일로 생성될 경우, 데이터를 지우고 다시 memtable에 데이터가 적재된 순서대로 값을 기록하게 된다.
위 사진을 보면 데이터가 순서가 서로 다른데, 메모리는 "key 기준 오름차순으로 정렬된 데이터"이고, 디스크는 "데이터 쓰기 요청이 들어온 순서"이다.
[5] LSM Tree
이제 SSTable과 memtable을 배웠으니 이제 LSM Tree에 대해 이야기를 할 수 있다. LSM Tree는 지금까지 우리가 다 배운 내용이다. 처음 데이터가 들어오면 메모리에 있는 memtable에 데이터를 적재하고, memtable에 데이터가 가득 차게 되면 디스크에 Sorted String Table로 정렬된 불변 데이터 구조로 저장한다. 말 그대로 수정이 불가능하고, 수정하려면 새로운 SSTable을 만들어야한다.
위에서 잠깐 정렬된 데이터이니 Merge Sort가 가능하다고 했는데, 이게 LSM Tree의 동작 방식중에 하나이다. SSTable은 트리의 레벨 개념처럼 특정 레벨에 속하게 되는데, 레벨에 속한 SSTable이 많아지게 되면 새로운 SSTable을 만들어서 병합 시킨다. 이때 각 파일끼리 중복된 데이터가 있을 수 있으므로 데이터를 제거하게 되는 과정을 거친다.
위 사진처럼 처음에는 memtable은 레벨 0이다가 디스크에 적재하면 SSTable은 레벨 1이고, 레벨 1 SSTable이 어느정도 모이게 되면 파일들을 병합해 레벨 2 SSTable을 만들게 된다. 결론적으로는 k-level이라면 제일 큰 SSTable이 될 수 있다.
3. 더 나아간 성능 최적화
이것도 그동안 배운 CS 개념의 변형인데, 내용이 위에보다 조금 어렵다.
[1] Bloom Filter (블룸 필터)
우리는 지금까지 아래 내용을 배웠다.
- Segment 방식을 통한 데이터 분산 저장
- Compaction을 사용한 파일 내부 데이터 중복 제거
- SSTable을 통해 O(logN)의 시간복잡도 개선
- 메모리 사용
- LSM Tree를 통해 파일 접근 I/O 성능 개선
근데 아직 완전 탐색으로 동작하는게 하나 남았다. 바로 "최신 순서로 파일을 읽어야 한다"는 것이다. 이거로 인해 O(MlogN)이 걸린다. 하지만 시간복잡도를 O(M) ~ O(MlogN)으로 바꾸는 기술이 존재한다. 바로 블룸 필터이다.
블룸 필터는 특정 원소가 어떤 집합에 속하는지 True, False로 확인할 수 있는 방법이다. 해시 함수를 사용하는 방법이다.
블룸 필터를 소개할 때, 보통은 해시 함수 3개를 사용하는 편이다. 위 사진에서도 3개의 해시함수를 사용한다. 단어는 potato 기준으로 설명하겠다.
- 첫번째 해시함수: f(potato) = 0 → arr[0] = 1
- 두번째 해시함수: g(potato) = 4 → arr[4] = 1
- 세번째 해시함수: h(potato) = 8 → arr[8] = 1
결과: arr = [1, 0, 0, 0, 1, 0, 0, 0, 1]
마찬가지로 ribeye도 저장되어 있다고 하면 어떤 SSTable엔 'ribeye'와 'potato'가 저장되어 있어서 배열 값은 위 사진처럼 될 것이다.
arr = [1, 1, 0, 1, 1, 0, 0, 0, 0, 1]
이때 SSTable에 'pork chop'이라는 단어가 있는지 확인한다고 해보자
- 첫번째 해시함수: f(pork chop) = 0
- 두번째 해시함수: g(pork chop) = 5
- 세번째 해시함수: h(pork chop) = 8
arr = [1, 0, 0, 0, 0, 1, 0, 0, 1]
그러면 arr[5]의 경우에는 SSTable[5] = 0이고, pork chop[5] = 1이므로 SSTable에 데이터가 없다는 것을 알 수 있다.
이런 방식으로 데이터의 존재 여부를 파악하는게 블룸 필터다.
동작 방식을 보고 '이거 없는 데이터도 있다고 할 수 있을 것 같은데?'라는 의문이 드신 분들도 있을텐데, 실제로 이런 문제가 발생한다. 이거는 False Positive라는 문제라고 한다. 우연한 해시 충돌로 인해 발생할 수도 있고, 위에 ribeye, potato를 저장하면서 여러 배열에 1을 설정해 얻어 걸릴 수도 있다.
사실 이거는 큰 문제가 아니기 때문에 블룸 필터를 사용하는 것이다. 왜냐하면 어차피 데이터가 존재한다고 하면 O(logN)으로 확인이 가능하니 만약 데이터가 없으면 다시 다음 파일에 데이터가 존재하는지 참/거짓 여부를 파악하면 되기 때문이다. 블룸 필터를 통해 확정 O(MlogN)에서 O(M) ~ O(MlogN)으로 바뀐 것만 해도 큰 도움이 된다는 것이다.
[2] Compaction Strategy
SSTable을 병합할 때, 실제 NoSQL 기술마다 전략이 다르다.
1. Apache Cassandra (Size Tiered Compaction Strategy)
STCS 방식을 사용하는데, 이건 크기가 비슷한 SSTable끼리 병합을 하는 방식이다. STCS가 기본값이다.
https://cassandra.apache.org/doc/stable/cassandra/operating/compaction/stcs.html
2. Apache HBase (Minor Compaction, Major Compaction)
memtable → memstore, SSTable → HFile로 용어가 살짝 다르다.
Minor Compaction은 여러 개의 HFile을 하나의 큰 HFile로 바꿔주는 역할을 한다.
Major Compaction은 Region이라는 여러 개의 HFile로 구성된 데이터 분할 단위인데, 하나의 Region에 있는 모든 HFile을 하나로 합치는 과정이다. 기본 옵션은 7일마다 실행하는 것으로 설정되어 있다.
https://data-flair.training/blogs/hbase-compaction/
3. Level DB, Rocks DB (Leveled Compaction Strategy)
우리가 위에서 LSM Tree에 나왔던 내용이랑 매우 비슷한 방법이다.
처음 메모리에서 디스크에 쓰이면 Level 0이 되고, Level 0의 SSTable이 모여서 합쳐지면 Level 1이 된다. Level 1 → Level 2 → ... 을 반복하는 것이다.
자세한 동작 방식은 rocksdb wiki에 잘 설명되어 있다.
https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
[3] 이후의 내용
지금까지 공부한 내용은 NoSQL의 가장 기본적인 동작 방식이다. 이후부터는 Compaction Strategy처럼 실제 기술마다 다를 확률이 높기 때문에 각 기술 문서를 살펴보는걸 추천한다.
5. 출처 및 참고하면 좋은 링크
TMI로 AOF가 사용되는 곳은 Redis가 장애가 일어나서 데이터가 날아갈 경우, 복구하는 방법중에 하나로 AOF를 사용한다.
위 포스팅은 데이터 중심 애플리케이션 설계 책을 기반으로 작성했다. 실제 책을 읽은건 아니지만 검색해보면 워낙 책 정리글이 많다. 책 후기들을 살펴보면 좋은 평가들이 가득하다. 현직자분들한테 유명한 책인듯
https://product.kyobobook.co.kr/detail/S000001766328
데이터 중심 애플리케이션 설계 | 마틴 클레프만 - 교보문고
데이터 중심 애플리케이션 설계 | 데이터는 오늘날 시스템을 설계할 때 마주치는 많은 도전 과제 중에서도 가장 중심에 있다. 확장성, 일관성, 신뢰성, 효율성, 유지보수성과 같은 해결하기 어려
product.kyobobook.co.kr
블룸 필터
- ByteByteGo - Bloom Filter 유튜브 영상
- 네이버 D2 기술블로그 - 확률적 자료구조를 이용한 추정 - 원소 포함 여부 판단과 Bloom Filter