분산 DBMS-동시성 제어
동시성 제어 기술은 트랜잭션의 ACID 속성과 일정의 직렬 성을 유지하면서 여러 트랜잭션이 동시에 실행되도록합니다.
이 장에서는 동시성 제어에 대한 다양한 접근 방식을 연구합니다.
잠금 기반 동시성 제어 프로토콜
잠금 기반 동시성 제어 프로토콜은 데이터 항목 잠금 개념을 사용합니다. ㅏlock데이터 항목에 대해 읽기 / 쓰기 작업을 수행 할 수 있는지 여부를 결정하는 데이터 항목과 관련된 변수입니다. 일반적으로 데이터 항목이 동시에 두 트랜잭션에 의해 잠길 수 있는지 여부를 나타내는 잠금 호환성 매트릭스가 사용됩니다.
잠금 기반 동시성 제어 시스템은 1 단계 또는 2 단계 잠금 프로토콜을 사용할 수 있습니다.
단상 잠금 프로토콜
이 방법에서 각 트랜잭션은 사용하기 전에 항목을 잠그고 사용이 완료되는 즉시 잠금을 해제합니다. 이 잠금 방법은 최대 동시성을 제공하지만 항상 직렬 성을 적용하지는 않습니다.
2 단계 잠금 프로토콜
이 방법에서는 모든 잠금 작업이 첫 번째 잠금 해제 또는 잠금 해제 작업보다 우선합니다. 거래는 두 단계로 구성됩니다. 첫 번째 단계에서 트랜잭션은 필요한 모든 잠금 만 획득하고 잠금을 해제하지 않습니다. 이를 확장 또는growing phase. 두 번째 단계에서 트랜잭션은 잠금을 해제하고 새 잠금을 요청할 수 없습니다. 이것은shrinking phase.
2 단계 잠금 프로토콜을 따르는 모든 트랜잭션은 직렬화 할 수 있습니다. 그러나이 접근 방식은 충돌하는 두 트랜잭션간에 낮은 병렬성을 제공합니다.
타임 스탬프 동시성 제어 알고리즘
타임 스탬프 기반 동시성 제어 알고리즘은 트랜잭션의 타임 스탬프를 사용하여 데이터 항목에 대한 동시 액세스를 조정하여 직렬 성을 보장합니다. 타임 스탬프는 DBMS가 트랜잭션의 시작 시간을 나타내는 트랜잭션에 제공하는 고유 식별자입니다.
이러한 알고리즘은 트랜잭션이 타임 스탬프에 지정된 순서대로 커밋되도록합니다. 오래된 트랜잭션이 더 젊은 트랜잭션보다 먼저 시스템에 들어가기 때문에 더 오래된 트랜잭션이 더 젊은 트랜잭션보다 먼저 커밋되어야합니다.
타임 스탬프 기반 동시성 제어 기술은 동일한 직렬 일정이 참여하는 트랜잭션의 나이 순서대로 정렬되도록 직렬화 가능한 일정을 생성합니다.
타임 스탬프 기반 동시성 제어 알고리즘 중 일부는 다음과 같습니다.
- 기본 타임 스탬프 순서 알고리즘.
- 보수적 인 타임 스탬프 순서 알고리즘.
- 타임 스탬프 순서를 기반으로하는 다중 버전 알고리즘.
타임 스탬프 기반 순서는 직렬화를 적용하기 위해 세 가지 규칙을 따릅니다.
Access Rule− 두 트랜잭션이 동일한 데이터 항목에 동시에 액세스하려고 할 때 충돌하는 작업에 대해 이전 트랜잭션에 우선 순위가 부여됩니다. 이로 인해 더 젊은 트랜잭션은 이전 트랜잭션이 먼저 커밋 될 때까지 기다립니다.
Late Transaction Rule− 더 젊은 트랜잭션이 데이터 항목을 쓴 경우 이전 트랜잭션은 해당 데이터 항목을 읽거나 쓸 수 없습니다. 이 규칙은 더 젊은 트랜잭션이 이미 커밋 된 후 이전 트랜잭션이 커밋되지 않도록합니다.
Younger Transaction Rule − 젊은 트랜잭션은 이전 트랜잭션에 의해 이미 작성된 데이터 항목을 읽거나 쓸 수 있습니다.
낙관적 동시성 제어 알고리즘
충돌 률이 낮은 시스템에서는 모든 트랜잭션의 직렬 성을 확인하는 작업이 성능을 저하시킬 수 있습니다. 이러한 경우 직렬 성 테스트는 커밋 직전으로 연기됩니다. 충돌 률이 낮기 때문에 직렬화 할 수없는 트랜잭션을 중단 할 가능성도 낮습니다. 이 접근 방식을 낙관적 동시성 제어 기술이라고합니다.
이 접근 방식에서 트랜잭션의 수명주기는 다음 세 단계로 나뉩니다.
Execution Phase − 트랜잭션은 데이터 항목을 메모리로 가져 와서 작업을 수행합니다.
Validation Phase − 트랜잭션은 데이터베이스에 대한 변경 사항 커밋이 직렬 성 테스트를 통과하는지 확인하기 위해 검사를 수행합니다.
Commit Phase − 트랜잭션은 메모리의 수정 된 데이터 항목을 디스크에 다시 기록합니다.
이 알고리즘은 유효성 검사 단계에서 직렬 성을 적용하기 위해 세 가지 규칙을 사용합니다.
Rule 1- 두 개의 트랜잭션 T 주어 I 및 T의 j는 T 경우 나 T의 데이터 항목 읽고 J가 작성된다 후 T I 의 실행 단계 수없는 오버랩 T를 가진 J 의 위상을 저지한다. T j 는 T i 가 실행을 마친 후에 만 커밋 할 수 있습니다 .
Rule 2- 두 개의 트랜잭션 T 주어 I 및 T의 j는 T 경우 나 T에있는 데이터 항목을 작성한다 J가 판독되어, 다음 T I 's는 T하지 오버랩 위상 수 커밋 J 의 실행 단계'. T j 는 T i 가 이미 커밋 된 후에 만 실행을 시작할 수 있습니다 .
Rule 3- 두 개의 트랜잭션 T 주어 I 및 T의 j는 T 경우 나 T의 데이터 항목을 작성한다 j는 또한 기록된다 후 T I 'S는 T에하지 오버랩 위상 수 커밋 J 의 위상 커밋'. T j 는 T i 가 이미 커밋 한 후에 만 커밋을 시작할 수 있습니다 .
분산 시스템의 동시성 제어
이 섹션에서는 위의 기술이 분산 데이터베이스 시스템에서 어떻게 구현되는지 살펴 보겠습니다.
분산 2 단계 잠금 알고리즘
분산 2 단계 잠금의 기본 원리는 기본 2 단계 잠금 프로토콜과 동일합니다. 그러나 분산 시스템에는 잠금 관리자로 지정된 사이트가 있습니다. 잠금 관리자는 트랜잭션 모니터의 잠금 획득 요청을 제어합니다. 다양한 사이트에서 잠금 관리자 간의 조정을 시행하기 위해 적어도 하나의 사이트에 모든 트랜잭션을보고 잠금 충돌을 감지 할 수있는 권한이 부여됩니다.
잠금 충돌을 감지 할 수있는 사이트의 수에 따라 분산 2 단계 잠금 방식은 세 가지 유형이 있습니다.
Centralized two-phase locking−이 접근 방식에서는 한 사이트가 중앙 잠금 관리자로 지정됩니다. 환경의 모든 사이트는 중앙 잠금 관리자의 위치를 알고 트랜잭션 중에 잠금을 얻습니다.
Primary copy two-phase locking−이 접근 방식에서는 여러 사이트가 잠금 제어 센터로 지정됩니다. 이러한 각 사이트는 정의 된 잠금 집합을 관리 할 책임이 있습니다. 모든 사이트는 어떤 잠금 제어 센터가 어떤 데이터 테이블 / 조각 항목의 잠금을 관리 할 책임이 있는지 알고 있습니다.
Distributed two-phase locking−이 접근 방식에는 여러 잠금 관리자가 있으며 각 잠금 관리자는 로컬 사이트에 저장된 데이터 항목의 잠금을 제어합니다. 잠금 관리자의 위치는 데이터 분배 및 복제를 기반으로합니다.
분산 된 타임 스탬프 동시성 제어
중앙 집중식 시스템에서 모든 트랜잭션의 타임 스탬프는 물리적 클록 판독에 의해 결정됩니다. 그러나 분산 시스템에서는 사이트의 로컬 물리적 / 논리적 시계 판독 값이 전역 적으로 고유하지 않기 때문에 전역 타임 스탬프로 사용할 수 없습니다. 따라서 타임 스탬프는 사이트 ID와 해당 사이트의 시계 판독 값의 조합으로 구성됩니다.
타임 스탬프 순서 알고리즘을 구현하기 위해 각 사이트에는 각 트랜잭션 관리자에 대해 별도의 대기열을 유지하는 스케줄러가 있습니다. 트랜잭션 중에 트랜잭션 관리자는 사이트의 스케줄러에 잠금 요청을 보냅니다. 스케줄러는 증가하는 타임 스탬프 순서로 해당 큐에 요청을 넣습니다. 요청은 타임 스탬프 순서 (가장 오래된 것 먼저)에 따라 대기열의 앞쪽에서 처리됩니다.
충돌 그래프
또 다른 방법은 충돌 그래프를 만드는 것입니다. 이 트랜잭션 클래스가 정의됩니다. 트랜잭션 클래스에는 읽기 세트 및 쓰기 세트라는 두 개의 데이터 항목 세트가 있습니다. 트랜잭션의 읽기 세트가 클래스의 읽기 세트의 서브 세트이고 트랜잭션의 쓰기 세트가 클래스의 쓰기 세트의 서브 세트 인 경우 트랜잭션은 특정 클래스에 속합니다. 읽기 단계에서 각 트랜잭션은 읽기 세트의 데이터 항목에 대한 읽기 요청을 발행합니다. 쓰기 단계에서 각 트랜잭션은 쓰기 요청을 발행합니다.
활성 트랜잭션이 속한 클래스에 대해 충돌 그래프가 생성됩니다. 여기에는 수직, 수평 및 대각선 모서리 세트가 포함됩니다. 수직 에지는 클래스 내의 두 노드를 연결하고 클래스 내의 충돌을 나타냅니다. 수평 에지는 두 클래스에 걸쳐 두 노드를 연결하고 다른 클래스 간의 쓰기-쓰기 충돌을 나타냅니다. 대각선 에지는 두 클래스에 걸쳐 두 노드를 연결하고 두 클래스 간의 쓰기-읽기 또는 읽기-쓰기 충돌을 나타냅니다.
충돌 그래프는 동일한 클래스 내에서 또는 두 개의 다른 클래스에 걸쳐 두 트랜잭션이 병렬로 실행될 수 있는지 확인하기 위해 분석됩니다.
분산 된 낙관적 동시성 제어 알고리즘
분산 낙관적 동시성 제어 알고리즘은 낙관적 동시성 제어 알고리즘을 확장합니다. 이 확장에는 두 가지 규칙이 적용됩니다.
Rule 1−이 규칙에 따라 트랜잭션이 실행될 때 모든 사이트에서 로컬로 검증되어야합니다. 트랜잭션이 사이트에서 유효하지 않은 것으로 확인되면 중단됩니다. 로컬 유효성 검사는 트랜잭션이 실행 된 사이트에서 직렬 성을 유지하도록 보장합니다. 트랜잭션이 로컬 유효성 검사를 통과하면 전역 적으로 유효성이 검사됩니다.
Rule 2−이 규칙에 따라 트랜잭션이 로컬 유효성 검사를 통과 한 후 전체적으로 유효성을 검사해야합니다. 전역 유효성 검사를 통해 두 개의 충돌 트랜잭션이 둘 이상의 사이트에서 함께 실행되는 경우 함께 실행되는 모든 사이트에서 동일한 상대적 순서로 커밋해야합니다. 커밋 전에 유효성 검사 후 트랜잭션이 다른 충돌 트랜잭션을 기다려야 할 수 있습니다. 이 요구 사항은 트랜잭션이 사이트에서 확인되는 즉시 커밋 할 수 없기 때문에 알고리즘의 낙관적이지 않게 만듭니다.