커밋 순서

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 기사는 컴퓨터 과학 전문가의 주의가 필요하다.구체적인 문제는 현재 상태로는 편집된 기사를 복사할 수 없다는 것입니다. Wiki Project Computer Science는 전문가를 채용하는 데 도움이 될 수 있습니다. (2012년 10월) 이 문서의 주제는 위키피디아의 일반적인 알림 가이드라인을 충족하지 못할 수 있습니다. 주제와는 무관하고 단순한 언급을 넘어 상당한 내용을 다루는 신뢰할 수 있는 2차 출처를 인용함으로써 주제 인지도를 입증할 수 있도록 도와주시기 바랍니다. 알림을 표시할 수 없는 경우 문서가 병합, 리디렉션 또는 삭제될 수 있습니다.출처 : '커밋 오더'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2011년 12월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2011년 11월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍을 확인) 이 기사는 대부분의 독자들이 이해하기에는 너무 전문적일 수 있다. 기술적인 세부사항을 삭제하지 않고 비전문가가 이해할 수 있도록 개선해 주세요.(2011년 11월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍을 확인) 이 글은 위키피디아 편집자의 개인적인 감정을 기술하거나 주제에 대한 독창적인 주장을 제시하는 개인적인 성찰, 개인적인 에세이 또는 논쟁적인 에세이처럼 쓰여집니다. 백과사전 형식으로 다시 작성하여 개선하시기 바랍니다. (2011년 11월) (이 템플릿메시지 삭제 방법 및 삭제 타이밍에 대해 알아보기) 이 문서는 Wikipedia의 품질 기준에 맞게 다시 작성해야 할 수 있습니다. 네가 도울 수 있어. 토크 페이지에 제안이 포함될 수 있습니다. (2020년 4월) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

커밋 오더(CO)는 데이터베이스, 트랜잭션 처리 및 관련 응용 프로그램의 동시성 제어에서 상호 운용 가능한 직렬화 기술 클래스입니다.이를 통해 낙관적인(비블로킹) 구현이 가능합니다.멀티코어 프로세서의 보급에 따라 CO는 동시 프로그래밍, 트랜잭션 메모리 및 소프트웨어 트랜잭션 메모리(STM)에서도 점점 더 많이 사용되어 최적의 시리얼라이제빌리티를 실현하고 있습니다.CO는 또한 결과 트랜잭션 스케줄(^[1]이력) 속성의 이름으로, 1988년에 동적 원자성이라는 이름으로 정의되었습니다.CO 준거 스케줄에서는 트랜잭션의 커밋 이벤트의 시간순서는 각 트랜잭션의 우선순위와 양립할 수 있다.CO는 다양한 동시성 제어 메커니즘을 사용할 수 있는 데이터베이스 시스템 집합 전체에 걸쳐 글로벌시리얼라이제빌리티(모듈러형 시리얼라이제빌리티)를 실현하기 위한 다양한 시리얼라이제이션과 효과적인 수단(신뢰성, 고성능, 분산성, 확장성)의 광범위한 특수한 케이스입니다(CO는 각 시스템의 시리얼라이제빌리티를 준수시킵니다).(아직은 없습니다.

CO에 준거하지 않는 각 데이터베이스 시스템은 CO 컴포넌트(commitment order cordinator: COCO)로 증강됩니다.CO컴포넌트는 데이터 액세스나 다른 트랜잭션 조작의 간섭 없이 CO컴플라이언스를 위한 커밋 이벤트를 명령합니다.이와 같이 CO는 멀티 데이터베이스 시스템 및 기타 트랜잭션 객체의 글로벌 동시성 제어(및 분산 동시성 제어)에 중요한 글로벌 직렬화(및 분산 동시성 제어)를 위한 낮은 오버헤드의 일반 솔루션을 제공합니다(예: 클라우드 컴퓨팅, 그리드 컴퓨팅 및 네트워크 내).마트폰)을 클릭합니다.ACP(Atomic Commitment Protocol, 모든 유형의 ACP)는 솔루션의 기본 부분으로, 충돌(우선순위, 시리얼라이제빌리티) 그래프에서 글로벌 사이클을 깨기 위해 사용됩니다.CO는 관련된 데이터베이스 시스템이 아토믹 커밋 프로토콜(수정되지 않음) 메시지를 넘어 동시성 제어 정보를 공유하지 않고 트랜잭션이 글로벌인지 로컬인지(데이터베이스 시스템이 자율적임)에 대한 지식이 없는 경우 글로벌 직렬성을 보장하는 가장 일반적인 속성(필요한 조건)입니다.따라서 CO(바리안트 포함)는 로컬 동시성 제어 정보(로컬 우선 관계, 잠금, 타임스탬프, 티켓 등)의 일반적인 배포가 필요하지 않은 유일한 일반적인 기술입니다.일반적인 Strong Strict Two-phase Locking(SS2PL) 속성을 일반화합니다.이 속성은 2단계 커밋 프로토콜(2PC)과 결합하여 (SS2PL 기반) 데이터베이스 시스템 전체에서 글로벌시리얼라이제빌리티를 실현하기 위한 사실상의 표준입니다.그 결과 CO 준거 데이터베이스 시스템(동시 제어 타입이 다른 것)은 글로벌시리얼라이저빌리티를 위해 이러한 SS2PL 기반 솔루션에 투과적으로 가입할 수 있습니다.

또한 잠금 기반 글로벌 교착상태는 CO 기반 다중 데이터베이스 환경에서 자동으로 해결되며, 이는 중요한 부수적 이점(완전 SS2PL 기반 환경의 특수한 경우 포함, SS2PL에 대해서는 이전에 눈치채지 못했던 사실)이다.

또한 엄격성과 CO의 교차점인 엄격한 커밋 오더(SCO; Raz 1991c)는 읽기/쓰기 경합(쓰기/읽기/쓰기 경합에 대한 동일한 블록 동작)이 발생할 때마다 SS2PL보다 뛰어난 퍼포먼스(평균 트랜잭션 완료 시간 단축 및 트랜잭션 스루풋 향상)를 제공합니다.비교표오버헤드 잠금).SCO의 장점은 특히 잠금 경합 시입니다.엄격성을 통해 SS2PL과 SCO 모두 동일한 효과적인 데이터베이스 복구 메커니즘을 사용할 수 있습니다.

CO에는 확장 CO(ECO; Raz 1993a)와 다중 버전 CO(MVCO; Raz 1993b)의 두 가지 주요 일반화 변종이 있습니다.또한 로컬 동시성 제어 정보 배포 없이 글로벌시리얼라이제이션이 가능하며 관련된 동시성 제어와 조합할 수 있으며 낙관적인 (비블로킹) 구현이 가능합니다.둘 다 CO 제약을 완화하고 더 나은 동시성과 성능을 달성하기 위해 추가 정보를 사용합니다.투표 순서(VO 또는 Generalized CO(GCO; Generalized CO); Raz 2009)는 CO 및 CO의 모든 변종을 위한 컨테이너 스케줄 세트(속성) 및 기법입니다.로컬 VO는 ACP 참가자가 동시성 제어 정보(일반화된 자율성 속성)를 공유하지 않는 경우 글로벌시리얼라이제빌리티를 보증하기 위해 필요합니다.CO와 CO의 변형은 서로 투명하게 상호 운용되며, 서로 다른 변형으로 혼합된 이기종 환경에서 글로벌 직렬화와 자동 글로벌 교착 상태 해결을 보장합니다.

개요

커밋 오더(CO; Raz 1990, 1992, 1994, 2009) 스케줄 속성은 동적 원자성(1988년부터^[1]), 커밋 오더(commit order), 커밋 오더(commit order serializability), 강력한 회복성(1991년부터)이라고도 불립니다.후자는 CO가 복구 가능성과 비교할 수 없는 이름이고, "strong"이라는 용어는 특별한 경우를 의미하기 때문에 잘못된 이름입니다.즉, 상당한 회수가능성 자산이 반드시 CO 속성을 가지고 있는 것은 아니며 그 반대의 경우도 마찬가지이다.

2009년에 CO는 이전에 알려진 (1980년대 이후) 3가지 주요 방법인 잠금, 타임스탬프 순서 부여 및 시리얼라이제이션 그래프 테스트와 함께 주요 동시성 제어 방법으로 특징지어졌으며 다양한 동시성 ^[2]제어 메커니즘을 사용하는 시스템의 상호 운용성을 가능하게 했습니다.

일반적으로 통신 네트워크에 분산되어 있는 페더레이션 데이터베이스 시스템 또는 기타 느슨하게 정의된 멀티데이터베이스 시스템에서 트랜잭션은 여러 개의 분산형 데이터베이스에 걸쳐 있습니다.이러한 시스템에 글로벌시리얼라이제빌리티를 적용하는 것은 문제가 있습니다.단일 데이터베이스의 모든 로컬 스케줄이 아직 시리얼 가능하더라도 시스템 전체의 글로벌 스케줄이 시리얼 가능하지는 않습니다.충돌 시리얼라이저빌리티에 도달하기 위해 데이터베이스 간에 충돌 정보가 대량으로 교환되면 주로 컴퓨터와 통신 지연 때문에 허용할 수 없는 성능이 저하될 수 있습니다.글로벌 시리얼라이제빌리티를 효과적으로 달성하는 문제는 1991년 CO의 발명가 Yoav Raz가 CO를 공개하기 전까지 해결되지 않은 것으로 특징지어졌습니다(Raz 1991a, 글로벌 시리얼라이제빌리티도 참조).

CO를 적용하는 것은 각 데이터베이스(또는 다른 트랜잭션 오브젝트)에서 CO를 로컬로 적용하기 때문에 분산 시스템에서 경합 시리얼라이제빌리티를 글로벌하게 적용하는 효과적인 방법입니다.각 데이터베이스는 다른 유형의 동시성 제어 메커니즘을 사용할 수 있습니다.이미 경합하는 시리얼라이제빌리티를 제공하고 있는 로컬메커니즘에서는 CO를 로컬로 적용해도 다른 중단은 발생하지 않습니다.이는 CO를 로컬로 적용해도 메커니즘의 데이터액세스 스케줄링 전략에 영향을 주지 않기 때문입니다(이 스케줄에 따라 시리얼라이제빌리티에 관련된 중단이 결정됩니다).이러한 메커니즘에서는 일반적으로 중단이 고려되지 않습니다.ts 또는 그 순서).CO 솔루션은 원자성에 도달하기 위해 각 분산 트랜잭션에 의해 이미 필요한 (수정되지 않은) 원자 약속 프로토콜 메시지만 사용하기 때문에 통신 오버헤드가 필요하지 않습니다.아토믹 커밋 프로토콜은 분산 CO 알고리즘의 중심 역할을 합니다.이 알고리즘은 글로벌컨플릭트그래프에서 글로벌사이클(2개 이상의 데이터베이스에 걸친 사이클)을 끊음으로써 글로벌하게 CO를 강제합니다.CO, CO의 특수한 경우 및 그 일반화는 상호 운용이 가능하며 글로벌 시리얼라이제빌리티를 달성함과 동시에 서로 다른 동시성 제어 메커니즘을 가진 객체로 구성된 단일 이기종 분산 환경에서 투명하게 함께 이용됩니다.따라서 커밋 오더(특별한 케이스 포함)와 그 일반화(아래의 CO 바리안트 참조)는 멀티데이터베이스 시스템의 이종환경에서 글로벌 시리얼라이제빌리티를 보증하기 위한 범용 고성능 완전 분산 솔루션(중앙처리 컴포넌트 또는 중앙데이터 구조 불필요)을 제공합니다.ems 및 기타 여러 트랜잭션 객체(트랜잭션 프로세스 프레임워크, 클라우드 컴퓨팅 및 그리드 컴퓨팅 내 등 트랜잭션에 의해서만 액세스 및 변경된 상태를 가진 객체)CO 솔루션은 성능에 부정적인 영향을 미치지 않고 네트워크 크기와 데이터베이스 수에 따라 확장됩니다(단일 분산 트랜잭션의 통계(예: 단일 트랜잭션과 관련된 평균 데이터베이스 수)는 변경되지 않는다고 가정합니다).

멀티코어 프로세서의 보급에 따라 Optimistic CO(OCO)도 소프트웨어 트랜잭션 메모리의 시리얼라이저빌리티를 실현하기 위해 점점 더 활용되고 있으며, 이미 "커밋 순서"를 이용한 수많은 STM 문서와 특허가 공개되어 있습니다(예^[3]: Zhang 등).

글로벌 시리얼라이저빌리티를 위한 커밋 오더

CO의 일반적인 특성화

