Category Archives: Research

gywndi’s 연구

InnoDB의 Adaptive Hash Index로 쿼리 성능에 날개를 달아보자!!

Overview

MySQL과 같은 RDBMS에서 대표적으로 가장 많이 사용되는 자료 구조는 B-Tree입니다. 데이터 사이즈가 아무리 커져도 특정 데이터 접근에 소요되는 비용이 크게 증가되지 않기 때문에 어느정도 예상할 수 있는 퍼포먼스를 제공할 수 있기 때문이죠. 그치만 상황에 따라서, B-Tree 사용에 따른 잠금 현상으로 최대의 퍼포먼스를 발휘하지 못하는 경우도 있습니다.

이에 대한 해결책으로 InnoDB에는 Adaptive Hash Index 기능이 있는데, 어떤 상황에서 효과가 있고 사용 시 반드시 주의를 해야할 부분에 대해서 정리해보겠습니다.

InnoDB B-Tree Index?

소개하기에 앞서서 먼저 InnoDB에서 B-Tree가 어떠한 방식으로 활용되는 지 알아볼까요?

InnoDB에서는 데이터들은 Primary Key순으로 정렬이 되어서 관리가 되는데.. 이것을 곧 PK로 클러스터링 되어 있다라고 합니다. 데이터 노드 자체가  PK 순으로 정렬이 되어있다는 말인데, 이는 곧 특정 데이터에 접근하기 위해서는 PK가 반드시 필요하다는 말이지요.

그리고 Secondrary Key는 [인덱스키+PK]를 조합으로 정렬이 되어 있습니다. 즉, 특정 데이터를 찾기 위해서는 Secondrary Key에서 PK를 찾아내고, 그 PK를 통해 데이터 트리로 접근하여 원하는 데이터로 최종 접근을 하는 것이죠.

InnoDB B-Tree Index

트리가 가지는 가장 큰 장점은, 데이터 접근 퍼포먼스가 데이터 증가량에 따라서도 결코 선형적으로 증가하지 않다는 점에 있습니다.  다들 아시겠지만, B-Tree에서 특정 데이터 접근에 소요되는 비용은 O(logN)인데, 이는 일정 데이터 건 수에서는 거의 선형으로 비용이 유지됩니다. (참고로, PK접근 시에는O(logN), Secondrary Key ㅈ버근 시에는 2 *O(logN) 이겠죠?)

그런데, B-Tree를 통하여 굉장히 빈도있게 데이터로 접근한다면, 어떻게 될까요? DB 자체적으로는 꽤 좋은 쿼리 처리량을 보일지는 몰라도, 특정 데이터 노드에 접근하기 위해서 매번 트리의 경로를 쫓아가야하기 때문에, “공유 자원에 대한 잠금”이 발생할 수 밖에 없습니다. 즉, Mutex Lock이 과도하게 잡힐 수 있는데, 이 경우 비록 데이터 셋이 메모리보다 적음에도 불구하고 DB 효율이 굉장히 떨어지게 됩니다.

InnoDB Adaptive Hash Index?

앞선 상황에서 좋은 성능을 보이기 위해서, InnoDB에서는 내부적으로 Adaptive Hash Index 기능을 제공합니다. “Adpative”라는 말에서 느껴지듯이, 이 특별한 자료구조는 명쾌하게 동작하지는 않고, “자주” 사용되는 데이터 값을 InnoDB 내부적으로 판단하여 상황에 맞게 해시를 생성” 합니다.

InnoDB-Adaptive-Hash-Index

위 그림에서 자주 사용되는 데이터들이 1,5,13,40이라고 가정할 때 위와 같이 내부적으로 판단하여 트리를 통하지 않고 “직접 원하는 데이터로 접근할 수 있는 해시 인덱스”를 통해 직접 데이터에 접근합니다.

참고로, Adative Hash Index에 할당되는 메모리는 전체 Innodb_Buffer_Pool_Size의 1/64만큼으로 초기화됩니다. 단, 최소 메모리 할당은 저렇게 할당되나, 최대 사용되는 메모리 양은 알 수는 없습니다. (경우에 따라 다르지만, Adaptive Hash Index가 사용하는 인덱스 사이즈를 반드시 모니터링해야 합니다.)

이 기능은 MySQL5.5버전(InnoDB Plugin 1.0.3)부터는 이 기능을 동적으로 On/Off할 수 있습니다. 아래와 같이.. ^^;;

