7. Hash Table

Review §

이전까지 정리를 했던 부분은 아래와 같습니다.

1. 우리가 DBMS를 통해서 어떤 목적을 이루려고 했는지?
2. DB에 저장되는 Tuple이 어떤식으로 Disk에 저장되는지?
3. 저장되는 방식에 따라서 어떤 장점과 단점을 가지는지?
4. Disk에서 Buffer Pool을 통해 어떻게 frame에 page를 Memory로 어떻게 Load하고 evict하는지? 위 질문에 앞서 배운 부분을 잘 정리해 보신다면 지금까지 배운부분을 review하실 수 있습니다.

Hash Table §

이번장에서는 Hash Table에 대해서 공부합니다. 사실 대한민국에서 공부하시는 분들이라면 hash table을 자료구조(Data Structure)에서 공부를 하셨을 겁니다. 이와 비슷하게 외국대학도 자료구조를 배우고 이 수업을 듣는 것 같지만 조금 더 DB관점에서 설명을 하는 것을 목표로 하는 것 같습니다.

Data Structure §

DBMS는 다양한 작업을 하는데 있어서 여러 자료구조를 사용합니다. 예를 들어보겠습니다.

1. Internal Meta-Data : 내부에 각 page가 어떤 disk에 있는지 혹은 tuple이 어떤 page에 있는지 좀더 빠른 속도로 알기 위해 Meta-Data라는 것을 만들어 놓을 때 자료구조를 사용합니다.
2. Core Data Storage : Tuple을 저장하는 저장장치를 구성할 때 3. Storage1 4. Storage2 또한 자료구조를 사용합니다. (Fixed Length Storage, Log Structure Storage)
3. Temporary Data Structure : 임시 자료구조라고도 하는데 join을 위한 hash table을 만들 때도 상요한하고 합니다.
4. Table Indices : 보조 index를 구성할 때도 여러 자료구조를 사용합니다.

이러한 다양한 작업에 자료구조를 사용하는 DBMS는 2가지 관점을 중요시하는 구현을 진행해야합니다.

1. Data Organization : DBMS의 기본적인 목적인 Disk <-> Memory의 데이터 교환의 효율성을 높이는 자료구조를 필요로합니다.
2. Concurrency : 여러 Thread가 동시에 접근하는 경우를 상정하고 Thread Safe한 자료구조를 필요로합니다.

Hash Table §

위의 요건을 구현하는 많은 자료구조가 있지만 Hash Table은 굉장히 효율적인 자료구조라고 할 수 있습니다.

• 자료를 저장하는 시점에 hash function은 O(1) 시간안에 key를 만들 수 있고 저장을 할 수 있습니다.
• 자료를 찾는 시점에도 평균적으로 O(1)의 시간이 걸립니다. (최악의 경우는 모든 Tuple을 뒤지면서 O(n)의 시간까지 늘어날 수 있습니다.)

이런 Hash Table은 DBMS에 있어서 page를 찾거나 혹은 특정 데이터를 저장하는데 굉장한 이점을 주는 자료구조입니다. (사실 필자도 실제 hash table이 어떤식으로 사용되는지 감이 아직 잘 오지 않습니다.)

좀 더 나아가 보면 hash table은 2개의 부분의 효율적인 구현을 목표로합니다.

1. Hash Function
   • 결국 데이터를 저장하기 위한 key값은 hash function에 의해서 결정됩니다. 이 hash function이 얼마나 다른 key값과 충돌을 방지하게 hashing하는지가 관건이 될 것입니다.
2. Hashing Scheme
   • Hashing Scheme라는 부분은 Key가 충돌이 난다면 어떤식으로 데이터를 저장할 것인지에 대한 정책입니다.

Hash Function §

Hash Function의 기본은 mod 연산입니다. 고정된 길이의 배열이 존재한다고 했을 때 특정 key(string)를 배열의 offset으로 변경시키는 부분을 통해 O(1)시간안에 데이터를 읽고 쓸수 있게 해줍니다.

다만 DBMS에서는 이런 연산이 Heavy한 것을 원하지 않습니다. 그 이유는 DBMS의 목적은 효율적으로 빠르게 읽고 쓸수 있는 자료구조를 구현하는 것이지 충돌이 없는 무거운 Hash function으로 무결한 Hash table을 구성하는 것이 아닙니다.

물론 이러한 과정에 Trade Off는 반드시 존재합니다. 하지만 중요한 목표는 데이터를 효율적으로 빠르게 찾을 수 있는 목적을 가지는 것이 DBMS에서 Hash Function의 기본 목적입니다.

현재 SOTA hash function은 facebook의 XXHash3라고 합니다.

Static Hash Scheme §

이 수업을 PDF를 읽지 않고 듣는다면 이 단어가 무슨 뜻인지 이해하기 쉽지 않습니다. Hash Scheme는 Collision을 handle하는 방법에 대한 것이라고 이해한다면 앞에 Static이 문제가 됩니다.

결과적으로 이는 고정된 Size의 배열을 가지는 Hash Table에서 충돌을 어떻게 Handle 할것인가? 에 대한 이야기 입니다.

Linear Probe Hashing §

Static Hash Scheme의 첫번쨰 방법은 Linear Probe Hashing입니다. 이 방식은 충돌이 날경우 다음 slot을 계속 탐색하면서 빈 공간을 찾은 뒤 해당 공간에 저장을 하는 방식입니다. 이러한 방식은 단순하다는 점과 빠르다는 점을 장점으로 가질 수 있습니다.

하지만 이 방식에 문제가 하나 존재하는데 바로 삭제를 진행하는 경우 입니다.

Linear Probe Hashing Deletion §