Commitment Ordering(CO; 커밋오더)은 conflict serializability의 특수한 경우입니다.CO는 비블로킹메커니즘을 사용하여 강제할 수 있습니다(각 트랜잭션은 데이터 액세스를 차단하지 않고 작업을 완료할 수 있으므로 최적의 동시성 제어가 가능하지만 커밋은 차단될 수 있습니다).CO 스케줄에서 트랜잭션의 커밋 이벤트의 (부분적) 우선순위는 서로 상충하는 액세스 조작(통상 읽기 및 쓰기(insert/modify/delete)에 의해 유도되는 (방향) 충돌 그래프(우선순위 그래프, serializability 그래프)의 각 트랜잭션의 (부분적) 우선순위에 대응한다.CO는 교환적이지 않은 경우 충돌하는 상위 수준의 운영에도 적용되며 다중 버전 데이터에 대한 운영 간의 충돌에도 적용됩니다.

정의: 커밋 순서

${\displaystyle {T1\mathrm{}}_{}}$ $({$},$T_{$2})를$$ 스케줄 내의 2개의 커밋된 트랜잭션으로 $합니다{\displaystyle {}_{}}$.${\displaystyle {이\mathrm{}}_{}}$ 경우 T2$({$$displaystyle$ T_${2$$})$는 $({$ $T_1})$과 경합합니다(${\displaystyle {T1\mathrm{}}_{}}$ ${$$displaystyle T_{2$}}).$$스케줄에는 Commitment Ordering(CO; 커밋 순서) 속성이 있습니다.이러한 $트랜잭션{\displaystyle {}_{}}$ 2개마다 ${\displaystyle {T1\mathrm{}}_{}}$$({$이 커밋되기 $전$에 T2$({$})가$$$$ 커밋됩니다.

커밋 결정 이벤트는 서로 다른 프로세스가 커밋 또는 중단 여부에 대한 합의에 도달할 필요가 있는 경우 로컬 커밋 메커니즘 또는 원자 커밋 프로토콜에 의해 생성됩니다.프로토콜은 배포되거나 중앙 집중화될 수 있습니다.트랜잭션은 커밋 부분 순서가 허용하는 경우(경합하는 작업이 없는 경우) 동시에 커밋될 수 있습니다.서로 다른 충돌하는 연산이 동일한 트랜잭션의 서로 다른 부분 순서를 유발한다고 가정합니다.이 경우 충돌 그래프에 사이클이 있으며 사이클의 모든 트랜잭션이 커밋되면 스케줄이 시리얼라이제빌리티를 위반합니다.이 경우 커밋이벤트의 부분 순서를 찾을 수 없습니다.따라서 트랜잭션을 중단하여 충돌 그래프의 주기를 끊어야 합니다.그러나 트랜잭션의 우선순위 부분 순서에 따라 커밋 이벤트를 적절히 지연시킴으로써 트랜잭션을 중단하지 않고 충돌할 수 있는 일정을 CO로 만들 수 있습니다.

CO의 실행 자체는 동시성 제어 메커니즘으로는 불충분합니다.이는 CO에는 복구 가능성 속성이 없기 때문입니다.또한 지원되어야 합니다.

분산 CO 알고리즘

완전히 분산된 글로벌 커밋 순서 부여 알고리즘이 존재하며, 참여하는 각 데이터베이스의 로컬 CO를 사용하며, 필요한 것은 (변경되지 않음)뿐입니다.더 이상의 통신이 없는 원자성 커밋 프로토콜 메시지입니다.분산 알고리즘은 로컬(각 데이터베이스에 대한) CO 알고리즘 프로세스와 원자 커밋 프로토콜(완전 분산 가능)의 조합입니다.아토믹 커밋 프로토콜은 각 분산 트랜잭션의 원자성을 강제하기 위해 필수적입니다(커밋 또는 중단 여부를 결정하기 위해. 이 절차는 항상 동시성 제어 및 CO와 독립적으로 분산 트랜잭션에 대해 수행됩니다).원자 커밋 프로토콜의 일반적인 예는 많은 유형의 시스템 장애에 대해 탄력적인 2단계 커밋 프로토콜입니다.신뢰할 수 있는 환경에서, 또는 프로세스가 일반적으로 함께 고장날 때(예를 들어, 동일한 집적회로에서) 원자공약을 위한 보다 단순한 프로토콜이 사용될 수 있다(예를 들어, 임의적이지만 알려진 특별한 참가자, 즉 거래의 조정자, 즉 단상 코드의 일종과의 분산 트랜잭션 참여 프로세스의 단순한 핸드쉐이크).mmit protocol).원자적 커밋 프로토콜은 이러한 참여자에 걸쳐 분산된(글로벌) 트랜잭션을 커밋할지 또는 중단할지 여부에 대해 참여자 간에 합의에 도달합니다.각 프로토콜의 필수 단계는 각 참가자에 의한 (명시적 또는 암묵적) 예스 투표이며, 이는 투표 참가자가 커밋 또는 중단 프로토콜의 결정에 따라야 할 의무를 의미한다.그렇지 않으면 참여자는 명시적으로 NO 투표로 일방적으로 거래를 중단할 수 있습니다.프로토콜은 모든 참가자로부터 예(YES) 투표를 받은 경우에만 트랜잭션을 커밋합니다(따라서 누락된 투표는 일반적으로 NO로 간주됩니다.그렇지 않으면 프로토콜이 트랜잭션을 중단합니다.다양한 아토믹 커밋 프로토콜은 서로 다른 컴퓨팅 환경 장애 상황 및 서로 다른 상황에서 필요한 작업량 및 기타 컴퓨팅 리소스 처리 능력에서 차이가 있을 뿐입니다.

글로벌 시리얼라이제빌리티를 위한 전체 CO 솔루션은 분산 트랜잭션에 대한 투표 누락 시 원자 커밋 프로토콜이 결국 이 트랜잭션을 중단한다는 사실에 기초한다.

글로벌 CO의 실시

각 데이터베이스 시스템에서 로컬 CO 알고리즘은 해당 데이터베이스에 필요한 커밋 순서를 결정합니다.위의 CO의 특성에 따라 이 순서는 트랜잭션의 로컬 우선순위에 따라 달라집니다.이 순서는 로컬 데이터 액세스스케줄링 메커니즘에 의해 결정됩니다.따라서 원자력 커밋 프로토콜의 YES 투표는 각 분산 트랜잭션에 대해 예약됩니다(다음에서 "투표"는 YES 투표를 의미합니다).두 트랜잭션 사이에 우선 순위 관계(충돌)가 존재한다고 가정합니다.이 경우 원자적 커밋 프로토콜에 의한 커밋 순서 위반 가능성을 방지하기 위해 첫 번째 커밋이 완료(커밋 또는 중단)되기 전에 두 번째 커밋은 투표되지 않습니다.이는 프로토콜에 의한 커밋 순서가 투표 순서와 반드시 동일하지는 않기 때문에 발생할 수 있습니다.우선순위 관계가 존재하지 않는 경우는, 양쪽 모두를 동시에 투표할 수 있습니다.이 투표 순서 지정 전략은 원자 약속 프로토콜이 약속 순서를 유지하도록 보장하며, 이는 글로벌 CO(및 데이터베이스의 로컬 CO.가 없으면 글로벌 CO와 로컬 CO(각 데이터베이스가 CO에 준거한다는 것을 의미하는 속성)를 위반할 수 있음)를 보증하기 위한 필수 조건입니다.

그러나 데이터베이스 시스템은 독립적으로 트랜잭션을 스케줄링하기 때문에 두 개 이상의 데이터베이스에 있는 트랜잭션의 우선순위가 호환되지 않을 수 있습니다(각 로컬 부분 순서를 함께 포함할 수 있는 글로벌 부분 순서는 존재하지 않습니다).CO의 경우 우선 순서는 커밋 순서이기도 합니다.동일한 분산 트랜잭션에 참여하는 데이터베이스가 해당 트랜잭션에 대해 호환되는 로컬 우선 순위를 가지고 있지 않은 경우(필요한 통신이 대량으로 이루어지며 허용할 수 없을 정도로 성능이 저하되기 때문에 일반적으로 데이터베이스 시스템 간의 조정은 존재하지 않습니다) 트랜잭션이 해당 트랜잭션에 상주함을 의미합니다.글로벌 컨플릭트그래프의 글로벌사이클(2개 이상의 데이터베이스를 참조).이 경우, 원자력 커밋 프로토콜은 해당 트랜잭션을 커밋하는 데 필요한 모든 표를 수집하지 못합니다.상기 투표 순서 전략에 따르면 적어도 하나의 데이터베이스는 자신의 약속(우선순위) 순서에 따라 해당 트랜잭션에 대한 투표를 무기한 연기합니다.이는 다른 순서가 있는 다른 데이터베이스에 의해 무기한 지연된 글로벌 사이클의 이전 트랜잭션이 완료될 때까지 대기하기 때문입니다.이는 해당 주기의 데이터베이스가 포함된 투표 교착 상태를 의미합니다.결과적으로, 프로토콜은 결국 이 글로벌 사이클에서 교착 상태인 트랜잭션을 중단합니다. 이러한 트랜잭션은 각각 최소 한 명의 참가자의 투표가 누락되기 때문입니다.중단되는 사이클에 대한 특정 트랜잭션 선택은 원자력 커밋 프로토콜의 중단 정책에 따라 달라집니다(타임아웃 메커니즘이 일반적이지만 사이클당 필요한 중단이 여러 개 발생할 수 있습니다. 불필요한 중단 방지와 중단 시간 단축은 모두 CO 전용 중단 메커니즘에 의해 달성될 수 있습니다).이러한 중단은 분산 트랜잭션과 관련된 글로벌 주기를 중단합니다.교착 상태에 있는 트랜잭션과 교착 상태에 있는(따라서 차단된) 다른 트랜잭션 모두 자유롭게 투표할 수 있습니다.투표 데드록과 관련된 각 데이터베이스는 교착 상태에 빠진 트랜잭션(일반적으로 거의 모든 미결 트랜잭션)과 충돌하지 않는 트랜잭션에 대해 정기적으로 투표를 계속한다는 점에 유의할 필요가 있습니다.따라서 로컬(부분) 커밋 순서가 호환되지 않는 경우, 원자력 커밋 프로토콜이 비호환의 원인이 되는 트랜잭션을 중단함으로써 자동으로 해결되므로 조치가 필요하지 않습니다.이는 상기의 투표 순서 전략이 글로벌 CO를 보증하기 위한 충분한 조건임을 의미한다.

다음과 같이 결론을 내립니다.

• 글로벌 CO 집행 정리를 위한 투표 순서 전략

T2({${\displaystyle {displaystyle\mathrm{}}_{}}$ $T_{1$$},$ ${2$$})$가 글로벌하고 $({$ $$${\displaystyle {}_{}}$({displaystyle T_1}, T_{1}, $({$ T_1$})$과 충돌하도록 $로컬$ $트랜잭션$에 CO를 강제하는 데이터베이스 시스템에서 미결정(커밋 또는 중단하지 않음) 트랜잭션을 $설정$합니다.$({$그 후, 멀티데이터베이스 환경에서 이러한 데이터베이스 시스템 ${\displaystyle {각각}_{}}$에서$$T2({$displaystyle T_$${$2})의 커밋이 $결정$되기 ${\displaystyle {전}_{}}$에$T1$({$displaystyle T_{$1})을 종료(커밋 또는 중단)하는 것은 글로벌 CO(Globa 보증 조건)를 보증하기 위한 필요충분한 조건이다.l CO, CO가 없으면 위반될 수 있습니다.)

코멘트:

1. 글로벌 CO를 강제하는 투표 순서 전략은 (Raz 1992년)에서는 C ${\displaystyle {}^{}}$3 C(\$displaystyle CD^{3$}C$$$)$라고 $합니다{\displaystyle }$.
2. 글로벌 스케줄의 로컬 CO 속성은 각 데이터베이스가 CO에 준거하고 있음을 의미합니다.필연성 논의에서 상기 부분은 글로벌 거래가 있을 때 '글로벌 CO'를 '로컬 CO'로 대체할 때도 이 정리가 성립한다는 것을 직결한다.이는 로컬 CO가 보증된 경우에만 글로벌 CO가 보증된다는 것을 의미합니다(글로벌컨플릭트시리얼라이저빌리티 및 로컬컨플릭트시리얼라이저빌리티에 대해서는 사실이 아닙니다.글로벌은 로컬을 의미하지만 그 반대는 아닙니다).

글로벌 CO는 글로벌시리얼라이제빌리티를 의미합니다.

글로벌 CO 알고리즘은 로컬 트랜잭션의 커밋을 주문함으로써(이하 '로컬) 각 참여 데이터베이스 시스템에서) CO를 강제하고(글로벌 트랜잭션의 경우)' 위의 정리에서의 투표 순서 전략을 강제하는 것으로 구성됩니다.

글로벌 사이클에 의한 투표 데드록의 정확한 특성

투표 교착 상태에 의한 위의 글로벌 사이클 제거 프로세스는 다음과 같은 관찰을 통해 자세히 설명할 수 있다.

첫 번째, 단순성을 위해 모든 트랜잭션이 Ready-to-commit 상태에 도달하고 적어도1개의 데이터베이스에 의해 폴링되는 것을 전제로 합니다(이는 잠금에 의한 블로킹이 발생하지 않음을 의미합니다).첫 번째 트랜잭션이 두 번째 트랜잭션(대기 그래프의 기존 에지 방향과 반대)의 커밋 투표를 차단하는 경우 트랜잭션을 노드로 하고 트랜잭션을 두 번째 트랜잭션에서 두 번째 트랜잭션으로 지정하는 방향 그래프로 "투표 대기" 그래프를 정의합니다.이러한 차단은 두 번째 트랜잭션이 첫 번째 트랜잭션과 충돌하는 경우에만 발생합니다(위 참조).따라서 이 "투표에 대한 대기" 그래프는 글로벌 충돌 그래프와 동일합니다."투표에 대한 대기" 그래프의 주기는 투표의 교착 상태를 의미합니다.따라서 충돌 그래프에 주기가 있을 경우 투표에 교착 상태가 발생합니다.로컬 시리얼화 메커니즘에 의해 로컬사이클(단일 데이터베이스에 접속)이 없어집니다.결과적으로, 글로벌 사이클만이 남습니다.이러한 사이클은, 각 투표가 누락(블록)된 교착 상태의 트랜잭션을 중단하면, 원자 커밋 프로토콜에 의해서 제거됩니다.

다음으로 로컬 커밋도 취급됩니다.CO를 강제할 때 로컬트랜잭션의 통상적인 로컬커밋을 대기하면 로컬커밋과 충돌 시 다른 트랜잭션의 투표가 차단될 수 있습니다.또한 글로벌트랜잭션의 상황도 위의 가정을 단순화하지 않으면 변경되지 않습니다.최종 결과는 로컬 트랜잭션에 대한 로컬 커밋에서도 동일하며, 로컬 트랜잭션에 대한 아토믹 커밋에서는 투표하지 않습니다.

마지막으로 잠금에 의한 차단(지금까지 제외)을 고려할 필요가 있습니다.잠금은 충돌하는 작업을 차단하고 충돌이 발생하는 것을 방지합니다.트랜잭션이 종료된 후에만 잠금이 해제된다고 가정합니다.이 경우 투표 또는 로컬 커밋을 직접 차단하는 것과 같은 효과로 다른 거래(현재 준비 상태가 되지 않음)의 투표 또는 로컬 커밋 중 하나를 간접적으로 차단할 수 있습니다.충돌 그래프에 사이클이 생성되는 것은 잠금에 의한 블록이 에지로도 표시되는 경우뿐입니다.이렇게 추가된 에지가 잠금별 차단 이벤트를 나타내면서 충돌 그래프는 증강 충돌 그래프가 되고 있습니다.

• 정의: 확장 충돌 그래프

증강된 충돌 그래프는 모서리가 추가된 충돌 그래프입니다.다음 두 가지 조건이 충족될 경우 원래 가장자리 외에 방향 가장자리가 $트랜잭션{\displaystyle {}_{}}$ $({$에서 $트랜잭션{\displaystyle {}_{}}$ $({$까지 존재합니다.

1. $({$ T_${2})$는 $({$에 $의해{\displaystyle {}_{}}$ 적용된 데이터 액세스 잠금에 의해 차단됩니다(블로킹은 $({$ T_${$$2}})$와$$T1({$displaystyle T_1})$의 경합이 발생하지 않도록 하며 일반 경합 그래프에 엣지가 있습니다).
2. 이 블로킹은 $({$})이$$ 종료될 $때$까지 정지하지 않습니다(커밋 또는 중단.잠금 기반 CO의 경우 모두 해당).

그래프는 (일반) 충돌 그래프와 (역방향 에지, 일반) 대기 그래프의 결합으로 정의할 수도 있습니다.

코멘트:

1. 여기서는 구체화된 충돌에 대해서만 가장자리가 있는 일반 충돌 그래프와 달리 구체화된 충돌과 비실체화된 충돌은 모두 가장자리로 표시됩니다.
2. 모든 새 가장자리는 대기 그래프의 모든 (기존과 반대되는) 가장자리입니다.대기 그래프는 구체화되지 않은 충돌의 그래프로 정의할 수도 있습니다.공통규칙에 따르면 컨플릭트 그래프 내의 엣지 방향은 컨플릭트 동작 간의 시간순서를 정의하며, 이는 대기 그래프 내의 엣지에 의해 정의된 시간순서와 반대된다.
3. 이러한 글로벌 그래프는 모든 (역방향 에지) 일반 로컬 대기 그래프를 포함하며 잠금 기반 글로벌 주기(로컬 그래프에는 존재하지 않음)를 포함할 수도 있습니다.예를 들어 글로벌 사이클의 모든 데이터베이스가 SS2PL 기반인 경우 관련된 모든 투표 차단 상황은 잠금으로 인해 발생합니다(이것은 데이터베이스 연구 문헌에서 다루어진 고전적이고 아마도 유일한 글로벌 교착 상황입니다).이는 관련된 각 데이터베이스가 사이클의 일부를 작성하지만 전체 사이클이 로컬 대기 그래프에 존재하지 않는 글로벌 교착 상태입니다.

CO가 존재하는 경우 증강된 충돌 그래프는 실제로 (역방향 에지) 로컬 커밋 및 투표 대기 그래프입니다.첫 번째 트랜잭션(글로벌한 경우)에서 첫 번째 트랜잭션(글로벌한 경우)이 종료되기를 기다리는 경우 또는 첫 번째 트랜잭션(글로벌한 경우)에서 첫 번째 트랜잭션(로컬 또는 글로벌한 경우)까지 에지가 존재합니다.이 그래프의 모든 글로벌사이클(2개 이상의 데이터베이스에 걸쳐)은 투표 데드록을 생성합니다.그래프의 전역 주기는 투표 교착 상태에 대한 완전한 특성을 제공하며 구체화된 충돌과 비실체화 충돌의 조합을 포함할 수 있다.구체화된 충돌의 주기만 일반 충돌 그래프의 주기이며 연속성에 영향을 미칩니다.사이클에서 하나 이상의 (잠금 관련) 비실체화 충돌이 발생하면 일반 충돌 그래프에서 해당 충돌이 사이클이 되지 못하고 잠금 관련 교착 상태가 됩니다.글로벌 시리얼성을 유지하고 데이터 액세스 잠금을 수반하는 글로벌 교착 상태를 해결하려면 모든 글로벌 사이클(투표-데드록)을 해제(해결)해야 합니다.사실 그들은 표결 교착 상태에서 표결 누락으로 인해 모두 원자력 약속 의정서에 의해 깨졌다.

코멘트:이 관찰은 또한 두 글로벌 트랜잭션 사이에 순서 관계(그래프 경로)가 존재하는 경우 글로벌 트랜잭션의 투표 순서는 투표 차단과 함께 충돌 그래프 순서를 따라야 한다는 것을 설명합니다.로컬 트랜잭션은 투표되지 않으며 충돌 시 해당(로컬) 커밋이 차단되지 않습니다.그 결과, ECO에서도 투표에 의한 데드록의 상황이나 글로벌 사이클의 배제 프로세스가 발생합니다.

투표 데드록 상황은 다음과 같이 요약할 수 있습니다.

• CO 투표-데드록 정리

멀티데이터베이스 환경에 CO 준거(로컬 사이클을 배제) 데이터베이스 시스템을 포함시켜 각 글로벌 CO를 강제합니다(위 정리의 조건을 사용).글로벌 확장 충돌 그래프에 글로벌사이클(2개 이상의 데이터베이스)이 존재하는 경우에만 투표 데드록이 발생합니다(데이터 액세스 잠금에 의한 블록도 에지로 표시됩니다).사이클이 중단되지 않았다고 가정합니다.이 경우, 모든 글로벌 거래는 각각의 투표 데드록과 관련된다.최종적으로는 각각 투표가 차단됩니다(데이터 액세스 잠금에 의해 직접 또는 간접적으로). 로컬 트랜잭션이 사이클에 존재할 경우 최종적으로 (로컬) 커밋이 차단됩니다.

코멘트: 드물게 (차단된 투표가 누락됨으로써) 투표 교착 상태가 발생할 수 있으며, 이러한 거래에 관련된 데이터베이스 시스템의 관련 사이클에 대한 투표가 이루어지지 않을 수 있습니다.이 문제는 로컬 하위 트랜잭션이 멀티 스레드일 때 발생할 수 있습니다.이러한 드문 사건의 가장 높은 확률의 인스턴스에는 두 개의 반대 사이클에 두 개의 트랜잭션이 동시에 포함됩니다.이러한 글로벌 사이클(데드록)은 로컬로 해결되는 로컬사이클과 중복되며 일반적으로 원자적인 약속 없이 로컬메커니즘에 의해 해결됩니다.형식적으로는 글로벌 사이클이기도 하지만 실제로는 로컬(로컬 사이클의 범위가 글로벌한 것을 생성한다.이를 확인하려면 각 글로벌 트랜잭션(노드)을 로컬 서브 트랜잭션(각각 데이터베이스로 제한되는 부분)으로 분할한다.각 로컬 서브 트랜잭션 사이에 엣지가 존재하는 경우 트랜잭션 간에 방향 에지가 존재한다.모든 에지가 같은 데이터베이스의 서브트랜잭션 간의 사이클에서 발생하는 경우 사이클은 로컬이며 그렇지 않은 경우 글로벌합니다.글로벌과 로컬은 오버랩할 수 있습니다.트랜잭션 간의 동일한 사이클은 서브트랜잭션 간의 여러 다른 사이클에서 발생할 수 있으며 로컬과 글로벌 모두일 수 있습니다).

또한 다음과 같은 잠금 기반의 특수 케이스가 결론지어진다.

• CO 잠금 기반의 글로벌 데드록 정리

CO 준거 멀티데이터베이스 시스템에서 잠금 기반의 글로벌 데드록은 적어도 1개의 데이터 액세스록(비물질화 컨플릭트) 및 2개 이상의 데이터베이스 시스템을 포함하며 글로벌 증강 컨플릭트 그래프에서 글로벌 사이클을 반영하여 투표 데드록이 발생한다.이러한 사이클은 (정규적인) 글로벌컨플릭트 그래프의 사이클이 아닙니다(이는 구체화된 컨플릭트만을 반영하므로 이러한 사이클은 시리얼라이제이션에 영향을 주지 않습니다).

코멘트:

1. 데이터 액세스 잠금이 아닌 사이클 내의 블로킹(엣지)은 투표 또는 로컬 커밋 중 하나를 직접 차단합니다.이 잠금 기반 유형을 포함하여 모든 투표 데드록이 해결됩니다(대부분의 경우 Atomic commitment에 의해 해결됩니다.상기의 코멘트를 참조해 주세요.
2. 잠금 기반의 글로벌 데드록은 완전히 SS2PL 기반의 분산 환경(CO 기반의 특수한 경우)에서도 생성할 수 있습니다.모든 투표 차단(및 투표 잠금)은 데이터 액세스 잠금이 원인입니다.많은 연구 논문들이 이러한 세계적인 교착 상태를 해결하기 위해 수년간 다루어 왔지만, (2009년 현재) 원자적인 헌신이 자동으로 해결된다는 것을 알아차리는 것은 알려진 바 없다.이러한 자동 해상도는 기존의 모든 SS2PL 기반 멀티데이터베이스 시스템에서 인식되지 않고 정기적으로 발생하며, 전용 해상도 메커니즘을 우회하는 경우가 많습니다.

투표용 데드록은 분산 CO 운영의 핵심이다.

글로벌 사이클 제거(여기서는 원자적 약속에 의한 투표-잠금 해결) 및 결과적으로 중단된 트랜잭션의 재실행은 동시성 제어에 관계없이 시간이 걸립니다.데이터베이스가 트랜잭션을 독립적으로 스케줄 하는 경우 글로벌 사이클은 피할 수 없습니다(로컬 SS2PL에서 생성되는 사이클/데드록과 완전히 유사합니다.배포에서는 트랜잭션 또는 운영 스케줄 조정이 자율성을 위반하고 일반적으로 상당한 성능 저하가 발생합니다).그러나 대부분의 경우 데이터베이스 및 트랜잭션 설계 가이드라인을 구현하여 글로벌 트랜잭션과 관련된 충돌 수를 줄임으로써 이러한 가능성을 매우 낮출 수 있습니다.이는 주로 핫스팟(접근 빈도가 높은 데이터베이스 객체)을 적절하게 처리하고 가능한 한 정류성을 사용하여 충돌을 회피함으로써 이루어집니다(예를 들어 재무에서처럼 카운터, 특히 핫스팟인 다중 트랜잭션 누적 카운터를 광범위하게 사용하는 경우).

원자 확약 프로토콜은 데이터베이스 동시성 제어를 고려하지 않고 원자성을 달성하도록 의도되고 설계됩니다.이들은 누락된 표를 감지하거나 휴리스틱하게 발견했을 때(예를 들어, 타임아웃에 의해; 때로는 실수로, 불필요하게) 중단되며, 일반적으로 글로벌 주기를 인식하지 못한다.이러한 프로토콜은 CO(아래 CO의 변형 포함)에 대해 특히 강화되어 불필요한 중단을 방지하고 글로벌 확장 충돌 그래프에서 글로벌 주기를 깨기 위해 사용되는 중단을 가속화할 수 있습니다(컴퓨팅 리소스의 트랜잭션 종료 및 일반적으로 잠긴 데이터에 대한 이전 릴리스로 성능을 향상시킵니다).예를 들어 타임아웃 이외의 기존 잠금 기반의 글로벌 데드록 검출 방식을 일반화하여 데이터 액세스 차단 외에 로컬커밋 및 투표 직접 블로킹을 검토할 수도 있습니다.이러한 메커니즘에 대한 가능한 타협은 가장 빈번하고 비교적 간단한 길이2 글로벌사이클을 효과적으로 검출 및 차단하고 검출되지 않은 빈도가 훨씬 낮은 긴 사이클에 타임아웃을 사용하는 것입니다.

CO의 로컬 적용

커밋 순서는 전용 CO 알고리즘 또는 특수한 CO 경우를 제공하는 알고리즘/프로토콜에 의해 로컬(단일 데이터베이스 내)로 강제할 수 있습니다.CO 스케줄을 생성하는 데이터베이스 시스템에서 광범위하게 사용되는 중요한 프로토콜은 강력한 2단계 잠금 프로토콜입니다(SS2PL: "트랜잭션이 커밋되거나 중단된 후에만 트랜잭션의 잠금을 해제한다."; 아래 참조).SS2PL은 2PL과 엄격성의 교집합 중 적절한 부분집합입니다.

범용 로컬 CO 알고리즘

범용 로컬 CO 알고리즘(Raz 1992; Algorithm 4.1)은 CO 속성을 정확하게 적용하는 구현 세부 정보와 독립적인 알고리즘입니다.데이터 액세스(비블로킹)는 차단되지 않으며 트랜잭션을 커밋할 때 특정 트랜잭션 세트를 중단하는 것으로 구성됩니다(필요한 경우에만).로컬에서 실행되어 향후 시리얼라이제빌리티 위반의 원인이 될 가능성이 있는(커밋 또는 중단되지 않은) 기타 미결정 트랜잭션의 최소 세트를 중단합니다(나중에 컨플릭트그래프에서 커밋된 트랜잭션의 사이클을 생성할 수 있습니다).이것은 커밋된 트랜잭션의 ABORT 세트입니다.T no를 커밋한 후입니다.커밋 시 ABTOB 내의 트랜잭션을 커밋할 수 있으며 모든 트랜잭션이 중단됩니다).이 집합은 커밋된 트랜잭션에 대한 충돌 그래프에 지정된 가장자리가 있는 모든 미결정 트랜잭션으로 구성됩니다.이 세트의 크기는 트랜잭션이 커밋되기를 기다리고 있을 때(Ready 상태: 처리가 종료됨)에는 증가할 수 없으며 일반적으로 트랜잭션이 결정될 때 감소합니다.따라서 해당 트랜잭션을 완료하기 위해 실시간 제약이 존재하지 않는 한 해당 트랜잭션을 커밋하고 이 집합의 크기를 줄이는 것이 좋습니다.다른 시리얼화 메커니즘이 로컬로 존재하는 경우(로컬컨플릭트그래프 내의 사이클을 배제) 또는 해당 트랜잭션과 관련된 사이클이 존재하지 않는 경우 세트는 최종적으로 비워지고 세트멤버를 중단할 필요가 없습니다.그렇지 않으면 로컬사이클 트랜잭션으로 세트가 안정되고 사이클을 중단하기 위해 세트멤버가 중단되어야 합니다.CO 경합이 발생하면 커밋 시 블로킹이 생성되므로 증강 컨플릭트그래프(상기 참조)의 로컬사이클은 로컬커밋 데드록을 나타내며 SS2PL과 같은 데드록 해결 기법(타임아웃이나 대기 그래프 등)을 사용할 수 있습니다.적어도 1개의 비실체화 경합이 있는 증강 경합 그래프의 로컬 사이클은 잠금 기반의 교착 상태를 반영한다.위의 로컬알고리즘은 일반 로컬컨플릭트그래프가 아닌 로컬 증강 컨플릭트그래프에 적용되며 로컬시리얼라이제빌리티를 보증하는 단일 로컬사이클 제거 메커니즘인 범용 확장 로컬 CO 알고리즘으로 구성됩니다.실질적으로 추가적인 동시성 제어 메커니즘이 항상 사용되는데, 이는 단순히 복구 가능성을 적용하기 위해서도 마찬가지입니다.범용 CO 알고리즘은 다른 로컬 동시성 제어 메커니즘과 함께 실행될 경우 로컬 데이터 액세스 스케줄링 전략에 영향을 주지 않습니다.이 명령어는 커밋 순서에만 영향을 줍니다.따라서 로컬 동시성 제어 메커니즘을 조합하여 시리얼라이저빌리티 위반을 방지하기 위해 필요한 트랜잭션보다 더 많은 트랜잭션을 중단할 필요가 없습니다.CO의 순효과는 필요한 커밋 순서를 준수하기 위한 커밋이벤트(또는 분산환경에서의 투표)의 지연(단, SS2PL 등의 특수한 경우보다 지연이 많지는 않고 평균적으로 현저하게 적음)일 가능성이 있습니다.

다음과 같은 정리가 성립한다.

• 일반 국소 CO 알고리즘 정리

데이터베이스 시스템에서 단독으로 또는 동시성 제어 메커니즘과 함께 실행하는 경우

1. 범용 로컬 CO 알고리즘은 (로컬) CO(CO 준거 스케줄)를 보증합니다.
2. Generic Enhanced Local CO 알고리즘은 (로컬) CO와 (로컬) 잠금 기반의 교착 상태 해결을 모두 보장합니다.또한 (타임아웃을 사용하지 않고 실시간 트랜잭션 완료 제약이 적용되지 않는 경우) 어느 알고리즘도 필요한 최소값보다 많은 트랜잭션을 중단합니다(트랜잭션의 작업 스케줄에 따라 알고리즘 범위를 벗어남).

예:동시 프로그래밍 및 트랜잭션 메모리

동시 프로그래밍 및 트랜잭션 메모리를 참조하십시오.

멀티코어 프로세서가 보급됨에 따라 범용 로컬 CO 알고리즘의 변종도 동시 프로그래밍, 트랜잭션 메모리, 특히 "커밋 순서"에 의해 최적의 시리얼라이제빌리티를 실현하기 위해 소프트웨어 트랜잭션 메모리에 점점 더 많이 사용되고 있습니다(예를 들어 라마단 등).2009년,^[4] Zhang ^[3]등 2006년, von Parun 등 2007년^[5])CO를 이용한 수많은 관련 기사 및 특허가 이미 발표되었습니다.

구현에 관한 고려사항:커밋 오더 코디네이터(COCO)

다단계 환경에서의 데이터베이스 시스템을 상정한다.소프트웨어 아키텍처의 관점에서 범용 CO 알고리즘을 로컬로 실장하는 CO 컴포넌트인 COCO(Commitment Order Coordinator)는 (단일) 데이터베이스 시스템과 원자 커밋 프로토콜 컴포넌트(Raz 1991b) 사이의 중개자로서 쉽게 설계할 수 있다.단, COCO는 일반적으로 데이터베이스 시스템의 일부입니다.COCO의 기능은 로컬 커밋 순서에 따라 준비 완료 글로벌 트랜잭션(처리가 종료됨)을 커밋하기 위해 투표하고 데이터베이스 시스템이 중단한 트랜잭션(데이터베이스 시스템이 여러 가지 이유로 어떤 트랜잭션도 중단하기 시작할 수 있음)을 중단하기 위해 투표하며 원자적인 커밋 결정을 통과시키는 것입니다.데이터베이스 시스템에 접속합니다.로컬 트랜잭션(식별 가능한 경우)의 경우 투표가 필요하지 않습니다.커밋 순서를 결정하기 위해 COCO는 데이터 구조(예를 들어 충돌을 캡처하기 위해 잠금과 유사한 메커니즘을 사용하는 등)로서 미결정(커밋되거나 중단되지 않음) 트랜잭션의 로컬 컨플릭트 그래프(또는 잠금 교착 상태를 캡처하기 위한 로컬 증강 컨플릭트 그래프)의 최신 표현을 유지한다.데이터 액세스블로킹)을 실행합니다.COCO 컴포넌트는 데이터베이스 시스템과의 인터페이스를 통해 데이터베이스 시스템으로부터 "conflict", "ready"(처리가 종료됨, 글로벌 트랜잭션에 대한 투표 또는 로컬 트랜잭션 커밋 준비 완료) 및 "abort" 알림을 수신합니다.또한 각 글로벌 트랜잭션에 대한 원자 약속 프로토콜의 결정을 투표하고 수신하기 위해 원자 약속 프로토콜과 인터페이스합니다.결정은 적절한 커밋 순서에 따라 로컬 트랜잭션의 커밋 알림뿐만 아니라 인터페이스를 통해 COCO에서 데이터베이스 시스템으로 전달됩니다.COCO는 CO의 다른 변종(아래 참조)을 실장하거나 데이터베이스의 동시성 제어 메커니즘에서 원자적인 약속에 대한 투표 이상의 역할을 하는 경우 인터페이스를 포함하여 강화될 수 있습니다.

COCO는 또한 단일 격리된 데이터베이스 시스템에서 로컬로 CO를 보장하며, 이 시스템은 원자 확약 프로토콜과의 인터페이스가 없습니다.

CO는 자율 데이터베이스 시스템 간의 글로벌시리얼라이저빌리티에 필요한 조건입니다.

분산 트랜잭션에 참여하는 데이터베이스(즉, 단일 데이터베이스 이상에 걸친 트랜잭션)가 공유 동시성 제어 정보를 사용하지 않고 수정되지 않은 원자 약속 프로토콜 메시지(원자성 도달)를 사용한다고 가정합니다.이 경우, (현지) 커밋 오더 또는 그 일반화 변형 중 하나(아래 참조)를 유지하는 것은 글로벌 시리얼라이제빌리티를 보증하기 위한 필수 조건이다(증거 기술은 (Raz 1992)에서 확인할 수 있으며, 이에 대한 다른 증명 방법은 (Raz 1993a)에서 확인할 수 있다). 또한 충분한 조건이다.이것은 연속성과 트랜잭션의 정의에서 파생된 수학적 사실이다.즉, CO에 준거하지 않는 경우, 이 조건(원자성 커밋 프로토콜 메시지를 넘어 데이터베이스 간에 로컬 동시성 제어 정보를 공유하지 않는 조건)에서는 글로벌시리얼라이제이션이 보증되지 않습니다.원자적 커밋은 항상 필요하므로 분산 트랜잭션에 대한 최소한의 요구 사항이며, 이는 트랜잭션 정의에 의해 암시됩니다.

(Raz 1992)는 데이터베이스 자율성과 독립성을 추가 현지 지식을 사용하지 않고 이 요건을 준수하는 것으로 정의한다.

• 정의: (환율관리 기반) 자율 데이터베이스 시스템

데이터베이스 시스템은 다른 엔티티와 변경되지 않은 원자 커밋 프로토콜 메시지 이상의 동시성 제어 정보를 공유하지 않는 경우 자율적입니다.또한 동시성 제어에는 충돌을 넘어서는 추가 로컬 정보를 사용하지 않습니다(마지막 문장은 명시적으로 나타나지 않고 오히려 Raz 1992의 추가 논의에 의해 암시됩니다).

이 정의를 사용하면 다음과 같은 결론을 얻을 수 있습니다.

• CO와 글로벌 직렬화성 정리

1. 멀티베이스 환경에서 모든 Autonomous Database 시스템(또는 트랜잭션)오브젝트)의 CO 준수는 글로벌시리얼라이제빌리티를 보증하기 위한 필수 조건입니다(CO가 없으면 글로벌시리얼라이제빌리티가 침해될 수 있습니다).
2. 모든 데이터베이스 시스템에 대한 CO 컴플라이언스는 글로벌 시리얼라이제이션(serializability)을 보증하기 위한 충분한 조건입니다.

단, 위의 자율성의 정의는 예를 들어 로컬 트랜잭션(단일 데이터베이스에 연결된)을 자율 데이터베이스 시스템에 의해 식별할 수 없는 방식으로 트랜잭션이 스케줄링된다는 것을 의미합니다.이는 일부 트랜잭션 오브젝트에서는 현실적이지만 범용 데이터베이스 시스템에서는 너무 제한적이고 현실적이지 않습니다.로컬 트랜잭션을 식별할 수 있는 기능으로 자율성이 강화되면 보다 일반적인 자산인 확장 커밋 오더(ECO, 이하 참조)에 준거하여 ECO가 필수 조건이 됩니다.

(Raz 2009)에서만 Generalized Autonomy의 개념은 의도된 자율성의 개념을 포착한다.

• 정의: 일반화된 자율성

데이터베이스 시스템은 (수정되지 않은) 원자 커밋 프로토콜 메시지를 초과하는 로컬 동시성 정보를 공유하지 않는 경우 Generalized autonomy 속성을 가집니다(다만, 로컬 정보는 사용할 수 있습니다).

이 정의는 데이터베이스 동시성 제어의 맥락에서 가능한 가장 광범위한 정의이며 CO와 CO를 함께 만듭니다(유용한 정의:동시성 제어 정보 분배 없음) 일반화 변종(투표 순서(VO), 아래의 CO 변종 참조)은 글로벌 직렬화에 필요한 조건이다(즉, CO와 그 일반화 변종의 결합은 필요한 집합 VO이며, 여기에는 알려지지 않은 새로운 유용한 일반화 변종도 포함될 수 있다).

요약

글로벌 시리얼라이저빌리티를 위한 커밋 오더(CO) 솔루션(테크니크)은 다음과 같이 요약할 수 있습니다.

멀티데이터베이스 환경의 각 데이터베이스(또는 다른 트랜잭션 오브젝트)가 CO에 준거하는 경우, 즉 로컬 충돌 그래프(시리얼리티 그래프)에 의해 유도되는 로컬(데이터베이스에 대한) 부분 순서에 따라 로컬 트랜잭션의 커밋과 (글로벌, 분산형) 트랜잭션에 대한 투표를 원자력 커밋 프로토콜에 배치한다.ph) 각 거래에 대해 글로벌 CO 및 글로벌 시리얼라이제빌리티가 보장됩니다.데이터베이스의 CO 컴플라이언스는 트랜잭션 실행 프로세스에 영향을 미치거나 트랜잭션 실행 프로세스를 스케줄링하거나 중단하지 않고 로컬 충돌 직렬화 기반 동시성 제어 메커니즘을 통해 효과적으로 달성할 수 있습니다.또한 데이터베이스의 자율성이 침해되지 않습니다.발생하는 유일한 낮은 오버헤드는 충돌을 감지하고(예를 들어 잠금 기능이 있지만 데이터 액세스 차단 기능이 없는 경우), 충돌에 따라 투표와 로컬 트랜잭션의 커밋을 지시하는 것입니다.

2개 이상의 데이터베이스의 부분 순서가 호환되지 않는 경우(글로벌 부분 순서가 각각의 로컬 부분 순서를 함께 포함할 수 없는 경우), 글로벌 컨플릭트 그래프에 글로벌 사이클(2개 이상의 데이터베이스)이 생성된다.이것은 CO와 함께 차단된 투표의 순환을 초래한다.해당 사이클의 데이터베이스에 대해 투표 데드록이 발생합니다(단, 각 데이터베이스에서 허용되는 동시 투표는 일반적으로 거의 모든 미결 투표에 대해 계속 실행됩니다).이 경우 원자적 커밋 프로토콜은 해당 글로벌 사이클에서 차단된 트랜잭션에 필요한 모든 표를 수집하지 못합니다.결과적으로 이 프로토콜은 투표 누락으로 일부 트랜잭션을 중단합니다.이는 지구촌의 순환을 깨뜨리고, 투표-잠금이 해결되며, 관련 차단된 투표는 자유롭게 실행될 수 있다.글로벌 컨플릭트그래프에서 글로벌사이클을 끊으면 글로벌 CO와 글로벌시리얼라이제빌리티가 유지됩니다.따라서 로컬(부분) 커밋 순서가 호환되지 않는 경우, 비호환성의 원인이 되는 트랜잭션을 중단함으로써 원자력 커밋 프로토콜이 자동으로 해결하므로 조치가 필요하지 않습니다.또한 잠금(적어도 1개의 데이터 액세스 블록이 있는 증강 컨플릭트 그래프에서의 글로벌 사이클)에 의한 글로벌 교착상태는 투표 교착상태를 초래하고 동일한 메커니즘에 의해 자동으로 해결된다.

로컬 CO는 관련된 데이터베이스가 (수정되지 않은) 원자 커밋 프로토콜 메시지 이상의 동시성 제어 정보를 공유하지 않는 경우(즉, 데이터베이스가 동시성 제어 컨텍스트에서 자율적인 경우) 글로벌 직렬화를 보장하기 위해 필요한 조건입니다.즉, Autonomous 데이터베이스의 모든 글로벌시리얼라이저빌리티 솔루션은 CO에 준거해야 합니다.그렇지 않으면 글로벌 시리얼라이제빌리티가 침해될 수 있습니다(따라서 고성능 환경에서는 매우 빠르게 침해될 수 있습니다).

CO솔루션은 공통의 분산형 아토믹 커밋아키텍처를 사용하는 경우 퍼포먼스 저하 없이 네트워크크기와 데이터베이스 수에 따라 스케일업합니다.

분산형 시리얼라이저빌리티 및 CO

분산 CO

분산형 시리얼라이저빌리티에 대한 CO솔루션이 다른 기술과 구별되는 특징은 충돌 정보(예를 들어 로컬 우선순위 관계, 잠금, 타임스탬프, 티켓)를 배포할 필요가 없다는 사실이며, 이는 CO솔루션을 고유하게 유효하게 한다.대신 (변경되지 않은) 원자 커밋 프로토콜 메시지(이미 사용됨)를 사용합니다.

(분산형) 시스템에서 분산형 시리얼라이제빌리티를 실현하는 일반적인 방법은 Distributed Lock Manager(DLM; 분산형 잠금 매니저)에 의한 것입니다.분산형 환경에서 잠금(비물질화된 충돌) 정보를 통신하는 DLM은 일반적으로 컴퓨터와 통신 지연으로 인해 시스템 성능이 저하됩니다.CO는 분산형 잠금 매니저 없이 매우 일반적인 조건에서 분산형 시리얼라이제빌리티를 달성할 수 있습니다.특히 신뢰성, 고성능, 확장성, 필요에 따라 낙관적인 동시 제어 사용 가능성, 충돌 정보 없음.(오버헤드와 지연이 발생한) 네트워크를 통한 활발한 통신과 자동 분산 교착 상태 해결.

모든 분산 트랜잭션 시스템은 분산 트랜잭션의 프로세스 간에 원자성(커밋 또는 중단 여부)을 조정하기 위해 일부 원자성 프로토콜에 의존합니다.또한 일반적으로 복구 가능한 데이터(예: 트랜잭션의 제어 하에 있는 데이터, 예를 들어 일정의 복구 가능성 속성과 혼동하지 말 것)는 로컬 서브 트랜잭션(분산 트랜잭션의 일부)을 처리하는 단일 트랜잭션 데이터 매니저 컴포넌트(리소스 매니저라고도 함)에 의해 직접 액세스됩니다.단일 위치(예: 네트워크 노드)에서, 이러한 데이터가 트랜잭션 중에 분산 시스템의 다른 엔티티에 의해 간접적으로 액세스되는 경우에도(즉, 간접 액세스는 로컬 하위 트랜잭션을 통한 직접 액세스를 필요로 한다).따라서 분산 트랜잭션 시스템에서 복구 가능한 데이터는 일반적으로 트랜잭션 데이터 관리자 간에 분할됩니다.이러한 시스템에서, 이러한 트랜잭션 데이터 관리자는 일반적으로 시스템의 원자 약속 프로토콜의 참가자로 구성됩니다.각 참가자가 CO에 준거하고 있는 경우(예를 들어 SS2PL, COCO, 또는 상기의 조합에 의해), 분산 시스템 전체가 CO를 제공합니다(위의 개념에 의해 각 참가자는 별개의 트랜잭션 오브젝트로 간주할 수 있습니다).따라서 (분산된) 시리얼라이제빌리티가 제공됩니다.더 나아가:CO가 원자 커밋 프로토콜과 함께 활용되면 데이터 액세스 잠금으로 인한 분산 데드록(즉, 두 개 이상의 데이터 관리자에 걸쳐 있는 데드록)도 자동으로 해결된다.따라서 다음과 같은 결과가 도출됩니다.

• CO기반분산직렬성

분산 트랜잭션 시스템(예: 분산 데이터베이스 시스템)이 시스템의 복구 가능한 모든 데이터를 관리하는 트랜잭션 데이터 관리자(리소스 관리자라고도 함)로 구성되도록 합니다.데이터 매니저는 다음 3가지 조건을 충족합니다.

1. 데이터 파티션:복구 가능한 데이터는 데이터 매니저 간에 파티셔닝됩니다.즉, 복구 가능한 각 데이터(데이터 항목)는 단일 데이터 매니저에 의해 제어됩니다(예를 들어 Shared nothing 아키텍처에서 공통되는 것처럼 서로 다른 데이터 매니저의 동일한 데이터 복사본도 물리적으로 구별되고 복제됩니다).
2. 원자적 약속 프로토콜의 참가자:이러한 데이터 관리자는 분산 트랜잭션의 원자성을 조정하기 위한 시스템의 원자 약속 프로토콜의 참여자입니다.
3. CO 컴플라이언스:이러한 각 데이터 매니저는 CO에 준거하고 있습니다(또는 일부 CO 배리언트 준거.아래 참조).

그리고나서

1. 분산 시스템 전체가 (분산 CO와) 시리얼라이제이션이 보증됩니다.
2. 데이터 액세스 기반의 분산 데드록(적어도1개의 비실체화 경합이 있는 2개 이상의 데이터 매니저가 관여하는 데드록)은 자동으로 해결됩니다.

더 나아가:CO 준거 데이터 매니저는 위의 조건 1, 2를 충족하는 시스템에서의 (분산형) 시리얼라이제빌리티에 필요한 조건입니다.데이터 매니저가 자율적인 경우, 즉 원자력 커밋 프로토콜의 수정되지 않은 메시지를 넘어 동시성 제어 정보를 공유하지 않습니다.

또한 이 정리는 각 트랜잭션 데이터 매니저에서 SS2PL(또는 다른 CO 바리안트)가 로컬로 사용되고 각 데이터 매니저가 그 데이터를 배타적으로 제어할 경우 분산 SS2PL 및 시리얼라이저빌리티에 분산형 SS2PL을 적용할 필요가 없음을 의미합니다.이는 광범위한 분산 트랜잭션 애플리케이션과 관련이 있으며, 정리 조건을 충족하도록 쉽게 설계할 수 있습니다.

분산 낙관적 CO(DOC)

Distributed Optimistic CO(DOC)를 구현하기 위해 범용 로컬 CO 알고리즘은 데이터 액세스 차단 없이 로컬 교착 상태 없이 시스템 내의 모든 원자 커밋 프로토콜 참여자에게 사용됩니다.이전 정리에는 다음과 같은 결과가 있습니다.

• 분산적 낙관적 CO(DOC) 정리

DOCO를 사용하는 경우:

1. 로컬 데드록은 발생하지 않습니다.
2. 글로벌(투표) 교착상태는 잠금 관련(블로킹 및 비블로킹 충돌 포함)이 아니라 자동으로 해결됩니다(및 모두 비블로킹 충돌 포함).

따라서 데드록 처리는 필요하지 않습니다.

예

분산형 SS2PL

SS2PL을 사용하는 분산 데이터베이스 시스템은 A와 B라는 두 개의 원격 노드에 있습니다.데이터베이스 시스템에는 각 노드에 하나씩 두 개의 트랜잭션 데이터 관리자(리소스 관리자)가 있으며, 데이터베이스 데이터는 각각 자체(노드에 대한 로컬) 데이터 부분을 배타적으로 제어하는 방식으로 두 데이터 관리자 간에 분할됩니다.각 관리자는 자신의 데이터를 처리하며 다른 관리자의 데이터를 인식하지 못하고 잠급니다.각 분산 트랜잭션에 대해 이러한 데이터 관리자는 사용 가능한 원자적 커밋 프로토콜을 실행해야 합니다.

$({$과 $({$의 2개의 분산 트랜잭션이 동시에 실행되고 있으며, 액세스 데이터 x와 y.x는 모두 A의 데이터 매니저(B의 매니저는 x에 액세스 할 수 없음)의 배타적 제어 하에 있으며, 그 아래의 y는 B의 데이터 매니저의 배타적 제어 하에 있다.

$({$은 A에서 x를 읽고 B에 y를 씁니다.$즉{\displaystyle {}_{}}$, ${\displaystyle {T1\mathrm{}}_{}}$ $=$ ${\displaystyle {\text{R1A}}_{}}$($)$ {$displaystyle T_{$1}=$R_{\text{1$}$A}(x)}$ $폭$${\displaystyle {}_{}}$ $)$ {$디스플레이 스타일$ W_${\text{1$$}$동시성 제어에 공통 표기법을$$ $사용$하는 경우 B$}(y)}.$

$({$는 B에서 y를 읽고 A에 x를 씁니다.$즉{\displaystyle {}_{}}$, ${\displaystyle {T2\mathrm{}}_{}}$ $=$ ${\displaystyle {\text{R2B}}_{}}$(${\displaystyle y}$ $){displaystyle T_{$2}=$R_{\text{2$})$B}(y)}$ ${\displaystyle {\text{W2A<img alt="{displaystyle T\_2=R\_{text{2B}}(y)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/8dfdaaa0ca846ad4e58728cbe5a120e9cb5a3fd1" style="vertical-align: -0.838ex; width:12.457ex; height:2.843ex;" papago-attr-id="362">}}_{}}$($)$ {$디스플레이$ 스타일 W_{\$text{2$$}$$A}}(x)}$

A 및 B의 각 로컬서브 트랜잭션(각 노드의 $(\$ $및$ $(\$의 부분)은 다음과 같습니다.

로컬 서브 트랜잭션

노드 거래.	A	B
${\displaystyle T_{1}}$	$\displaystyle T_{\text{1}A}}=R_{\text{1}A}}(x)}$	$\displaystyle T_{\text{1}B}}=W_{\text{1}B}}(y)}$
${\displaystyle T_{2}}$	$\displaystyle T_{\text{2}A}}=W_{\text{2}A}}(x)}$	$\displaystyle T_{\text{2}B}}=R_{\text{2}B}}(y)}$

특정 시점의 데이터베이스 시스템 스케줄은 다음과 같습니다.

${\displaystyle R_{\text{1}A}}(x)}$ ${\displaystyle R_{\text{2}B}}(y)}$

($또한{\displaystyle {}_{}}$ ${\displaystyle {\text{R2B}}_{}}$(${\displaystyle y}$ $){displaystyle R_{\$text{$2$})$B}(y)}$ $R$${\displaystyle {}_{}}$ ${\displaystyle {\text{1A}}_{}}$(${\displaystyle x}$) { $displaystyle R_{$ \$text$ { $1$ }$A}}(x)}$ 가능$$)

${\displaystyle {T\mathrm{}}_{}}$ 1$({$ T_${1})$은 x에서 읽기 잠금을 유지하고 ${\displaystyle {T\mathrm{}}_{}}$ 2$({$는 y에서 읽기 잠금을 유지합니다.${\displaystyle \mathrm{따라서}}$ ${\displaystyle {\text{W1B}}_{}}$(${\displaystyle }$y $){display$ W_${\text{1$}$B}(y)}$ $및$ $)$ {\$displaystyle W_{\text{2$}A$}}(x)}$은(는) SS2PL의 잠금 호환성 규칙에 의해 차단되어 실행할 수 없습니다.이것은 분산된 교착 상태이며, 길이 2(에지의 수, 경합, 2가 가장 빈번한 길이)의 분산(글로벌) 사이클을 가진 투표 데드록(아래 참조)이기도 합니다.로컬 서브트랜잭션은 다음 상태입니다.

$(\$$$$A}}$이(가) 준비 완료(실행이 종료됨) 및 투표 완료(원자성 커밋)

$(\$$$$B}}$이(가) 실행 중이고 차단되었습니다(비실체화된 충돌 상황. 투표할 수 없음).

$(\$$$$B}}$이(가) 준비되고 투표되었습니다.

$(\$$$$A}}$이(가) 실행 중이고 차단되었습니다(비물질화된 충돌, 투표 없음).

Atomic Commitment Protocol은 차단된 서브 트랜잭션(투표 데드록)에 대해 투표를 받을 수 없으므로 $({$$displaystyle$ T_${1$ $또는{\displaystyle {}_{}}$ $({$displaystyle $T_{2$ 중 $하나{\displaystyle {}_{}}$(또는 타임아웃이 매우 가까운 경우 둘 다)가 누락된 일부 트랜잭션을 최종적으로 중단합니다.그러면 글로벌 교착 상태가 해결됩니다.나머지 트랜잭션은 실행이 완료되고 투표되고 커밋됩니다.중단된 트랜잭션은 즉시 재시작되고 다시 실행됩니다.

평.

1. 예를 들어 데이터 파티션(A의 x, B의 y)이 없으면 B에서 직접 x에 액세스할 수 있기 때문에 데이터 파티션(A의 x, B의 y)은 중요합니다.$트랜잭션{\displaystyle {}_{}}$ $({$이 ${\displaystyle {T1\mathrm{}}_{}}$$({$$displaystyle T_{1$$})$ 및$$ $({$ $T_{2$$})$와 동시에 B에서 실행되고 x를 직접 쓰는 경우 분산 잠금 매니저가 $없으면{\displaystyle {}_{}}$ ${\displaystyle A_{}}$의 $x$에 대한 읽기 잠금을 B에서 볼 수 없으며 B에서 볼 수 없습니다.e $of{\displaystyle {}_{}}$ ${\displaystyle {T\mathrm{}}_{}}$ 3$($$또는$비블로킹 CO 변종인 경우 표면화된 경합 신호를 보냅니다. 아래 참조).따라서 시리얼라이제빌리티를 위반할 수 있습니다.
2. 데이터 파티션으로 인해 x는 B에서 직접 액세스할 수 없습니다.단, 기능에는 제한이 없으며 B에서 실행되는 트랜잭션은 여전히 x(일반적이지 않음)의 쓰기 또는 읽기 요청을 발행할 수 있습니다.이 요청은 A에 있는 트랜잭션의 로컬 하위 트랜잭션으로 전달되며(아직 존재하지 않는 경우 생성됨) A에 있는 로컬 데이터 관리자에게 이 요청을 발행합니다.

바리에이션

위의 시나리오에서는 양쪽 경합이 구체화되지 않고 글로벌 투표 데드록은 글로벌 투표 대기 그래프에 사이클로 반영됩니다(그러나 글로벌 충돌 그래프에는 반영되지 않습니다.상기 글로벌 사이클에 의한 투표 데드록의 정확한 특성 참조).그러나 데이터베이스 시스템은 정확히 동일한 충돌과 투표-잠금 상황 및 동일한 분해능을 가진 모든 CO 변형을 사용할 수 있습니다.충돌은 사용된 CO 변종에 따라 구체화되거나 비실체화될 수 있습니다.예를 들어 분산 데이터베이스 시스템에서 SS2PL이 아닌 SCO(아래)를 사용하는 경우, 이 예에서는 2개의 경합이 발생하고 모든 로컬 서브 트랜잭션이 준비 상태가 되며, 각 노드에서1개의 투표 블로킹이 발생합니다.이는 충돌로 인해 A와 B 모두에 개별적으로 적용되는 CO 투표 규칙 때문입니다.$displaystyle T_{$$$$A}}=W_{\text{2$$}$$A}}(x)}$은(는) ${\displaystyle {\text{T1A}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{R1A}}_{}}$ $)$ {\$style T_{\text${1} $이전$에 투표되지 않았습니다.$A}}=R_{\text{1$$}$$A}(x)}$이 $종료$되고 ${\displaystyle {\text{T1B}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\text{W1B}}_{}}$ (${\displaystyle y}$) {$displaystyle T_{$ \$text$ { $1$ }$B}}=W_{\text{1$$}$$B}}(y)}$은(는) ${\displaystyle {\text{T2B}}_{}}$ ${\displaystyle {}_{}}$ $)\style T_{\$text${2$} $이전$에 투표되지 않았습니다.$B}}=R_{\text{2$$}$$B}(y)}$이(가) 종료됩니다.이것은 투표용 데드록입니다.이제 충돌 그래프는 글로벌 사이클(모든 충돌이 구체화됨)을 가지며, 다시 원자 약속 프로토콜에 의해 해결되어 분산 직렬화가 유지됩니다.분산 데이터베이스 시스템에서는 불가능하지만 원칙적으로는 가능하지만(또한 다중 데이터베이스에서 발생), A는 SS2PL을 사용할 수 있고 B는 SCO를 사용할 수 있습니다.이 경우 글로벌 사이클은 wait-for 그래프나 serializability 그래프가 아니라 증강된 충돌 그래프(양자의 결합)에 있습니다.다음 표에 다양한 조합을 정리합니다.

투표에 의한 데드록 상황

사례.	노드 A	노드 B	가능한 일정	구체화 갈등들 예정대로	비(非 실현된 갈등들	$\displaystyle T_{\text{1}A}}=R_{\text{1}A}}(x)}$	$\displaystyle T_{\text{1}B}}=W_{\text{1}B}}(y)}$	$\displaystyle T_{\text{2}A}}=W_{\text{2}A}}(x)}$	$\displaystyle T_{\text{2}B}}=R_{\text{2}B}}(y)}$
1	SS2PL	SS2PL	${\displaystyle R_{\text{1}A}(x)R_{\text{2}B}}(y)}$	0	2	준비가 되어 있습니다! 투표필	입니다. (차단)	입니다. (차단)	준비가 되어 있습니다! 투표필
2	SS2PL	SCO	${\displaystyle R_{\text{1}A}(x)R_{\text{2}B}}(y) W_{\text{1}B}}(y)}$	1	1	준비가 되어 있습니다! 투표필	준비가 되어 있습니다! 투표 차단	입니다. (차단)	준비가 되어 있습니다! 투표필
3	SCO	SS2PL	${\displaystyle R_{\text{1}A}(x)R_{\text{2}B}}(y) W_{\text{2}A}}(x)}$	1	1	준비가 되어 있습니다! 투표필	입니다. (차단)	준비가 되어 있습니다! 투표 차단	준비가 되어 있습니다! 투표필
4	SCO	SCO	${\displaystyle R_{\text{1}A}(x)R_{\text{2}B}}(y) W_{\text{1}B}}(y) W_{\text{2}A}}(x)}$	2	0	준비가 되어 있습니다! 투표필	준비가 되어 있습니다! 투표 차단	준비가 되어 있습니다! 투표 차단	준비가 되어 있습니다! 투표필

