2상 잠금

Two-phase locking
이 기사는 동시성 통제에 관한 것이다. 분산 트랜잭션 내에서 컨센서스를 커밋하려면 2단계 커밋 프로토콜을 참조하십시오.

데이터베이스와 트랜잭션 처리에서 2상 잠금(2PL)은 연속성을 보장하는 동시성 제어 방식이다.[1][2] 데이터베이스 트랜잭션 일정(이력)의 결과 집합의 이름이기도 하다. 프로토콜은 거래에 의해 데이터에 적용되는 잠금장치를 사용하며, 이는 거래 수명 동안 다른 거래가 동일한 데이터에 접근하는 것을 차단(정지 신호로 해석)할 수 있다.

2PL 프로토콜에 의해 다음과 같은 두 단계로 잠금장치를 적용하고 제거한다.

  1. 확장 단계: 잠금 장치를 획득하고 잠금 장치를 해제하지 않는다.
  2. 수축 단계: 잠금이 해제되고 잠금이 획득되지 않는다.

두 가지 유형의 잠금장치가 기본 프로토콜에 의해 사용된다. 공유 및 배타적 잠금. 기본 프로토콜의 개선은 더 많은 잠금 유형을 사용할 수 있다. 프로세스를 차단하는 잠금장치를 사용하면 2PL은 두 개 이상의 트랜잭션을 상호 차단하여 발생하는 교착 상태가 발생할 수 있다.

데이터 액세스 잠금

잠금(lock)은 기본 유형의 데이터 항목, 데이터베이스의 행 또는 메모리 페이지와 같은 공유 리소스와 연결된 시스템 개체다. 데이터베이스에서 데이터베이스 오브젝트에 대한 잠금(데이터 액세스 잠금)은 오브젝트에 접근하기 전에 트랜잭션에 의해 획득되어야 할 수 있다. 잠금 장치를 올바르게 사용하면 공유 리소스에 대한 다른 동시 트랜잭션의 원치 않거나 부정확하거나 일관되지 않은 작업을 방지할 수 있다. 한 거래에서 취득한 기존 잠금장치가 있는 데이터베이스 객체에 다른 거래로 접속할 필요가 있는 경우, 해당 객체에 대한 기존 잠금과 의도된 접근의 유형을 시스템에 의해 점검한다. 기존 잠금 유형이 이러한 특정 동시 액세스 시도 유형을 허용하지 않는 경우, 미리 정의된 계약/구성표에 따라 액세스를 시도하는 트랜잭션이 차단된다. 실제로, 객체에 대한 자물쇠는 객체에 대한 거래의 작동을 직접적으로 차단하는 것이 아니라, 이 작업을 수행하기 전에 해당 거래에서 보유/소유할 필요가 있는 동일한 객체에 대한 다른 잠금장치를 획득하는 것을 차단한다. 따라서 잠금 메커니즘으로 필요한 작동 차단은 적절한 잠금 차단 방식에 의해 제어되며, 이는 어떤 유형의 잠금 장치 차단을 나타내는 것인지 나타낸다.

다음과 같은 두 가지 주요 유형의 잠금 장치가 사용된다.

  • 쓰기 잠금(독점 잠금)은 트랜잭션에 의해 데이터베이스 개체와 연결된다(터미널학: 이 객체를 쓰기 전에 "거래가 객체를 잠근다" 또는 "이 객체를 잠근다").
  • 읽기 잠금(공유 잠금)은 이 개체를 읽기 전에 트랜잭션에 의해 데이터베이스 개체와 연결된다(상태 검색).