예를 들어 충돌이 난 후에 다음 주소 값을 따라가면서 빈 slot에 저장을 했다고 가정해보겠습니다. 이후 특정 값에 대한 삭제를 진행해서 주소값을 따라서 지웠다면 지운 이후의 데이터는 hash table에는 존재하지만 찾을 수없는 값이 됩니다.

이를 해결하는 몇가지 방법이 있습니다.

1. 데이터를 지우고 한칸씩 당겨주면 됩니다.
   • 단순한 아이디어고 구현도 간단합니다.
   • 다만 데이터가 1조개 되는 크기라면 문제가 쉽지 않습니다. 1번 지울 때마다 모든 데이터를 앞으로 당겨줘야 하는데 이는 O(n)의 시간복잡도를 가지며 굉장히 비용이 많이드는 연산입니다.
2. 위 방식에서 문제를 해결한 것이 Tombstones 방식입니다.
   • 데이터가 지워지면 지워졌다는 표식을 남겨줍니다. (null, string, bit… anything)
   • 이렇게 되면 값을 찾을 때 tombstone은 넘어가서 찾으면 되고 값을 쓸 때도 tombstone을 없애고 넣으면 되기 때문에 효율적으로 진행할 수 있습니다.

Cuckoo Hashing §

이런 Linear Probe Hashing과 다른 방법으로 Cuckoo Hashing이라는 기법이 있습니다. 이 방법의 중요 포인트는 Hash Function이 여러개 라는 것 입니다.

Key가 들어온 순간 여러개의 Hash Function으로 key를 Hashing합니다. 그후 fixed size array에서 각 key가 비어있는지 확인하고 slot에 적재합니다.

만약 모두다 차있다면 첫번째 혹은 N번째 Hash값을 통한 key를 evict합니다. 해당 자리에 새로운 key-value를 넣어주고 evicted된 key-value는 hash function의 순서에 따라 다른 자리를 찾아서 떠돌게 됩니다.

이러한 Cuckoo Hashing은 O(1)의 읽고 삭제하는 시간복잡도를 가지지만 데이터를 쓰는 과정에서 이보다 비용이 더 들 수 있습니다.

Dynamic Hashing Schemes §

앞 부분까지 고정된 Array에서 Collision을 Handle하는 방식에 대해서 배워봤습니다. 이번에는 고정되지 않은 Dynamic Hashing에서 Collision을 Handle하는 방식에 대해서 배워보겠습니다.

Chained Hashing §

기본적으로 Dynamic Hashing은 Linked List를 통해서 구현하고 충돌이 나면 줄줄이 Linked List를 통해서 데이터를 추가하는 Chained Hashing을 사용합니다.

이런 줄줄이 소시지를 Bucket이라고 부르고 해당 구조에 Linked List를 구현하여 데이터를 저장합니다.

강의에서는 Bloom Filter라는 개념을 소개합니다. Dynamic Hashing도 좋지만 문제는 Bucket을 꺼내서 읽기 전까지 데이터가 있는지 없는지 모른다는 것입니다. 이를 조금 더 빠른 시간안에 확인하기 위해 Bit array를 통해서 데이터를 저장합니다. 그 과정은 아래와 같습니다.

1. hash table과 size가 같은 고정 bit array를 준비합니다.
2. Key를 Hashing하는 순간 bucket의 번호의 bit array를 1로 변화 시켜줍니다.
3. Key를 통해 데이터를 찾는 경우 bit array를 먼저 look up하고 1이면 내부에 데이터가 있는게 미리 확인이 되었음으로 full scan을 진행하고 0이라면 데이터가 없다는 이야기 이므로 맨 마지막 bucket에 데이터를 추가합니다.

Extendible Hashing §

Extendible Hashing은 global bit와 local bit를 통해서 데이터의 bucket을 저장합니다.

Global 00 -> local 001101010
Global 01 -> local 011101001
Global 11 -> local 110010110

위 와 같이 Hashing된 Key에 앞 2자리에 따라서 Global Bucket에 저장을 해주는 방식입니다. 여기서 주요한 점은 만약 데이터가 늘어남에 따라서 resizing이 필요한 경우 가장 첫번째와 마지막을 제외한 가운제 부분만 resizing을 진행하면 되는 점입니다.

사실 해당 Hashing은 뭐가 좋은지 아직 모르겠습니다,.

Linear Hashing §

이부분도 마찬가지로 뭐가 좋은지 아직 모르겠습니다 해당 hashing은 resize를 할 bucket을 지정하는 pointer를 통해서 resizing을 진행합니다. 해당 pointer가 가리키는 bucket은 현재 다 차있지 않음에도 불구하고 resizing을 진행하게 됩니다.

1. 만약 overflow가 난 상황에서 split pointer가 가리키는 bucket은 새로운 bucket을 만들고 새로운 hash function( e.g mod 4 and mod 8)을 이용해서 rehashing을 진행합니다.
2. 이후 split pointer 다음으로 변경합니다.
3. Key를 통해서 분리하기 이전 데이터에 접근하려고 하는 경우 새로운 hash function을 통해서 데이터를 찾습니다.
4. split pointer가 끝에 다다르게 되면 새로운 hash function을 없애고 pointer를 처음으로 되돌립니다. 잘이해가 되지 않지만 이러한 과정은 사용하지 않는 bucket을 마지 garbage collecting하는 방식으로 관리하면서 메모리를 적절하게 사용하게 하는 방법인 것 같습니다.

E.O.D §

지금까지 Hashing에 대해서 배운 부분을 정리했습니다. 다음 부분에는 B+ Tree를 통해 어떻게 Index를 지원하는지가 예정되어있습니다.