Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Published by Scroll Versions from space ML1 and version 5.3
Sv translation
languageen

Table of Contents

Introduction

Excerpt

Xpand uses a combination of Multi-Version Concurrency Control (MVCC) and 2 Phase Locking (2PL) to support mixed read-write workloads. In our system, readers enjoy lock-free snapshot isolation while writers use 2PL to manage conflict. The combination of concurrency controls means that readers never interfere with writers (or vice-versa), and writers use explicit locking to order updates. 

Multi-Version Concurrency Control

Xpand implements a distributed MVCC scheme to ensure that readers are lockless, so that readers and writers never interfere with each other. As writers modify rows within the system, Xpand maintains a version history of each row. Each statement within a transaction uses lock-free access to the data to retrieve the relevant version of the row. 

Visibility Rules

Visibility rules within Xpand are governed by sets of ids (identifiers) associated with each transaction and statement execution. Rows modified by a transaction will only become visible to other transactions after the modifying transaction commits. Once the transaction commits, it generates a commit id (cid) at which the modification becomes visible.

The following chart displays the transaction lifespan. 

Transaction Lifespan
Image Modified
xidTransaction start id. Marks the logical beginning of the transaction.
iidInvocation id. Marks the beginning of a statement within a transaction.
cid

Commit id. Marks the id at which transaction changes are visible to other transactions.

The following table describes MVCC visibility rules in different isolation levels. Note that Xpand does not support the read uncommitted level.

Anchor
Isolation_Levels
Isolation_Levels
Isolation Levels

Each isolation level has a different set of visibility rules. The following table describes the basic rules for row visibility between transactions. 

Isolation LevelSnapshot AnchorComment
Read committedstatement

More strict than read committed as defined by ANSI. Allows a per-statement consistent snapshot read.

Each subsequent statement in a transaction gets a new iid, so every new statement can see rows committed before statement started executing (but never during).

Most similar to Oracle's consistent read isolation.

Rows are visible when statement (invocation) id > the modifying transaction commit id.

Repeatable read

(default)

transaction

More strict than repeatable read as defined by ANSI. Allows a per-transaction consistent snapshot read.

Each subsequent statement in a transaction sees the database at the start of transaction.

Transactions may also observe changes to the database made within the transaction.

Rows are visible when transaction id > the modifying transaction commit id.

Serializabletransaction

Strict ANSI isolation level. Used by the system to perform data moves within the cluster.

Rows visible when transaction id > modifying transaction commit id.

Database returns an error when the MVCC scheduler cannot guarantee transaction serializability.

Note: serializable isolation not currently available to end user transactions.

The following example demonstrates how transaction visibility works at different isolation levels. 

Image Modified

ID Generator

Xpand uses a globally unique ordered transaction id (xid) along with statement invocation id (iid) to control row visibility. Both the xid and iid generators use a combination of system wide clock and a unique node id to create a globally unique ordered identifier. 

Anchor
Version_History_and_Garbage_Collection
Version_History_and_Garbage_Collection
Version History and Garbage Collection 

Xpand maintains version history through the undo log. Since the undo log must already maintain information about the previous version of the row for transaction rollback, we can rely on using this information to access previous versions of the row for MVCC. The technique allows Xpand to maintain tables clustered by primary key instead of managing a large heap space. For inserts and updates, garbage collection occurs when we trim the undo log. However, Xpand keeps enough undo log history to service currently executing transactions. In addition to limiting undo log trim to local checkpoint rules, we also limit trimming based on the id of the oldest transaction within the system. 

Image Modified

The diagram above demonstrates how the system keeps multiple versions of the row in the undo log. Each row contains a Log Sequence Number (LSN) which points at the previous version of the row. We know that we've reached the end of the history chain when the previous LSN pointer precedes the trim LSN. 

Two Phase Locking for Writes

Optimistic concurrency controls do not work well in the presence of conflict (two transactions attempting to update the same row simultaneously). In such cases, a purely MVCC system would roll back one or both of the conflicting transactions and restart the operation. Since Xpand does not require the use of predetermined transactions (e.g. all logic within a stored procedure), such errors could bubble up to the application. Additionally, it's possible to create live-lock scenarios where transactions cannot make progress because of constant conflict.

