# 3장 저장과 검색

데이터 중심 애플리케이션 구축(Designing Data-Intensive Application, 2017) 책을 읽고 정리하였습니다.

1. 데이터베이스에 힘을 더하는 자료구조

Bash 함수로 데이터베이스의 값을 넣고 찾아오는 걸을 구현해보자.

# bash 함수 구현 
db_set () {
 echo "$1,$2" >> database
}
db_get () {
 grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

# 첫번째 시도 
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

# 키 42의 값인 attractions를 변경후 재조회
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

# 데이터베이스에 모든 데이터 조회 
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

db_get 사용시 모든 데이터를 순착적으로 확인 후 원하는 데이터를 만나면 가져온다. 비효율. O(n)의 시간 복잡도가 나온다. 쉽게 말해, 레코드가 두배 많아지면 찾는 시간도 두배 많아진다. 따라서 위와 같은 자료구조를 데이터베이스에 적용할 수가 없다.

데이터베이스에는 인덱스라는 자료구조가 있다.

쓰기시 추가적인 구조(모든 인덱스 종류)는 오버헤드를 발생시킨다. 따라서 간단하게 파일에 덧붙이는 자료구조를 이길 수 없다. 하지만 잘 선택된 인덱스는 읽기 시 좋은 성능을 내기 위한 trade-off가 된다. 이러한 이유로 상황에 따라 적절히 사용할 수 있게, 인덱스 기능은 디폴트로 제공되지 않고 개발자나 DBA에게 선택권을 준다.

이제 다양한 indexing structures을 살펴보자.

1.1 Hash Indexes

1.2 SSTables and LSM-Trees

1.3 B-Trees

1.4 B-Trees와 LSM-Trees 비교

1.5 다른 인덱싱 구조

2. 트랜잭션 처리와 분석

Data Warehousing

Stars and Snowflakes: Schemas for Analytics

3. Column-Oriented Storage

정리

• 데이터베이스가 어떻게 데이터를 저장하고 되찾아오는지 알아보았다.

• 자세히 말하면, 저장이 되었을때 무슨일이 발생하고 같은 쿼리를 이후에 날릴때 어떻게 데이터베이스가 작동하는지에 대해 알아보았다.

• 저장엔진은 크게 2개의 큰 카테고리로 나뉜다.

  • OLTP에 최적화된 것 유저와 직접적인 작업으로 많은양의 리퀘스트가 발생한다. 이 부하를 다루기 위해서는, 대부분 각 쿼리에서 레코드(데이터)들의 작은 수량만에 접근한다. 때로는 Disk seek time에서 bottleneck 현상이 발생하기도 한다.

  • OLAP에 최적화된 것 많은 유저가 사용하는 것이 아니라 규모는 작지만 각 쿼리 마다 매우 Demanding하다.(수백만의 레코드들이 짧은 시간에 스캔이 되어야 하기 때문) 또한 OLTP와 다르게 Seek Time이 아니라 Disk Bandwidth에서 병목현상이 발생한다. 이를 해결하기 위해 Column-orientied Storage가 주목 받는다.

• OLTP의 두가지 주요 SCHOOL

  • log-structured school 파일에 appending 하는 것과 안쓰는 파일 삭제는 허용되고, 이미 작성된 곳에 덮어쓰기는 안된다. Bitcask, SSTables, LSM-trees, LevelDB, Cassandra, HBase, Lucene가 대표적이다.

  • update-in-place school 덮어쓰기가 가능한 정해진 크기 페이지들의 집합으로 디스크를 다룬다. 대부분의 관계형, 비관계형에 사용되는 B-trees가 대표적이다.

• log-structured school가 더 최근것이며, 무작위 접근 쓰기를 디스크의 순차적 쓰기로 체계적으로 전환한다. SSD와 하드드라이브들의 성능의 특징상 높은 쓰기 처리량을 보여준다.