## 켜다
mariadb> set global innodb_adaptive_hash_index = 1;
 
## 끄다
mariadb> set global innodb_adaptive_hash_index = 0;

관련 통계 정보는 아래와 같이 확인..ㅋ

mariadb> show global status like 'Innodb_adaptive_hash%';
+----------------------------------------+------------+
| Variable_name                          | Value      |
+----------------------------------------+------------+
| Innodb_adaptive_hash_cells             | 42499631   |
| Innodb_adaptive_hash_heap_buffers      | 0          |
| Innodb_adaptive_hash_hash_searches     | 21583      |
| Innodb_adaptive_hash_non_hash_searches | 3768761684 |
+----------------------------------------+------------+

자주 사용되는 데이터는 해시를 통해서 직접 접근할 수 있기에, Mutex Lock으로 인한 지연은 확연하게 줄어듭니다. 게다가 B-Tree의 데이터 접근 비용(O(LogN))에 비해, 해시 데이터 접근 비용인 O(1)으로 굉장히 빠른 속도로 데이터 처리할 수 있습니다.

단, “자주” 사용되는 자원만을 해시로 생성하기 때문에, 단 건 SELECT로 인하여 반드시 해당 자원을 향한 직접적인 해시 값이 만들어지지 않습니다.

InnoDB는 Primary Key를 통한 데이터 접근을 제일 선호하기는 하지만, 만약 PK접근일지라도 정말 빈도있게 사용되는 데이터라면 이 역시 Hash Index를 생성합니다. (처음에는 단건 PK 접근에는 절대로 Hash Index를 만들지 않을 것이라 생각했지만, 곧 생각을 고쳐먹었습니다. ㅋㅋ)

Adaptive Hash Index Power!!

흠.. 말만 하지말고.. 눈에 보이는 효과를 보도록 할까요? 글빨이 안되니.. 비주얼로 승부를!!ㅋㅋ

아래와 같이 간단한 테스트 케이스(1300만 건 데이터)를 만들어서, IN 조건으로 PK를 통하여 데이터를 추출하는 테스트를 해보도록 해요. IN절에는 약 30개 정도의 파라메터를 넣고, 300개의 쓰레드에서 5ms 슬립을 줘가며 무작위로 트래픽을 보내봅니다.ㅋㅋ

## 테이블 스키마
create table ahi_test(
  i int unsigned not null primary key auto_increment,
  j int unsigned not null,
  v text,
  key ix_j(j)
);
 
## SELECT 쿼리
select left(v, 1) from ahi_test 
where i in (x,x,x,x,x,...x,x,x,,);

 

Adaptive Hash Index를 사용하지 않는 오른쪽 결과에서는 CPU가 100%였으나, Adaptive Hash Index를 사용한 이후에는 60%정도로 사용률이 내려갔습니다.

InnoDB-Adaptive-Hash-Index-Effect1

게다가, CPU는 줄었으나, 쿼리 응답 시간이 줄었기에 처리량 또한 20,000 -> 37,000으로 늘어났습니다. 참으로 놀라운 결과지요?? ㅋㅋ

InnoDB-Adaptive-Hash-Index-Effect2

Adaptive Hash Index를 켠 이후에는 확실히 B-Tree를 통해서 데이터에 접근하는 빈도가 줄어든 것도 확인할 수 있고요~

InnoDB-Adaptive-Hash-Index-Effect3

이에 따라 내부적인 잠금 현상도 확연하게 줄어들었습니다.

InnoDB-Adaptive-Hash-Index-Effect4

다른 것은 손대지 않고, Adaptive Hash Index만 켰을 뿐인데….

결론은 따~봉!! 굉장히도 풍요로운 꽁짜 점심이죠? ㅋㅋ

Cautions

자.. 이제 InnoDB Adaptive Hash Index 효과를 보았으니, 영혼없이 아무 곳에서나 무조건 쓰도록 할까요? 노노~! InnoDB Adaptive Hash Index 가 필요할 정도라면, SELECT가 꽤 많이 발생하는 서비스라고 생각해볼 수 있는데요.. 이 상황에서 테이블 DROP시 문제가 발생할 수 있습니다.

아래 그림은 percona-online-schema-change 툴을 활용하여 스키마를 변경한 전/후 Adaptive Hash Index사이즈를 체크한 것인데, 전후로 두 배로 해시 사이즈가 증가하였습니다. 그런데 두 배가 문제가 되기보다는, 아래와 같은 상황이 수 개월 동안 유지될 수 있다는 점입니다.

