Parallel Execution (Parallel Replay)

커밋이 온 트랜잭션은 반영을 할 수 있으면 반영을 하고, 반영을 할 수 없으면 큐에서 대기하게 된다. 반영 가능 여부는 반영하고자 하는 트랜잭션과 반영 중인 트랜잭션 간의 의존성 체크를 통해 서로 독립적일 경우 반영이 가능하다고 판단한다.

의존성 체크는 Table과 Row 단위 모두 확인을 한다. 트랜잭션은 레코드로 이루어져 있고, 레코드에는 본인이 건드리는 Row가 정해져 있기 때문에, 해당 데이터를 기반으로 다른 트랜잭션과 의존 관계인지 여부를 판단한다.

의존성 확인 동작은 Hash Table과 Linked List로 관리가 되고 있다. Table 단위로 Hash Table을 확인하고, Table이 확인되면, 해당 위치에 존재하는 다음 Hash Table에서 Row를 확인한다. 이 위치엔 Linked List가 존재하며, 트랜잭션은 해당 List에 의존성 객체(TX Dependency )를 달아 놓는다.

이 동작을 통해 트랜잭션이 건드리는 모든 Row에 대한 Linked List에 TX Dependency가 등록이 된다. 반영 중인 트랜잭션이나 반영 대기 중인 트랜잭션 모두 이 구조 안에서 관리된다.

반영 가능 여부는 트랜잭션의 모든 TX Dependency가 Linked List의 front에 존재하는 지의 여부로 확인한다. 하나라도 front에 존재하지 않는다면 반영이 불가능하고, 앞서 반영 중인 트랜잭션의 완료를 대기하게 된다.

그림 1. 반영이 가능한 경우

반영이 가능한 경우는 위 그림과 같이 모든 의존성 체크를 했을 때 Linked List 상에 TX Dependency 가 가장 앞선 경우이다.

그림 2. 반영이 불가능한 경우

만약 위 그림과 같이 xid: 111인 트랜잭션이 아직 반영이 끝나지 않았다면 대기하게 된다. 반영이 완료된 트랜잭션은 위 Linked list에서 제거가 되고, xid: 112가 반영 가능하게 되면 반영 작업을 진행한다.

참고

의존성 판단 기준

그림을 보면 확인이 가능하듯이, Row 단위의 비교가 가능해야 한다. 오라클과 티베로와 같은 RDBMS 에는 ROWID라는 Row별 고유 식별자가 존재한다. (다른 RDBMS에선 다른 데이터가 사용된다.)

ROWID를 구성하는 요소는 데이터 파일 번호, 데이터 파일 내 블락 번호, 블락 내 Row데이터 위치로 구성이 되고 이 데이터는 Row의 고유 ID가 된다. ProSync는 기본적으로 이 데이터를 통해 의존성을 확인한다.

또한 Primary key, Foreign key 관계에 있는 두 Row데이터의 경우 시간 순서를 반드시 맞춰주어야 한다. 따라서 이 경우도 위 Row에 대한 Hash Table과는 별개의 Hash Table로써 관리가 된다.

주의

Hash Table의 사용 여부

Hash Table은 O(1) 시간 내에 데이터를 탐색할 수 있다는 장점을 가진 자료구조이다. 하지만 Hash함수의 특성 상 모든 데이터들은 정해진 갯수 내의 데이터로 매핑이 되어버린다. 이로 인해 적은 테이블을 동기화 하는 경우나 트랜잭션 내 동기화할 데이터가 많은 경우에 서로 다른 Row임에도 의존성 확인 과정에서 서로 같은 Row로 판단할 확률이 올라간다.

예를 들면, 위 그림에서 xid: 111과 xid: 112가 Table1의 Row1 을 건드린다고 판단하여 같은 의존성 관계에 있다고 생각하지만, 사실 이는 Hash 함수의 결과로써 실제로는 다른 Row를 건드리고 있을 수 있다.

Hash Bucket 수가 많아져서 Mapping할 수 있는 영역을 넓힌다 하여도, 많은 수의 Row를 건드리는 두 트랜잭션간에는 서로 충돌확률이 기하급수적으로 늘어난다.

Birthday paradox와 유사한 이유 때문인데, 약 1,000,000 개의 Hash Bucket을 가진 Table에 10,000개의 Row데이터를 가지는 서로 다른 두 트랜잭션이 있으면, 이들이 서로 겹치지 않을 확률은 $P(\text{no collision}) = \frac{\dbinom{N}{n} \cdot \dbinom{N - n}{n}}{\dbinom{N}{n}^2}$ 로 계산이 가능하고 근사치로 계산했을 때 약 $3 \times 10^{-44}$ 이 나와서 사실상 겹치지 않는 것이 불가능 하다고 생각하면 된다.

이로 인해 차기 버전부터는 RedBlack Tree로의 변경이 이루어진다. 현재 버전까지는 병렬화 과정의 한계로 위와 같은 구조를 그대로 사용한다.

관련 파라미터는 REPLAY_THREAD_CNT 로, 해당 값이 올라가면 병렬 세션의 수가 많아진다. 하지만 위 로직을 보면 알 수 있다시피 결국 Hash Table 내에서 Table, Row단위로 TX Dependency가 잘 풀려야 병렬 반영이 가능하다. 이로 인해 숫자를 올린다고 반드시 올린 숫자만큼 정비례하게 증가하지 못하는 경우도 발생한다.