들어가며

• 일반적으로 NoSQL 데이터베이스는 ACID 트랜잭션을 지원하지 않습니다.
• DynamoDB는 높은 가용성, 처리량과 낮은 지연율에도 불구하고, ACID 특성을 가진 트랜잭션을 지원합니다.
  • AWS에서 DynamoDB는 1초에 천억 개의 트랜잭션을 처리하고 있다고 합니다.
• DynamoDB가 어떻게 ACID 트랜잭션을 처리하는지 알아보겠습니다.
• DynamoDB 설계의 기본이 궁금하신 분들은 이 글을 읽어보시면 도움이 됩니다.

본문

기존 트랜잭션 인터페이스와 다른점

Single Request

기존 트랜잭션 인터페이스에서는 시작, 커밋 혹은 어보트하는 인터페이스를 제공합니다. 여러 수행의 결과를 유기적으로 사용할 수 있는 장점이 있지만, 한 트랜잭션이 길어질 수 있는 문제가 있습니다. 길어진 트랜잭션은 시스템 리소스에 대한 잠금을 잡기 때문에 대규모 트래픽에서는 문제를 일으킬 수 있습니다. 따라서 DynamoDB에서는 여러 연산을 한 번에 요청하고, 모두 성공 혹은 모두 실패로 반환합니다.

Inplace Update

기존 트랜잭션 인터페이스들은 새 버전을 생성하는 동안 읽기 전용 트랜잭션은 이전 버전의 데이터에 접근할 수 있는 MVCC 구현체를 많이 사용합니다. MVCC를 지원하기 위해서는 PSQL처럼 row에 append 하거나, MySQL에서 undo 영역을 관리해야 합니다. 이런 작업들은 기존의 DynamoDB 서버를 크게 변경해야 하고 추가 데이터 적재를 위해 많은 저장 공간이 필요합니다. 따라서 DynamoDB에서는 MVCC를 지원하지 않고, 한 row는 동시에 하나의 버전으로만 업데이트됩니다.

No Lock

2단계 잠금(2PL)은 일반적으로 동시 트랜잭션이 동일한 데이터 항목을 읽고 쓰는 것을 방지하기 위해 사용되지만, 단점이 있습니다. 잠금은 동시성을 제한하고 교착 상태를 초래할 수 있습니다. 또한 트랜잭션의 일부로 잠금을 획득한 후 해당 트랜잭션이 커밋되기 전에 애플리케이션이 실패할 경우 잠금을 해제하기 위한 복구 메커니즘이 필요합니다. 설계를 간소화하고 운영을 최소화 하기 위해 DynamoDB는 잠금을 완전히 피하는 낙관적인 동시성 제어 체계를 사용합니다.

내부 동작 이해하기

큰 그림 살펴보기

1. 트랜잭션 요청이 들어오면, 요청 라우터가 요청에 필요한 인증과 권한 부여를 수행한 후 트랜잭션 코디네이터에게 요청을 전달합니다.
2. 트랜잭션 코디네이터는 트랜잭션을 key 기준으로 연산을 나누고, key에 해당하는 스토리지 노드들과 통신하여 트랜잭션을 완료 혹은 실패 처리합니다.
3. 그 결과는 다시 라우터를 통해 클라이언트로 전달됩니다.

Transaction Coordinator와 2PC

• 트랜잭션 코디네이터(TC)는 각 스토리지 노드(SN)들과 2단계 커밋 프로토콜(2PC)로 소통합니다.

  • 수도 코드로 표현하면 다음과 같습니다.

    TransactWriteItem(TransactWriteItems input):
        # Prepare all items
        TransactionState = 'PREPARING'
        for operation in input:
            sendPrepareAsyncToSN(operation)
        waitForAllPreparesToComplete()
    
        # Evaluate whether to commit or cancel the transaction
        if all prepares succeeded:
            TransactionState = 'COMMITTING'
            for operation in input:
                sendCommitAsyncToSN(operation)
            waitForAllCommitsToComplete()
            TransactionState = 'COMPLETED'
            return 'SUCCESS'
        else:
            TransactionState = 'CANCELLING'
            for operation in input:
                sendCancellationAsyncToSN(operation)
            waitForAllCancellationsToComplete()
            TransactionState = 'COMPLETED'
            return 'ReasonForCancellation'
    

• 2PC의 문제 중 하나인 코디네이터가 죽어서 응답 처리가 안되는 문제를 해결하기 위해 Ledger(장부)를 이용합니다.

  • TC들은 항상 트랜잭션에 대한 상태(생성, 성공, 실패)를 Ledger에 기록합니다.
  • Ledger에 만들어진지 오래되었지만, 처리되지 않은 트랜잭션들을 주기적으로 읽어서 다른 TC가 수행합니다.
  • 여러 TC가 수행하거나, 진행되는 트랜잭션들의 중복 수행 문제를 보완하기 위해 각 명령은 transactionID 기반으로 SN에서 멱등적으로 수행됩니다.

