타임스탬프 기반 동시성 제어

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글에는 출처가 없다 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Timestamp 기반 동시성 제어" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2007년 6월) (이 템플릿 메시지 제거 방법과 시기 학습) 이 글의 사실적 정확성은 논쟁의 여지가 있다. 관련 토론은 토크 페이지에서 찾을 수 있다. 논쟁의 여지가 있는 진술이 안정적으로 소싱되도록 도와주십시오.(2012년 4월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 주제를 잘 모르는 사람들에게 불충분한 맥락을 제공한다. 독자에게 더 많은 컨텍스트를 제공하여 기사를 개선할 수 있도록 도와주십시오. (2020년 3월) (이 템플리트 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

컴퓨터 과학에서 타임스탬프 기반의 동시성 제어 알고리즘은 비잠금 동시성 제어 방법이다.타임스탬프를 사용하여 트랜잭션을 안전하게 처리하기 위해 일부 데이터베이스에서 사용된다.

작전

가정

• 모든 타임스탬프 값은 고유하며 시간의 순간을 정확하게 나타낸다.
• 어떤 두 타임스탬프도 같을 수 없다.
• 고값 타임스탬프는 저값 타임스탬프보다 나중에 발생한다.

타임스탬프 생성

타임스탬프를 생성하기 위해 여러 가지 다른 방법이 사용됨

• 트랜잭션 시작 시 시스템 클럭 값을 타임스탬프로 사용하십시오.
• 트랜잭션 시작 시 증가되는 스레드 세이프 공유 카운터를 타임스탬프로 사용하십시오.
• 위의 두 가지 방법의 조합.

격식

