Author: gywndi

Dongchan is DBA at KakaoBank, the Korean internet bank. He is very interested in data efficient processing and automation. His final goal is building unbreakable data system. He is interested in all elements (monitoring, automation) for a stable system configuration.

TokuDB? Fractal Index에 대해 알아보아요~!

Posted on | by gywndi | 1 Comment on TokuDB? Fractal Index에 대해 알아보아요~!

이 글은 제가 MySQL Power Group에 예전에 포스팅한 자료입니다.
참고 : http://cafe.naver.com/mysqlpg/189

과거와는 다르게 데이터 사이즈가 비약적으로 커지고 있습니다. 특히, 최근 들어 SNS 서비스가 성황을 이루면서, 개인화된 데이터는 날이 갈수록 기하 급수적으로 늘어나고 있습니다. 최근 Fratical Index 기반의 TokuDB가 오픈 소스로 풀리면서 재조명을 받고 있는데, 이에 대해서 간단하게 설명해보도록 하겠습니다.

B-Tree?

TokuDB에 논하기에 앞서, 전통적인 트리 구조인 B-Tree에 대해 알아보도록 하죠.

일반적으로 RDBMS에서 인덱스는 대부분 B-Tree기반으로 동작하는데, 크게는 “Internal Node”와 “Leaf Node”로 나뉩니다. Internal Node는 데이터를 어느 방향(작으면 왼쪽, 크거나 같으면 오른쪽)으로 보낼 지 결정하는 Pivot과 다음 Pivot의 위치를 알려주는 포인터로 구성됩니다. Internal Node의 가장 마지막 포인터는 Leaf Node를 향하는데, Leaf Node에는 보통은 데이터가 저장이 되죠.

B-Tree

Leaf Node는 트리 특성대로 왼쪽에서 오른쪽으로 순서대로 데이터가 저장되어 있습니다. 이러한 특성으로 트리로 구성된 구조에서는 데이터를 특정 범위를 가져올 수 있는 Range 처리가 가능하죠.

B-Tree는 데이터가 증가를 해도 Pivot을 거치는 횟수가 일정 수치 이상으로는 늘어지는 않습니다. 물론 Pivot 수와 Leaf Node 수는 데이터 증가 수와 비례하여 선형적으로 늘어날 수도 있겠지만, 원하는 Leaf Node에 접근하기 위해 거치는 Pivot 수는 크게 늘지는 않습니다. (비용으로 따진다면.. 1회 데이터 접근이 O(logN)라는 수치가.. 신경은 안쓰셔도 됩니다. ^^)

위 트리에서 Leaf Node에 접근하기 위해 거치는 Pivot 수는 3입니다. 만약 Leaf Node가 8개로 늘어나게 되면 거쳐야 하는 수는 4번이고, 16개이면 5번이 됩니다. 즉, Leaf Node 수(데이터 사이즈)가 현재 수보다 2배 사이즈가 되어야 1회 더 거치게 되는 것이죠.

Leaf Node는 키 순으로 저장이 되어 있다는 것과 Pivot을 통한 데이터 접근이 가능한 B-Tree의 특성으로 단 건 데이터 접근과 특정 범위 처리에 좋은 성능을 보여줍니다.

그러나, 데이터 사이즈가 커지게 되면 B-Tree에도 큰 문제점에 봉착하게 되는데, 메모리 자원은 한계가 있다는 점입니다. 데이터가 커지면 모든 데이터를 메모리에 위치할 수가 없겠죠. 메모리 자원은 한정적이기 때문에, Leaf Node의 대부분은 디스크에 존재할 가능성이 크다. Leaf Node가 디스크에 존재하는 비율이 높아질 수록 해당 데이터를 Read/Write 시 잦은 Disk I/O가 발생할 수 밖에 없습니다.

B-Tree 한계

컴퓨터 시스템 내부에서 가장 느린 성능을 보여주는 것은 바로 디스크로부터 Read/Write을 수행하는 것인데요.. 아무리 좋은 알고리즘을 가지고 데이터를 처리한다 하여도, 잦은 디스크 접근을 통해 동작하게 되면, 게다가 그 동작이 순서가 보장되지 않는 랜덤한 디스크 블록을 읽어야하는 이슈라면 결코 성능이 보장되지 않습니다.