To overcome these issues Xpand uses locking for writer-writer conflict resolution. Writers always read the latest committed information and acquire locks before making any changes.

Distributed Lock Manager

Xpand implements a distributed lock manager to scale write access to hot tables. Within the cluster, each node maintains a portion of the lock domain. No single node holds all of the lock information for the cluster.

Row Level and Table Level Locking

Xpand implements row level locks for transactions which touch a few rows at a time (a runtime configurable variable). For statements which affect a significant portion of a table, the query optimizer will promote row level locks to a table lock. 

Sv translation
languageko

Table of Contents

소개

Excerpt

ClustrixDB는 MVCC(Multi-Version Concurrency Control)와 2PL(2 Phase Locking)의 조합을 사용하여 혼합된 읽기-쓰기 워크로드를 지원합니다. 이 시스템에서 Reader는 락프리(lock-free) 스냅샷 격리를 활용하는 반면 Writer는 충돌 관리에 2PL을 사용합니다. 동시성 제어의 조합은 Reader가 Writer를 간섭하지 않으며 (반대의 경우도 마찬가지임), Writer는 명시적 잠금을 사용하여 업데이트를 실행한다는 것을 의미합니다.

Multi-Version Concurrency Control

ClustrixDB는 Reader와 Writer가 절대로 서로 간섭하지 않도록 하기 위해 Reader가 잠금이 없도록 분산된 MVCC 체계를 구현합니다. Writer가 시스템 내의 행을 수정하면 ClustrixDB는 각 행의 버전 기록을 유지 관리합니다. 트랜잭션 내의 각 명령문은 데이터에 대한 잠금 없는 액세스를 사용하여 관련 행 버전을 검색합니다.

가시성 규칙

ClustrixDB 내의 가시성 규칙은 각 트랜잭션 및 명령문 실행과 관련된 ids(식별자) 집합으로 관리됩니다. 트랜잭션에 의해 수정된 행은 수정 트랜잭션이 커밋된 후에만 다른 트랜잭션에서 볼 수 있게 됩니다. 트랜잭션이 커밋되면 변경 내용이 표시되는 커밋 ID(cid)를 생성합니다.

다음 도표는 트랜잭션 수명을 표시합니다.

트랜잭션 수명
Image Added
xid트랜잭션 시작 ID. 트랜잭션의 논리적 시작을 표시합니다.
iid호출 ID. 트랜잭션 내에서 명령문의 시작을 표시합니다.
cid

커밋 ID. 트랜잭션 변경이 다른 트랜잭션에 보여지는 ID를 표시합니다.

다음 표는 서로 다른 격리 수준에서 MVCC 가시성 규칙을 설명합니다. ClustrixDB는 read uncommitted 수준을 지원하지 않습니다.

격리 수준

각 격리 수준에는 다른 일련의 가시성 규칙이 있습니다. 다음 표에서는 트랜잭션 간의 행 가시성에 대한 기본 규칙을 설명합니다.

격리 수준스냅샷 허용 수준설명
Read committedstatement

ANSI에 정의된 대로 read committed보다 제한적입니다. 명령문마다 일치하는 스냅샷 읽기를 허용합니다.

트랜잭션의 각 후속 명령문은 새 iid를 가져오므로 모든 새 명령문은 명령문이 실행되기 전에 커밋된 행을 볼 수 있습니다 (실행 중에는 불가능).

오라클의 consistent read isolation과 가장 유사합니다.

statement (invocation) id > 수정 트랜잭션 커밋 ID일 때 행을 볼 수 있습니다.

Repeatable read

(default)

transaction

ANSI에서 정의한 대로 repeatable read보다 제한적입니다. 트랜잭션마다 일관성 있는 스냅샷 읽기를 허용합니다.

트랜잭션의 각 후속 명령문은 트랜잭션 시작 시 데이터베이스를 보게 됩니다.

트랜잭션은 트랜잭션 내에서 만들어진 데이터베이스에 대한 변경 사항을 관찰할 수도 있습니다.

transaction id > 수정 트랜잭션 커밋 ID일 때 행을 볼 수 있습니다.

Serializabletransaction