이러한 잠금 유형 간의 공통 상호작용은 다음과 같은 차단 동작으로 정의된다.

  • 데이터베이스 개체의 기존 쓰기 잠금은 각 쓰기 잠금이 다른 트랜잭션에 의해 획득되는 것을 차단하여 다른 트랜잭션에 의해 동일한 개체(이미 요청/발행된)에 대해 의도된 쓰기를 차단한다. 두 번째 쓰기 잠금은 획득되며, 요청된 개체의 쓰기는 기존 쓰기 잠금이 해제된 후에 이루어진다(실제화).
  • 쓰기 잠금은 각 읽기 잠금을 차단하여 다른 트랜잭션에서 읽으려는(이미 요청/발행된)을 차단한다.
  • 읽기 잠금은 각 쓰기 잠금을 차단하여 다른 트랜잭션에 의해 의도된 쓰기를 차단한다.
  • 읽기 잠금은 다른 거래에서 의도한 읽기를 차단하지 않는다. 의도된 읽기의 각 읽기 잠금은 의도된 읽기를 요청한 직후에 획득된다(이전 읽기와 공유됨). 그리고 의도된 읽기 자체가 이루어진다.

이러한 주요 잠금 유형의 여러 가지 변형과 정교함이 존재하며, 각각의 차단 동작의 변형이 있다. 첫 번째 잠금 장치가 다른 잠금을 차단하면 두 개의 잠금은 비호환이라고 하며, 그렇지 않으면 잠금 장치가 호환된다. 종종 잠금 유형 차단 상호작용은 잠금 호환성 표에 의해 기술 문서에 제시된다. 다음은 일반적인 주요 잠금 유형과 관련된 예:

호환성 테이블 잠금
잠금유형 자물쇠를 채우다 글씨를 잠그다
자물쇠를 채우다 ✔ X
글씨를 잠그다 X X
✔은 호환성을 나타냄
X는 비호환성을 나타낸다. 즉, 물체의 첫 번째 유형(왼쪽 열)의 잠금이 두 번째 유형(맨 위 행)의 잠금을 동일한 개체(다른 트랜잭션에 의해)에서 획득하는 것을 차단하는 경우. 개체는 일반적으로 각 잠금 장치를 사용하여 요청된(트랜잭션에 의해) 대기 중인 작업 대기열을 가진다. 기존 차단 잠금이 개체에서 제거되는 즉시 큐의 첫 번째 차단된 작동 잠금을 획득한 후 각각의 작동이 실행된다. 대기열의 작동을 위한 잠금장치가 기존 잠금장치에 의해 차단되지 않는 경우(동일한 물체에 여러 개의 호환 잠금장치가 동시에 존재할 수 있음) 즉시 획득된다.
설명: 일부 간행물에서 표 항목은 단순히 "호환성" 또는 "호환성" 또는 "예" 또는 "아니오"로 표시된다.

2상 잠금 및 특수 케이스

2상 잠금

2상 잠금 프로토콜에 따르면, 거래는 거래의 실행 중 두 개의 뚜렷하고 연속적인 단계로 그 잠금을 처리한다.

  1. 확장 단계(일명 성장 단계): 잠금 장치를 획득하고 잠금 장치를 해제하지 않는다(잠금 수는 증가만 할 수 있다).
  2. 수축 단계(일명 계약 단계): 잠금을 해제하고 잠금을 획득하지 않는다.

두 단계 잠금 규칙은 다음과 같이 요약할 수 있다: 잠금이 해제된 후에는 잠금을 획득하지 않는다. 이 규칙을 준수하는 트랜잭션이 있는 스케줄에 대해 연속성 속성이 보장된다.

일반적으로 1단계 종료 시 거래에 대한 명시적 지식이 없으면 거래 처리가 완료되고 커밋이 요청된 경우에만 안전하게 결정된다. 이 경우 모든 잠금장치를 한 번에 해제할 수 있다(2상).

보수 2상 잠금

2PL과 C2PL의 차이점은 C2PL의 거래는 거래가 시작되기 전에 그들이 필요로 하는 모든 잠금장치를 획득한다는 것이다. 이는 이미 일부 잠금 장치를 보유하고 있는 거래가 다른 잠금 장치를 기다리는 것을 차단하지 않도록 하기 위함이다. 보수적인 2PL은 교착상태를 방지한다.

엄격한 2상 잠금

