Haeinsa: HBase Transaction Library

2013 Deview 2일차 세션7 TRACK2
대부분의 NoSQL들은 트렌젝션이나 인덱스 같은 중요한 기능을 제공하지 않아 일반적인 서비스 구현에 어려움을 겪는 경우가 많습니다. 메세지 중심의 서비스이기 때문에 트렌젝션이 굉장히 많이 일어나고 유연한 확장성이 중요했던 비트윈에서는 이 문제를 해결하기 위해 여러가지 노력을 하였고,결국 HBase에서 트렌젝션을 제공해주는 라이브러리인 Haeinsa를 구현하여 실제 서비스에 성공적으로 적용하여 사용하고 있습니다. 오픈소스로 공개된 Haeinsa 라이브러리의 동작과 성능에 대해 소개합니다.
https://github.com/vcnc/haeinsa

Transcript

1. Haeinsa HBase Transaction Library 김영목 VCNC
2. 이 발표에서는 해인사를 소개합니다.
3. Between은 HBase를 사용하고 있습니다. 발표자: 김영목 VCNC 여기는 봉은사
4. 비트윈에서는 HBase를 사용합니다 HBase (Cluster) ELB (HTTP) API #1 API #2 HTTP ELB #1 (TCP) ELB #2 (TCP) ZooKeep er TCP API #3 ELB #3 (TCP) 비트윈의 시스템 아키텍처
5. Linearly Scalable Fault Tolerant Write Throughput HBase를 쓰는 메신저 서비스 HBase의 좋은 점
6. Row단위 ACID만 지원 Document 단위 ACID만 지원 Row 단위 ACID만 지원 그러나 NoSQL 데이터베이스 트랜잭션이 없다
7. T1 T2 bobBal = Read(bob,bal) bobBal = Read(bob,bal) joeBal = Read(joe,bal) aliceBal = Read(alice,bal) Write(bob, bobBal - $7) Write(alice, aliceBal - $2) Write(joe, joeBal +$7) Write(bob, bobBal + $2) • Bob은 $10, Joe는 $2, Alice는 $8가 있다고 해봅시다. • 아래 트랜잭션의 결과는 어떻게 될까요? 트랜잭션이 없으면 불편한 점
8. Multi-Row ACID 지원! 하지만, Google에는 트랜잭션이 있다! Row단위 ACID만 지원 Document 단위 ACID만 지원 Row 단위 ACID만 지원
9. Full ACID Support + Linearly Scalable Fault Tolerant Write Throughput 모든 Hbase의 장점뿐만 아니라 트랜잭션도 지원해야한다! NoSQL 트랜잭션, 어떤 특징들을 가져야 하는가?
10. 1. Multi-row, Multi-table 트랜잭션 지원 2. Linearly scalable 3. Failure tolerant 4. Low overhead Haeinsa의 특징 Haeinsa는 HBase에서 트랜잭션을 제공합니다.
11. 1. HBase에 대한 수정은 전혀 없습니다. 2. 따라서 현재 운영 중인 HBase 클러스터에 쉽게 적용 가능 합니다. Haeinsa의 특징 Haeinsa는 클라이언트 라이브러리입니다. Application Haeinsa HBase Client Library
12. Haeinsa의 특징 Haeinsa는 이미 비트윈에 적용되어 사용되고 있습니다! 1. 2개월간 아무 문제 없이 돌아가고 있습니다. 2. 하루에 3억건의 트랜잭션을 처리하고 있습니다.
13. Haeinsa의 특징 Haeinsa는 오픈소스 입니다. https://github.com/vcnc/haeinsa
14. Haeinsa 이름의 유래 Haeinsa는 정말로 해인사에서 따온 이름입니다. 1. 해인사에는 팔만대장경이 보존되어 있습니다. 2. 팔만대장경은 81,258개의 목판본으로 이루어져 있습니다. 3. 오탈자 없이,52,382,960글자가 새겨져 있습니다. 4. 800년 가까이 아무 문제 없이 보존되었습니다. 5. 개발 시작 당시 VCNC의 사무실이 봉은사 옆에 있었습니다.
15. 분산시스템에서의 트랜잭션 구현
16. T 1 T 2 T 3 T 4 Write Set: Transaction Timeline: R1, R2 R2, R3 R1, R2, R3 R4 트랜잭션 관리하기 동시에 실행되는 트랜잭션은 어떻게 관리해야할까요?
17. T 1 T 2 T 3 T 4 Transaction Timeline: 트랜잭션 관리하기 가장 단순한 방법은 한번에 하나씩만 실행하기 입니다. 하지만 동시성이 떨어져 성능은 좋지 않습니다.
18. T 1 T 2 T 3 T 4 Transaction Timeline: 트랜잭션 관리하기 동시에 실행해도 되는 것들은 동시에 실행하는 것이 좋습니다!
19. T 1 T 2 T 3 T 4 Write Set: Transaction Timeline: R1, R2 R2, R3 R1, R2, R3 R4 트랜잭션 관리하기 일단 트랜잭션을 실행하다가 커밋시에 충돌하는 트랜잭션을 실패시키면 됩니다
20. • 동시성을 위해 더 작은 단위의 Locking이 필요 • Row 단위나 Column단위로 Locking을 해야 함 • 이를 위해 2PC와 같은 프로토콜이 필요! 트랜잭션 동시성 향상 시키기
21. Coordinator Participant Participant Prepared! Prepared! Prepared! Voting Phase에서는 각 Participant들을 준비시킵니다. 2-Phase Commit Voting Phase
22. Coordinator Participant Participant Commited! Commited! Commited! Commit Phase에서는 각 Participant를 Commit시킵니다. Commit Phase 2-Phase Commit
23. • Haeinsa에서 트랜잭션의 상태를 저장하기 위한 특수 칼럼 • Row 단위 칼럼이 하나씩 존재 • 읽기/쓰기 시마다 확인 Row key bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 3: $2 State:STABLE CommitTimestamp:3 Lock Column
24. Stable Committed Prewritten Stable Aborted Prewritten 트랜잭션 성공시 트랜잭션 실패시 Lock Column State Diagram 각 Row의 상태 변화는 다음과 같습니다.
25. 3.구현
26. BeginTransaction() bobBalance = Read(Bob, balance) Write(Bob, balance, bobBalance-$7) joeBalance = Read(Joe, balance) Write(Joe, balance, joeBalance+$7) Commit() 아래 예제를 통해서 Haeinsa의 동작을 알아봅시다. How it works
27. Get(Bob, lock) Get(Bob, bal) bobBal = Read(Bob,bal) How it works
28. Write(Bob, bobBal - $7) How it works
29. joeBal = Read(Joe,bal) Get(Joe, lock) Get(Joe, bal) How it works
30. Write(Joe, joeBal + $7) How it works
31. Commit() How it works
32. 3개 Row 트랜잭션의 커밋을 살펴봅시다. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation ()
33. Primary Row부터 prewrite 합니다. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation ( )
34. 나머지 두 개의 Secondary Row들도 차례로 Prewrite합니다. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation (1 )
35. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation (2 ) 나머지 두 개의 Secondary Row들도 차례로 Prewrite합니다.
36. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation ( ) Primary Row를 Commit 상태로 원자적으로 변경합니다. 이 이후에는 문제가 발생해도 이 트랜잭션은 성공한 것으로 처리합니다.
37. 우선 Secondary Row들부터 Stable상태로 만듭니다. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation (1 )
38. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation (2 ) 우선 Secondary Row들부터 Stable상태로 만듭니다.
39. 1 2 PREWRITTEN COMMITTED STABLE Commit Operation ( ) 마지막으로 Primary를 Stable로 만듭니다. 이로써 트랜잭션은 처리가 완료되었습니다.
40. 아래 주황색 영역에 대해서 각 Row에 새로운 값이 쓰였는지를 확인 쓰여있지 않으면 동시에 Row들을 잠금 Summary
41. 아래 녹색부분 동안 각 Row들이 잠겨있음 Summary
42. 파란색 부분 이후부터는 이 트랜잭션이 성공한 것으로 인식하게 됨 Summary
43. 실패시 동작 트랜잭션이 진행되면서 각 단계에서 실패가 날 수 있습니다. 가능한 모든 경우를 고려해야 합니다.
44. 실패시 동작 특히 커밋시 진행되는 각 단계에서 실패가 나는 경우에 대해 살펴봐야합니다.
45. 이 단계를 실패 시켜 보겠습니다. 실패! 실패시 동작
46. 1 2 PREWRITTEN COMMITTED STABLE 실패시 동작 Secondary2에 Prewrite 실패시 이 상태가 됩니다
47. 1 2 a( ) PREWRITTEN COMMITTED STABLE ABORTED 실패시 동작 일단 Primary를 Abort상태로 바꿉니다
48. 1 2 PREWRITTEN COMMITTED STABLE ABORTED 실패시 동작 (1 ) 이미 Pewritten상태인 Secondary1을 Stable로 바꿉니다
49. 1 2 PREWRITTEN COMMITTED STABLE ABORTED 실패시 동작 마지막으로 Primary를 Stable로 만듭니다. 이로써 트랜잭션은 복구가 완료되었습니다. ( )
50. 어떻게 변경사항을 취소하는가? Row key Bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 4: $9 3: $2 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Primary:Bob Alice 7:$10 State:STABLE CommitTimestamp:7 데이터를 여러 Timestamp에 걸쳐 여러 버전을 저장해 둡니다.
51. 어떻게 변경사항을 취소하는가? Row key Bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 4: $9 3: $2 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Primary:Bob Alice 7:$10 State:STABLE CommitTimestamp:7 PrewriteTimestamp이 가리키는 버전을 지우면 변경사항을 취소할 수 있습니다.
52. 어떻게 변경사항을 취소하는가? Row key Bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 4: $9 3: $2 State:STABLE CommitTimestamp:6 Alice 7:$10 State:STABLE CommitTimestamp:7 PrewriteTimestamp이 가리키는 버전을 지우면 변경사항을 취소할 수 있습니다.
53. 어떻게 변경사항을 취소하는가? Row key Bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 3: $2 State:STABLE CommitTimestamp:6 Alice 7:$10 State:STABLE CommitTimestamp:7 PrewriteTimestamp이 가리키는 버전을 지우면 변경사항을 취소할 수 있습니다.
54. 이번엔 이 단계를 실패 시켜 보겠습니다. 실패시 동작 실패!
55. 1 2 PREWRITTEN COMMITTED STABLE 실패시 동작 (1 ) 실패한 경우 이 상태가 됩니다.
56. 1 2 PREWRITTEN COMMITTED STABLE 실패시 동작 (2 ) 우선 Secondary Row들부터 Stable상태로 만듭니다.
57. 1 2 PREWRITTEN COMMITTED STABLE 실패시 동작 ( ) 마지막으로 Primary를 Stable로 만듭니다. 이로써 트랜잭션은 복구가 완료되었습니다.
58. 4.성능
59. 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 0 10 20 30 40 50 60 Tx/Sec # of Region Server Haeinsa HBase Practical Performance (Throughput) 메시지 전송 (3 rows, 3 gets, 6 puts)
60. 0 5 10 15 20 25 30 35 0 10 20 30 40 50 60 ms # of Region Server Haeinsa HBase Practical Performance (Latency) 메시지 전송 (3 rows, 3 gets, 6 puts)
61. 0 20000 40000 60000 80000 100000 120000 0 10 20 30 40 50 60 Tx/Sec # of Region Server Haeinsa HBase Worst Case Performance (Throughput) 3 rows, 1 gets, 2 puts
62. 0 5 10 15 20 25 30 0 10 20 30 40 50 60 ms # of Region Server Haeinsa HBase Worst Case Performance (Latency) 3 rows, 1 gets, 2 puts
63. 5.비트윈 서비스에 적용 사례
64. 그냥 적용해 봤습니다 HBase (Cluster) Between 테스트 서버 비트윈 클라이언트 Haeinsa 적용 • HBase의 기본 연산을 모두 제공합니다. • Lock Column만 추가하면 기존 HBase클러스터에 쉽게 적용 이 가능합니다.
65. • 일반적인 경우의 충돌 비율: 0.004% ~ 0.010% • 하지만 유저가 의도적으로 많은 요청을 보낼 때에는 충돌이 자 주 나는 현상이 발생하였습니다. 그냥 적용했을때의 문제점 HBase (Cluster) Between 테스트 서버 비트윈 클라이언트 요청을 의도적으로 많이 보내는 경우, 충돌이 자주남
66. • 특정 유저의 연산을 특정 쓰레드가 처리하도록 구현 • 결과적으로 한 유저에 대해서는 Serial Scheduling이 되어 한 유저가 의도적으로 요청을 많이 보내도 Conflict이 나지 않음 특정 쓰레드로 요청을 스케쥴링 비트윈 서버내 쓰레드풀 비트윈 클라이언트
67. • 만약 Conflict이 나게 되면 요청을 처음 부터 다시 시작 • 다시 충돌이 나는 경우를 방지하기위해 적당히 Backoff를 함 • Conflict Rate가 크게 줄었음: 0.0003%~0.0010% Conflict Rate를 더욱 낮추기 위해서 재시도를 함 비트윈 클라이언트 HBase (Cluster) Conflict 발생시 다시 재시도
68. 6.정리
69. 정리 • Haeinsa는 HBase상에서 트랜잭션을 지원하면서 Lineary Scalable한 클라이언트 라이브러리 입니다. • 비트윈 서비스에서 2달간 적용되어 안정성을 확보하였습니다. • 다른 트랜잭션 라이브러리에 비해 성능이 뛰어나고 HBase보 다 더 좋은 성능을 내기도 합니다.
70. Multi-Row ACID 지원! 정리 Document 단위 ACID만 지원 Row 단위 ACID만 지원 Haeinsa를 통해 Multi-Row ACID 지원
71. 정리 http://github.com/vcnc/haeinsa
72. jobs@vcnc.co.kr
73. THANK YOU
74. Q&A
75. There is rows representing balance of Bob and Joe. Let’s track how Haeinsa works by studying the transaction that Bob giving the $7 to Joe. HBase-side Row key Bal Lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side Appendix A: How it works? << Before Transaction >>
76. Nothing to do HBase-side Row key bal lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [] Locks = {}
77. Read Bob’s Lock column first. And then read Bob’s Balance column. HBase-side Row key bal lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 Client-side State of Transaction Writes = [] Locks[Bob] = (STABLE, 3) BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit()
78. Bob’s new balance put into writes. Store on client- side memory. It will be write on Hbase on commit. HBase-side Row key bal lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 Client-side State of Transaction Writes = [(Bob, bal, $3)] Locks[Bob] = (STABLE, 3) BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit()
79. Read Joe’s Lock column first. And then read Joe’s Balance column. HBase-side Row key bal lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 Client-side State of Transaction Writes = [(Bob, bal, $3)] Locks[Bob] = (STABLE, 3) Locks[Joe] = (STABLE, 3) BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit()
80. Joe’s new balance put into writes. HBase-side Row key bal lock Bob 3: $10 State:STABLE CommitTimestamp:3 Joe 3: $2 State:STABLE CommitTimestamp:3 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [(Bob, bal, $3), (Joe, bal, $9)] Locks[Bob] = (STABLE, 3) Locks[Joe] = (STABLE, 3)
81. Prewrite value on primary row. Primary row is selected by particular algorithm by Haeinsa. HBase-side Row key bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 3: $2 State:STABLE CommitTimestamp:3 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [(Bob, bal, $3), (Joe, bal, $9)] Locks[Bob] = (PREWRITTEN, 6, 4, [Joe]) Locks[Joe] = (STABLE, 3)
82. Prewrite value on secondary row. Secondary row is the row which is not primary row. HBase-side Row key bal lock Bob 4: $3 3: $10 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Secondaries:[Joe] Joe 4: $9 3: $2 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Primary:Bob BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [(Joe, bal, $9)] Locks[Bob] = (PREWRITTEN, 6, 4, [Joe]) Locks[Joe] = (PREWRITTEN, 6, 4, , Bob)
83. If prewrite all succeed, change state of primary row to COMMITED. The transaction can be treated as succeed at this moment. HBase-side Row key bal lock Bob 4: $3 3: $10 State:COMMITTED CommitTimestamp:6 Secondaries:[Joe] Joe 4: $9 3: $2 State:PREWRITTEN CommitTimestamp:6 PrewriteTimestamp:4 Primary:Bob BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [] Locks[Bob] = (COMMITTED, 6, , [Joe]) Locks[Joe] = (PREWRITTEN, 6, 4, , Bob)
84. Change state of secondary row to STABLE. HBase-side Row key bal lock Bob 4: $3 3: $10 State:COMMITTED CommitTimestamp:6 Secondaries:[Joe] Joe 4: $9 3: $2 State:STABLE CommitTimestamp:6 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [] Locks[Bob] = (COMMITTED, 6, , [Joe]) Locks[Joe] = (STABLE, 6)
85. Change state of primary row to STABLE. HBase-side Row key bal lock Bob 4: $3 3: $10 State:STABLE CommitTimestamp:6 Joe 4: $9 3: $2 State:STABLE CommitTimestamp:6 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [] Locks[Bob] = (STABLE, 6) Locks[Joe] = (STABLE, 6)
86. Transaction completed. All rows are in stable state. HBase-side Row key bal lock Bob 4: $3 3: $10 State:STABLE CommitTimestamp:6 Joe 4: $9 3: $2 State:STABLE CommitTimestamp:6 BeginTransaction() bobBal = Read(Bob, bal) Write(Bob, bal, bobBal-$7) joeBal = Read(Joe, bal) Write(Joe, bal, joeBal+$7) Commit() Client-side State of Transaction Writes = [] Locks={}