분산 DBMS-교착 상태 처리

이 장에서는 데이터베이스 시스템의 교착 상태 처리 메커니즘에 대해 설명합니다. 중앙 집중식 및 분산 데이터베이스 시스템 모두에서 교착 상태 처리 메커니즘을 연구합니다.

교착 상태는 무엇입니까?

교착 상태는 각 트랜잭션이 다른 트랜잭션에 의해 잠긴 데이터 항목을 기다리고있을 때 두 개 이상의 트랜잭션이있는 데이터베이스 시스템의 상태입니다. 교착 상태는 그래프 대기의 주기로 표시 될 수 있습니다. 정점이 트랜잭션을 나타내고 가장자리가 데이터 항목을 기다리는 것을 나타내는 방향 그래프입니다.

예를 들어, 다음 그래프 대기에서 트랜잭션 T1은 T3에 의해 잠긴 데이터 항목 X를 기다리고 있습니다. T3은 T2에 의해 잠긴 Y를 기다리고 있고 T2는 T1에 의해 잠긴 Z를 기다리고 있습니다. 따라서 대기주기가 형성되고 어떤 트랜잭션도 실행을 계속할 수 없습니다.

중앙 집중식 시스템의 교착 상태 처리

교착 상태 처리에 대한 세 가지 고전적인 접근 방식이 있습니다.

교착 상태 방지.
교착 상태 방지.
교착 상태 감지 및 제거.

세 가지 접근 방식은 모두 중앙 집중식 및 분산 데이터베이스 시스템에 통합 될 수 있습니다.

교착 상태 방지

교착 상태 방지 접근 방식은 어떤 트랜잭션도 교착 상태로 이어지는 잠금을 획득하는 것을 허용하지 않습니다. 규칙은 둘 이상의 트랜잭션이 동일한 데이터 항목을 잠그도록 요청하면 그중 하나만 잠금을 부여 받는다는 것입니다.

가장 널리 사용되는 교착 상태 방지 방법 중 하나는 모든 잠금을 사전 획득하는 것입니다. 이 방법에서 트랜잭션은 실행을 시작하기 전에 모든 잠금을 획득하고 전체 트랜잭션 기간 동안 잠금을 유지합니다. 다른 트랜잭션에 이미 획득 한 잠금이 필요한 경우 필요한 모든 잠금을 사용할 수있을 때까지 기다려야합니다. 이 접근 방식을 사용하면 대기중인 트랜잭션이 잠금을 보유하고 있지 않기 때문에 시스템이 교착 상태가되는 것을 방지합니다.

교착 상태 방지

교착 상태 방지 접근 방식은 교착 상태가 발생하기 전에 처리합니다. 트랜잭션과 잠금을 분석하여 대기로 인해 교착 상태가 발생하는지 여부를 판별합니다.

이 방법은 다음과 같이 간략하게 설명 할 수 있습니다. 트랜잭션은 실행을 시작하고 잠그는 데 필요한 데이터 항목을 요청합니다. 잠금 관리자는 잠금이 사용 가능한지 확인합니다. 사용 가능한 경우 잠금 관리자가 데이터 항목을 할당하고 트랜잭션이 잠금을 획득합니다. 그러나 호환되지 않는 모드에서 다른 트랜잭션에 의해 항목이 잠긴 경우 잠금 관리자는 트랜잭션을 대기 상태로 유지하면 교착 상태가 발생하는지 여부를 테스트하는 알고리즘을 실행합니다. 따라서 알고리즘은 트랜잭션이 대기 할 수 있는지 또는 트랜잭션 중 하나가 중단되어야하는지 여부를 결정합니다.

이를 위해 두 가지 알고리즘이 있습니다. wait-die 과 wound-wait. 두 개의 트랜잭션 T1과 T2가 있다고 가정 해 보겠습니다. 여기서 T1은 이미 T2에 의해 잠긴 데이터 항목을 잠그려고합니다. 알고리즘은 다음과 같습니다-

Wait-Die− T1이 T2보다 오래된 경우 T1은 대기 할 수 있습니다. 그렇지 않고 T1이 T2보다 어린 경우 T1이 중단되고 나중에 다시 시작됩니다.
Wound-Wait− T1이 T2보다 오래된 경우 T2가 중단되고 나중에 다시 시작됩니다. 그렇지 않고 T1이 T2보다 어린 경우 T1은 대기 할 수 있습니다.

교착 상태 감지 및 제거

교착 상태 감지 및 제거 방법은 교착 상태 감지 알고리즘을 주기적으로 실행하고 교착 상태가있는 경우이를 제거합니다. 트랜잭션이 잠금 요청을 할 때 교착 상태를 확인하지 않습니다. 트랜잭션이 잠금을 요청하면 잠금 관리자는 잠금이 사용 가능한지 확인합니다. 사용 가능한 경우 트랜잭션은 데이터 항목을 잠글 수 있습니다. 그렇지 않으면 트랜잭션이 대기 할 수 있습니다.