S2PL 프로토콜을 준수하기 위해, 트랜잭션은 2PL을 준수하고, 종료된 후에만 쓰기(배타적) 잠금장치를 해제할 필요가 있다. 즉, 커밋되거나 중단된다. 한편, 2단계에서는 판독(공유) 잠금장치가 정기적으로 해제된다. 이 프로토콜은 병목 현상을 일으키기 때문에 B-tree에서는 적절하지 않다(B-tree는 항상 상위 루트로부터 검색을 시작한다).[citation needed]

강력 엄격한 2상 잠금

또는 엄격한 스케줄링 또는 엄격한 2상 잠금

강력하게 엄격한 2상 잠금(SS2PL)을 준수하기 위해 잠금 프로토콜은 트랜잭션이 종료된 후에만, 즉 실행(준비)을 완료하고 커밋되거나 중단된 후에만 트랜잭션에 의해 적용되는 쓰기(배타적) 잠금과 읽기(공유) 잠금을 모두 해제한다. 이 프로토콜은 S2PL 규칙도 준수한다. SS2PL을 준수하는 거래는 거래의 전체 실행 기간을 지속하는 1단계와 2단계(또는 퇴보 단계 2)가 없는 것으로 볼 수 있다. 따라서 실제로 단 하나의 위상만이 남아 있으며, 2PL로부터 개념의 역사적 전개에 의해 2PL이 슈퍼클래스라는 명칭의 '2상'이 여전히 사용되고 있는 것으로 보인다. 일람표의 SS2PL 속성은 엄격성이라고도 한다. 또한 이 속성을 가진 일정의 클래스의 이름이기도 하며, SS2PL 일정을 "고정 일정"이라고도 한다. "고정성"이라는 용어는 어떤 (잠금) 메커니즘에도 독립적일 뿐만 아니라 "2상"이라는 불필요한 유산이 없다(원칙적으로 다른 차단 메커니즘을 사용할 수 있다). 속성의 각각의 잠금 메커니즘은 때때로 엄격한 2PL로 언급된다.

SS2PL은 S2PL의 특별한 경우로서, 즉 SS2PL 스케줄 클래스는 S2PL의 적절한 하위 클래스(모든 SS2PL 스케줄도 S2PL 스케줄이지만 SS2PL 스케줄이 아닌 S2PL 스케줄이 존재함)이다.

SS2PL은 1970년대 초반부터 대부분의 데이터베이스 시스템에서 선택한 동시성 제어 프로토콜이다. 여러 상황에서 효과적인 메커니즘으로 입증되었으며, 연속성 외에도 효율적인 데이터베이스 복구에 중요한 엄격성(Cascadless Recoverability의 특별한 경우), CO 기반 연속성과 gl을 분산한 분산 환경에 참여하는 CO(Committion Ordering)를 제공한다.부계 연속성 솔루션을 채택하였다. CO의 하위 집합으로서 분산형 SS2PL의 효율적인 구현은 분산형 잠금 관리자(DLM) 없이 존재하는 반면 분산형 교착상태(아래 참조)는 자동으로 해결된다. 다중 데이터베이스 시스템에 고용된 SS2PL이 전지구적 연속성을 보장한다는 사실은 CO가 발견되기 몇 년 전부터 알려져 왔지만, CO를 통해서만 글로벌 연속성을 유지하는 데 있어 원자력이용 프로토콜의 역할에 대한 이해와 더불어 자동 분산 교착상태 해결의 관찰(디타일 참조)이 이루어졌다.d 분산 SS2PL)의 예 사실, SS2PL은 2PL의 하위 집합보다 더 중요하며, 이는 단순한 연속성 메커니즘으로 구성되는 것 외에(그러나 CO에 의해서도 연속성이 함축되어 있음) SS2PL을 다른 중요한 품질로 제공하는 것으로 알려져 있지 않다. 일반적으로 2PL 형식뿐만 아니라 Strongness와 결합되었을 때, 즉 Strong 2PL (S2PL)은 실제에 사용되는 것으로 알려져 있지 않다. 인기 있는 SS2PL은 2PL과 S2PL과 같이 "1단계의 종료"를 표시할 필요가 없으므로 구현이 더 간단하다. 또한, 일반 2PL과 달리 SS2PL은 위에서 언급한 바와 같이 유용한 엄격성 및 의무 주문 속성을 제공한다.

