2016. 09. 13. [Seminar] 차세대 비휘발성 메모리를 활용한 데이터베이스 성능향상 기법

일시: 2016. 09. 13. 12:50 ~ 13:45     장소: 서울대학교 302동 105호     강사: UNIST 컴퓨터공학과 교수 남범석

#define NVRAM non-volatile RAM // 차세대 비휘발성 메모리

▶ Overview

▷ merits

> 연산 속도 비교

> CPU ↔ DRAM by 80 GB/s, Memory Bus; DRAM은 휘발성 메모리이다.

> CPU ↔ SSD by 1GB/s, PCI

> CPU ↔ SSD by 600 MB/s, SATA

> CPU ↔ HDD by 50 ~ 100 MB/s, SATA

> NVRAM은 DRAM과 같은 속도를 유지하면서 SSD와 같은 지속성을 가짐

> How?

> DRAM: 8 byte or 64 byte로 처리 ↔ SSD 등 File system: 블록 단위(512 B, 1 kB, 4 kB, 8 kB)

> NVRAM은 8 byte로 처리할 것이라는 예측이 우세

> 따라서 NVRAM은 DRAM의 최적화 전략을 적용할 여지가 많음

▷ trade-off

> 가격이 높음

> 비동기화: 비휘발성 메모리를 사용하면 재부팅 시 초기상태로 돌아오지 않음

> 오류 해결 불가능

> Apps, Middleware, Os, Silicon 차원의 광범위한 노력이 필요

> 코딩상의 어려움

> ex. 메모리를 비운 뒤 그 메모리에 어떤 값을 저장하는 코드

> non-sorting 발생: CPU가 메모리에 어떤 값을 저장한 뒤 메모리를 비울 수 있음

> CPU processor는 메모리 excess를 최소화하려고 연산 순서를 sorting하지 않음

> 그럼에도 기존 방식은 volatile memory를 사용했으므로 상관 없었음

> mfence(); // 연산의 reordering을 방지

> ex. 프로그램이 데이터를 메모리에 안 쓰고 CPU cache에 저장하는 현상이 발생

> 기존의 DRAM도 어차피 휘발성이었으므로 문제되지 않았음

> clflush(); // instruction을 데이터를 메모리에 내려보냄, cache line flush

> ex. 데이터를 쓰는 도중에 다른 함수를 실행시켜서 혼선이 올 수 있음

> pcommit(); // 메모리 소자에 쓸 때까지 기다리는 함수, 오래 걸림

▶ Persistent in-memory B-tree for NVRAM

$ Warning. This part could contain wrong statements.

▷ B-tree(binary search tree)를 활용하여 NVRAM에 효율적으로 정보를 저장할 수 있는 방법 소개

> Note 1. 새로운 값을 넣는 과정과 기존의 값을 지우는 과정은 유사함을 명심

> Note 2. 값을 쓰는 과정은 오래 걸리는 과정이므로 그 수가 줄어들어야 메모리의 연산 속도가 빨라짐 

▷ 기존 자료구조

> count ∥ value1 ∥ value1 child pointer ∥ value2 ∥ value2 child pointer ∥  ···

> value가 크기 순서대로 정렬돼 있는 블럭에서 새로운 값을 추가할 때 끝에서부터 값들을 옮겨서 공간을 확보해야 한다.

> shift-and-Add 시 최대 연산 횟수: 페이지 크기 ÷ DRAM 크기

> ex. 페이지 크기가 4 kB이고, DRAM 크기가 64 B이면, 최대 clflush & pcommit 연산 횟수는 64번이다.

▷ 개선된 자료구조: Append-only Update Strategy

> bitmap ∥ offset array ∥ value1 ∥ value1 child pointer∥ value2 ∥ ···

> bitmap은 어떤 value가 쓰레기값(0)인지, 의미있는 값(1)인지 나타내는 부분

> offset은 각 value의 pointer로 이 부분이 크기순으로 배열되어 value가 크기순으로 배열되는 효과

> 새로운 값을 넣는 과정

> bitmap 비활성 → offset 비활성 → 새로운 값을 기입 → offset 크기순 배열 → offset 활성 → bitmap 활성

> bitmap은 0, 1뿐인 정보들이므로 연산 속도에 거의 기여하지 않음

> offset array는 이진 트리로 구성돼서 크기순 배열 시 끝에 값 추가, 포인터 연결로 2번의 clflush & pcommit 필요

> 새로운 값은 아무 데나 쓰고, 최종적으로 bitmap과 포인터 연결로 2번의 clflush & pcommit 필요

> 총 clflush & pcommit 연산 횟수는 4번이다. (밑줄)

> 탐색 연산 속도가 느려지게 함

▷ 새로운 자료 구조(교수님의 연구 분야): Failure-Atomic BST

> root ∥ value1 ∥ value1 child pointer ∥ L ∥ R ∥ value2 ∥ ···

> L과 R은 이진트리에서 각각 left sibling node와 right sibling node의 포인터를 가리킴

> 새로운 값은 아무 데나 적고 root에서 순차적으로 이동하면서 sibling node가 null이 되는 지점과 포인터로 연결

> 총 쓰기연산 횟수는 2번이다.

> page 내 용량이 초과해도 Failure-Atomic BST를 통해 쉽게 새로운 page에 atomic하게 연결 가능

▶ Persistent database of slotted-page for NVRAM

$ Warning. This part could contain wrong statements.

▷ 기존의 방식: Logging

> 백업 파일을 만든 뒤 거기다 입력한 정보를 저장시킴 // consistent even in power-off

> 백업 파일에다 commit mark를 찍어 백업 파일을 원본처럼 인식 // consistent even in power-off

> 백업 파일을 원본 파일에 덮어쓰기 시작 // consistent even in power-off

> 원본에 다 쓰면 백업 파일의 commit mark를 지움 // consistent even in power-off

> 한 정보를 두 번씩 쓰기 때문에 비효율적임

▷ 새로운 방식: Failure-Atomic BST

> 도식

^[각주:1]

> Memo

> Table을 디스크에 저장: heap, B-tree ↔ slotted-paging(키 사이즈가 가변적일 때)

> Slotted-paging는 Header, Free zone, Data, Pointer 등으로 구성되고 키 사이즈도 저장

> 새 header를 만들고 commit mark를 찍으면 Atomic하게 기존 header의 내용을 무시

> 교수님의 실험 결과: FASH(slot-header logging; duplicated write) vs FAST(RTM; single mark)

> insert 성능이 2 ~ 3배, # of CLFLUSH가 7 → 5로 개선 

> Record size에 대해 비의존적 ↔ Logging 기법은 선형적으로 증가하는 모양

2016.09.13 22:02

1. 출처: https://dzone.com/articles/caching-wcf-services [본문으로]