색인(index)의 두 가지 형태 : LSM 트리 & B 트리 -1

Database Internals 의 2장 B-트리 개요를 읽으면서 Index 라는 것 자체를 찾아보게 되었다. 0. Database? 데이터를 받아서 저장하고 데이터를 요청받으면 다시 저장했던 데이터를 반환해 준다. 1. Index - 쿼리 퍼포먼스를 올리기 위해 추가적으로 가지고 있는 데이터 스트럭쳐이다. - 위의 과정을 좀 더 효율적으로 하기위해 Index를 활용하게 된다. - Index의 추가와 삭제는 기존 데이터의 내용에 영향을 미치면 안된다. - 오로지 질의 성능에만 영향을 주게된다. - READ 성능을 높인다. - 따라서 적절하고 적당한 Index 가 필요하다. - 단점이 있을까? - 추가적으로 가지고 있는 스트럭쳐라서 추가적인 메모리와 디스크 용량을 사용하게된다. - DB를 write 할때 Index 도 같이 해주어야해서 write 퍼모먼스가 안좋아질 수 있다. * HashMap - Hashing?? : hash 함수를 이용해서 데이터를 HashTable 에 저장하고 검색하는 기법 - Hash 함수?? : 데이터가 저장되어 있는 곳을 알려주어 대량의 데이터 중에서도 원하는 데이터를 빠르게 찾게함. 키를 있는 그대로 저장하는 경우 다양한 키의 길이 만큼의 크기를 마련해두어야함 - in memory hash map을 index로 사용해서 각각의 key의 값이 disk 어디에 있는지 저장해둔다. - 실제로 Bitcask 라는 key/value store 에서 이런방식을 사용하고 있다. (https://github.com/basho/bitcask) 2. LSM(Log-Structed-Merge) Tree - Patrick O’Neil이 1996년 발표한 논문 The Log-Structured Merge-Tree (LSM-Tree)에서 처음 발표되었다. - task tracking, workflow automation 등의 최적화 활동관리 기능의 수요가 증가하던 시대였다. - 이름처럼 Log 파일 기반으로 작동하는 방식이다. (여기서 말하는 Log 파일이란 Append-Only 파일 : 한번 쓰여진 파일은 바뀌지 않는다. 새로운 데이터는 파일의 끝에 추가된다. ) - B-tree 구조로는 구조상 디스크의 random I/O 가 무수히 발생할 수 있어 쓰기요청이 많은 로그성 데이터에는 부적합했다. - Sorted String Table 을 사용해서 유저가 쓴 순서대로 key를 넣는게 아니라, key들이 sort 되어있다. - 그렇게 되면 Append-Only가 깨지지 않을까? - 새로운 key/value를 추가하려 할 때 SSTable 에 넣는게 아니라 메모리에 있는 binary tree 에 추가한다. - memory 에 keep하고 있는 테이블을 Memtable 이라고한다. 요 테이블에서 저장 된게 일정 사이즈를 넘어가면 SSTable 로 옮긴다. - 쓸때는 compaction이 이루어진다. - 그럼 SSTable 에 저장되기전에 충돌이 나면 다 날아가는건가? - 아니다. disk의 log file 에 기록을 남겨둔다. - 이후 SSTable 에 저장된 후에는 memory 와 log file은 삭제한다. - 데이터를 읽는 순서는 Memtable 에서 확인하고 없으면 SSTable을 확인하게 된다. [ 특징정리 ] - write 이 빠르다. - memtable 과 log file 만 업데이트 하면 끝이다. - 모든 키를 메모리에 넣을 필요가 없다. - Range 쿼리가 가능하다. - 많은 NoSQL 데이터 베이스들이 LSM Tree를 사용한다. [ LSM 트리가 성능을 최적화한 방법 ] * 블룸 필터 (Bloom Filter) - 블룸 필터는 원소가 특정 집합에 속하는지 여부를 확률적으로 알아낼 수 있는 자료구조로, 이를 활용하면 키가 데이터베이스가 존재하는지 유무를 알 수 있다. - 블룸 필터를 통해 데이터가 없다고 판단되었을 경우, 실제로도 찾으려는 데이터가 디스크에 존재하지 않음이 보장되기 때문에 추가적인 디스크 읽기를 아낄 수 있다. - 다만, 블룸 필터는 데이터가 있다고 판단했지만 실제 디스크에는 데이터가 없는 False Positive 가 발생할 수 있다. * 레벨 컴팩션 (Leveled Compaction) - SS 테이블을 여러 단계(level)로 구분한다. 단계가 높아질수록 테이블의 크기가 커진다. 상대적으로 좀 더 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 연이어 합치는 방식이다. 한 레벨의 SS 테이블 파일들끼리는 키가 겹치지 않는 특징 때문에 데이터를 찾기 위해서 level 수만큼만 쿼리하면 된다. * Skip List - 멤테이블에 데이터를 효율적으로 쓰고 읽기위해 멤테이블을 skip list 로 구현하는 경우도 있다. (Rocks DB, Level DB) 출처 : Database Internals, https://code-run.tistory.com/69