InnoDB-Adaptive-Hash-Index-Effect5

평소 운영 시에는 전~혀 문제가 되지 않지만, 수 개월동안 전~혀 사용하고 있지 않던 테이블을 영혼없이 정리하다보면 치명적인 장애에 직면할 수 있는 것이죠. 바로 저처럼.. -_-;;

아래 수치는 앞선 테스트 테이블에 트래픽을 주는 상황에서 OLD 테이블을 DROP하였는데, 테이블 정리 도중에는 처리량이 급감(3.8만 -> 2.7만)한 상황을 보여줍니다. 아래 현상이 굉장히 많은 SELECT가 발생하던 서버에서 발생을 하였다면, 단위 쿼리 처리량이 줄어듬에 따라 어플리케이션 쪽에 문제가 발생할 수도 있겠죠. ㅠㅠ

| Com_select | 39041 |
| Com_select | 39189 |
| Com_select | 38774 |
| Com_select | 38953 |
| Com_select | 39527 |
| Com_select | 37906 |
| Com_select | 39316 |
| Com_select | 37541 |
| Com_select | 37972 |
| Com_select | 32484 | <=== DROP OLD TABLE START
| Com_select | 27514 |
| Com_select | 27602 |
| Com_select | 27692 |
| Com_select | 27918 |
| Com_select | 27818 |
| Com_select | 28266 |
| Com_select | 28383 |
| Com_select | 28350 |
| Com_select | 37047 | <=== DROP OLD TABLE END
| Com_select | 39572 |
| Com_select | 38868 |
| Com_select | 39315 |
| Com_select | 38738 |
| Com_select | 39548 |
| Com_select | 39413 |
| Com_select | 38978 |

설혹, 데이터가 2G일지라도, 또한 파일 시스템이 xfs일지라도.. 이것은 디스크적인 요소라기 보다는 Memory 내부적인 잠금 이슈이기 때문에.. 어찌 해결해볼 방법은 없습니다.

InnoDB 내부적으로는 테이블 DROP시 Sleep없이 죽어라고 Hash Index에서 관련 노드를 모두 삭제한 후 테이블이 제거합니다. 그런데 이것이 단일 Mutex로 관리되기 때문에 기존 SELECT 성능에도 지대한 영향을 끼치는 것이죠. 그나마 최대한 이러한 현상을 회피할 수 있는 방법은 innodb_adaptive_hash_index_partitions을 수십개(기본값은 1)로 늘려놓고, 경합을 최대한 줄이는 방법만이 유일할 듯하네요. ^^ (테이블 드랍은 트래픽이 제일 없을 때로!!)

아.. 혹은 테이블 드랍을 수행할 때는 최대한 트래픽이 없는 새벽에, Adaptive Hash Index를 순간 OFF/ON을 하여 메모리를 해제하고, 테이블을 DROP하는 방법도 될 수 있겠네요. ^^ 선택은 서비스 상황에 맞게..

InnoDB Adaptive Hash Index가 사용하는 메모리 사이즈도 지속적으로 모니터링을 해야할 요소라는 것도 잊지 말아야할 것이고요. ^^

Conclusion

InnoDB Adaptive Hash Index는 B-Tree의 한계를 보완할 수 있는 굉장히 좋은 기능임에는 틀림 없습니다. 특히나 Mutex와 같은 내부적인 잠금으로 인한 퍼포먼스 저하 상황에서는 좋은 튜닝요소가 될 수 있습니다.

그러나, “자주” 사용되는 데이터를 옵티마이저가 판단하여 해시 키로 만들기 때문에 제어가 어려우며, 테이블 Drop 시 영향을 줄 수 있습니다. Hash Index 구조가 단일 Mutex로 관리되기 때문에, 수개월간 테이블이 사용되지 않던 상황에서도 문제가 발생할 수 있는 것입니다.

굉장한 SELECT를 Adaptive Hash Index로 멋지게 해결하고 있다면, 이에 따른 Side Effect도 반드시 인지하고 잠재적인 장애에 대해서 미리 대비하시기 바래요. ^^

 

MariaDB의 FederatedX 엔진으로 데이터를 주물러보자.

Overview

FederatedX는 MariaDB에서 제공하는 확장된 기능의 Federated이며, 기본적으로 MariaDB에서는 별다른 옵션 없이 사용할 수 있습니다.