코멘트:

1. 컨플릭트 그래프 내의 컨플릭트 및 사이클은 사용되는 컨클릭티 컨트롤과는 별개로 트랜잭션과 그 초기 스케줄링에 의해서만 결정됩니다.CO의 모든 변종에서는 모든 글로벌 사이클(즉, 두 개 이상의 데이터베이스에 걸쳐 있음)에 의해 투표 교착 상태가 발생합니다.특정 충돌이 구체화되었는지 또는 비실체화되었는지 여부에 따라 CO 변형이 다를 수 있습니다.
2. 위의 일정에서 일부 제한된 작업 순서 변경은 트랜잭션 내 주문에 의해 제한될 수 있지만, 이러한 변경은 테이블의 나머지 부분을 변경하지 않습니다.
3. 위에서 설명한 바와 같이 (일반적인) 충돌 그래프에서 시리얼라이저빌리티에 영향을 주는 사이클을 설명하는 것은 케이스4 뿐입니다.케이스 1 ~ 3 에서는, 락 베이스의 글로벌 데드록의 사이클에 대해 설명합니다(적어도1개의 록블록이 존재합니다).모든 사이클 유형은 원자성 커밋 프로토콜에 의해 균등하게 해결됩니다.케이스 1은 1980년대부터 사용되고 있는 일반적인 분산형 SS2PL입니다.그러나 CO 기사를 제외하고는 2009년 현재 이 자동적인 글로벌 교착 상태 해결에 주목하는 연구 기사는 없는 것으로 알려졌다.이러한 글로벌 교착상태는 일반적으로 전용 메커니즘에 의해 처리되어 왔다.
4. 위의 사례 4는 분산 낙관적 CO(DCO)가 사용되는 경우의 전형적인 투표 데드록의 예이기도 하다(즉, A와 B 모두에서 낙관적 CO(OCO; 아래 참조)가 SCO를 대체하는 경우 사례 4는 변경되지 않는다).데이터 액세스 차단은 발생하지 않으며 구체화된 충돌만 존재합니다.

