Posting

Machbase의 최신 소식을 지금 만나보세요

[MACHBASE 이야기] 버그수정과 성능 향상

마크베이스(Machbase) 개발비화

버그수정과 성능 향상 두마리 토끼를 잡아보자!

마크베이스 개발본부 책임연구원 신진

처음 테크블로그 의뢰를 받았을 때에는 무얼 쓸까 며칠 고심했습니다. 시스템 프로그래밍만 죽어라 파왔고, 딥러닝이며 가상화폐 등 흥미로운 주제로 글을 쓸 자신도 없었기 때문이죠. 머릿속에서 맴도는 건 각종 알고리즘들 뿐이고 전공자라면 누구나 아는 사실을 굳이 다시 풀어놓을 필요가 있나 생각에 생각을 반복했습니다. 그래도 역시 송충이는 솔잎을 먹어야 하는 법, 제가 가장 오래 다루어온 분야에서 주제를 하나 따와서 소개하는 것도 나쁘지 않다 생각했습니다. 마침 어렵지 않은 알고리즘으로 제품에 좋은 영향을 준 버그픽스가 있었기에 간단히 소개해보고자 합니다.

배경지식

병렬 처리 속도 향상

병렬처리 성능을 올리는데에는 몇가지 방법이 있는데, 대표적으로 병목(Bottleneck)을 제거하는 방법이 그 첫번째입니다. 여러 CPU가 한 곳에 막혀서 프로그램 진행이 안 되는 부분을 시원하게 뚫어주는 것이죠.
두번째는 핫스팟(Hotspot)을 최적화, 병렬화해서 처리속도를 높이는 방법입니다. 핫스팟은 프로그램 코드 중 CPU 시간을 가장 많이 차지하거나, 가장 많은 인스트럭션을 실행하는 부분을 의미합니다. CPU를 가장 많이 차지하고 있는 부분의 속도를 높이면 프로그램의 전체적인 성능도 올라가게 됩니다. 다만 알고리즘의 데이터 의존성 분석 없이 함부로 병렬화를 수행하면 틀린 결과를 받아들게 될 수도 있습니다.

데이터 의존성

구문 S1과 S2가 있을 때, 아래 조건을 만족하면 S2는 S1에 의존성이 있습니다.

  • (I(S1) ∩ O(S2)) ∪ (O(S1) ∩ I(S2)) ∪ (O(S1) ∩ O(S2)) ≠ φ
  • I는 S가 읽기 연산을 하는 메모리 영역이다.
  • O는 S가 쓰기 연산을 하는 메모리 영역이다.
  • S2는 S1이 수행되고 일정한 시간 이후에 수행된다.

데이터 의존성은 크게 세 가지로 구분할 수 있습니다.

  • Anti Dependency (Write after Read – WAR Dependency): I(S1) ∩ O(S2) ≠ φ
  • Flow Dependency (Read after Write – RAW Dependency): O(S1) ∩ I(S2) ≠ φ
  • Output Dependency (Write after Write – WAW Dependency): O(S1) ∩ O(S2) ≠ φ

데이터 의존성이 존재하지만 S2가 파이프라인, 알고리즘 설계의 실수, 버그 등으로 S1보다 먼저 수행되어 연산 결과가 틀릴 때가 있습니다. 이를 데이터 위험(Data Hazard)이라고도 부릅니다. 즉, 의존성이 존재하는 연산들은 반드시 순서를 지켜서 수행해야 틀린 결과를 얻지 않습니다.

데이터 의존성 제거하기

세 가지 의존성 중 anti dependency와 output dependency는 변수 이름 변경(Variable Renaming)을 통해 의존성을 제거할 수 있습니다. Anti-dependency의 예제를 보자면, 아래 코드에서 3번 구문은 반드시 2번 구문 이후에 수행되어야 하며 순서가 바뀌면 데이터 위험이 발생하여 결과가 틀리게 됩니다.

  • 코드 1. Anti Dependency 예제.

1: b = 7;
2: a = b + 1;
3: b = 15;

여기에 임시 변수 b2를 추가해 값을 백업해두면 2번 구문과 3번 구문은 동시에 수행이 가능해집니다. 이제 3번 구문은 2번 구문에 의존성이 사라졌습니다.

  • 코드 2. Anti Dependency 제거