SS2PL의 많은 변형들이 존재하며, 거래 중 잠금형식의 변경의 경우를 포함하여 다양한 상황에서 다양한 의미론들을 가지고 다양한 잠금형태를 사용한다. 주목할 만한 것은 다중 세분성 잠금을 사용하는 변형이다.

설명:

  1. SS2PL 대 S2PL: 둘 다 연속성과 엄격성을 제공한다. S2PL은 SS2PL의 슈퍼클래스이기 때문에 원칙적으로 더 많은 동시성을 제공할 수 있다. 그러나 일반적으로 동시성 우위성은 실질적으로 주목되지 않으며(S2PL의 경우 사실상 초기 잠금 해제가 많지 않은 상태에서 양쪽 모두에 대해 정확히 동일한 잠금이 존재하며), 거래 종료와 별도로 S2PL의 단계 종료 1 메커니즘을 다루는 오버헤드는 정당화되지 않는다. 또한 SS2PL은 약속 순서를 제공하지만 S2PL은 그렇지 않다. 이것은 S2PL보다 SS2PL의 선호를 설명한다.
  2. 특히 1990년 이전이지만, 많은 기사와 서적에서, 예를 들어 (Bernstein et al. 1987, 페이지 59),[1] "Strct 2PL"(S2PL)이라는 용어는 SS2PL의 프로토콜인 잠금 프로토콜 "거래 종료 후에만 모든 잠금 해제"에 의해 자주 정의되어 왔다. 따라서 "Strct 2PL"은 SS2PL 프로토콜에 의해 생성된 클래스보다 큰 Strongness와 2PL의 교차점 이름이 될 수 없다. 이로 인해 혼란이 야기되었다. SS2PL의 새로운 명칭인 엄격함과 2PL의 교차점으로서 S2PL을 명시적으로 정의하고, S2PL과 SS2PL 등급의 명시적인 구분을 통해, 기사(Breitbart et al. 1991년)[3]와 (Raz 1992년)[4]는 혼란을 해소하고자 하였다. 첫 번째 명칭은 "강성"과 두 번째 "SS2PL"이다.
  3. SS2PL보다 더 일반적인 속성(일정 슈퍼클래스), 엄격한 약속 순서(Strong CO 또는 SCO)이 존재하며, 연속성, 엄격성 및 CO를 모두 제공하며 잠금 오버헤드가 유사하다. SS2PL과 달리, SCO는 읽기-쓰기 충돌(읽기 잠금은 쓰기 잠금 획득을 차단하지 않으며, SCO와 SS2PL 모두 쓰기-읽기 및 쓰기-쓰기 충돌에 대해 동일한 동작을 가지고 있음)을 지연된 커밋의 비용으로 차단하지 않으며, 이러한 충돌 유형 SCO는 SS2보다 평균 트랜잭션 완료 시간이 짧고 성능이 우수하다.PL.[5] SS2PL은 위의 잠금 호환성 표를 준수하지만 SCO에는 다음 표가 있다.
SCO에 대한 잠금 호환성
잠금유형 자물쇠를 채우다 글씨를 잠그다
자물쇠를 채우다 X
글씨를 잠그다 X X
SCO가 트랜잭션 엔드의 모든 잠금을 해제하고 2PL 잠금 규칙을 준수하지만, 잠금 호환성 테이블이 다르기 때문에 SCO가 2PL의 하위 집합이 아니라는 점에 유의하십시오. SCO는 1단계에서 두 트랜잭션 간에 구체화된 읽기-쓰기 충돌을 허용하며, 2PL은 1단계에서 허용하지 않는다(Serializeability에서 구체화된 충돌에 대한 참조). 반면 2PL은 SCO가 전혀 허용하지 않는 2단계에서 다른 구체화된 갈등 유형을 허용한다. 이는 일정 클래스 2PL과 SCO가 비교할 수 없다는 것을 의미한다(즉, 다른 클래스를 포함하는 클래스는 없음).