B-Tree 특성 상 트리에 데이터 유입 시 바로 반영을 해주어야 하기 때문에, 메모리가 부족하게 되면 Disk Read/Write에서 즉시 성능 병목 현상이 발생할 수밖에 없는 것이죠.

B-Tree 특성

아무리 CPU 자원이 남아돌아도, Disk I/O Wait으로 인해 처리할 데이터를 메모리에 로딩하지를 못하면, 의미없는 상태입니다. 디스크로부터 데이터를 읽어와야 요청을 처리할 수 밖에 없기 때문이죠. 잦은 Disk I/O Wait.. 이것은 성능 저하를 유발하는 가장 큰 요소입니다.

tokutek에서는 이러한 잦은 디스크 I/O로 인한 문제를 해결하고자 새로운 해결법은 제시하였는데, 그것은 바로 “Fractal Tree”입니다.

Fractal Tree?

그렇다면 Fractal Tree란 무엇일까요?

Fractal Tree는 “Big I/O”에 촛점을 맞춘 자료 구조로, 잦은 Disk I/O를 줄이고, 한번에 다량의 데이터를 하단 노드로 전달함에 따라 데이터가 많은 상황에서도 효과적으로 처리할 수 있는 방안을 제시합니다.

Fractal Tree의 생김새는 B-Tree와 크게 다르지는 않습니다. Fractal Tree는 B-Tree와 같이 Internal Node와 Leaf Node로 구성되어 있고, Leaf Node에는 일반적으로 데이터가 저장되어 있습니다. Internal Node는 데이터를 어느 방향(작으면 왼쪽, 크거나 같으면 오른쪽)으로 보낼 지 결정하는 Pivot과 다음 Pivot의 위치를 알려주는 포인터로 B-Tree와 마찬가지로 구성되나 한가지 특이한 점이 더 추가됩니다. 바로 각 Pivot에는 “Buffer 공간”이 있다는 점이죠.. 바로 아래 그림처럼 말이죠. ^^

Fractal Index

데이터가 유입되면, B-Tree처럼 바로 데이터를 Child Node(Pointer가 가리키는 Node)로 전달하지 않고, Buffer 공간에 저장을 합니다. 그리고 Buffer에 데이터가 가득 차는 순간 Buffer에 쌓인 데이터를 Child Node로 전달하게 됩니다. 버퍼를 어떻게 Child Node에 넘기는 지에 대한 내용은 스킵.. (쵸큼 많이 복잡해서.. 그림 그리기가 힘들어요. ㅠㅠ)

하단 이미지의 왼쪽 트리를 보면, 각 노드마다 버퍼 공간(회색 사각형)이 있습니다. 이 버퍼는 메모리 상에 존재하는 별도의 공간이며, 데이터가 유입 시 바로 자식 노드로 데이터를 내려보지 않고, 일시적으로 버퍼 공간에 보관을 합니다. 만약 하단 트리에서 2, 22 데이터가 유입되면(오른쪽 이미지 참고), 22 노드의 자식 노드로 바로 데이터를 내리지 않고 일시적으로 보관하고 있음을 보여줍니다. (버퍼는 최대 2개의 데이터를 저장할 수 있다고 가정!!)

Fractal Index Insert

이 상태에서 추가로 99 데이터가 들어오게 되면, 하단 그림 1)번과 같이 오른쪽 버퍼 공간에 채워지게 됩니다. 이후 23 데이터가 들어오면, 오른쪽 버퍼에 더 이상 공간이 없게 되므로, 이 순간 데이터를 자식 노드로 내리게 되죠. 이 단계에서 Disk I/O가 발생할 수는 단계이다. 버퍼 공간이 확보되면, 23을 다시 빈 버퍼 공간에 넣게 되며, 최종적으로 23이 Fractal Tree에 저장되게 됩니다.

즉, B-Tree에서 데이터 유입시 매번 자식 노드로 데이터를 보내며 발생하던 잦은 Disk I/O 수가 Fractal Tree에서는 각 노드에 존재하는 버퍼 공간으로 인해 극적으로 감소합니다. 실제로 TokuDB를 사용하고 테스트 데이터를 생성하는 동안, TokuDB의 데이터 사이즈 변화가 크지 않음에 처음에는 의아하기도 하였어요. ^^