1: b = 7;
N: b2 = b;
2: a = b2 + 1;
3: b = 15;

이렇게 의존성을 제거한 연산들이나, 처음부터 의존성이 없는 연산들끼리는 병렬로 수행이 가능합니다. 전체적인 성능 향상과 처리 순서의 유연성은 덤으로 따라오죠. 참고로 flow dependency는 없애는 것이 불가능합니다. 이 때문에 ‘True Dependency’라고도 칭합니다.
의존성과 최적화에 대한 더 자세한 내용은 프로그래밍 서적이나 각종 정보 사이트 등을 참고하시면 되겠습니다.

제품에 버그가 있다!

기본 처리

machbase의 로그 테이블은 UPDATE와 중간 행 DELETE가 불가능합니다. 모든 DELETE는 테이블의 시작부터 지정한 Row ID(이하 RID), 또는 지정한 입력시간 이전의 레코드까지만 가능합니다. 이 특성 때문에 DBMS의 ACID 특성 중 Isolation에 대한 연산 부담을 상당히 줄일 수 있습니다. 이 부분은 단점이자 장점으로, 자유로운 UPDATE, DELETE가 불가능한 대신 복잡한 undo log, redo log 처리가 필요없기 때문에 machbase는 막강한 입력 속도를 자랑하고 있습니다.
내부 작동을 간략히 설명합니다. SELECT 세션에서는 테이블에 공유 잠금(Shared Lock)을 획득한 후 진행합니다. SELECT 중간에 DROP TABLE 등으로 테이블이 삭제돼버리면 안 되기 때문에 최소한의 동시성 제어를 해 둡니다. SELECT가 완료되면 잠금을 풀어줍니다.
DELETE 세션에서는 우선 삭제할 위치를 판단한 후, 테이블의 RID를 삭제 지점으로 변경해줍니다. 이후 wait 모드라면 테이블에 배타적 잠금(Exclusive Lock)을 획득해 선행 SELECT들이 완료할때까지 대기한 후 잠금을 해제하고 데이터파일을 삭제합니다. No-wait 모드이면 별도의 스레드에 데이터파일 삭제를 지시합니다.

  • 그림1. DELETE 연산 기본 작동

연산별 데이터 의존성

  • Flow(RAW) Dependency: SELECT AFTER APPEND – 만족
  • Output(WAW) Dependency: DELETE AFTER APPEND – 만족
  • Anti(WAR) Dependency: DELETE AFTER SELECT – ?

machbase의 다른 모든 연산은 의존성을 해치는 데이터 위험이 없지만, SELECT 이후에 DELETE를 수행하는 부분에 헛점이 존재했습니다. 아래 문단에 더 자세히 설명합니다.

SELECT 도중 File not found 오류!

상술했듯이 no-wait 모드일 때에는 테이블의 시작 RID만을 변경한 후 파일 삭제는 별도의 스레드로 수행합니다. 그런데 파일 삭제 스레드에서 선행 SELECT를 확인하지 않았기 때문에 선행 SELECT가 이미 삭제된 파일을 참조하는 오류가 발생했습니다. ENOENT인 에러넘버 2까지 뚜렷하게 찍혀 있군요.

  • 코드 3. 에구머니나!
select name, count(*) from logtbl1 group by name order by name;
name count(*)
----------------------------------------------
[ERR-00010: Failed to open file<.../machbase_home/dbs/SYSTEM_TABLESPACE/35/54/281474976710691.dat>, errno = 2.]
[0] row(s) selected.
Mach>

즉, 쓰기 연산이 읽기 연산 이후에 일어나야 하는데, 반대로 쓰기 연산이 먼저 이루어졌습니다. Anti dependency를 만족시키지 못한 상황입니다.

  • 그림 2. 안전하지 못한 SELECT, DELETE 병행