각 트랜잭션(${\displaystyle {Ti}_{}}$ ${\$은 순서가 지정된 동작 목록(${\displaystyle {\mathrm{Ai}}_{}}$ x ${\$이다.$$트랜잭션이 첫 번째 작업을 수행하기 전에(${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{i}}_{}}$ ${\displaystyle 1_{}}$ ${\$ 현재 타임스탬프 또는 기타 완전히 순서가 정해진 순서가 표시된다.${\displaystyle TS(T_{i})=NOW()}$. Every transaction is also given an initially empty set of transactions upon which it depends, ${\displaystyle DEP(T_{i})=[]}$, and an initially empty set of old objects which it updated, ${\displaystyle OLD(T_{i})=[]}$.

Each object ${\displaystyle (O_{j})}$ in the database is given two timestamp fields which are not used other than for concurrency control: ${\displaystyle RTS(O_{j})}$ is the time at which the value of object was last used by a transaction, ${\displaystyle WTS(O_{j})}$ is the time at트랜잭션에 의해 마지막으로 업데이트된 개체 값.

모든 ${\displaystyle {Ti}_{}}$ ${\$에 대해 $:$

$각{\displaystyle {}_{}}$ 작업 ${\displaystyle A_{}}$ i$$x {\$displaystyle A_${ix$}}$에 대해 $:$

$A{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ x ${\$이(가) O ${\displaystyle j_{}}$ ${\$의 값을 사용하려는$$ 경우$$:

S ( j) > S ( ) ${\displaystyle WTS(O_{j})$ >인 경우$TS(T_{i})$를 수행한 후 중단하십시오(더 최신 스레드가 값을 덮어썼음).

그렇지 않으면 종속성 $D{\displaystyle }$ ${\displaystyle E}$ ${\displaystyle P}$( ${\displaystyle T_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$. ${\displaystyle \mathrm{d}}$ ${\displaystyle \mathrm{d}}$( ${\displaystyle W}$ ${\displaystyle T}$ ${\displaystyle S}$( ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$)${\displaystyle DEP(T_{i})$ 집합을 업데이트하십시오.$\mathrm {add}(WTS(O_{j})}$을(를) 설정하고 R ${\displaystyle T}$ S${\displaystyle (O_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$= ${\displaystyle 최대(R}$ T ${\displaystyle S(}$ ${\displaystyle {}_{}}$ j${\displaystyle {}_{}}$)${\displaystyle }$, ${\displaystyle T}$ ${\displaystyle S(T_{}}$ i${\displaystyle {}_{}}$) ${\displaystyle RTS(O_{j})=\max(RTS(O_{j}),$$TS(T_{i})}$;

$A{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ x ${\$이(가) O ${\displaystyle j_{}}$ ${\$의 값을 업데이트하려는$$ 경우$$:

R ( )> S( i) ${\displaystyle RTS(O_{j})$ >인 경우$TS(T_{i})$를 수행한 다음 중단하십시오(더 최신 스레드가 이미 이전 값에 의존함

S ( j) > S ( ) ${\displaystyle WTS(O_{j})$ >인 경우$TS(T_{i}})$를 건너뛰고(토머스 쓰기 규칙),

그렇지 않으면 이전 $값$인 O ${\displaystyle L}$ ${\displaystyle D}$( ${\displaystyle T_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$. ${\displaystyle \mathrm{d}}$ ${\displaystyle \mathrm{d}}$( ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$, ${\displaystyle W}$ ${\displaystyle T}$ ${\displaystyle S}$( O ${\displaystyle j_{}}$)${\displaystyle Old(T_{i})$를 저장한다.$\mathrm {add}(O_{j},$$WTS(O_{j$ $W{\displaystyle }$ ${\displaystyle T}$ S${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$)${\displaystyle }$= ${\displaystyle T}$ ${\displaystyle S}$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ )${\displaystyle WTS(O_{j})=$ 설정$TS(T_{i}})$및 $O{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$의 값을 업데이트하십시오$.$

$D{\displaystyle }$ ${\displaystyle E}$ ${\displaystyle P}$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle DEP(T_{i})$에 종료되지 않은 트랜잭션이 있는 동안: 대기

$D{\displaystyle }$ ${\displaystyle E}$ ${\displaystyle P}$( ${\displaystyle T_{}}$ i${\displaystyle {}_{}}$) ${\displaystyle DEP(T_{i})$에서 중단한$$ 트랜잭션이 있는 경우 중단

그렇지 않은 경우: 커밋.

중단하려면:

$각{\displaystyle }$(${\displaystyle o}$ ${\displaystyle \mathrm{d}}$ O ${\displaystyle j_{}}$,${\displaystyle {}_{}o}$ l W ${\displaystyle T}$ ${\displaystyle S}$( O ${\displaystyle j_{}}$) {\$displaystyle(\mathrm {old} O_{j},\mathrm {old} WTS(O_{j})}$에 대해$,{\displaystyle }$ O L D${\displaystyle ({}_{}}$) ${\displaysty OD(T_{i})}$

If ${\displaystyle WTS(O_{j})}$ equals ${\displaystyle TS(T_{i})}$ then restore ${\displaystyle O_{j}=\mathrm {old} O_{j}}$ and ${\displaystyle WTS(O_{j})=\mathrm {old} WTS(O_{j})}$

비공식적

트랜잭션이 시작될 때마다 타임스탬프를 수신한다.이 타임스탬프는 다른 트랜잭션과 비교하여 트랜잭션이 발생해야 하는 순서를 나타낸다.따라서 동일한 개체에 영향을 미치는 두 개의 트랜잭션을 고려할 때, 이전 타임스탬프를 사용한 트랜잭션 작업은 이후 타임스탬프를 사용한 트랜잭션의 작업 전에 실행되어야 한다.그러나, 만약 잘못된 거래의 조작이 실제로 먼저 제시된다면, 그것은 중단되고 거래를 다시 시작해야 한다.

데이터베이스의 모든 오브젝트에는 오브젝트 데이터를 읽을 때마다 업데이트되는 읽기 타임스탬프와 오브젝트 데이터가 변경될 때마다 업데이트되는 쓰기 타임스탬프가 있다.

트랜잭션에서 객체를 읽으려면

• 그러나 트랜잭션은 개체의 쓰기 타임스탬프 이전에 시작되었으며, 트랜잭션 시작 후 개체의 데이터가 변경되었음을 의미한다.이 경우 거래가 취소되어 다시 시작해야 한다.
• 그리고 트랜잭션은 개체의 쓰기 타임스탬프 이후에 시작되었으며, 이는 개체를 읽는 것이 안전하다는 것을 의미한다.이 경우 트랜잭션 타임스탬프가 개체의 읽기 타임스탬프 이후인 경우 읽기 타임스탬프는 트랜잭션 타임스탬프로 설정된다.

트랜잭션에서 객체에 쓰기를 원할 경우,

• 그러나 트랜잭션은 개체의 읽기 타임스탬프 이전에 시작되었으며, 이는 어떤 것이 개체를 살펴봤다는 것을 의미하며, 우리는 개체의 데이터의 복사본을 가져갔다고 가정한다.따라서 복사된 데이터를 무효로 만들 수 있으므로 객체에 쓸 수 없으므로 트랜잭션이 중단되고 다시 시작되어야 한다.
• 트랜잭션은 개체의 쓰기 타임스탬프 전에 시작되었으며, 이는 트랜잭션을 시작한 이후 어떤 것이 개체를 변경했다는 것을 의미한다.이 경우 우리는 Thomas 쓰기 규칙을 사용하고 단순히 쓰기 작업을 건너뛰고 정상적으로 계속한다. 트랜잭션을 중단하거나 다시 시작할 필요가 없다.
• 그렇지 않으면 트랜잭션은 객체에 쓰이고, 객체의 쓰기 타임스탬프는 트랜잭션의 타임스탬프로 설정된다.

복구 가능성

타임스탬프의 기본 형식 순서는 복구 가능한 기록을 생성하지 않는다는 점에 유의하십시오.예를 들어 T ${\displaystyle {1\mathrm{}}_{}}$ ${\$및$$ T ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 트랜잭션의 다음 이력을 고려하십시오$.$

${\displaystyle W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}:{1}$

이는 TO 스케줄러에 의해 생성될 수 있지만, 커밋되지 않은 트랜잭션에서 읽었음에도 $불구하고{\displaystyle {}_{}}$ T ${\displaystyle {2\mathrm{}}_{}}$ ${\$}가 커밋되기$$ 때문에 복구할 수 없다.복구 가능한 이력을 생성하기 위해 스케줄러는 각 트랜잭션에서 읽은 다른 트랜잭션 목록을 보관하고 이 목록이 커밋된 트랜잭션으로만 구성되기 전에 트랜잭션을 커밋하지 않도록 할 수 있다.계단식 중단을 방지하기 위해 스케줄러는 커밋되지 않은 트랜잭션에 의해 작성된 데이터에 더러움을 태그할 수 있으며 태그가 지정되지 않은 데이터 항목에 대해 읽기 작업이 시작되지 않도록 할 수 있다.엄격한 기록을 얻기 위해 스케줄러는 더러운 항목에 대한 어떠한 작업도 허용하지 않아야 한다.

구현 문제

타임스탬프 해상도

이것은 인접한 두 타임스탬프 사이에 경과된 최소 시간이다.타임스탬프의 해상도가 너무 큰 경우(공동 연습) 두 개 이상의 타임스탬프가 같을 가능성이 높아져 일부 트랜잭션이 올바른 순서를 벗어나 커밋할 수 있게 된다.예를 들어 초당 100개의 고유 타임스탬프를 만들 수 있는 시스템을 갖추고 있고, 2밀리초 간격으로 발생하는 두 개의 이벤트가 주어진다고 가정하면 실제로 다른 시간에 발생했더라도 동일한 타임스탬프가 주어질 것이다.

타임스탬프 잠금

비록 이 기법이 비잠금 기법일지라도, 오브젝트가 트랜잭션 기간 동안 동시 액세스에서 잠기지 않는 만큼, 오브젝트에 대해 각 타임스탬프를 기록하는 행위는 오브젝트 또는 오브젝트의 프록시에 대해 극히 짧은 기간 잠금을 요구한다.

참고 항목

• 다중 신호 동시성 제어
• 타임스탬프(컴퓨팅)