한번에 Disk I/O가 발생하기에 얻을 수 있는 점은 I/O 횟수 외에 추가로 더 있습니다. B-Tree에서는 잦은 Random Insert시 Leaf Node의 블록이 단편화되는 현상이 잦아들 수 있겠지만, Fractal Tree에서는 뭉쳐서 Disk I/O를 수행하므로 압축률이 좋을 뿐만 아니라 블록 단편화가 훨씬 줄어들게 되는 것이죠. 물론 InnoDB에서 Barracuda로 압축 포멧으로 테이블을 구성할 수는 있겠지만, 블록 단편화가 많아지는 경우 압축률이 저하될 수밖에 없기에, 얻는 것보다는 오히려 잃는 것이 더 많아질 수 있습니다.ㅜㅜ

Fractal Index 특징

TokuDB에서 Fractal Tree Index는 Message 기반으로 동작을 합니다. 데이터 변화가 발생하더라도, 즉시 Leaf Node로의 전달이 일어나는 것이 아닌, 발생했던 이벤트를 각 노드가 가지는 Buffer에 순차적으로 붙이고, 버퍼가 가득 차게 되면, 자식 노드로 버퍼에 저장된 메시지를 전달합니다.

Fractal Index in TokuDB

위 그림에서 가장 마지막에 수행된 연산은 99번 데이터를 지우라는 것이나, 실제로 Leaf Node에서 즉시 지워지지 않습니다. 이에 대한 이벤트는 메시지 형태로 버퍼에 저장이 되고, 관련 내용은 언젠가는 Leaf Node로 전달되어 적용될 것입니다.

자~! 야심한 이 밤!! 여기까지 정리하도록 하겠습니다. ^^
사실 B-Tree와는 컨셉이 조금 다른지라, 많이 헤매기도 했었지만.. 그림을 그리다보니 여기까지 오게되었네요. -_-;;

저와는 조금 다르게 생각하시는 분은 언제든지 제게 지적질을 해주세요!! 원래 지적 받으며 성장하기 마련..쿨럭~!

 

예전 포스팅을 새삼 여기에 붙인 이유는 무엇일까요? TokuDB에 대한 내용 2탄을 작성하기 위해서죠. ^^ 어쩌다 보니, TokuDB 를 조금 더 깊에 테스트하게 되었는데, 조만간 정리하여 블로그에 포스팅하도록 하겠습니다.

Linux Hot Copy(hcp) – Snapshot Tool

Posted on | by gywndi

Overview

몇 달전 Linux Hot Copy(HCP) 유틸리티가 무료로 풀리면서, 고가의 스냅샷 유틸리티를 구입 없이도 얼마든지 사용할 수 있게 되었습니다. 스냅샷을 멋지게 활용할 수 있다면, 단순히 데이터 백업 뿐만 아니라 DB 시스템과 같이 복잡하게 얽혀서 구동되는 데이터도 특정 시점으로 데이터를 복사할 수 있습니다.

이 경우 Linux Hot Copy(hcp)에 대해 알아보도록 하겠습니다.

Feature

  1. Point-in-Time 디스크 볼륨 스냅샷
  2. Copy on Write 방식의 Snapshot
  3. 서비스 영향없이 스냅샷을 생성

<Snapshot 비교>

  1. Copy-on-Write
    Write 시 원본 데이터 Block을 Snapshot 스토리지로 복제하는 방식으로 Snapshot 데이터 Read 시 변경되지 않은 데이터는 원본 블록에서,변경된 데이터는 Snapshot 블록에서 처리
    데이터 변경 분만 저장하므로 공간을 효율적으로 활용하나 블록 변경 시 원본 데이터와 스냅샷 데이터 양쪽 모두에서 Write이 발생
  2. Redirect-on-Write
    Copy-on-Write와 유사하나, 원본 볼륨에 대한 Write을 별도의 공간에 저장하는 방식으로 Copy-on Write(원본 Read, 원본 Write, 스냅샷 Write)에 비해 Write이 1회만 발생하나, 스냅샷 해제 시 변경된 블록들을 원본 데이터 블록으로 Merge시켜야함
  3. Split mirror
    원본 볼륨과 동일한 사이즈의 별도 복제 볼륨 생성하는 방식으로 데이터를 Full Copy하므로 즉시 생성이 어렵고 용량 또한 많이 필요

