[ DB ] Chapter 14. Indexing

1. Storage Access

 

cache 메모리는 byte 단위로 접근 가능하지만 SSD와 HDD는 block 단위로 접근한다. 이러한 block은 보통 4KB이며 main memory와 Disk 사이를 통신할때의 단위이다. DBS는 통신하는 block의 개수를 최소화하고자한다. main memory에 최대한 많은 block을 유지시키면 Data Access의 수를 줄일 수 있다.

이를 위해 Buffer를 사용한다. 이는 disk block의 복사본을 저장하는데 사용되는 main memory의 일부분 공간이다. 이 buffer에 공간을 할당하고 관리하는 주체를 buffer manager라고 부른다.

1.1 Buffer manager

프로그램은 disk에 있는 block이 필요할때 buffer를 호출한다. 이때 block이 이미 버퍼에 있다면 buffer magager는 main memory에 저장되어있는 block의 주소를 반환한다. 반면 block이 버퍼에 저장되어있지 않다면 버퍼매니저는 그 block에 대한 공간을 버퍼에 할당한다. 이때 버퍼가 가득 차있다면 다른 블록을 replace한다. 이때 대체되는 block이 수정되었다면 disk에 다시 저장해줘야한다. 그 후 새로운 block을 버퍼에 저장하고 이의 주소를 반환하게 된다.

 

transaction은 모두 수행되거나, 되지 말하야하기 때문에 순차적으로 buffer에 업데이트하다가 commit 연산을 하게되면 update된 내용을 disk에 저장한다. 여기서 flush는 버퍼에 있는 것들을 disk에 저장하는 연산을 의미한다. 이에 대한 내용은 뒤에서 더 자세하게 다룬다.

 

Pinned block

이는 pin을 이용하여 block을 사용중임을 표시하는 방법이다. block을 사용하기 전에는 pin연산을 사용이 끝났을때는 Unpin 연산을 수행해야한다. pin 상태일때는 replace될 수 없다. DB를 여러명에서 사용중이라면 count와 같은 변수를 통해 관리할 수 있다.

Shared and exclusive locks on buffer

버퍼에서도 lock이 사용된다. 이는 app, user, thread 등이 동시에 접근하여 충돌하는 것을 방지하기 위함이다. shared lock은 read하기 위한 lock이다. 읽기만 하는 스레드들은 여러개가 동시에 접근해도 상관 없다. exclusive lock 은 write하기 위한 lock이다. 수정하고 있을 때에는 다른 스레드가 read/write하지 못하게 막아야한다.

 

Locking rules

• 하나의 스레드만이 exclusive lock을 걸 수 있다.
• shared lock과 exclusive lock은 동시에 걸 수 없다.
• shared lock은 동시에 걸 수 있다.

1.2 Buffer-Relpacement Policies

이는 버퍼가 가득차 특정 버퍼를 relpace할때의 정책을 다룬다.

Least recently used (LRU)

가장 최근에 사용된 데이터가 또 사용될 확률이 높다는 논리에서 나온 정책이다. pin 해제 시간을 보고 사용된지 오래된 block을 대체한다. 이는 여러 시스템에서 많이 쓰이지만 DB에서는 적합하지 않을수도 있다. DB의 작업패턴 때문이다. 예를 들어 두 테이블에 대해서 natural join을 수행했다고 가정하면 그 두 테이블을 join한 테이블을 자주 사용이되어도, 그 외의 두 테이블은 자주 사용되지 않을 것이다. 또 table을 sequential하게 읽으며 무언가를 찾고있다면 찾기 위해 읽어진 값들은 나중에 사용될 확률이 적다. 하지만 이는 단일쿼리에서는 좋은 성능을 보인다.

Toss-immediate

이는 특정 block에 대한 연산이 모두 마치면 바로 버퍼에서 삭제되는 전략이다. 이는 LRU에서 발견된 문제점을 보완한다.

Most recently used (MRU)

이는 toss-immediate와 비슷하지만, 연산이 다 마쳐도 바로 버려지지 않고 버려질 후보가 된다. 이 또한 LRU와 대조되게 최근에 사용된 데이터들을 우선적으로 버려지게 된다. 이는 DB에서 생각보다 좋은 성능을 보인다.

 