요약 - 클래스 간의 관계

클래스 제약 예약: 클래스 A에서 클래스 B까지의 화살표는 클래스 A가 B를 엄격하게 포함하고 있음을 나타내며, 클래스 사이에 지시된 경로가 없다는 것은 클래스가 비교할 수 없다는 것을 의미한다. 다른 거래에서 특정 사건이 발생할 때까지 거래의 데이터 액세스 운영을 차단함으로써만 강제할 수 있다면, 부동산은 본질적으로 차단되고 있다. (Raz 1992년)

공통 스케줄이 있는 두 개의 스케줄 클래스(스케줄의 각 속성으로 정의) 사이에 다른 스케줄이 포함되거나(같지 않으면 엄격히 포함) 비할 수 없는 스케줄 클래스. 2PL 클래스와 기타 주요 일정 클래스 간의 격납 관계는 다음 도표에 요약된다. 2PL과 그 하위 클래스는 본질적으로 차단되고 있으며, 이는 해당 클래스에 대해 낙관적인 구현이 존재하지 않는다는 것을 의미한다(그리고 "Optimistic 2PL"이 언급될 때마다 sc도 포함하는 클래스와 다른 메커니즘을 가리킨다).2PL 등급이 아닌 위험회피).

2PL의 교착 상태

블록 데이터 액세스 작업 잠금 거래 간 상호차단은 교착상태에 빠지며, 이러한 거래의 실행이 정체되고, 완료에 도달할 수 없다. 따라서 이러한 트랜잭션의 실행을 완료하고 관련 컴퓨팅 리소스를 공개하려면 교착 상태를 해결해야 한다. 교착상태는 우선 순위 그래프에서 차단을 하지 않고 발생할 수 있는 잠재적 주기를 반영하는 것이다. 교착상태는 그러한 잠재적 주기와 관련된 거래를 중단시키고 그 주기를 중단함으로써 해결된다. 대기 그래프(잠금 때문에 차단된 충돌 그래프, 차단된 작동으로 인해 데이터베이스에서 구체화되지 않은 충돌은 우선 순위 그래프에 반영되지 않고 연속성에 영향을 주지 않음)를 사용하여 탐지되는 경우가 많은데, 이 그래프는 어떤 트랜잭션이 어떤 거래를 "대기 중"인지, 싸이(cy)를 나타낸다.clear는 교착 상태를 의미한다. 사이클당 하나의 트랜잭션을 중단하면 사이클을 중단하기에 충분하다. 교착해결로 거래가 중단되었다면, 다음에 무엇을 할 것인가는 어플리케이션에 달려 있다. 일반적으로 애플리케이션은 거래를 처음부터 다시 시작하지만, 다른 교착 상태를 야기하지 않기 위해 다른 트랜잭션을 완료하기에 충분한 시간을 주기 위해 이 작업을 지연시킬 수 있다.[6]

분산 환경에서는 원자 약속 프로토콜, 일반적으로 2상 커밋(2PC) 프로토콜이 원자성을 위해 사용된다. 2PC 참여자(즉, 각 데이터 오브젝트는 단일 2PC 참여자에 의해 제어됨)로 분할된 복구 가능한 데이터(거래 통제 하에 있는 데이터)가 분산(글로벌) 교착상태, 2PC 참여자 2명 이상이 참여하는 교착상태는 다음과 같이 자동으로 해결된다.