바로 이전 포스팅(http://j.mp/16VA8x6)에서는 이 FederatedX 엔진을 활용하여 대용량 테이블을 서비스에 큰 지장없이 이관을 했던 사례에 대해서 정리를 했었는데요. 이 경험을 바탕으로 서비스에서 조금 더 유용하게 활용할 수 있을 방안에 대해서 상상(?)을 해보았습니다.

즉, 지금부터는 FederatedX 엔진 관련된 테스트를 바탕으로 정리하는 내용이오니, 만약 실 서비스에 적용하고자 한다면 반드시 검증 후 진행하셔야 합니다. ^^

Why FederatedX?

단일 데이터베이스의 성능을 따지자면, 굉장한 퍼포먼스를 발휘하는 MySQL 이기는 합니다만.. SNS 서비스 환경에서는 결코 단일 서버로는 커버 불가능합니다. 이 상황에서는 반드시 샤딩(데이터를 분산 처리) 구조로 설계를 해야하는데, 한번 구성된 샤딩은 온라인 중에 변경하기가 참으로 어렵습니다.

서비스 순단을 발생할 수 있지만, 온라인으로 데이터를 재배치를 할 수 있는 방법은 없을까? 하는 생각을 하던 와중에, 저는 FederatedX 엔진에서 해답을 찾았습니다.

FederatedX-Shard-Reorg1

 

MariaDB에서 제공하는 FederatedX엔진은 MySQL에서 제공하는 기능 외에 트랜잭션 및 파티셔닝 기능이 확장되어 있는데, 이 두가지 특성을 활용한다면 앞선 그림처럼 기존 데이터 구조를 원하는 형태로 재배치할 수 있다는 생각이 번뜩 났습니다. ㅎㅎ

단, 아래에서 설명할 모든 상황들은 아래 4 가지 상황이어야한다는 가정이 필요합니다.

  1. 샤드 키 업데이트는 없어야 한다.
    업데이터 시 기존 샤드 데이터가 DELETE되지 않음
  2. ALTER 작업은 없어야 한다.
    FederatedX 스키마 변경 불가
  3. 샤드 키는 문자열 타입이어서는 안된다.
    문자열로는 Range 파티셔닝 사용 불가
  4. 원본 서버 Binary Log은 ROW 포멧이어야 한다.
    FederatedX 에서 일부 쿼리 미지원
    ex) 
    INSERT INTO .. ON DUPLICATE UPDATE

자, 각 상황에 맞게 이쁜(?) 그림으로 간단하게 살펴보도록 할까요?

1) 샤드 재배치

기존 샤드를 재배치하는 경우인데, 만약 일정 범위(1~100, 101~200)로 데이터가 분산 저장되어 있는 경우를 해시 기준으로 변경하고 싶을 때 유용하게 적용가능할 것이라고 생각되는데요.

FederatedX-Shard-Reorg2

위 상황에서 FederatedX1과 FederatedX2을 다음과 같은 스키마 구성합니다.

CREATE TABLE `tab` (
  `p_id` int(11) NOT NULL,
  `col01` bigint(20) NOT NULL,
  `col02` bigint(20) NOT NULL,
  PRIMARY KEY (`user_id`)
) ENGINE=FEDERATED
PARTITION BY LIST (mod(p_id,3))
(PARTITION p0 VALUES IN (0) ENGINE = FEDERATED connection='mysql://feduser:fedpass@Nshard1_host:3306/db/tab',
 PARTITION p1 VALUES IN (1) ENGINE = FEDERATED connection='mysql://feduser:fedpass@Nshard2_host:3306/db/tab',
 PARTITION p1 VALUES IN (1) ENGINE = FEDERATED connection='mysql://feduser:fedpass@Nshard3_host:3306/db/tab');

원본 샤드 데이터를 각 FederatedX에 Import 후 리플리케이션 구성하면, 파티셔닝 정의에 맞게 데이터샤드들이 저장되겠죠? ^^

단, 데이터 동기화에 가장 큰 요소는 바로.. Network Latency입니다. 동일 IDC, 다른 스위치 장비에 물려있는 DB 경우에는 약 초당 500 ~ 700 rows정도 데이터 변경이 이루어졌습니다. 물론, 동일 스위치 경우에는 이보다 훨씬 더 좋은 데이터 변경 처리가 이루어질 것이라고 예측됩니다만.. 흠.. 이것은 기회가 된다면, 테스트하고 싶네요. ^^;;

2) 로컬 데이터 재구성