buffer manager는 여러 전략의 과거 결과들을 보고 가장 효율적으로 버퍼를 관리할 수 있는 전략을 선택한다. 이는 쿼리에 특성에 따라 많이 달라진다. 그리고 filesystem은 buffer에 있는 정보를 순서대로 저장하지 않고 reordering할 수도 있다. 이때 우리가 의도한대로 동작되지 않을 수도 있다. 이는 transaction으로 방지할 수 있다.

 

---

 

2. Indexing

 

Indexing은 data를 모두 scan하지 않아도 index를 이용하여 특정 데이터에 쉽게 접근할 수 있도록해주는 기법이다. 이는 대용량 데이터의 특정 데이터에 접근할때의 속도를 크게 증가시킨다. 데이터가 실제로 sequential하게 저장되어있던 random하게 저장되어있던 빠르게 찾을 수 있다.

Search key

이는 그냥 key라고도 부르며 index를 이용할 때 기준이 되는 값이다.

 

Index file

이는 index entry라고 부르는 record 들로 이루어져있는 파일이다. 이는 key값과 그의 value들이 저장되어있는 pointer값을 저장하고 있기 때문에 원래의 table보다는 크기가 훨씬 작다.

 

2.1 Index Evaluation Metrics

index의 성능을 계산할때 고려해야하는 요소들이다

• Access type
  • Point query
  • Range query
• Access time : index로 데이터를 찾을 때 걸린 시간
• Insertion time
• Deletion time
• Space overhead : 저장공간에 대한 오버헤드

indexing의 방법으로는 order이 되어있는 Ordered Indices와 order이 되어있지 않은 hashing indices가 있다. 전자는 연속적인 index가 필요할때 유리하고 후자는 특정 데이터를 필요로할대 유리하다.

 

---

 

3. Ordered Indices

 

이는 search key를 기준으로 정렬하는 indexing 방법이다. 이런방식으로 저장된 file을 Indexed-sequentail file (ISAM)이라고 부른다.

파일은 여러가지 index를 가질 수 있다.

• Clustered index (primary index) : 실제 순서를 결정하는 index이다.
• nonclustered index (Secondary index) : 실제 정렬순서와 다른순서를 지정하는 인덱스. 빈번하게 사용되는 attribute로 지정. (ex.컴공학생들을 찾을때 ID로 찾는것보다 학과정보를 보고 찾는게 더 쉽다)

index record는 seach key와 pointer로 구성되어있다. 이에 따라 ordered indices는 두가지 타입이 존재한다.

 

3.1 Dense Index Files

 

모든 index entry들이 모든 tuple과 mapping되어있는 구조이다. primary index의 경우 이런 구조를 갖는다. 왼쪽은 ID의 dense index 이고 왼쪽은 dept_name의 dense index이다.

 

3.2 Sparse Index Files

이는 특정 search key만 포함하고있다. 레코드들이 순차적으로 정렬되어있다면 특정 key에 접근하고 순차적으로 원하는 키에 접근하는 방식으로 동작한다. 크기는 작아 효율적이지만 원하는 값을 찾기 위해서는 한번 더 읽어줘야한다.

 

3.3 Sencondary Indices

secondary indice는 특정 indirection한 중간 계층을 가리키고, 다시 그 중간 계층이 실제 데이터를 가르키기 때문에 memory access가 두번 일어난다. 이는 secondary index의 값으로 정렬되어있지 않기 때문에 dense해야한다.

 

 

3.4 Multilevel Index

만약 인덱스가 메모리보다 크다면 disk에 접근해야하기 때문에 성능이 떨어지게된다. 이에 dense한 inner index를 두고 이를 기준으로 sparse한 outer index를 만들어 outer index를 메모리에 저장할 수 있게하는 방법이 제시되었다.

 

---

 

4. B+Tree Index Files

 

B+tree는 데이터를 관리하는 balansed tree이다. root tree와 internal node에는 실제 데이터가 아닌 자식 page의 주소를 저장하고있고 leaf노드에는 실제 recode를 가르키는 주소를 가지고 있다. leaf 노드들끼리는 순차적으로 포인터로 연결되어있다.

 

internal node에서는 key의 오른쪽에는 자신보다 같거나 큰 key들에게 접근할 수 있는 주소가 저장되어있고, 왼쪽은 자신보다 작은 값에 접근할수 있는 주소가 저장되어있다. leaf node에서는 왼쪽에는 자신의 data 주소가 저장되어있고 page의 맨 마지막에는 순차적으로 옆 page를 가르키는 주소가 저장되어있다.

