db index / index 가 저장되는 방법
storage and retrieval
ref.1 의 storage and retrieval 부분을 정리중…
index 저장에 대한 구현방법
- log 를 append 를 하는 것이 빠르게 write 할 수 있는 방법. 기존의 것에 overwrite 하는 것보다 유리하다.
- 이것은 특정 size 의 segment 까지만 저장하고, 한도를 넘어가면 새로운 파일로 저장. 이런식으로 여러 segmemt를 저장한다.
compaction 과 merge:
- log를 write 하면서 동시에 가장 최근 값만 남기고 버리는 작업을 진행. 이것을 compaction 이라고 하자.
- 이 compaction 을 하면서 동시에 다른 segment 것과 합치는 작업(merge) 를 진행할 수도 있다.
- compaction 과 merge 를 완료하면, 최종적으로 모든 segement 에서 1개의 key 만 남게 된다.
hash table 한계:
- 각 segment 에 대한 hash table 은 메모리에 둔다. hash table 은. file
버전은 효율적이지 않아서 없다.
- file 버전의 hash table 은 많은 랜덤 액세스 I/O가 필요하고, 가득 차면 커지는 데 비용이 많이 들며, 해시 충돌에는 까다로운 로직이 필요하다.
- hash table은 range query에는 적합하지 않다. kitty00000과 kitty99999 사이의 모든 키를 스캔하려 할 때, 할 수 없으며 해시 맵에서 각 키를 개별적으로 조회해야만 한다.
SSTable:
- sorted string table 의 약자다.
- 각 segment는 key 순으로 정렬되게 insert한다.(이러면 당연히 sequential insert 가 안된다.) 그리고 각 segment 에서 compaction 을 시킨다.(그러면, 키가 unique하게 된다.) 이제 이 segement들을 merge 하면서 sort 한다.(merge sort)
- 이렇게 되면, 모든 key 에 대한 hashmap 을 갖지않고, 듬성듬성 key 를 갖는 sparse hash map 으로도 괜찮다. 근처에 있는 key 의 위치로 가서, 그 안에서 다시 찾아들어가면 된다.
- 이것은 hash map 으로 찾아들어간 key들이 들어있는 chunk 의 경우는 압축해서 보관해도 된다. 압축을 하게 되면, I/O 대역폭 사용을 줄이고, disk 공간도 줄 일 수 있다.
- insert 할 때부터, key를 정렬하면서 insert 를 하는 방법은 AVL tree 나 red-black tree 등이 있다.
- B-tree 등을 이용하면, disk 에서도 이 정렬된 구조를 유지하는 것이 가능하지만, 메모리에서 이 정렬된 구조(structure)를 유지하는 것이 쉽다.
이제 storage engine 이 동작은 이렇게 하게 된다.
- balanced tree 가 메모리에 있다.
- write 이 들어오면, balanced tree 에 추가하게 된다.
- 이 in-memory tree 를 memtable 이라 하자.
- 이 memtable 이 대략적으로 수MB 정도로 커지면, 지금까지의 tree 를 file로 저장한다.
- 이 때 이 file 은 SSTable(Sorted String Table, key 로 정렬된 data 를 가진 chunk 로 보면 된다. 즉, tree 의 leaft node를 순서대로 저장한 모양이 될 것) 로 저장한다.
- 이것이 효과적인 이유는 tree 가 이미 key로 정렬된 key-value pair들을 유지하고 있기 때문이다.
- 새롭게 만들어진 SSTable file 이 가장 최근 db segment 가 된다.
- 이 SSTable file 로 이전의 key 가 저장되는 동안에도 write 가 들어오면, 새로운 memtable 이 생성된다.
결과적으로, 하나의 SSTable 에는 특정시간동안 쌓인 key 들이 있게 된다.
read 를 처리할때는
먼저 memtable 에서 key를 찾는다.
여기에 없으면, 가장최근의 disk segment 로 간다. 거기도 없으면, 그 다음 오래된 segment 로 가서 key 를 찾게 된다.
때떄로 merge 및 compaction process 를 backgroud 에서 실행한다. 이 때 SSTable 이 줄어든다.
이것을 실행해서, segment 파일들을 merge하고, overwritten 된 값이나 delted 된 값들을 버린다.
이때 만약 memtable 이 날라갈 때를 대비해서, write 될때 그냥 sequential 한 log 를 남기는 것으로 이 문제를 어느정도 커버할 수 있다. 그리고 이 로그는 SSTable 를 만들때 discard 하면 된다.
Reference
- Designing Data Intensive Applications
댓글 없음:
댓글 쓰기