가상 멀티 싱글 스레드 코어(MuSiC) 환경

코멘트:위의 예에서는 CO의 실제 권장 사용률을 설명하고 있지만, 이 예에서는 데모용으로만 가정하고 있습니다.

특정 실험용 분산 메모리 상주 데이터베이스는 Multi Single-Treaded Core(MuSiC; 싱글 스레드 코어) 트랜잭션 환경을 지원합니다."단일 스레드"는 트랜잭션 스레드만 나타내며 트랜잭션의 직렬 실행을 나타냅니다.그 목적은 동일한 코어의 여러 스레드에서 기존 트랜잭션 실행에 비해 성능(예: H-Store^[6] 및 VoltDB)이 크게 향상되는 것입니다.다음에 설명하는 바와 같이 MuSiC는 코어의 분포 방식과는 무관합니다.이러한 칩은 하나의 집적회로(칩)에 존재할 수도 있고 지리적으로 많은 컴퓨터에 분산되어 있는 여러 칩에 존재할 수도 있습니다.이러한 환경에서 복구 가능한(트랜잭션) 데이터를 스레드(코어) 간에 분할하여 이전 섹션에서 설명한 바와 같이 분산 CO에 대해 기존 방식으로 구현하면 DOCO와 Strictness가 자동으로 존재합니다.그러나 이러한 환경의 간단한 구현에는 단점이 존재하며 범용 솔루션으로서의 실용성은 의문이다.한편, 대부분의 상황에서 이러한 단점을 우회할 수 있는 애플리케이션에서는 상당한 성능 향상을 달성할 수 있습니다.

