[CMU 15-445 Intro to DB Sys] Lec07 Hash Tables

• DBMS에 사용되는 자료구조의 디자인에 있어서는 data organization(어떻게 효율적으로 access할 수 있을지), concurrency(여러 Thread가 문제 없이 access할 수 있도록)를 고려해야 함.

Hash Tables

• unordered associative array that maps keys to values로서, 해쉬함수를 통해 key로부터 value가 담긴 곳의 offset을 계산한다.
• space complexity는 $O(n)$, time complexity는 평균적으로 $O(1)$, 최악의 경우 $O(n)$다. 그럼에도 불구하고 DBMS에서는 $O(1)$과 같은 constant도 최적화하는 것이 중요하다.

  Hash Function

• 해쉬함수는 large key space에서 smaller domain으로 map한다. 보다 구체적으로는 key를 입력받아 integer representation of that key(hash값)를 반환하는데, 이는 deterministic하다.
  • DBMS에서는 cryptographic hash(e.g. SHA-2)를 사용하지 않는다.
• Trade-off: fast vs collision rate
  • 모두 같은 해쉬값을 반환하는 해쉬 함수는 극단적으로 빠르겠지만, 항상 collision이 발생한다.

    Hashing Scheme

• collision이 발생했을 때 어떻게 다루는지이다.
• Trade-off: 큰 해쉬 테이블 사용하기 vs get/put 과정에서 추가적인 instruction 사용

Static Hashing Schemes

• static하게 한 slot마다 하나의 element를 넣는 scheme을 생각해보자. 이는 다음 3가지 비현실적인 가정에 기초하고 있다.

  • element의 개수를 사전에 알고 있다.
  • keys are unique. 즉 두 개의 서로 다른 value가 같은 key를 갖지 않는다.
  • perfect hash function. 즉 서로 다른 key값에 대해서는 서로 다른 hash값을 주기 때문에 collision이 일어나지 않는다.

• 따라서 현실에서는 이러한 문제를 다루어야 한다.

  Linear Probe Hashing

• collision이 발생하면 linear하게 다음 빈 슬롯을 찾는다. 이는 address가 특정한 위치로 고정되지 않기 때문에 "open addressing"이라고도 불린다.

• slot 내에 key와 value값을 모두 저장해야지만 우리가 원하던 Key값을 발견하였는지를 알 수 있다.

• 문제는 entry를 삭제 했을 때, 그 entry로 인해 밀려나갔던 다른 entry를 찾는 것을 어렵게 만들 수 있다. 이를 해결하기 위해 "tombstone" 마커를 넣어주어, Lookup 과정에서는 지나가서 다음 값을 보고, 새로운 key를 삽입할 경우 해당 자리를 빈 자리처럼 사용하게 할 수 있다.

• 삭제 후에 끌어당겨서 빈칸을 채우는 방식은 key의 개수가 많을 경우 expensive할 수 있기 때문에 잘 사용하지 않는다.

• (Non-unique keys) 여러 다른 값들이 같은 key를 갖는 경우에 대해서는 다음의 두 가지 접근법이 있다.

  • separate linked list: 값을 바로 저장하는 대신에, 별도의 storage area에 대한 포인터를 저장한다. 하지만 이 storage area가 너무 커져서 Overflow하게 될 수도 있다.
  • redundant keys: 대개의 시스템이 사용하는 방식으로, 해쉬 테이블 상에 중복되는 키값들을 그냥 다 저장한다. 이렇게 해도 Linear probing scheme에는 문제가 없다.

• optimizations

  • key의 자료형에 따른 해쉬테이블 구현: 예를 들어서 string key라면 smaller string만을 해쉬테이블에 저장하거나 전체 string에 대한 포인터를 저장하는 식이다.
  • metadata in separate array: empty slot/tombstone 정보를 bitmap형식으로 page header나 별도의 hash table 등에 저장한다.
  • table 및 slot의 version metadata를 사용: 해쉬 테이블에 메모리를 할당하는 것이 expensive하기 때문에 동일한 메모리를 재사용한다. 이를 위해 slot들을 삭제하는 대신에 table의 version을 하나 올리고, version이 서로 다를 경우 slot이 empty인 것으로 취급한다.

Cuckoo Hashing

• 여러 개의 hash function을 사용하여 여러 개의 location을 찾아 본다.
  • 만약 여러 location 중 빈 자리가 있으면 그곳에 insert하고, 그렇지 않으면 이미 들어가 있는 것 중 하나를 밀어낸다. 밀어내진 것은 rehash하여 새로운 자리를 찾는다.
  • 이 경우에 infinite loop에 빠질 가능성이 있기 때문에 이를 체크해야 함.
• 이러한 scheme에서는 여러 개의 hash 값 중 하나에는 반드시 key값이 존재하거나 아니면 아예 테이블 상에 없게 된다.

Dynamic Hashing

• 위의 static hashing scheme에서는 사전에 element의 개수를 알고 있어야 하고, 만약 많아질 경우에는 rebuild해야 한다. 아래에서는 rebuild할 필요 없이 dynamic하게 resize할 수 있도록 한다.

Chained Hashing

• 각 slot 내에서 linked list of buckets를 유지한다. 여기서는 같은 hash값을 가진 element를 같은 bucket에다가 집어넣어버린다.
• lookup하는 과정에서 linked list traversal이 너무 오래 걸릴 수 있기 때문에, 효율성을 위해 Bloom filter를 bucket pointer list에 넣어서 특정 Key가 있는지 없는지를 미리 체크한다.
  • Bloom Filter에서는 false negative는 일어나지 않는다(다른 key들로 인한 false positive는 가능)

Extendible Hashing

• chain을 계속 늘려나가는 대신에 bucket을 나누어준다. 이렇게 나누면서 리밸런싱할 때 해쉬테이블에서 사용하는 global bit의 개수를 늘려주고, split되는 bucket의 entry만을 적절히 나누어주면 된다(다른 bucket들은 그대로 두어도 된다. 다만 이 bucket chain을 가리키는 slot location은 2배로 증가한다).
  • global과 Local depth bit counts가 있다. global은 전체적으로 몇 개의 bit를 사용해서 나누는지이고, local은 해당 bucket에 포함되는지 식별하기 위해 필요한 bit의 개수다.
  • 만약에 local depth가 global depth보다 작으면 그냥 새로운 bucket을 하나 추가해주면 충분하고, 그렇지 않으면 global을 늘려서 slot array 자체를 크게 만들어야 한다.

Linear Hashing

• overflow가 발생하면 그 bucket을 바로 split하는 것이 아니라, split pointer가 가리키는 bucket을 split해준다.
• split할 때는 새로운 slot entry 및 새로운 hash function(원래 $n$으로 나누어주었다면 새로운 해쉬함수에서는 $2n$으로 나눈다)을 추가하여 해당 bucket의 키를 rehash해준다.
• split pointer가 제일 끝에 도달하면, 원래의 hash function을 없애고 포인터를 다시 제일 위로 올려준다.(즉 새롭게 추가되었던 hash function이 기본 hash function으로 변한다)
• 만약 split pointer 아래의 바로 나오는 bucket이 비어있을 경우에는 이를 삭제하고 split pointer를 위로 올려주는 것도 가능하다.