Observation

• node들은 물리적으로 연속적으로 존재하지는 않지만 논리적으로 연속적으로 저장되어있다.
• B+tree의 leaf 노드는 dense insices이고 internal nodes는 sparse indices이다.
• 보통 root 노드의 크기는 충분히 크기 때문데 tree의 level이 크게 높지 않다 → cost가 크지 않다.

Query on B+-tree

function find(v)
		set C = root node
		while (C is not a leaf node) 
				Let i = least number such that v ≤ C.K(i)
				if there is no such number i then 
						Seaf node가 나올 때까지 비교해나가며 내려가다가 값을 찾는 것이 반복해서 일어난다는 것et P(m) = last non-null pointer in the node
						set C = C.P(m)
				else if (v = C.K(i)) then set C = C.P(i+1)
				else set C=C.P(i)   /* v < C.K(i) */ 
		end
		/*C is a leaf node*/
		if for some i, K(i)=v then return C.P(i)
		else return null ; /* No record with key value v exists*/

 

leaf node가 나올 때까지 비교해나가며 원하는 값을 찾는다. leaf 노드들끼리 연결되어있기 때문에 range를 찾을 때 range의 처음을 찾고 range의 끝지점이 나올 때까지 탐색하는 방식으로 쉽게 구할 수 있다.

 

4.1 Insert

travers하며 삽입할 leaf 노드를 찾고 삽입한다. 자리가 없다면 split를 수행해주고 중간 값을 위로 올려준다. (과제 내용이기 떄문에 생략)

4.2 Deletion

traverse하여 지울 leaf노드를 찾아 제거해준다. leaf노드들이 빈공간을 많이 가지고 있다면 merge 해준다. merge로 인해 페이지의 첫 값이 바꼈다면 부모노드 값도 수정해준다. 이렇게 순차적으로 모든 internal node의 값을 수정해준다. 만약 값이 삭제 된 후 merge하려고 했는데 주변에 빈공간을 가진 node가 없다면 그 노드에 있는 값을 내 페이지에 삽입할 수 있다. 이를 redistribution이라고 한다. 이는 parent node를 변하게 된다. 정리하자면 delete가 수행되고 내 page가 절반도 못채웠다면 주변 page를 살펴본다. 이때 두변 Page 중 자리가 있다면 merge가 수행이되고, 자리가 없다면 redistribution이 수행이 된다.

4.3 Complexity of Updates

모든 update가 수행되기 위해서는 find가 수행되어야한다. 이때문데 update의 cost는 트리의 높이의 의존적이다. 실제로는 internal node가 버퍼에 있는 경우도 있고 b+tree는 충분한 데이터를 담을 수 있기 때문에 split, merge하는 경우가 흔치 않다. 노드점유율은 insert의ㅣ 순서에 영향을 받는다. random으로 들어올경우에는 2/3정도로하고, 순차적으로 들어올때는 1/2로 한다.

 

4.4 File Organization

 

우리는 b+tree를 인덱스로 사용할뿐만 아니라 파일레코드에 대한 자료로도 활용한다. 이때 leaf node는 pointer 대신 record를 저장한다. insertion/deletion/update가 있는 경우에도 data record를 클러스터링된 상태로 유지할 수 있도록 지원한다. record가 pointer보다 더 많은 space를 사용하기 때문에 space의 활용을 높이기 위해 split과 merge를 할 때 더 많은 sibling을 redistribution에 참여시킨다.

 

4.5 Secondary Indices and Record Relocation

recode가 split나 merge 등으로 인해 재배치가 되면 해당 record 포인터를 저장하는 모든 secondary 인덱스들을 업데이트해야한다. 하지만 이는 IO작업이 많아 비용이 매우 높다. 이에 secondary index에서 record pointer 대신 B+tree file의 search key를 저장하는 방법이 있다. 이때 seach key가 unique하지 않다면 record id를 따로 추가하는 방법도 있다. 하지만 이 방법을 이용하면 특정 record를 찾기 위한 traverse가 추가로 시행되어야한다.

4.6 Indexing String