다행히 machbase에서는 이미 입력한 데이터에 대한 쓰기 연산이 DELETE뿐이므로, 쓰기 연산 이후에 해당 부분을 다시 참조할 필요가 없습니다. 따라서 DELETE 연산에 따라오는 파일 삭제를 선행 SELECT가 완료된 이후에 수행하면 충분합니다. 일반적인 DBMS에서는 undo log가 anti-dependency 제거 기법에서 사용하는 백업본 변수의 역할을 합니다.

  • 그림 3. DELETE 연산 이후 SELECT에서 백업본 참조

버그를 수정해보자. 기왕이면 속도도 높이면서.

Anti-Dependency에 위배되지 않도록 수정. 그런데 느려터졌다.

그러면 no-wait DELETE를 시작할 때에도 테이블을 배타적으로 잠가놓고 선행 SELECT들이 모두 완료될때까지 대기하면 되겠군요. 이로써 데이터 위험 문제는 사라졌습니다.
그런데 DELETE가 대기하는동안 후속 SELECT들도 모두 함께 대기하는 현상이 발생합니다.

  • 그림 4: 후속 SELECT 모두 대기.

보통 배타적 잠금이 대기중이면 이후에 획득을 시도하는 공유 잠금들 역시 대기하도록 구현됩니다. 이렇게 해야 배타적 잠금이 기아 현상을 겪지 않기 때문입니다. 이 때문에 선행 SELECT가 오래 걸리면 후속 SELECT들은 선행 SELECT가 모두 끝난 이후에야 수행이 가능합니다.
그런데 후속 SELECT들은 선행 SELECT와 DELETE에 데이터 의존성이 없습니다. DELETE 연산을 수행하면 테이블의 시작 RID가 바로 바뀌기 때문에, 후속 SELECT에서는 삭제 대상 레코드를 참조하지 않습니다. 즉, 파일 삭제보다 후속 SELECT를 먼저 수행해도 전혀 지장이 없습니다. 그럼 SELECT를 무조건 먼저 수행하면 될까요?
SELECT들을 무조건 먼저 수행하면 이번에는 DELETE가 기아 현상을 겪게 됩니다. 두 가지를 한번에 해결해야 합니다.

그럼 언제 작업할지 어떻게 결정하지?

어쨌거나 DELETE는 선행 SELECT가 완료될때까지 기다려야 합니다. 그래야만 anti dependency를 깨뜨리지 않을 수 있습니다. 그럼 선행 SELECT는 언제 끝날까요? 만해 한용운 선생님의 표현을 빌자면 ‘알 수 없어요’입니다. 며느리도 모릅니다. 시어머니도 모릅니다. 무하마드 알리도 알 리가 없습니다. 끝날 때까지 끝난 게 아닙니다.

  • 그림 5. 내일의 날씨는……

…… 아재 티는 그만 내고 계속해 보겠습니다. SELECT 세션이 종료되면 어딘가에 작업 상태를 기록하여 완료되었다는 사실을 DELETE 세션에게 알려 주면 됩니다. 그리고 완료된 작업은 더 이상 보존할 필요가 없으니 기록 장소에서 빼내어 제거해야겠죠. 이 작업에 가장 적합한 자료구조는 우선순위 큐(Priority Queue)입니다.

우선순위 큐 추가

각 테이블별로 작업 내역을 저장하는 우선순위 큐를 추가합니다. 일종의 스케줄러 역할이죠. 큐의 각 노드별 내용은 작업 시작시 테이블의 시작 RID와 작업 내용(SELECT/DELETE), 작업 완료 여부입니다. SELECT, 혹은 DELETE가 완료되면 자신의 작업 내역에 완료 표기를 해줍니다. 큐의 우선순위는 시작RID가 작은 작업이 더 높으며, 시작 RID가 같다면 DELETE가 SELECT보다 우선권을 가지도록 설정합니다.
우선순위 큐는 연결 리스트나 이진 탐색 트리 등을 이용해도 만들 수 있지만 보통 선택하는 알고리즘은 최소 힙(Min Heap)입니다. 세션 개수가 K개라면 연결 리스트는 삽입에 O(K), 삭제에 O(1), 도합 O(K)가 필요하지만, 힙에서는 삽입, 삭제에 모두 O(logK)가 필요합니다. 탐색 트리 역시 O(logK)이지만 필요한 기능에 비해 트리 연산의 오버헤드가 너무 큽니다. 연결 리스트가 삭제에 O(1)이긴 하지만 삽입이 O(K)이기 때문에 평균적으로는 힙을 사용하는쪽이 유리합니다. 힙은 보통 완전 2진 트리 구조를 따르는 배열로 구현합니다.
이 방법을 채택하면 우선순위 큐를 재조정하는 과정 동안만 배타적 잠금을 획득하면 충분하기 때문에 임계구역이 짧아지는(Fine-Grained Locking) 효과가 있습니다. 일반적으로 테이블 데이터는 최소한 레코드 수천만~수십억 개를 기준으로 하는 반면 한 서버의 최대 세션 개수는 수천개이면 매우매우 많은 편입니다.
SELECT 세션에서는 조회 시작 당시 테이블의 시작 RID를 큐에 삽입하고, DELETE 세션에서는 삭제 이후 테이블의 시작 RID를 큐에 삽입해 줍니다.

  • 그림 6: 우선순위 큐와 파일 접근 예측