Serializable Isolation Level과 Timestamp Ordering

• DynamoDB는 직렬화 수준의 격리 레벨을 지원합니다.
  • 이때 앞서 설명한 봐와 같이, 2PL과 같은 잠금을 사용하지 않습니다.
• 낙관적 잠금의 일종인 Timestamp Ordering의 아이디어를 차용하고 살짝 변형해서 이용합니다.
  • 수도 코드로 보면 다음과 같습니다.

    def processPrepare(PrepareInput input):
        item = readItem(input)
        if item != NONE:
            if (evaluateConditionsOnItem(item, input.conditions) and
                evaluateSystemRestrictions(item, input) and
                item.timestamp < input.timestamp and
                item.ongoingTransactions == NONE):
                item.ongoingTransaction = input.transactionId
                return SUCCESS
            else:
                return FAILED
        else:  # item does not exist
            item = new Item(input.item)
            if (evaluateConditionsOnItem(item, input.conditions) and
                evaluateSystemRestrictions(input) and
                partition.maxDeleteTimestamp < input.timestamp):
                item.ongoingTransaction = input.transactionId
                return SUCCESS
            return FAILED
    
    def processCommit(CommitInput input):
        item = readItem(input)
        if item == NONE or item.ongoingTransaction != input.transactionId:
            return COMMIT_FAILED
        applyChangeForCommit(item, input.writeOperation)
        item.ongoingTransaction = NONE
        item.timestamp = input.timestamp
        return SUCCESS
    
    def processCancel(CancellationInput input):
        item = readItem(input)
        if item == NONE or item.ongoingTransaction != input.transactionId:
            return CANCELLATION_FAILED
        item.ongoingTransaction = NONE
        # item was only created as part of this transaction
        if item was created during prepare:
            deleteItem(item)
        return SUCCESS
    

  • PostgreSQL의 낙관적 잠금을 사용하는 Serializable Snapshot Isolation (SSI) 구현체와 유사합니다. 자세한 내용은 이 글을 참고하세요.
• Timestamp Ordering을 사용할 때 주의해야 할 점은 분산된 환경에서 각 기기 별로 시간 차이가 있을 수 있다는 것입니다. (동기화된 시계 문제)
  • 각 TC에서 시계가 다르면 다른 타임스탬프가 부여되어 실제 순서와 다르게 트랜잭션 순서가 부여될 수 있습니다.
  • 하지만, DynamoDB에서는 각 TC가 동기화된 시계를 사용하는 것을 보장하지는 않습니다.
  • AWS는 어느 정도 동기화된 시계를 사용하기 때문에 미세한 차이만 발생하여 큰 문제가 되지 않습니다.
  • 또한, 네트워크 지연과 가용성 보장을 위해 failover 후 처리 등 때문에, 완벽히 동기화된 시계가 있어도 어려움이 존재합니다. 따라서 그 실제 발생시간과 부여된 timestamp의 차이는 무시했다고 합니다.
  • 분산 환경에서 시계 동기화 문제가 궁금하다면 Google Spanner에 사용된 TrueTime을 참고하세요.

마무리 하며

• 분산 환경에서의 트랜잭션들은 상황에 따라 다르게 구현됩니다.
  • 일부 시스템은 동시성 제어를 위해 비관적 잠금을 사용하기도 하고, 타임스탬프를 사용하기도 합니다. 시스템마다 정밀한 시계, 로컬 노드의 시계, 하이브리드 논리적 시계 등 다양한 시간 소스를 사용합니다.
• DynamoDB의 트랜잭션 보장 요구는 고객들로부터 시작되었다고 합니다. 고객들의 니즈를 파악한 결과, 장시간 실행되는 트랜잭션이 필요하지 않고 위와 같은 정도로 작업할 수 있다고 판단했다고 합니다.
• 문제 정의에 따라서 큰 시스템들도 다른 노선을 선택합니다. 이를 보면 문제 해결을 위해서는 문제 파악과 정의가 중요하다는 것을 알 수 있었습니다.
• 이 글에서는 Timestamp Ordering에 대해 깊이 다루지 않았지만, 참조된 논문과 발표 자료들을 보면 도움이 될 것입니다.

참조

• Distributed Transactions at Scale in Amazon DynamoDB
• AWS DynamoDB 트랜잭션 API 문서
• Amazon DynamoDB: A Scalable, Predictably
  Performant, and Fully Managed NoSQL
  Database Service
• Timestamp Ordering
• DynamoDB의 시스템 디자인과 분산 트랜잭션 구현 원리
• AWS Time Sync 서비스 블로그