코멘트:여기서 설명하는 MuSiC의 간단한 실장(예를 들어 분산 CO에서 통상 사용하는 것과 같이 필요할 때 원자적인 커밋 프로토콜에서 투표(및 트랜잭션스레드) 블록을 사용하는 것)은 데모용일 뿐 H-Store 또는 기타 프로젝트에서의 실장과는 관련이 없습니다.

MuSiC 환경에서는 로컬 예약이 일련 번호입니다.따라서 로컬 Optimistic CO(OCO; 아래 참조)와 원자력 약속 프로토콜에 대한 글로벌 CO 집행 투표 순서 지정 전략 조건이 모두 자동으로 충족됩니다.이를 통해 분산 CO 컴플라이언스(및 분산 시리얼화 가능성)와 자동 글로벌 교착 상태 해결(투표)이 모두 이루어집니다.

게다가 시리얼 스케줄에서는, 로컬의 Strictness도 자동적으로 추종합니다.(Raz 1992; page 307)의 정리 5.2에 따르면 CO 투표 순서 전략이 적용될 때 글로벌 엄격성도 보장된다.serial local은 엄격함과 "optimic"(데이터 액세스 차단 없음)을 동시에 사용할 수 있는 유일한 모드입니다.

다음과 같이 결론을 내립니다.

