쿠...sal: [컴] storage and retrieval

db index / index 가 저장되는 방법

storage and retrieval

ref.1 의 storage and retrieval 부분을 정리중…

compaction 과 merge:

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 이 날라갈 때를 대비해서, write 될때 그냥 sequential 한 log 를 남기는 것으로 이 문제를 어느정도 커버할 수 있다. 그리고 이 로그는 SSTable 를 만들때 discard 하면 된다.