SS2PL이 분산 환경에서 효과적으로 사용될 경우, 잠금으로 인한 글로벌 교착상태는 2PC에서 투표 데드록을 생성하고 2PC에 의해 자동으로 해결된다(CO 참조), 글로벌 사이클에 의한 투표 데드록의 정확한 특성화, CO 기사 이외에는 이를 알 수 없는 것으로 알려져 있다). 일반적인 2PL의 경우, 글로벌 교착상태는 분산 트랜잭션의 1단계 엔드 동기화 포인트 프로토콜("투표"에 의해 달성된다(로컬 1단계 엔드를 통지함), 분산 트랜잭션의 참가자에게 결정 지점과 동일한 방식으로 전파됨)에 의해 글로벌 교착상태도 자동으로 해결된다. 원자력의 약속; CO의 의사결정 지점과 유사하게, 2PL의 충돌 작동은 1단계 종료 동기화 지점 이전에 일어날 수 없으며, 글로벌 데이터 액세스 교착 상태의 경우 동일한 결과로 투표 데드락(잠금 기반 글로벌 교착 상태)은 프로토콜 중단에 의해 자동으로 해결된다.e 트랜잭션 관련, 투표 누락, 일반적으로 시간 초과 사용).

설명:

원자력이용 프로토콜(예: 2PC) 참여자들 사이에 데이터가 분할될 때, 데이터베이스 연구 문헌에서 자동 글로벌 교착상태 해결은 간과되어 왔으나, 그러한 시스템의 교착상태는 상당히 집중적인 연구 영역이었다.
  • CO와 그것의 특수한 경우 SS2PL의 경우,원자핵약정프로토콜에 의한 자동해결은 카이 트리아 오닐 기사에서만 주목되어 왔다. 그러나 실제로 많은 경우, 전용 해결 메커니즘에 의해 전지구적 교착 상태가 매우 드물게 감지되는 경우가 예상할 수 있는 것보다 적다("왜 우리는 전지구적 교착 상태를 그렇게 적게 보는가?"). 그 이유는 자동으로 해결되어 메커니즘에 의해 처리 및 마운트 해제되지 않는 교착 상태 때문일 것이다.
  • 일반적으로 2PL의 경우(필수사항)단계 종료 1동기화 포인트 프로토콜에 의한 자동 해결(원자약정 프로토콜과 동일한 투표 메커니즘을 가지고 있으며, 투표 교착 상태 시 동일한 투표 처리 누락으로 글로벌 교착 상태 해결이 초래됨)은 오늘(2009년)까지 언급되지 않았다. 실질적으로 원자력 커밋 프로토콜 외에 위상 1의 종료 동기화가 필요하지 않은 특수 케이스 SS2PL만 사용된다.
복구 가능한 데이터가 원자력 약속 프로토콜 참여자들 사이에 분할되지 않는 분산 환경에서는 그러한 자동 해결이 존재하지 않으며, 분산된 교착상태는 전용 기법으로 해결할 필요가 있다.

참고 항목

참조

  1. ^ a b 필립 A. 번스타인, 바소스 하질라코스, 네이선 굿맨(1987년): 데이터베이스 시스템의 동시성 제어 및 복구, 애디슨 웨슬리 출판사, ISBN0-201-10715-5
  2. ^ Gerhard Weikum, Gottfried Vossen(2001): 트랜잭션 정보 시스템, Exvier, ISBN 1-55860-508-8
  3. ^ Yuri Breitbart, Dimitrios Georgakopoulos, Marek Russinkiewicz, Abraham Silbershatz(1991): "엄격한 트랜잭션 스케줄링", IEEEE Transactions on Software Engineering (TSE), 1991년 9월, 제9권, 제9권 954-960권, 제960권, ISSN 0098-5589호
  4. ^ Yoav Raz (1992): "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment" Archived 2007-05-23 at the Wayback Machine (PDF), Proceedings of the Eighteenth International Conference on Very Large Data Bases (VLDB), pp. 292-312, Vancouver, Can1992년 8월 ISBN 1-55860-151-1(DEC-TR 841, 디지털 장비 주식회사, 1990년 11월)
  5. ^ Yoav Raz(1991) : "잠금 기반 엄격한 약속 명령 또는 잠금 기반 리소스 관리자에서의 동시성 향상 방법", DEC-TR 844, 1991년 12월.
  6. ^ 거래 처리 원리: ISBN 9780080948416; 6장 152페이지