엄격한 ANSI 격리 수준. 시스템에서 클러스터 내에서 데이터 이동을 수행하는 데 사용됩니다.

transaction id > 수정 트랜잭션 커밋 ID일 때 행을 볼 수 있습니다.

MVCC 스케줄러가 트랜잭션 직렬화를 보장할 수 없으면 데이터베이스에서 오류를 반환합니다.

주: 최종 사용자 트랜잭션에는 serializable isolation을 현재 사용할 수 없습니다.

다음 예제는 서로 다른 격리 수준에서 트랜잭션 가시성이 작동하는 방법을 보여줍니다.

Image Added

ID 생성기

ClustrixDB는 행 표시 여부를 제어하기 위해 명령문 호출 ID(iid)와 함께 전역으로 고유한 정렬된 트랜잭션 ID(xid)를 사용합니다. xid 및 iid 생성기는 시스템 전체 클락(clock)과 고유한 노드 ID의 조합을 사용하여 전역으로 고유한 정렬된 식별자를 만듭니다.

버전 기록 및 가비지 컬렉션

ClustrixDB는 Undo 로그를 통해 버전 기록을 관리합니다. Undo 로그는 트랜잭션 롤백을 위해 행의 이전 버전에 대한 정보를 이미 유지해야 하므로 이 정보를 사용하여 MVCC의 이전 행 버전에 액세스할 수 있습니다. 이 방법을 통해 ClustrixDB는 큰 힙 공간을 관리하는 대신 기본 키로 클러스터 된 테이블을 유지 관리할 수 있습니다. 삽입 및 업데이트의 경우, Undo 로그를 트리밍할 때 가비지 컬렉션이 발생합니다. 그러나, ClustrixDB는 현재 실행 중인 트랜잭션을 서비스하기 위한 충분한 Undo 로그 기록을 유지합니다. Undo 로그 트림을 로컬 체크 포인트 규칙으로 제한하는 것 외에도 시스템 내에서 가장 오래된 트랜잭션의 ID를 기반으로 트리밍도 제한합니다.

Image Added

위의 다이어그램은 시스템이 Undo 로그에 행의 여러 버전을 유지하는 방법을 보여줍니다. 각 행은 행의 이전 버전을 가리키는 LSN(Log Sequence Number)을 포함합니다. 이전 LSN 포인터가 트림 LSN보다 앞에 오면 히스토리 체인이 끝났음을 알 수 있습니다.

쓰기를 위한 2PL(Phase Locking)

낙관적 동시성 제어는 충돌이 있는 경우 (동일한 행을 동시에 업데이트하려고 시도하는 두 개의 트랜잭션) 잘 작동하지 않습니다. 이럴 때 순수 MVCC 시스템은 충돌하는 트랜잭션 중 하나 또는 둘 다 롤백하고 작업을 다시 시작합니다. ClustrixDB는 미리 결정된 트랜잭션(예: 저장 프로시저 내의 모든 논리)을 사용할 필요가 없으므로, 이러한 오류가 응용 프로그램에 반환될 수 있습니다. 또한, 지속적인 충돌로 인해 트랜잭션을 진행할 수 없는 라이브 잠금(live-lock) 시나리오를 만들 수도 있습니다.

이러한 문제를 해결하기 위해 ClustrixDB는 writer-writer 충돌 해결을 위해 잠금을 사용합니다. Writer는 항상 최신으로 커밋된 정보를 읽고 변경하기 전에 잠금을 획득합니다.

분산 잠금 매니저(Distributed Lock Manager)

ClustrixDB는 핫 테이블에 대한 쓰기 액세스를 조정하는 분산 잠금 매니저를 구현합니다. 클러스터 내에서 각 노드는 잠금 도메인 일부를 유지 관리합니다. 단일 노드는 클러스터에 대한 모든 잠금 정보를 보유하지 않습니다.

행 수준 및 테이블 수준 잠금

ClustrixDB는 한 번에 몇 행을 처리하는 트랜잭션에 대한 행 수준 잠금을 구현합니다 (런타임에 설정할 수 있는 변수). 테이블의 상당 부분에 영향을 주는 명령문의 경우 Query Optimizer는 행 수준 잠금을 테이블 잠금으로 승격시킵니다.