SELECT, DELETE세션 모두 연산이 끝나면 우선 자신의 작업에 완료 플래그를 켜 줍니다. 그리고 큐의 첫번째 항목이 미완료 상태가 될때까지, 자신의 작업 내역이 아니더라도 노드를 꺼내 해제합니다. 이렇게 하면 미완료된 작업 중 가장 우선 순위가 높은 작업이 항상 큐의 시작 위치에 존재하게 됩니다. 반대로 큐의 시작 위치가 미완료 상태라면 자신의 작업이 완료되었어도 제거하지 않습니다.
DELETE 세션은 큐의 시작 위치가 자신의 작업이 되기를 기다려 파일 삭제 작업을 개시합니다. 큐의 시작이 자신이 아니면 대기합니다.
SELECT 세션은 바로 조회를 시작합니다. 선행 SELECT가 완료될때까지 DELETE 세션이 대기하기 때문에 안전하게 데이터파일을 조회할 수 있으며, 후속 SELECT 세션들은 DELETE에 의존성이 없어서 먼저 수행해도 전혀 이상이 없습니다.

  • 그림 7: SELECT는 우선순위 큐에 작업을 추가한 후 바로 실행 가능

SELECT 세션 일부가 종료되어도, 큐의 시작 위치가 완료 상태가 아니라면 큐에서 내역을 꺼내지 않습니다.

  • 그림 8: SELECT 세 건 완료. DELETE는 대기 중.
  • 그림 9: 선행 SELECT 완료.

선행 SELECT 세션이 모두 완료되어 큐의 시작 위치가 드디어 완료 상태가 되었습니다. 큐에서 완료 노드를 꺼내고 힙을 재조정하는 과정을 반복합니다.

  • 그림 10: 우선순위 큐 조정 과정

DELETE 세션이 큐의 시작 위치로 올라왔군요. 큐에서 노드를 꺼내는 것을 중지하고 파일 삭제 작업을 개시합니다. 삭제 대상 파일을 읽어야 하는 세션들은 이미 모두 종료되었습니다.

  • 그림 11: DELETE 세션에서 파일 삭제 개시

DELETE 중간에 다른 병행 SELECT들이 모두 완료되고 새로운 SELECT 세션이 하나 추가되었다고 가정해 보겠습니다. 이제 데이터파일 [0~400)은 참조되지 않습니다. 하지만 첫번째 DELETE가 아직 덜 끝났습니다.

  • 그림 12: SELECT 모두 완료, 새 SELECT 세션 시작
  • 그림 13: 첫번째 DELETE 완료.

드디어 첫번째 DELETE가 완료되었습니다. 우선순위 큐에서 완료 표기된 세션을 제거해 줍니다. 아직 시작하지 않은 두번째 DELETE 세션이 큐의 시작 위치까지 올라왔습니다. 이제 두번째 DELETE 세션을 개시합니다. 그 중간에 마지막으로 시작된 SELECT 세션은 종료되었다고 가정합니다.

  • 그림 14: 두번째 DELETE 진행

두번째 DELETE 세션도 완료되었습니다. 우선순위 큐에서 완료 표기된 노드를 또 제거해 줍니다.

  • 그림 15: 두번째 DELETE 완료
  • 그림 16: 우선순위 큐에서 완료된 노드 모두 제거