B+tree에서 index를 string으로 두면 생기는 문제가 있다. 문자열의 길이는 유연하기 때문에 node 점유율을 search key의 개수가 아닌 사용중인 공간의 크기로 판단해야한다는 것이다. 또, 길이가 길어질수록 split이 자주 일어날 것이기 떄문에 비용도 증가한다.

이에 대한 해결방안으로는 Prefix compression이 있다. internal node에 key 전부를 저장하지 않고, 최소한의 길이로 저장하는 것이다. 이는 노드의 fanout을 증가시킬 수 있다. 예를 들어 ‘이해나’와 ‘이찬양’이 있다면 각각 ‘이해’와 ‘이찬’까지마나 저장할 수 있다.

4.7 Bulk Loading and Bottom-Up Build

대용량 relation을 B+tree로 구현했다고 해보자. relation은 메모리보다 훨씬 크고 메모리보다 큰 senconsary index를 생성한다고 해보자. 이때 insert를 하는 과정에서 각 리프노드에 접글할 때 노드들 간의 순서가 존재하지 않기 떄문에 해당 노드가 버퍼에 존재하지 않을 확률이 크다. 그렇다면 매번 disk를 탐색하게 된다. 이는 매우 많은 시간이 소요된다. 대량의 엔드리들을 한번에 insert하는 것을 bulk loading이라고 한다. 이를 효율적으로 하는 방법은 다음과같다.

1. 우선 insert할 엔트리들을 정렬하고 insert한다. b+tree는 정렬되어있기 때문에, 정렬된 엔트리를 insert해주면 disk 접근이 줄어들 것이다.
2. Bottom-up B+tree construction : 트리가 처음부터 비어있는 경우 entry를 정렬하고 이를 leaf node부터 시작하여 하양식으로 b+tree를 구축한다.

2번방법은 대부분의 DBS 에서 구현된다.

 

4.8 B-Tree

위 그림은 B-tree 이고 밑의 그림은 B+tree이다. 이는 같은 데이터를 가지고 있다. B-tree는 internal node에도 값을 가지고 있다. 또 각 노드들에 같은 key 값이 전혀 없다. b+tree에서는 leaf 노드에 모든 값이 다 있었기 때문에 range 쿼리에 유리했었지만, b-tree는 range 쿼리를 수행하려면 부모노드에 접근해야해서 복잡해진다.

 

---

 

 

5. Hash Indices

 

Hashing은 메인 메모리에서 인덱스를 구축하기 위해 널리 사용되는 기술이다. hash table에는 여러개의 bucket과 hash function을 가지고 있다. bucket이란 entry를 포함하는 저장공간이다. 이는 보통 disk의 block size에 맞춰져있다. hash function은 특정 bucket의 위치를 찾는 데에 사용된다. 서로 다른 search key는 동일한 bucketdp mapping될 수 있다. b+tree와 같이 hash index에서 bucket은 record의 pointer가 담긴 entry를 저장하고 file system 에서는 record를 저장한다.

 

5.1 Static hashing

static hashing에서 bucket의 수는 고정되어있다. bucket은 순차적으로 할당되며 한번 할당되면 절대 해지되지 않는다. 여러개의 record가 한 bucket에 저장되어있기 때문에 bucket에 접근한 뒤로는 linear하게 탐색해야한다. 위 예시는 hash function으로 mod를 사용하였다. 이는 key 을 bucket의 개수로 나눠 나온 나머지에 할당해준다. mod 연산은 key를 랜덤하게 넣었을 때 한 bucket에 몰리는 현상을 불러올 수 있다. uniform하게 분배해주는 hash function이 좋은 함수라고 할 수 있다.

overflow

bucket이 부족하거나 한 bucket에만 레코드가 몰릴때 오버플로우가 일어날 수 있다. 한 bucket에만 레코드가 몰리는 이유는 여러 레코드가 같은 key를 갖거나 hash function이 적절하지 않기 때문이다. 우리는 오버플로어의 가능성은 줄일 수 있지만 완전히 제거할 수는 없다. 오버플로어는 보통 overflow bucket을 통해 처리된다.

overflow chaining