잠금 요청을 부여하는 동안 예방 조치가 없기 때문에 일부 트랜잭션이 교착 상태가 될 수 있습니다. 교착 상태를 감지하기 위해 잠금 관리자는 주기적으로 wait-forgraph에주기가 있는지 확인합니다. 시스템이 교착 상태 인 경우 잠금 관리자는 각주기에서 희생 트랜잭션을 선택합니다. 피해자는 중단되고 롤백됩니다. 나중에 다시 시작했습니다. 피해자 선택에 사용되는 방법 중 일부는 다음과 같습니다.

가장 어린 거래를 선택하십시오.
데이터 항목이 가장 적은 트랜잭션을 선택하십시오.
최소한의 업데이트를 수행 한 트랜잭션을 선택하십시오.
재시작 오버 헤드가 가장 적은 트랜잭션을 선택하십시오.
두 개 이상의주기에 공통되는 거래를 선택하십시오.

이 접근 방식은 트랜잭션이 적고 잠금 요청에 대한 빠른 응답이 필요한 시스템에 주로 적합합니다.

분산 시스템의 교착 상태 처리

분산 데이터베이스 시스템의 트랜잭션 처리도 분산됩니다. 즉, 동일한 트랜잭션이 둘 이상의 사이트에서 처리 될 수 있습니다. 중앙 집중식 시스템에없는 분산 데이터베이스 시스템의 두 가지 주요 교착 상태 처리 문제는 다음과 같습니다.transaction location 과 transaction control. 이러한 문제가 해결되면 교착 상태 방지, 교착 상태 방지 또는 교착 상태 감지 및 제거를 통해 교착 상태를 처리합니다.

거래 장소

분산 데이터베이스 시스템의 트랜잭션은 여러 사이트에서 처리되며 여러 사이트에서 데이터 항목을 사용합니다. 데이터 처리량은 이러한 사이트간에 균일하게 분산되지 않습니다. 처리 기간도 다릅니다. 따라서 동일한 트랜잭션이 일부 사이트에서는 활성화되고 다른 사이트에서는 비활성화 될 수 있습니다. 두 개의 충돌하는 트랜잭션이 사이트에 있으면 그중 하나가 비활성 상태 일 수 있습니다. 이 조건은 중앙 집중식 시스템에서는 발생하지 않습니다. 이 문제를 트랜잭션 위치 문제라고합니다.

이 문제는 Daisy Chain 모델로 해결할 수 있습니다. 이 모델에서 트랜잭션은 한 사이트에서 다른 사이트로 이동할 때 특정 세부 정보를 전달합니다. 세부 정보 중 일부는 필요한 테이블 목록, 필요한 사이트 목록, 방문한 테이블 및 사이트 목록, 아직 방문하지 않은 테이블 및 사이트 목록, 획득 한 잠금 목록 (유형 포함)입니다. 트랜잭션이 커밋 또는 중단에 의해 종료 된 후 정보는 모든 관련 사이트로 전송되어야합니다.

거래 통제

트랜잭션 제어는 분산 데이터베이스 시스템에서 트랜잭션을 처리하는 데 필요한 사이트를 지정하고 제어하는 것과 관련이 있습니다. 거래를 처리 할 위치와 제어 중심을 지정하는 방법에 관한 많은 옵션이 있습니다.

하나의 서버를 제어의 중심으로 선택할 수 있습니다.
제어 중심은 한 서버에서 다른 서버로 이동할 수 있습니다.
제어 책임은 여러 서버에서 공유 할 수 있습니다.

분산 교착 상태 방지

중앙 집중식 교착 상태 방지와 마찬가지로 분산 교착 상태 방지 접근 방식에서는 트랜잭션이 실행을 시작하기 전에 모든 잠금을 획득해야합니다. 이것은 교착 상태를 방지합니다.

거래가 입력되는 지점이 관리 지점으로 지정됩니다. 제어 사이트는 항목을 잠그기 위해 데이터 항목이있는 사이트로 메시지를 보냅니다. 그런 다음 확인을 기다립니다. 모든 사이트가 데이터 항목을 잠근 것을 확인하면 트랜잭션이 시작됩니다. 사이트 또는 통신 링크가 실패하면 트랜잭션이 복구 될 때까지 기다려야합니다.

구현은 간단하지만이 접근 방식에는 몇 가지 단점이 있습니다.