더 이상은 세션들이 없기 때문에 우선순위 큐도 완전히 비었습니다.

완료된 노드의 우선순위를 높여서 먼저 제거하는 것도 생각할 수 있습니다. 하지만 힙 데이터구조에서 세션 완료 여부로 우선순위를 결정하면 데이터 삽입, 삭제와 관계없이 노드의 정렬 순서가 바뀌어 버립니다. 이렇게 하면 힙 자료구조의 정렬이 무너집니다. 세션 완료시 자신의 정보를 제거하지 않아도 후속 세션이 완료된 노드를 모두 제거하기 때문에 굳이 완료 여부까지 우선순위에 포함하지 않아도 됩니다. RID와 연산 종류만으로 충분합니다.

이 작업을 통해 SELECT 세션은 DELETE 세션 존재 여부와 관계없이 즉각 조회를 시작할 수 있습니다. DELETE 역시 데이터파일을 참조하는 SELECT가 모두 완료되면 즉시 작업 권한을 얻어 파일을 안전하게 삭제할 수 있습니다. 데이터 위험도 제거했고 기아현상도 방지했습니다. 두 마리 토끼를 모두 잡았습니다.

결과

이제야 만족할만한 성능이 나온다.

아래 성능비교표는 레코드 5천만 건이 들어있는 테이블에 0.1~0.2초 내외로 걸리는 짧은 SELECT를 멀티스레드로 반복하면서 DELETE를 1백만건씩 49회 반복 삭제하는데 걸리는 시간을 측정한 결과입니다. 대조군으로 DELETE 없이 SELECT만 반복하는 테스트도 함께 수행하였습니다. DELETE 병행 테스트에서 잠금 방식에 16스레드 이후의 결과가 없는 이유는 너무 오래 걸려서 테스트가 무의미하기 때문입니다. 테스트를 시작하고 퇴근했는데, 다음날 출근해서 결과를 확인할때까지(16시간 이상) 테스트가 끝나지 않았습니다.

SELECT만잠금 방식우선순위 큐 방식성능향상
스레드 개수경과 시간(초)총 SELECT 수초당 SELECT경과 시간(초)총 SELECT 수초당 SELECT
111.8091008.512.1651008.2-2.9%
413.73440029.112.8340031.27.0%
814.21780056.313.78580058.03.1%
1614.2251600112.513.6661600117.14.1%
3223.613200135.523.4733200136.30.6%
  • 표 1. SELECT 여러 세션을 병행했을 때 알고리즘별 성능 비교
DELETE 병행잠금 방식우선순위 큐 방식성능향상
스레드 개수경과 시간(초)총 SELECT 수초당 SELECT경과 시간(초)총 SELECT 수초당 SELECTSELECTDELETE
1360.52629808.36.128498.0-3.3%5783.3%
4922.2932738029.77.97323329.2-1.6%11467.7%
87990.59546254157.98.75250257.4-0.9%91200.2%
1610.0161132113.0
3214.8512140144.1
  • 표 2. DELETE 한 세션과 SELECT 여러 세션을 병행했을 때 알고리즘별 성능 비교

확연한 차이를 볼 수 있습니다.

참고문헌

Horowitz, Sahni, and Anderson-Freed. Fundamentals of Data Structures in C. W.H. Freeman and Company, 1993.
김민장. 『프로그래머가 몰랐던 멀티코어 CPU 이야기』. 한빛미디어, 2010.

연관 포스트

C언어로 Binary data를 Machbase에 넣기

1.개요 Data를 다루다 보면 numeric, varchar 형 데이터뿐만 아니라 JPG, PNG, MP3와 같은 Binary data도 database에 저장해야 할 때가 존재한다. 그러나 일반 data들과는 달리 Binary

[MACHBASE 연동] Android studio에서 JDBC 연결하기

마크베이스 기술지원본부 이현민 1. 개요 수많은 데이터들이 많은 환경에서 생성되고 있는 오늘날, 우리 현대인들의 동반자인 스마트폰 또한 데이터생성의 주체로써 또는 전달자로서 알게 모르게 그 구실을