• MuSiC 정리

MuSiC 환경에서 복구 가능한(트랜잭션) 데이터가 코어(스레드) 간에 분할되어 있는 경우, 두 가지 모두

1. OCO(및 암시적 시리얼라이저빌리티, 즉 DOCO 및 분산 시리얼라이저빌리티)
2. 엄격성(효과적인 회복 가능, 1과 2는 엄격한 CO를 의미함) 및
3. 교착 상태 해결

사용되는 코어 수의 무한 확장성과 함께 글로벌하게 자동으로 존재합니다.

코멘트:그러나 특별한 취급이 필요한 두 가지 단점이 있을 수 있습니다.

1. 글로벌 트랜잭션의 로컬 하위 트랜잭션은 커밋될 때까지 차단되며, 이로 인해 각 코어가 아이돌 상태가 됩니다.이로 인해 로컬 서브트랜잭션의 스케줄이 거의 동시에 모든 서브트랜잭션을 시간적으로 실행하려고 해도 코어 사용률이 크게 감소합니다.이는 글로벌 트랜잭션에 대한 커밋(일부 원자적 커밋 프로토콜 포함)에서 실행을 분리함으로써 극복할 수 있으며, 이를 위해 캐스케이드 중단이 발생할 수 있습니다.
2. 복구 가능한 데이터의 양(패키지 크기)에 대한 코어 수를 늘리면 코어당 평균(패키지된) 데이터 양이 줄어듭니다.이로 인해 데이터 사용률 분포에 따라 일부 코어가 유휴 상태가 되는 반면 다른 코어는 매우 비지 상태가 될 수 있습니다.또한 로컬(코어에 대한) 트랜잭션은 필요한 데이터에 도달하기 위해 글로벌(멀티 코어)이 될 수 있으며 추가적인 오버헤드가 발생할 수 있습니다.따라서 코어의 수가 증가함에 따라 각 코어에 할당되는 데이터의 양과 유형이 데이터 사용량에 따라 균형을 맞춰야 합니다.따라서 코어가 과부하가 되어 병목현상이 되거나 코어가 너무 자주 아이돌 상태가 되어 사용률이 낮아지지 않습니다.또 다른 고려사항은 로컬 트랜잭션의 수를 최대화하고 분산된 글로벌 트랜잭션의 수를 최소화하기 위해 일반적으로 동일한 트랜잭션에서 액세스하는 모든 데이터를 동일한 코어 파티션에 넣는 것입니다(가능한 경우).이는 부하 밸런싱(데이터 액세스 밸런싱) 및 트랜잭션별 데이터 사용 패턴에 따라 코어 간에 데이터를 가끔 재분할함으로써 달성할 수 있습니다.이 단점을 크게 완화하기 위한 또 다른 방법은 일부 핵심 파티션 간에 적절한 물리적 데이터 복제를 통해 읽기 전용 글로벌 트랜잭션을 완전히 방지하고 전용 커밋 메커니즘을 통해 복제 변경을 동기화하는 것입니다.

CO 바리안트: 특수한 케이스와 일반화

특수 케이스 스케줄 속성 클래스(예: 아래의 SS2PL 및 SCO)는 CO 클래스에 엄격하게 포함됩니다.일반화 클래스(ECO 및 MVCO)에는 CO 클래스가 엄밀하게 포함되어 있습니다(즉, CO 준거가 아닌 스케줄도 포함됩니다).또한 일반화 변형은 로컬 동시성 제어 정보를 배포하지 않고 글로벌 시리얼라이제빌리티를 보증합니다(각 데이터베이스는 일반화된 자율성 속성: 로컬 정보만 사용). CO 제약을 완화하고 추가(로컬) 정보를 사용하여 동시성과 성능을 향상시킵니다.ECO는 다음 정보에 대한 지식을 사용합니다.트랜잭션은 로컬(즉, 단일 데이터베이스로 제한됨)이며 MVCO는 데이터 버전 값의 가용성을 사용합니다.CO와 마찬가지로, 두 일반화 변형 모두 논블로킹이며, 트랜잭션의 운영 스케줄링을 방해하지 않으며, 관련된 동시성 제어 메커니즘과 심리스하게 결합될 수 있습니다.