Installation

설치 버전을 다운로드 하기 위해서는 하단 페이지에서 등록해야하는데, 등록하게 되면 설치 바이너리를 다운로드 받을 수 있는 별도의 링크를 메일로 보내줍니다. 완벽한 오픈소스는 아닌지라.. 설치하기가 조금은 짜증이 나지만.. 일단은..뭐.. ㅎㅎ

http://www.idera.com/productssolutions/freetools/sblinuxhotcopy

hcp installation

설치 파일 압축을 풀면 아래와 같이 OS 별로 설치 바이너리가 있습니다.

$ unzip Idera-hotcopy.zip
$ cd Idera-hotcopy
$ ls
Idera-hotcopy.zip Installing+Hot+Copy.html idera-hotcopy-5.2.2.i386.rpm idera-hotcopy-5.2.2.x86_64.rpm idera-hotcopy-amd64-5.2.2.deb idera-hotcopy-i386-5.2.2.deb idera-hotcopy-i386-5.2.2.tar.gz idera-hotcopy-x86_64-5.2.2.tar.gz

서버에 사용하고자 하는 설치 바이너리를 설치합니다.

$ rpm -i idera-hotcopy-5.2.2.x86_64.rpm
$ hcp-setup --get-module

이제는 리눅스 커널에 맞는 모듈을 업그레이드해야 합니다. hcp-setup 명령어로 쉽게 가능하며, 업그레이드 시 https접근(443포트)이 필요합니다.

Usage

사용법은 다음과 같이 “hcp –help” 명령어를 통해 확인해볼 수 있습니다.

$ hcp --help
Usage: hcp -h | -m <MOUNT POINT> <DEVICE> | -l | -r <DEVICE>
Options:
  -h, --help             Show this help message.
  -l, --list             List active Hot Copy sessions.
  -r, --remove           Remove Hot Copy session.
  -m, --mount-point      Specify mount point.
  -o, --read-only        Mount hcp fs read only.
  -c, --changed-blocks   Specify changed blocks storage device.
  -q, --quota            Sets quota for changed blocks storage.
  -s, --show-hcp-device  Show the Hot Copy device path for a given 
                         device.
  -v, --version          Show the Hot Copy driver version.
Examples:
    Start session:
        hcp /dev/sdb1
        hcp -m /mnt/tmp /dev/sdb1
    Remove session:
        hcp /dev/hcp1
    List sessions:
        hcp -l

변경된 블록들이 저장한 디바이스가 별도로 존재한다면 -c 옵션으로 스토리지를 분리할 수 있습니다. 그렇지 않으면, 스냅샷을 생성한 디스크에 기본적으로 변경 블록이 기록됩니다.

Example

1) 스냅샷 생성 – 변경 블록이 저장될 스토리지(/dev/sdb1) 분리

$ hcp -c /dev/sdb1 /dev/sdc1
Idera Hot Copy     5.2.2 build 19218 (http://www.r1soft.com)
Documentation      http://wiki.r1soft.com
Forums             http://forum.r1soft.com
Thank you for using Hot Copy!
Idera makes the only Continuous Data Protection software for Linux.
Starting Hot Copy: /dev/sdc1.
Changed blocks stored: /backup/.r1soft_hcp_sdc1
Snapshot completed: 0.000 seconds
File system frozen: 0.019 seconds
Hot Copy created: Tue Jul 18:31:02 KST 2013
Creating hotcopy snaphost device: /dev/hcp1, Please wait...
Hot Copy created at: /dev/hcp1
making new path: /var/idera_hotcopy/sdc1_hcp1
Mounting /dev/hcp1 read-write
Hot Copy mounted at: /var/idera_hotcopy/sdc1_hcp1

2) 스냅샷 현황

$ hcp -l
Idera Hot Copy     5.2.2 build 19218 (http://www.r1soft.com)
Documentation      http://wiki.r1soft.com
Forums             http://forum.r1soft.com
Thank you for using Hot Copy!
Idera makes the only Continuous Data Protection software for Linux.
****** hcp1 ******
 Real Device:           /dev/sdc1
 Virtual Device:        /dev/hcp1
 Changed Blocks Stored: /backup/.r1soft_hcp_sdc1.cow_hcp1
 Mounted:               /var/idera_hotcopy/sdc1_hcp1
 Time Created:          Tue Jul 18:31:02 KST 2013
 Changed Blocks:        0.25 MiB (262144 bytes)

3) 스냅샷 삭제