overflow bucket은 오버플로우가 일어난 bucket과 Linked list로 연결된다. 따라서 오버플로어가 일어났을 때 선형적으로 overflow buffer를 확인하며 빈공간을 탐색하고 값이 삽입된다. 이렇게 빈공간을 찾는 것을 Linear probing라고 한다. open hashing은 overflow bucket을 추가하기 전에 다른 bucket의 빈 공간을 살펴보고 없을때 overflow bucket을 추가한다. 이는 hashing의 장점을 흐린다. Closed hashing에서는 bucket이 꽉차면 바로 overflow bucket을 추가한다. 이는 공간을 많이 차지하지만 그래도 closed한 방법이기 때문의 hash의 장점을 살릴 수 있다. 이에 대한 성능저하를 막기 위해 overflow bucket의 개수를 제한하기도 한다.

Deficiencies

DB는 시간에따라 커지기도하고 작아지기도 한다. 하지만 bucket의 수가 너무 많으면 bucket의 남는 공간이 낭비되고 디스크 공간이 낭비된다. 하지만 bucket의 수가 너무 적으면 overflow가 일어나 성능이 저하된다. 이에 대한 해결방법으로 주기적으로 새 hash function으로 바꾸는 rehashing이 있다. 하지만 이는 비용이 너무 많이 들어 정상적인 동작을 못할 수도 있다. 이에 Dynamic Hash를 사용하는 것이 더 좋은 해결방법이다.

 

5.2 Dynamic Hashing

동적 hashing 기법은 정적 hashing 기법의 단점을 커버한다. 이에는 linear hashing 과 Extendible hashing이 있다.

Extendible Hashing

이는 DB의 크기가 변화함에 따라 bucket을 분할하고 병합하며 공간 효율성을 유지시켜주는 방법이다. 이는 한번에 하나의 bucket에 대해서만 조정 작업을 수행하기 때문에 성능 오버헤드가 작다. 이는 bucket에 대한 pointer directory를 사용한다. directory를 2배로 하여 buckekt의 수도 2배로 늘리게 된다. 이는 overflow된 bucket만 split한다.

이때 key는 hash key의 postfix나 prefix를 사용한다. fostfix의 길이를 i bit(0 <= i <= 32)라고 하면 디렉토리의 사이즈는 2^i가 된다. 처음 i는 0으로 시작하고, DB의 크기에 따라 증가하거나 축소된다.

이때 여러개의 entry가 하나의 bucket을 가르킬 수도 있다. 따라서 실제 bucket의 개수는 2^i개 미만이 되어야한다. bucket의 수는 split과 merge로 인해 동적으로 변하게 된다.

bucket address table = directory

directory의 크기가 4이기 때문의 이를 표현하기 위해서는 2개의 비트가 필요하다. 즉 이는 2개의 비트로 hash 연산을 하고있는 상태이다. 이에 대한 정보는 Global depth를 보면 된다. 위에 그림에서 G는 2이므로 최하위 비트 2개를 보고 hash 연산을 진행하면 된다. 각 bucket에는 local depth 정보가 나와있다. 이는 현재 bucket의 있는 key 값들을 식별하기 위해 읽어야하는 비트의 개수이다. 이는 split할때마다 1씩 증가한다. G = L이라면 그 bucket은 하나의 entry가 가르키고 있다는 것을 알 수 있다.

새로운 값이 들어가야하는데, bucket이 가득 찼다면 split 해줘야한다. 대상 bucket이 G>L이라면, 즉 한 bucket을 가르키는 엔트리가 2개 이상이라면 이는 split할 수 있다.

 

bucket을 추가로 하나 더 생성해주고 L를 하나 씩 증가시켜준다. 그리고 디렉토리가 새로운 bucket을 가르키도록 업데이트 해준다.

 

bucket이 가득 차 split을 해주려고 하는데 이미 G = L이라면 이 때는 directory의 개수를 늘려줘야한다. G를 1 증가시키고 디렉토리의 크기를 2배로 늘려주어 key의 길이를 늘려 식별할 수 있는 엔트리의 수를 늘려준다.

 

보통은 기존에 있던 값들 앞에 0을 추가해주고 1을 추가해준 key들을 확장한 공간에 추가해준다. 이제 G가 3이 되었으니까 G > L이 충족되었고 아까 하지 못했던 split를 진행해준다.

 

• 장점
  • 파일이 늘어남에 따라 hash의 성능이 저하되지 않고 공간에 대한 오버헤드가 줄어든다.