CO 바리안트라는 용어는 일반적으로 CO, ECO, MVCO 또는 관련된 동시성 제어 메커니즘 또는 속성(멀티 버전 기반 ECO, MVECO 포함)을 가진 각각의 조합을 말합니다.(로컬 동시성 제어 정보 배포 없이 글로벌시리얼라이제이션성을 보증하는) 다른 일반화 바리안트는 알려져 있지 않지만 검출될 가능성이 있습니다.

강력한 2상 잠금(SS2PL)

Strong Strict Two Phase Locking(SS2PL; 엄격도 또는 엄격한 스케줄링이라고도 함)은 트랜잭션의 읽기 및 쓰기 잠금이 모두 트랜잭션 종료(커밋 또는 중단) 후에만 해제됨을 의미합니다.SS2PL 스케줄 세트는 CO 스케줄 세트의 적절한 서브셋입니다.이 속성은 데이터베이스 시스템에서 널리 사용되고 있으며 CO를 의미하기 때문에 CO를 사용하고 글로벌 트랜잭션에 참여하는 데이터베이스는 (멀티 데이터베이스 환경에서 원자성에 필요한 임의의 원자 약속 프로토콜을 사용할 때) 직렬화 가능한 글로벌 일정을 함께 생성합니다.이 경우 CO 분산 솔루션에 참여하기 위해 데이터베이스를 변경하거나 추가할 필요가 없습니다.위의 로컬 범용 CO 알고리즘에서 커밋하기 전에 중단되는 미결정 트랜잭션세트는 잠금 때문에 비어 있습니다.따라서 이 경우 이러한 알고리즘은 불필요합니다.트랜잭션은 "ready" 상태가 된 직후에 데이터베이스 시스템에 의해 폴링될 수 있습니다.즉, 로컬에서 태스크 실행이 완료됩니다.그것의 잠금은 원자 약속 프로토콜에 의해 결정된 후에만 데이터베이스 시스템에 의해 해제되며, 따라서 위의 글로벌 CO 시행 정리의 조건은 자동으로 유지됩니다.로컬 타임아웃 메커니즘이 데이터베이스 시스템에 의해 (로컬) SS2PL 교착 상태를 해결하기 위해 사용되는 경우 차단된 트랜잭션을 중단하면 글로벌 충돌 그래프(증강된 충돌 그래프의 실제 사이클)의 잠재적인 로컬 사이클뿐만 아니라 데이터베이스 시스템의 잠재적인 글로벌 사이클도 부수어집니다.중단 메커니즘이 상대적으로 느립니다.여러 주체에 의한 이러한 독립적 중단은 일반적으로 글로벌 주기당 여러 트랜잭션에 대해 불필요한 중단을 초래할 수 있습니다.로컬 그래프 기반 메커니즘에서는 상황이 다릅니다.이는 글로벌 사이클을 식별할 수 없으며, 결과적인 투표 교착 상태가 다른 데이터베이스에서 더 일찍 해결되지 않으면 원자적 약속 프로토콜이 글로벌 사이클을 깰 것입니다.

로컬 SS2PL과 글로벌시리얼라이제빌리티를 암시하는 원자적인 약속도 직접 추론할 수 있습니다.분산형 트랜잭션을 포함한 모든 트랜잭션은 2PL(SS2PL) 규칙을 따릅니다.여기서 원자력 커밋 프로토콜 메커니즘은 커밋에 대한 합의를 위해 필요한 것이 아니라 단계 2 동기화 포인트의 종료를 위해 필요합니다.아마도 이러한 이유로 원자력 약속 투표 메커니즘을 고려하지 않고 CO 이전에 자동 글로벌 교착 상태 해결이 주목되지 않았습니다.

엄격한 CO(SCO)

엄격한 커밋 오더(SCO; (Raz 1991c)는 엄격성과 CO의 교차점이며, 두 특성이 모두 존재할 때 스케줄의 동시성에 대한 상한을 제공한다.비슷한 오버헤드를 가진 일반적인 SS2PL에 사용되는 것과 유사한 블로킹메커니즘(잠금)을 사용하여 실장할 수 있습니다.

SS2PL과 달리 SCO는 읽기/쓰기 경합을 블록하지 않지만 커밋을 블록할 가능성이 있습니다.SCO와 SS2PL은 다른 두 가지 경합 유형(쓰기-읽기 및 쓰기-쓰기)에 대해 동일한 블로킹 동작을 가집니다.그 결과 SCO는 평균 블로킹 기간이 짧아지고 동시성이 높아집니다(예를 들어 SCO와 동일한 순서 공유를 가진 가장 중요한 록의 변형에 대한 단일 데이터베이스의 성능 시뮬레이션). 일부 트랜잭션 부하에 대해 약 100%의 이득을 얻을 수 있습니다.또한 동일한 트랜잭션 부하에 대해서도 SCO는 높은 수준에 도달할 수 있습니다.SS2PL보다 높은 트랜잭션 환율).동시성이 높다는 것은 주어진 컴퓨팅 리소스를 통해 더 많은 트랜잭션이 시간 단위로 완료되고(트랜잭션 속도, throughput이 높음), 트랜잭션의 평균 지속 시간이 짧아진다는 것을 의미합니다(더 빠른 완료, 차트 참조).SCO의 이점은 잠금 경합 중에 특히 중요합니다.

• SCO와 SS2PL의 퍼포먼스 정리

읽기/쓰기 경합이 존재하는 경우 SCO는 SS2PL보다 평균 트랜잭션 완료 시간을 단축합니다.SCO와 SS2PL은 다른 점에서는 동일합니다(쓰기/읽기 및 쓰기/쓰기 경합에 의한 블로킹 동작은 동일합니다).

SCO는 SS2PL과 마찬가지로 실용적이며, SS2PL은 직렬화 기능뿐만 아니라 엄격성을 제공하므로 장애로부터 데이터베이스를 효율적으로 복구하기 위한 기초로서 널리 활용되고 있습니다.SS2PL 기구를 SCO 기구로 변환하여 회복 방법을 변경하지 않고 간단하게 성능을 향상시킬 수 있다.SCO 구현에 대한 설명은 (Perrizo 및 Tatarinov 1998)^[7]에서 확인할 수 있다.반낙관적인 데이터베이스 스케줄러를 참조해 주세요.

SS2PL은 SCO의 적절한 서브셋입니다(이는 SCO가 SS2PL보다 구속력이 적고 동시성이 높은 또 다른 이유입니다).

OCO(Optimistic CO)

Optimistic Commitment Ordering(OCO; 옵티머스 커밋오더링)의 실장에서는 범용 로컬 CO 알고리즘이 데이터액세스 블로킹 없이 사용되므로 로컬 데드록이 발생하지 않습니다.트랜잭션 또는 동작 스케줄링 제약이 없는 OCO는 CO 클래스 전체를 대상으로 하며 CO 클래스의 특수한 경우가 아니라 유용한 CO 변종 및 메커니즘 특성화입니다.

확장 CO(ECO)

ECO의 일반적인 특징

확장 커밋 오더(ECO; (Raz 1993a))는 CO를 일반화한다.로컬 트랜잭션(단일 데이터베이스로 제한되는 트랜잭션)이 글로벌(분산) 트랜잭션(2개 이상의 데이터베이스에 걸친 트랜잭션)과 구별할 수 있는 경우 커밋 순서는 글로벌 트랜잭션에만 적용됩니다.따라서 로컬(데이터베이스에 대한) 스케줄이 ECO 속성을 가지기 위해서는 글로벌 트랜잭션만의 커밋이벤트의 시간순서(부분적)가 각 로컬컨플릭트 그래프상의 순서와 일치합니다.

• 정의: 확약 주문

${\displaystyle {T1\mathrm{}}_{}}$ $({$ T_${1}, T_{2})$를 스케줄 내의 2개의 커밋된 글로벌트랜잭션으로 $합니다{\displaystyle {}_{}}$.이를 통해 $(\$$displaystyle$ $T_{1$})에서$$T2(\$displaystyle$ T_${$$1$})$$로의 컨플릭트그래프(우선순위 그래프)에 왜곡되지 않은 트랜잭션의 다이렉트패스가 존재합니다.$2({$ T_{2$\}\},$ 아마도 과도적, 간접적).스케줄에는 Extended Commitment Ordering(ECO; 확장 커밋 순서) 속성이 있습니다.이러한 $트랜잭션{\displaystyle {}_{}}$ 2개마다 ${\displaystyle {T1\mathrm{}}_{}}$$(\$ T_${1})$이 커밋되기 $전$에 T2$(\$ T_${2})$가 커밋됩니다.

한 분산된 알고리즘 세계적인 ECO을 보장하기 위해 존재한다.카이 트리아 오닐에 대해 말하자면, 알고리즘만(변경되지 않은)원자 약속 프로토콜 메시지를 필요가 있다.위해서 세계적인 직렬화 성질을 보장하기 위해, 각 데이터베이스는 다른(지역)동시 실행 제어 메커니즘에 의해 자체 거래의 충돌을 직렬화 성질을 보장할 필요가 있다.

• 그 ECO그리고 위성 Serializability 정리.

1. (이곳의 지구를 의미한다.)ECO함께 지역 갈등 직렬화 성질이 필요 충분 조건 세계 분쟁 직렬화 성질을 보장하기 위해.
2. 언제 원자 약속 메시지의 동시 실행 제어 정보는 데이터베이스(자율성)밖에 두고 지역 거래 확인할 수 있습니다 공유된 경우 그것이 또한 필요 조건이었다.

(레즈 1993a)에 필수적인 증거를 참조하십시오.

이 조건(지역 직렬화 성질과 ECO)카이 트리아 오닐보다 더 복잡한 지역 알고리즘( 하지만, 카이 트리아 오닐과 실용적인 간접비 차이가 있다고 하)의 비용에 더 많은 동시성을 허용하고 더 약하다.

언제 모든 거래의 결제 국제적인(예를 들어, 만약 어떤 정보도 거래 이용 가능하다 지역 것)가정 된다면, ECO콜로라도로 줄어든다.

ECO 알고리즘

전에는 전역 트랜잭션 전념하고 있는 제네릭 국내(데이터베이스로)ECO알고리즘 미정 거래의 충돌 그래프에 되었고 주기까지 초래할 수 있는 최소한의 집합(지 않으며, 낙태, 지역의 거래, 국제적은 지역별로 운영하는 헌신적), aborts.만약 각 트랜잭션을 무게(은 거래의 중요성과 컴퓨팅 자원들은 이미 실행 중인 거래에 투자에 의해, 최적화, 예를 들어, 막스 흐름으로부터 네트워크 prob 감소에 의해 수행될 수 있는지 판단을 일으킬 수 있으며 할당된 거래(독특한, 카이 트리아 오닐에 반대되는) 이러한 일련의 최적화될 수 있다.lem(레즈 1993a)).처럼 CO을 위해 그렇게 정해진 시간, 그리고 결국 빈 되게 의존하고 있다.사실상, 모든 거의 나갈 때만 집합은 비어(과 정해진 최적화 적용된다)트랜잭션야 한다 구현이 필요했다.(그 ECO알고리즘에서 별도의)을 수행하면 지역 사이클(카이 트리아 오닐, 자신에 의해 직렬화 성질을 의미하고, 달리 하지만, 실제적으로 또한 카이 트리아 오닐에 대한 국내 동시성 메커니즘, 적어도 보장하기 위해 활용한다 Recoverability)제거된다 지역(데이터베이스에)동시 실행 제어 메커니즘입니다.국내 거래 항상 동시에(비록 어떤 선행 관계, 카이 트리아 오닐과는 달리 존재하) 행해질 수 있다.전체 트랜잭션의 로컬 부분 순서(로컬 컨플릭트그래프에 의해 결정되며, 현재는 로컬시리얼라이저빌리티 메커니즘에 의해 사이클이 삭제되기 때문에 가능한 일시적인 로컬 사이클만 사용)가 허용되면 글로벌 트랜잭션도 동시에 커밋되도록 투표할 수 있습니다(모든 트랜잭션의 (직접적인) 이전(co를 통해)nfconflict) 글로벌 트랜잭션이 커밋되지만, 트랜잭션으로 선행하는 로컬 트랜잭션은 모든 상태에 있을 수 있습니다.이는 분산 CO 알고리즘의 강력한 동시 투표 조건과 유사하며, 이 조건에서는 모든 거래 선행 트랜잭션을 커밋해야 합니다.)

글로벌 ECO를 보증하는 조건은 CO와 유사하게 요약할 수 있습니다.

• 글로벌 ECO 실시 투표 전략 정리