잠금을 사전 획득하려면 통신 지연에 오랜 시간이 필요합니다. 이것은 거래에 필요한 시간을 증가시킵니다.
사이트 또는 링크 장애가 발생한 경우 사이트가 복구 될 수 있도록 트랜잭션이 오래 기다려야합니다. 한편 실행중인 사이트에서는 항목이 잠겨 있습니다. 이로 인해 다른 트랜잭션이 실행되지 않을 수 있습니다.
제어 사이트가 실패하면 다른 사이트와 통신 할 수 없습니다. 이러한 사이트는 잠긴 데이터 항목을 잠금 상태로 계속 유지하므로 차단됩니다.

분산 된 교착 상태 방지

중앙 집중식 시스템에서와 마찬가지로 분산 교착 상태 방지는 발생 전에 교착 상태를 처리합니다. 또한 분산 시스템에서 트랜잭션 위치 및 트랜잭션 제어 문제를 해결해야합니다. 거래의 분산 특성으로 인해 다음과 같은 충돌이 발생할 수 있습니다.

동일한 사이트에있는 두 거래 간의 충돌.
서로 다른 사이트에서 두 거래 간의 충돌.

충돌이 발생하면 트랜잭션 중 하나가 중단되거나 분산 대기 다이 또는 분산 상처 대기 알고리즘에 따라 대기 할 수 있습니다.

두 개의 트랜잭션 T1과 T2가 있다고 가정 해 보겠습니다. T1은 사이트 P에 도착하여 해당 사이트에서 이미 T2에 의해 잠긴 데이터 항목을 잠그려고합니다. 따라서 사이트 P에 충돌이 있습니다. 알고리즘은 다음과 같습니다.

Distributed Wound-Die
- T1이 T2보다 오래된 경우 T1은 대기 할 수 있습니다. T1은 사이트 P가 T2가 모든 사이트에서 성공적으로 커밋되었거나 중단되었다는 메시지를 수신 한 후 실행을 재개 할 수 있습니다.
- T1이 T2보다 어린 경우 T1이 중단됩니다. 사이트 P의 동시성 제어는 T1이 T1을 중단하기 위해 방문한 모든 사이트에 메시지를 보냅니다. 제어 사이트는 T1이 모든 사이트에서 성공적으로 중단되면 사용자에게 알립니다.
Distributed Wait-Wait
- T1이 T2보다 오래된 경우 T2를 중단해야합니다. T2가 사이트 P에서 활성화 된 경우 사이트 P는 T2를 중단하고 롤백 한 다음이 메시지를 다른 관련 사이트로 브로드 캐스트합니다. T2가 사이트 P를 떠났지만 사이트 Q에서 활성 상태이면 사이트 P는 T2가 중단되었음을 브로드 캐스트합니다. 그런 다음 사이트 L은 T2를 중단하고 롤백하고이 메시지를 모든 사이트로 보냅니다.
- T1이 T1보다 어린 경우 T1은 대기 할 수 있습니다. T1은 사이트 P가 T2가 처리를 완료했다는 메시지를 수신 한 후에 실행을 재개 할 수 있습니다.

분산 교착 상태 감지

중앙 집중식 교착 상태 감지 접근 방식과 마찬가지로 교착 상태가 발생할 수 있으며 감지되면 제거됩니다. 시스템은 트랜잭션이 잠금 요청을 할 때 어떤 검사도 수행하지 않습니다. 구현을 위해 전역 그래프 대기가 생성됩니다. 글로벌 그래프 대기에주기가 있으면 교착 상태를 나타냅니다. 그러나 트랜잭션이 네트워크를 통해 리소스를 대기하므로 교착 상태를 발견하기가 어렵습니다.

또는 교착 상태 감지 알고리즘에서 타이머를 사용할 수 있습니다. 각 트랜잭션은 트랜잭션이 완료 될 것으로 예상되는 기간으로 설정된 타이머와 연결됩니다. 트랜잭션이이 기간 내에 완료되지 않으면 타이머가 꺼져 교착 상태 일 수 있음을 나타냅니다.

교착 상태 처리에 사용되는 또 다른 도구는 교착 상태 감지기입니다. 중앙 집중식 시스템에는 교착 상태 감지기가 하나 있습니다. 분산 시스템에는 둘 이상의 교착 상태 감지기가있을 수 있습니다. 교착 상태 감지기는 제어중인 사이트에 대한 교착 상태를 찾을 수 있습니다. 분산 시스템에서 교착 상태 감지를위한 세 가지 대안이 있습니다.

Centralized Deadlock Detector − 한 사이트가 중앙 교착 상태 탐지기로 지정됩니다.
Hierarchical Deadlock Detector − 많은 교착 상태 감지기가 계층 구조로 배열되어 있습니다.
Distributed Deadlock Detector − 모든 사이트가 교착 상태를 감지하고 제거하는 데 참여합니다.