• 단점
  • 추가된 디렉토리에서 cache miss가 발생할수도 있다.
  • 디렉토리의 크기 자체가 매우 커질수도 있다. 이에 디렉토리를 B+tree로 관리 하기도 한다.
  • 디렉토리의 사이즈를 증가하고 감소하는 것은 높은 비용을 갖는다.

 

Linear Hashing

이는 디렉토리를 사용하지 않고 overflow chain의 문제를 처리하는 dynamic hashing 기법이다. 이는 임시 overflow bucket이 사용되고 round-robin 방식으로 분할할 bucket을 선택한다. 이는 hash function의 모음을 가지고 있다. h_i(key) = h(key)  mod (2^iN)가 되며 i 가 증가할때마다 고려할 비트가 한비트씩 늘어난다. 즉 범위가 2배씩 늘어난다.

한 시행을 round라고 하며 최근 round 수를 level이라고 한다. 한 round는 모든 초기 버킷이 분할될때를 기점으로 한다. 한 round가 지날때마다 level은 하나 증가하고 Next 포인터는 0으로 초기화 된다.

Insert를 하기 위해 원하는 bucket으르 찾는다. 자리가 있다면 삽입하고 자리가 없다면 임시 overflow bucket을 만들어 삽입해주고 해당 bucket에 연결해준다. 그 후 Next가 가르키고 있던 bucket을 split하고 Next 포인터를 증가시킨다. split되어 새로생긴 bucket은 맨 아래에 추가된다. i가 하나 증가된 모양의 h를 이용하여 hash function을 다시 꾸려 배포한다.

 

현재 43, 즉 101011를 삽입하고자 한다. 하지만 h0가 11인 곳을 보니 가득 차있다. 이에 임시 overflow bucket을 만들어 삽입해주고 Next가 가르키는 bucket을 split 해주었다. split해준 bucket은 000과 100으로 나뉘어 h1의 100에 추가 될 것이다. split가 되었기 때문에 Next는 하나 증가시킨다.

 

 

이렇게 insert를 진행하다가 next가 overflow bucket을 가진 bucket을 가르키게 되면 임시 overflow bucket은 사라지고 새로운 bucket을 만들어준다.

우리는 level이 0인 상황에서 5 (00101)를 찾는다고 가정해보자. level이 0이기 때문에 h0을 먼저 보게 될 것이다. 끝의 2비트를 보고 01에 접근해보았지만 next는 이미 이를 지난 상태이다. 즉, 이 bucket은 이미 split된 상태이다. 그렇기 때문에 우리는 h1의 값인 101 bucket을 찾아가 값을 찾아야한다.

 

---

 

6. Comparison of Ordered Indexing and Hashing

 

Cost of periodic re-organization

이는 주기적인 re-organization에 대한 비용을 의미한다. B-tree 같은 경우 쭉 re-organization이 필요한 거에 비교하면 비용이 굉장히 적은 편이다.

Relative frequency of insertions and deletions

현재하는 작업이 I/O가 잦은지 보고, 잦다면 I/O 연산이 저렴한 indexing 기법을 택해야한다.

average access time vs worst-case access time

평균 access time을 중심으로 볼건지 tail latency를 볼건지 결정해야함

hashing은 보통 point query에 더 적합하고 ordered index는 range query에 더 적합하다. 특정 소프트웨어에서 어떤 조건에 의해 범위에 대한 연산을 주로 쓴다면 B+-tree를 써야 한다. 복잡한 query 연산을 요구하지 않을 때 hash indexing을 사용하기 좋다.

 

---

 

 

7. Write-Optimized Index Structures

 

7.1 LSM Trees

 

쓰기 연산이 많은 workload의 경우 b+tree의 성능이 저하될 수 있다. write의 비용을 줄이기 위해서는 Log-structured merge tree를 사용할 수 있다. LSM tree는 write연산이 많은 workload를 위해 설계되었다. write의 성능을 올려주는 대신 search의 성능은 떨어지게 된다. 이는 다양한 key-value store에 쓰이고 있다.

 

 

이는 전체적으로 Memtable에 쓰여진 데이터를 모아놨다가 어느정도 모이면 수정할 수 없는 Immutable Memtable로 옮겨지게된다. Backgraound에서는 이 를 Disk에 저장할 수 있는 SSTable 형태로 바꾸어 disk에 저장하게 된다.

 