아래와 같이 현재의 DB 혹은 테이블을 여러 개의 객체로 찢는 경우를 말할 수 있는데요, 앞서 치명적인 요소가 되었던 Network Latency는 이 상황에서는 별다른 문제가 되지 않습니다. 모든 통신이 메모리 상에서 이루어지기 때문에, 본연의 속도가 나올 수 있는 것이죠. ^^

FederatedX-Shard-Reorg3

FederatedX 전용 서버를 다음과 같은 설정(/etc/my_fed.cnf)으로 구동하도록 합니다. 포트는 13306으로 띄운다는 가정으로..

[mysqld_safe]
timezone = UTC
 
[mysqld]
port     = 13306
socket   = /tmp/mysql_fed.sock
character-set-server = utf8
skip-innodb
server-id = xxx
binlog_format = row
 
[client]
port    = 13306
socket    = /tmp/mysql_fed.sock
 
[mysql]
no-auto-rehash
default-character-set = utf8

FederatedX 전용 서버를 간단하게 아래와 같이 띄우면 되겠죠? ㅎ

/usr/local/mysql/bin/mysqld_safe --defaults-file=/etc/my_fed.cnf 

그후 아래와 같이 FederatedX 테이블을 생성 후 원본 테이블 데이터 Import 후 리플리케이션을 맺어주면, DB별로 데이터가 재배치된 샤드 형태가 완성됩니다. ^^

CREATE TABLE `tab` (
  `p_id` int(11) NOT NULL,
  `col01` bigint(20) NOT NULL,
  `col02` bigint(20) NOT NULL,
  PRIMARY KEY (`user_id`)
) ENGINE=FEDERATED
PARTITION BY LIST (mod(p_id,3))
(PARTITION p0 VALUES IN (0) ENGINE = FEDERATED connection='mysql://feduser:fedpass@127.0.0.1:3306/db1/tab',
 PARTITION p1 VALUES IN (1) ENGINE = FEDERATED connection='mysql://feduser:fedpass@127.0.0.1:3306/db2/tab',
 PARTITION p2 VALUES IN (2) ENGINE = FEDERATED connection='mysql://feduser:fedpass@127.0.0.1:3306/db3/tab');

테스트를 해보니 초당 수천 건 데이터 변경이 가능하며, 단일 서버 데이터 재배치에 가장 유용하게 활용될 수 있다고 생각되네요.

3) 데이터 통합

늘 서비스가 잘되면 참 좋겠지만.. 때로는 망해가는 서비스의 DB를 한곳으로 몰아야할 경우도 있습니다. ㅜㅜ  앞에서 설명한 것들을 이 상황에 맞게 조금만 수정을 하면 되니, 굳이 길게 설명은 하지 않도록 하겠습니다.

 

FederatedX-Shard-Merge1

단, 기존 샤드의 데이터가 샤드키에 맞게 엄격하게 분리가 되어 있어야 합니다. (리플리케이션에서 충돌날 수 있어요!!)

4) 아카이빙

수년을 보관해야하는 당장 정리가 불가한 콜드데이터 성격의 데이터를 한 곳에 모은다는 컨셉인데요.. 이에 대한 것은 사전에 안정성 테스트 반드시 필요합니다. (어디까지나 테스트를 바탕으로 활용 가능한 상황인지라.. ^^;;)

FederatedX-Shard-Archieving

하루에 한번씩 돌아가면서 리플리케이션 IO_THREAD를 ON/OFF를 하게되면, 다수의 데이터베이스로부터 오는 데이터를 쉽게 한 곳으로 모을 수 있겠죠. 만약, 원본 테이블에서 파티셔닝 관리를 한다면, 이에 대한 에러 스킵 설정을 FederatedX에 미리 정의해놓으면 참 좋겠네요. ^^

Conclusion

처음에 버리다시피 전혀 검토를 하지 않았던 FederatedX를 다른 시각으로 발상을 전환해보니, 매우 활용할 수 있는 분야가 많았습니다. 물론 아직 실 서비스에서 직접 해보지는 않았지만, 이에 대한 각 테스트를 해보니 충분히 활용해볼 만한 여지는 있었습니다.

참고로, 위에서 설명하지는 않았지만, FederatedX +Blackhole을 활용하게 된다면, Network Latency 극복을 어느정도 할 수 있다고 생각합니다.

부족한 설명을 읽어주셔셔 감사합니다. ^^

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 를 조금 더 깊에 테스트하게 되었는데, 조만간 정리하여 블로그에 포스팅하도록 하겠습니다.