${\displaystyle {T1\mathrm{}}_{}}$ $(\$$style$ $T_{1}, T_{2})$를 로컬로 시리얼라이제빌리티를 보증하는 데이터베이스 시스템에서 글로벌트랜잭션을 미결정(커밋 또는 중단하지 않음)으로 $합니다{\displaystyle {}_{}}$.이것에 의해, $(\$에서 T1(\displaystyle T_1})까지의$$ 로컬컨플릭트 그래프(데이터베이스 자체의)에 폐기되지 않은 트랜잭션의 방향 경로가 존재합니다.$({$ 그 후$T2$({$displaystyle T_{$2$$$}})$의 커밋이 $투표$되기 ${\displaystyle {전}_{}}$에 T1$({$ T_{1$})$을 종료(커밋 또는 중단)$하는{\displaystyle {}_{}}$ 것은 멀티데이터베이스 환경의 모든 데이터베이스 시스템에서 글로벌 ECO(보증 조건)를 보증하기 위한 필수적이고 충분한 ${\displaystyle {\mathrm{조건}}_{}}$입니다.글로벌 ECO(이것이 없으면 위반될 수 있습니다)

글로벌 ECO(글로벌컨플릭트그래프 내의 모든 글로벌사이클은 원자적인 커밋에 의해 삭제됨)와 로컬시리얼라이제빌리티(즉, 각 데이터베이스 시스템은 로컬로 시리얼라이제빌리티를 유지하고 모든 로컬사이클은 삭제됨)는 글로벌시리얼라이제빌리티(모든 사이클이 삭제됨)를 나타냅니다.즉, 멀티데이터베이스 환경 내의 각 데이터베이스 시스템이 로컬 시리얼라이제빌리티를 제공하고(어떤 메커니즘에 의해) 상기 정리(CO의 투표순서 전략의 일반화)에서 투표순서 전략을 실시하면 글로벌 시리얼라이제빌리티가 보증됩니다(더 이상 로컬 CO는 필요 없음).

CO와 마찬가지로 ECO 투표 데드록 상황은 다음과 같이 요약할 수 있다.

• ECO 투표-데드록 정리

멀티데이터베이스 환경이 각각 글로벌 ECO(위의 정리 조건을 사용)와 로컬 컨플릭트시리얼라이제빌리티(글로벌컨플릭트그래프 내의 로컬사이클 제외)를 강제하는 데이터베이스 시스템으로 구성하도록 하겠습니다.그런 다음 글로벌 증가 충돌 그래프에 글로벌 사이클(2개 이상의 데이터베이스)이 존재하는 경우에만 투표 데드록이 발생합니다(데이터 액세스 잠금에 의한 블록도 에지로 표시됩니다).사이클이 중단되지 않으면 사이클 상의 모든 글로벌트랜잭션은 각각의 투표 데드록과 관련되어 최종적으로 각각 투표가 차단됩니다(직접 또는 간접적으로 데이터 액세스록).로컬 트랜잭션이 사이클 상에 존재하는 경우 로컬트랜잭션은 중단되지 않은 상태(실행 중, 준비 중 또는 커밋됨)일 수 있습니다(CO와 달리 로컬커밋 블로킹은 필요 없습니다).

CO와 마찬가지로 데이터 액세스잠금(적어도1개의 잠금블록 포함)에 의한 글로벌 데드록도 투표 데드록이며 원자적인 커밋에 의해 자동으로 해결됩니다.

멀티버전 CO(MVCO)

Multi-version Commitment Ordering(MVCO; (Raz 1993b))은 다중 버전 리소스를 가진 데이터베이스용 CO의 일반화입니다.이러한 리소스를 사용하면 읽기 전용 트랜잭션이 차단되거나 더 나은 성능을 위해 차단되지 않습니다.이러한 리소스를 활용하는 것은 오늘날 개체가 기록될 때마다 데이터베이스 개체의 새 버전을 생성하고 트랜잭션의 마지막 관련 버전(각 개체의)의 읽기 작업을 허용함으로써 동시성과 성능을 향상시키는 일반적인 방법입니다.MVCO는 One-copy-serializability(1SER 또는 1SR)를 의미합니다.이것은 멀티버전리소스의 시리얼라이저빌리티의 일반화입니다.CO와 마찬가지로 MVCO는 비블로킹이며 간섭 없이 관련 다중 버전 동시성 제어 메커니즘과 결합할 수 있습니다.MVCO 충돌에 대해 도입된 기본 이론에서는 동일한 자원의 다른 버전에 대해 일반화된다(이전 다중 버전 이론과는 다르다).다른 버전에서는 충돌하는 작업에 대한 일반적인 정의를 유지하면서 시간순서가 버전 순서로 대체되거나 반대로 표시될 수 있습니다.일반 및 증강 충돌 그래프에 대한 결과는 변경되지 않으며, CO와 마찬가지로 단일 버전과 다중 버전 리소스가 모두 포함된 혼합 환경(현재 단일 버전은 다중 버전의 특수한 경우)에 분산 MVCO 적용 알고리즘이 존재합니다.CO의 경우 MVCO 알고리즘은 추가적인 통신 오버헤드를 수반하지 않고 (수정되지 않은) 원자 커밋 프로토콜 메시지만 필요로 합니다.잠금 기반 글로벌 교착 상태는 투표 교착 상태로 변환되어 자동으로 해결됩니다.CO와 유사하게 다음과 같은 사항이 있습니다.

• MVCO와 글로벌 원카피 연속성 정리

1. 싱글버전과 멀티버전 데이터베이스가 혼재하는 멀티베이스 환경에서 모든 Autonomous 데이터베이스 시스템(또는 트랜잭션오브젝트)의 MVCO 준거는 글로벌한 One-Copy-Serializability(1SER)를 보증하기 위한 필수 조건입니다.
2. 모든 데이터베이스 시스템의 MVCO 준거는 글로벌 1SER를 보증하기 위한 충분한 조건입니다.
3. 잠금 기반 글로벌 교착 상태는 자동으로 해결됩니다.

코멘트:이제 CO 준거 싱글버전 데이터베이스 시스템도 자동으로 MVCO 준거가 됩니다.

MVCO는 ECO(MVECO)의 일반화를 채택하도록 더욱 일반화할 수 있다.

예: CO 기반 스냅샷 분리(COSI)

CO 기반 스냅샷 격리(COSI)는 스냅샷 격리(SI)와 MVCO의 교차점입니다.SI는 성능이 우수하고 여러 측면에서 직렬화 가능성(1SER)과 유사하기 때문에 널리 사용되는 다중 버전 동시성 제어 방법입니다.위에서 설명한 MVCO에 대한 (Raz 1993b)의 이론은 SI의 충돌을 직렬화하기 위해 SI의 충돌을 분석하기 위해 (Fekete et al. 2005) 및 SI에 관한 기타 기사(예: (Cahill et al. 2008),^[8] 또한 스냅샷 격리를 직렬화 및 참조를 참조하십시오.(Cahill et al. 2008), 시리얼화 가능한 스냅샷 분리(시리얼화 가능)에 제시된 방법SI)의 낮은 오버헤드 수정은 SI에 비해 우수한 성능 결과를 제공하며, 직렬화 적용에 대한 단점은 적습니다.다른 방법은 SI를 MVCO(COSI)와 결합함으로써 SI를 비교적 낮은 오버헤드로 직렬화할 수 있도록 하는데, 이는 일반 CO 알고리즘을 단일 버전 메커니즘과 결합하는 것과 유사하다.게다가 MVCO 준거의 COSI를 조합하는 것으로써, COSI 준거의 데이터베이스 시스템을 상호 운용해, CO솔루션에 투과적으로 참가시켜 분산/글로벌의 시리얼라이제빌리티를 실현할 수 있습니다(아래를 참조).오버헤드 외에도 프로토콜의 동작을 정량적으로 비교해야 합니다.한편, 시리얼 가능한 모든 SI 스케줄은 트랜잭션을 중단하지 않고 COSI에 의해 MVCO(필요에 따라 가능한 커밋 지연)로 만들 수 있습니다.한편, 시리얼 대응SI는 시리얼화 가능한 SI 스케줄에서도 일정 비율의 트랜잭션을 불필요하게 중단하고 재시작하는 것으로 알려져 있습니다.

CO와 CO의 변형은 글로벌 시리얼라이저빌리티를 위해 투과적으로 상호 운용 가능

CO 및 CO의 변형(위의 SS2PL, SCO, OCO, ECO, MVCO 등)을 통해 글로벌 시리얼라이제빌리티는 원자 커밋 프로토콜 기반의 분산 알고리즘을 통해 달성됩니다.CO 및 CO의 모든 변형에 대해 원자력 약정 프로토콜은 글로벌 증강(따라서 일반) 충돌 그래프에서 글로벌 주기(즉, 글로벌 데이터 구조 구현 필요 없음)를 제거하기 위한 수단이다.2개 이상의 데이터베이스에 호환되지 않는 로컬 커밋 순서(글로벌 부분 순서가 각각의 로컬 부분 순서를 함께 포함할 수 없는 경우) 또는 데이터 액세스 잠금 관련 투표 교착 상태(글로벌 확장 충돌 그래프에 글로벌 사이클을 암시하고 표가 누락됨)의 경우 원자 커밋 프로토콜은 이러한 c를 파괴한다.미정의 트랜잭션을 중단하는 것으로, 이 트랜잭션을 중단합니다(위의 분산 CO 알고리즘 참조).다양한 변형 간의 차이는 로컬 수준(참여 데이터베이스 시스템 내)에서만 존재합니다.모든 변종의 각 로컬 CO 인스턴스는 로컬 커밋 순서 내에서 모든 글로벌 트랜잭션(두 개 이상의 데이터베이스에 걸친 트랜잭션)의 위치를 결정하기 위해, 즉 원자 커밋 프로토콜에서 로컬에서 트랜잭션이 투표될 차례가 언제인지 결정하기 위해 동일한 역할을 가진다.따라서, 모든 CO 변종들은 원자 투입에 관해 동일한 행동을 보인다.이는 모두 원자적인 커밋(일반적으로 서비스로 제공되는 동일한 소프트웨어 인터페이스 사용, 일부는 2단계 커밋 프로토콜(예를 들어 X/Open XA)에 대해 이미 표준화되어 있음)을 통해 상호 운용이 가능하며 모든 분산 환경에서 투명하게 사용할 수 있음을 의미합니다(각 CO 바리안트 인스턴스).e는 관련된 로컬 동시성 제어 메커니즘 유형과 관련될 수 있습니다).

요약하면 단일 글로벌트랜잭션은 (각 데이터베이스에서 프로세스를 동시에 실행하고 각 데이터베이스 내의 로컬트랜잭션 및 기타 글로벌트랜잭션과 동시에 실행하면서) 다른 CO바리안트를 사용할 수 있는 데이터베이스에 동시에 참여할 수 있습니다.원자 커밋 프로토콜은 CO와 무관하며, 다양한 CO 변형을 구별하지 않는다.증강된 글로벌컨플릭트그래프로 생성되는 모든 글로벌사이클은 다른 CO바리안트의 데이터베이스에 걸쳐서 단일 CO바리안트 환경과 동일한 방법으로 원자적인 커밋에 의해 해결되는 투표 교착 상태를 생성할 수 있습니다.로컬 사이클(현재는 구체화 및 비실체화 충돌이 혼합되어 직렬화 및 데이터 액세스 잠금 교착 상태에 모두 관련됨, 예를 들어 SCO)은 로컬(각각의 변형 인스턴스 자체의 로컬 메커니즘에 따라 각각 해결됩니다.

투표 순서(VO 또는 Generalized CO(GCO; Generalized CO); Raz 2009)는 CO와 그 모든 종류의 조합으로 유용한 개념이자 글로벌 시리얼라이제빌리티 기술입니다.VO에 준거하기 위해서는 로컬시리얼라이제빌리티(가장 일반적인 형식, 정류성 기반, 멀티버전 포함)와 투표순서 전략(로컬 우선순위에 의한 투표)이 필요합니다.

CO와 CO의 변형에 대한 결과를 종합하면 다음과 같은 결론을 얻을 수 있다.

• CO Variants 상호운용성 정리

1. 각 데이터베이스 시스템(트랜잭션 오브젝트)이 CO 바리안트 속성(VO 준거)에 준거하고 있는 멀티 데이터베이스 환경에서는 모든 글로벌 트랜잭션이 CO 바리안트 데이터베이스에 동시에 참여할 수 있으며 글로벌 시리얼라이제빌리티(글로벌 시리얼라이제빌리티를 위한 충분한 조건)가 보증됩니다.copy-serializability(1SER), 멀티버전 데이터베이스가 존재하는 경우.
2. 모든 데이터베이스 시스템에서 로컬(데이터베이스 시스템에 대한) 동시성 제어 정보만 사용하는 경우(각각은 일반화된 자율성 속성, 일반화된 자율성을 가지고 있음), 각 시스템의 CO 바리안트 속성(VO 컴플라이언스) 준수는 글로벌 시리얼라이제빌리티(및 글로벌 1SER)를 보증하기 위한 필수 조건입니다.위반될 수 있습니다.)
3. 또한 이러한 환경에서 데이터 액세스 잠금 관련 글로벌 교착상태는 자동으로 해결된다(각 교착상태는 증강된 충돌그래프(즉, 투표 교착상태)의 글로벌 사이클에 의해 생성된다). 즉, 적어도 하나의 데이터 액세스 잠금(비실체화된 충돌)과 2개의 데이터베이스 시스템을 포함한다.따라서 규제 내의 사이클이 아니다.ar conflict 그래프는 시리얼라이저빌리티에 영향을 주지 않습니다).

레퍼런스

• 레즈, Yoav(8월 1992년),"원리 몰입 발주 또는 의한 Serializability의 Heterogeneous 환경 다중 자치 자원 관리 부장 이용한 원자력 의무 이행"(PDF), 제18국제 회의 초대형 데이터 기지, 캐나다 밴쿠버를 대신하여 서명함에 회보. 292–312(또한 DEC-TR 841년, 디지털 이큅먼트 사rporation, 1990년 11월)
• Raz, Yoav (September 1994), "Serializability by Commitment Ordering", Information Processing Letters, 51 (5): 257–264, doi:10.1016/0020-0190(94)90005-1
• Raz, Yoav (June 2009), Theory of Commitment Ordering: Summary, retrieved November 11, 2011
• Raz, Yoav (November 1990), On the Significance of Commitment Ordering (PDF), Digital Equipment Corporation
• Yoav Raz (1991a): US patents 5,504,899 (ECO) 5,504,900 (CO) 5,701,480 (MVCO)
• Yoav Raz (1991b): "The Commitment Order Coordinator (COCO) of a Resource Manager, or Architecture for Distributed Commitment Ordering Based Concurrency Control", DEC-TR 843, Digital Equipment Corporation, December 1991.
• Yoav Raz (1991c): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", DEC-TR 844, December 1991.
• Yoav Raz (1993a): "Extended Commitment Ordering or Guaranteeing Global Serializability by Applying Commitment Order Selectivity to Global Transactions." Proceedings of the Twelfth ACM Symposium on Principles of Database Systems (PODS), Washington, DC, pp. 83-96, May 1993. (also DEC-TR 842, November 1991)
• Yoav Raz (1993b): "Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources." Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Vienna, Austria, pp. 189-198, April 1993. (also DEC-TR 853, July 1992)

각주

외부 링크

• Yoav Raz의 커밋 주문 페이지