Memtable은 기존적으로 메모리에 저장되어있다. disk에 접근하는 것은 너무 느리기 때문에 상대적으로 빠른 메모리에 저장해놓고 한번에 Disk에 기록하는 전략을 사용한다. MemTable은 SkipList라는 자료구조로 이루어져 있다. 이는 메모리에 데이터가 들어오면 정렬된 상태로 저장한다.

 

메모리상 Memtable이 가득 차면 더 이상 사용하지 못하고 Immutable이 되고 새로운 MemTable을 생성한다. 이 Immutable은 수정되지 않는 상태로 대기하다가 background에 의해 disk에 기록된다.

 

SkipList 내에서 데이터를 정렬된 상태로 뽑아내서 SSTable이라는 자료구조에 데이터를 정렬하여 삽입한다. 이를 background가 비동기적으로 하게 되고, 이렇게 데이터를 제정비하면서 저장하는 연산을 compaction연산이라고 부른다. 병목현상의 원인으로 지목되는 연산 중 하나이다.

 

 

SSTable에 저장된 데이터를 보면 SSTable끼리 구간이 겹치는 것을 볼 수 있다. 그렇기 때문에 특정 level의 SSTable의 수가 어느정도 찼다고 하면 background compaction 연산을 통해 겹치는 범위를 조정해주고 다음 level의 SSTable로 merge sort해준다. 이 과정은 중복도 제거해주고 데이터를 가장 최신데이터로 유지하기 위해 중요한 과정이다.

 

 

이는 LSM tree의 전반적인 그림이다. key들은 모두 정렬되어있기 때문에 random I/O를 줄여주었다. 또, 데이터를 하나하나 disk에 접근하면 매우 속도가 느릴텐데, 한번에 접근하면 이에대한 오버헤드가 많이 극복된다 .

하지만 이를 현실에서 실제 사용해보면 메모리가 disk에 비해 너무 빠르고 disk 내의 Merge sort가 너무 느려 Memtable이 SSTable에 저장될 차례에도 저장되지 못하는 상황이 올 수도 있다. 이를 Write Stall Problem이라고 한다.

 

 

7.2 SkipList

 

이는 확률기반의 자료구조이다. 기본적으로는 linked list의 형태를 띈다. key가 새로 들어오면 random하게 level이 주어진다.

 

 

파란색은 27을 lookup하는 과정이고 빨간색은 31를 찾는 과정이다. 일단 27은 최상위 level에서 linked list 처럼 쭉 읽다가 찾게되었다. 하지만 31은 최상위 level에 존재하지 않는다. 이에 쪽 읽다가 NULL이거나 자신보다 큰 값을 발견하면 다시 돌아가 아래 level로 내려가 다시 탐색한다. 이를 반복하면 된다.

 

 

위 그림은 level이 3인 20을 insert하는 과정이다. lookup과 유사하다.

 

위 그림은 delete하는 과정이다 lookup한 후에 free해주면 된다.

 

---

 

8. Bitmap Index

 

bitmap index는 multi key을 효율적으로 처기할 수 있다. 레코드는 0부터 순차적으로 번호가 매겨지는 것을 가정한다. 숫자 n이 주어지면 레코드 n 을 편하게 검색할 수 있다. bitmap은 단순히 비트들의 배열이다. 이는 각 attribute의 값에 대한 비트맵을 갖는다. 이의 길이는 레코드의 개수가 되고 개수는 해당 attribute 속성의 종류의 개수가 된다 .

 

gender는 m과 f로 두 종류가 있기 때문에 2개의 bitmap을 갖는다. m을 보면 1번째와 4번째 비트가 1로 표시되어있는데, 이는 record number가 1인 레코드와 4인 레코드가 gender 속성이 m 이라는 의미이다.

비트맵 인덱스는 여러 속성에 대한 query에 유리하다. 단일속성 쿼리에는 딱히 좋지 않다. 쿼리는 and나 or과같은 비트연상을 통해 반환되기 때문에 저렴하다. 또, 조건에 대당하는 튜플의 개수를 세는것이 매우 쉽다. 이는 크기도 매우 작기 때문에 공간 오버헤드가 작다.

꽤 유용해서 은근 자주 사용되지만 다양한 조건을 다루기에는 적절하지 않다.