CMU Databse Fall 2022 를 듣고 정리한 글입니다.
Data Structure
DBMS는 시스템의 내부의 다양한 파트에서 다양한 자료구조를 사용한다.
- Internal Meta-data: DB와 systems state에 대한 정보를 저장한다. (page table, page directory ...)
- Core Data Storage: Tuple을 저장하기 위해 사용한다.
- Temporary Data Structures: query 등의 실행 속도를 높이기 위해 임시로 만드는 자료구조이다.
- Table Indices: 특정 tuple을 빠르게 찾기 위해 별도로 존재하는 자료구조이다.
DBMS는 이러한 자료구조들을 결정하고 구현할 때 크게 이 두 가지를 고려해야 한다.
- Data organization: 어떤 메모리에 어떤 자료구조를 넣어서 효율적으로 access 할 수 있게 할 것인가?
- Concurrency: 어떻게 동시에 여러 thread가 문제 없이 데이터에 access 할 수 있게 할 것인가?
Hash Table
Hash Table은 key를 value로 mapping 시키는 associative array로 평균 O(1) operation complexity (최악 O(N))와 O(N) space complexity를 보장한다. Hash Table은 Hash Function과 Hashing Sceheme로 구성된다.
- Hash Function: key space를 더 작은 domain으로 mapping하는 함수로 execution time과 collision rate 간의 trade-off가 있다.
- Hashing Sceheme: key collision이 발생했을 때 어떻게 처리할 것인지를 결정한다. 마찬가지로 collision이 발생 했을 때의 overhead와 collision을 덜 발생시키기 위한 overhead 사이의 tradeoff가 있다.
Static Hashing Scheme
Static Hashing Scheme에서는 hash table size가 고정되어 있고, hash table이 가득 차면 기존의 table보다 더 큰 (일반적으로 2배) size의 table을 새로 생성한다. 이 작업은 매우 비싸다.
Liner Probe Hashing
가장 일반적으로 사용하는 hashing scheme으로 일반적으로 가장 빠르기도 하다. slot을 circular buffer로 간주하고, hash function이 key를 mapping 해 주면 빈 slot을 찾을 때 까지 linear search를 수행한다.
lookup 시에는, hash 함수를 계산한 후, 해당 slot을 확인한다. slot이 비어 있으면, 해당 key에 해당하는 element가 없는 것이다. 한편, element가 있는 경우, (collision이 일어났었을 수 있기 때문에) linear search를 수행한다. (이 때문에 value에는 key를 같이 저장해야만 한다.) slot을 한 바퀴 돈 경우, 마찬가지로 element가 없는 것이다.
deletion의 경우, 이러한 lookup 과정 때문에 실제로 element를 지우는 것이 아니라, tombstone entry를 넣어 linear scan을 계속 할 수 있도록 해야 한다. (그렇지 않으면 entry들을 shifting 해 주어야 하는데, 너무 비싼 작업이다.)
Robin Hood Hashing
Robin Hood Hashing은 Linear Probe Hashing 의 일종인데, hash function에 의해 mapping 된 position으로부터 실제로 값이 저장된 position까지의 거리를 기록해 두었다가, 새 entry를 insert 할 때 linear scan 과정에서 자신보다 더 좋은 거리를 가지고 있는 entry 자리에 본인을 삽입하고, 해당 entry를 table의 더 먼 위치에 삽입한다.
Cuckoo Hashing
Hash table을 여러 개 두고 서로 다른 hash function을 둔다. 일반적으로는 같은 알고리즘에 seed를 다르게 둔다.
insert 시에는 free slot이 있는 table 하나를 고른다. 모든 table이 가득 찼다면 랜덤하게 한 개의 table을 골라 eviction algorithm을 돌린다. 드물게, 무한루프를 도는 경우 모든 table을 재구축한다. 이 hashing 방법은 O(1) lookup 과 deletion을 보장한다. insert의 경우 O(N) 이지만 실제 O(N)이 되는 경우는 드물다.
Dynamic Hashing Schemes
Dynamic Hashing Scheme의 경우 hash table을 rebuild 할 필요 없이 on demand로 resize 할 수 있다.
Chained Hashing
가장 일반적인 scheme으로, DBMS는 각 hash table의 slot에 대해 linked list를 유지한다. collision이 일어나는 경우 단순히 해당 linked list에 이어붙인다.
Extendible Hashing
Chained Hashing을 개선한 것으로, slot은 bucket chain을 가리키고, chain이 영원히 커지는 것을 방지하도록 bucket 크기가 특정 시점을 넘어가면 chain을 쪼갠다. 이렇게 하면 전체 hash table을 rebuild하는 대신, split chain에 해당하는 데이터들에 대해서만 오버헤드가 발생한다.
hash(C)의 prefix는 10 이므로 10 이 가리키는 bucket 에 element가 들어가야 하지만, 이미 bucket이 가득 차 split 이 발생한다.
이 과정에서는 먼저 slot에서 bucket 을 찾아가기 위해 필요한 prefix bit을 1 만큼 늘린 다음, slot과 bucket의 mapping을 재조정하게 된다. 이 slot들은 일반적으로 directory라고 부르고, directory는 메모리 상에 위치해 disk에 존재하는 bucket들보다 더 저렴하게 조작할 수 있다.
Linear Hashing
Linear hashing에서는 split 할 bucket을 가리키는 포인터를 하나 갖는다. 특정 bucket이 overflow 되면, 포인터가 가리키는 bucket을 쪼갠다.
key에 bucket을 매핑하기 위해서는 여러 개의 hash function을 사용한다.
overflow가 발생하면 어떤 bukcet인지와 무관하게 포인터가 가리키는 bucket을 쪼갠다. 새 hash 가 필요하면 hash function을 만들고 bucket의 element들을 rehashing 한다. split pointer가 마지막 slot에 도달하는 경우 원래의 hash function을 새로 추가한 hash function으로 대체한 다음 처음으로 되돌아간다.