스냅샷이 마운트된 포인트를 인수로 줘서 스냅샷을 삭제합니다.

$ hcp -r /dev/hcp1
Idera Hot Copy     5.2.2 build 19218 (http://www.r1soft.com)
Documentation      http://wiki.r1soft.com
Forums             http://forum.r1soft.com
Thank you for using Hot Copy!
Idera makes the only Continuous Data Protection software for Linux.
Hot Copy Session has successfully been stopped.
All active Hot Copy sessions have been stopped. It is now safe to restart the Idera Backup Agent.

Conclusion

Linux Hot Copy(hcp)는 설치 및 사용이 편리할 뿐만 아니라 무료로 사용할 수 있기에, 조금만 활용하면 멋진 백업 솔루션도 만들어낼 수 있습니다. 다음 번 포스팅에서는 이에 대한 내용을 정리해보도록 하겠습니다. ^^

HCP 스냅샷 유틸리티를 활용하여 DB의 시점 백업에 활용할 수 있는데, 다음번 이야기에서는 이 내용을 포스팅하도록 하겠습니다.

MySQL의 User Level Lock를 활용한다면?

Posted on | by gywndi

Overview

DB에는 크게는 두 가지 타입의 Lock이 있습니다. Table Level Lock, Row Level Lock.. 두 가지 타입의 Lock은 RDBMS에서 대표적인 Lock이라고 지칭할 수 있습니다.

Table Level Lock은 데이터 변경 시 테이블 자체를 Lock을 걸어 안전하게 데이터를 변경하는 방식이고, Row Level Lock은 변경되는 칼럼의 Row에만 Lock을 걸어서 데이터를 조작하는 방식입니다. 일반적인 상황에서는 두 가지의 Lock만으로도 충분히 다양한 사용자의 요구사항을 충족할 수가 있습니다.

그러나, 테이블 파티셔닝을 하는 경우나, 혹은 다양한 서버에 데이터가 분산 저장되는 경우 DB 내적인 제약사항 혹은 데이터 공간 자체의 한계로 인해 상황에 따라 더욱 확장된 Lock이 필요한 경우가 있습니다.

MySQL에서는 User Level Lock 기능을 제공하는데, 오늘은 이것에 관련된 내용을 정리해보도록 합니다.

Why User Level Lock?

User Level Lock에 대해 언급하기에 앞서서 조금 전 언급했던 파티셔닝 시 제약 사항에 대해서 간단하게 짚고 넘어가도록 하죠. ^^

MySQL에서 테이블을 파티셔닝 하게 되면, 단일 테이블로 보여지지만 내부적으로는 수 개의 테이블로 쪼개져서 별도의 테이블로 관리가 됩니다. 즉, 특정 테이블을 10개로 파티셔닝을 하였다면, DB내적으로는 10 개의 테이블을 Merge한 형태로 관리하는 모습을 보여줍니다.

MySQL table partition files
MySQL table partition files

그런데 물리적인 저장소를 분산 저장하기 위해서는 가장 중요한 제약 사항이 있는데, 파티셔닝 키 안에 Primary Key 안에 포함이 되어야 한다는 것입니다. Primary Key가 일반적으로 물리적인 저장소의 주소 역할을 일반적으로 수행하기 때문에 당연한 현상일 수 있겠죠.

여기서, 가장 큰 제약 사항 하나!! 바로 Primary Key 외에 추가로 Unique 속성과 같은 제약 사항을 추가할 수 없다는 것입니다. Foreign Key 도 당연히 추가할 수 없습니다. 어찌 보면, 거대 테이블을 처리하기 위한 일부 기능적인 부분 포기(?)라고 볼 수도 있겠네요. ^^;;

그런 상황 속에서 User Level Lock을 잘~ 활용한다면 단순히 파티셔닝 제약 조건을 뛰어넘어 다수의 서버 환경에서도 적용할 수 있습니다.

User Level Lock?

서론이 너무 길었네요. 이제 User Level Lock에 대해서 정리해보도록 하겠습니다.

User Level Lock이란 사용자가 특정 “문자열”에 Lock을 걸 수 있는 Lock을 의미합니다. 그리고 User Levl Lock 관련 메쏘드는 아래와 같습니다.

  • GET_LOCK(str,timeout)
    문자열 str에 해당하는 Lock을 획득하는 메쏘드. Lock 획득 성공 시 1리턴, timeout 동안 Lock획득 못한 경우 0 리턴, 에러 발생 시 NULL 리턴
  • IS_FREE_LOCK(str)
    문자열 str을 사용할 수 있는 상태인지 체크
  • IS_USED_LOCK(str)
    문자열 str이 사용되고 있는 지 체크
  • RELEASE_LOCK(str)
    str에 걸려있는 Lock을 해제

단, 주의할 점은 User Level Lock은 Client Base가 아닌 Server Base로 동작한다는 점입니다. 당연한 이야기이겠지만, 다수의 클라이언트에서 User Level Lock을 사용하게 되면, 클라이언트가 아닌 서버 측에서 경합이 발생한다는 점입니다. ^^

문자열에 Lock을 걸 수 있는 이 기능을 활용한다면, 앞서 말씀드린 파티셔닝 제약 혹은 물리적인 제약 사항을 극복(?)할 수 있는 솔루션이 될 수 있습니다.

Partitioning Limitation?

테이블 파티셔닝이 반드시 필요한 상황에서 일정 기준으로 유니크 보장도 하고 싶은 경우가 있습니다. 예를 들어 1개월 간 세션 키를 발급하는 경우, 그 기간 동안에는 절대 세션 키가 중복되어서는 안됩니다. 그렇다고 모든 유저에서 발급되는 세션키를 데이터 정리 없이 매번 서버에 적재할 수도 없는 노릇이죠.

이러한 요구 사항 속에서 User Level Lock을 활용하여 제약을 극복해 봅시다.

세션 키를 발급하는 순서는 다음과 같습니다.

user level lock

테이블 스키마는 아래와 같이 간단하게 정의한다고 가정했을 때,

create table t_sessions(
  user_id int not null,
  s_key varchar(32) not null,
  create_at datetime not null,
  primary key(user_id, create_at),
  key ix_skey(s_key)
) engine=innodb 
partition by range columns(create_at)(
  partition p_201310 values less than ('2013-11-01'),
  partition p_201311 values less than ('2013-12-01'),
  partition p_201312 values less than ('2014-01-01')
)

각 단계 별로 SQL을 간단하게 작성해본다면 다음과 같습니다. 위에서 주목할 사항은 s_key에는 유니크 속성이 없음에도 s_key를 중복 체크를 할 수 있다는 점입니다.

##  1단계
select get_lock('session key', 1);

## 2단계
select 1 from t_sessions
where s_key = 'session key';

## 3단계 (30일 동안 중복 세션 키가 없는 경우)
insert into t_sessions values ('myid','session key',now());

## 4단계
select release_lock('session key');

꽤 많은 코드(?)들을 생략하기는 했지만.. 흐름만 알려드리기 위한 예시라.. 넓은 마음으로 이해해 주세요. ^^;

위 예시를 활용한다면, 파티셔닝 테이블에 Foreign Key 효과도 넣을 수 구현할 수 있겠네요. (이것은 멋진 상상력을 발휘해서 구현해보세요. ㅎ)

Conclusion

User Level Lock은 앞에서의 간단한 파티셔닝 테이블 뿐만 아니라, 전~혀 연관이 없는 테이블 사이의 데이터를 처리하는 데에도 활용할 수 있습니다. 게다가, 동일 서버가 아닌, 다수 서버에서 분산된 데이터를 같이 처리해야하는 경우에도 유용하게 사용할 수 있습니다.

User Level Lock은 사용자가 메쏘드를 통해 특정 문자열에 대하여 Lock을 획득하는 것으로, MySQL 테이블 간 제약 사항을 간단하게 극복할 수 있는 초석이 될 수 있습니다. 적절한 시점에 활용하여, 데이터 신뢰성 향상은 물론 개발 시 스트레스도 줄여보도록 해요. ^^