일관성 모델
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
일관성 모델은 분산 시스템에서 데이터의 일관성을 유지하기 위한 규칙을 정의하며, 엄격 일관성, 순차적 일관성, 인과적 일관성 등 다양한 모델이 존재한다. 이러한 모델들은 하드웨어와 프로그래밍 방식에 영향을 미치며, 성능과 일관성 사이의 트레이드 오프를 고려하여 선택된다. 완화된 메모리 일관성 모델은 성능 향상을 위해 메모리 접근 순서를 완화하며, 트랜잭션 메모리 모델은 메모리 일관성과 캐시 일관성을 결합한다. 클라이언트 중심 일관성 모델은 단일 사용자 환경에서의 일관성을 보장하며, 데이터 복제 환경에서의 일관성 유지를 위해 다양한 프로토콜이 사용된다.
일관성 모델의 개념은 분산 컴퓨팅 초기부터 등장했으며, 시스템 발전에 따라 다양한 형태로 진화했다. 일관성 모델은 발행 방식과 관찰 방식, 두 가지 방법으로 정의하고 분류할 수 있다.
2. 역사적 배경
예를 들어, 어떤 일관성 모델은 이전에 발행된 연산이 모두 완료될 때까지 프로세스가 새 연산을 발행할 수 없도록 제한할 수 있다. 일관성 모델에 따라 적용되는 조건은 다르며, 어떤 모델은 다른 모델보다 더 강력한 조건을 요구하기도 하고, 더 적은 제약 조건을 가진 약한 모델도 있다.
이러한 모델은 하드웨어 배치 방식, 프로그래머의 코딩 방식, 그리고 컴파일러의 명령 재정렬 방식에 영향을 미친다. 일반적으로 컴파일러는 명령 간의 제어 종속 관계나 같은 위치에 대한 쓰기 순서가 유지된다면 필요에 따라 명령을 재정렬할 수 있지만, 일부 모델에서는 로드 전 쓰기 순서 변경에 제약이 있을 수 있다.
순차적 일관성의 요구 사항을 완화한 모델을 완화형 일관성 모델이라고 부른다[38]。 완화형 모델은 하드웨어 수준에서 메모리 일관성을 제공하지 않기 때문에, 프로그래머가 직접 동기화 기술을 적용해야 한다.
2. 1. 초기 모델
엄밀한 일관성은 가장 강력한 일관성 모델이다. 이 모델에서는 임의의 프로세서가 변수에 쓰는 모든 쓰기를 모든 프로세서가 즉시 확인해야 한다.
엄밀 모델과 비엄밀 모델의 차이는 시간 제약인 "순간"으로 나타낼 수 있다. 이는 마치 글로벌 클록이 존재하고 모든 쓰기가 해당 클록 기간 말까지 모든 프로세서의 캐시에 반영되어야 하는 것처럼 이해할 수 있다. 다음 작업은 다음 클록 기간에만 수행되어야 한다.
| 시퀀스 | 엄밀한 모델 | 비엄밀한 모델 | ||
|---|---|---|---|---|
| P1 | P2 | P1 | P2 | |
| 1 | W(x)1 | W(x)1 | ||
| 2 | R(x)1 | R(x)0 | ||
| 3 | R(x)1 | |||
이 모델은 가장 엄격하며, 프로그래머가 기대한 결과가 매번 반환되므로 결정론적 모델이다. 순간적인 메시지 교환은 불가능하므로, 실용적인 관련성은 사고 실험과 형식 논리에 국한된다. 또한 동시 쓰기가 불가능하다는 것을 전제로 하기 때문에, 동일한 데이터 항목에 대한 동시 쓰기의 충돌 해결 문제에도 도움이 되지 않는다.
逐次 일관성 모델은 램포트(1979)가 제창했다. 엄밀한 일관성보다 약한 메모리 모델이다. 변수에 대한 쓰기는 즉시 확인할 필요는 없지만, 서로 다른 프로세서에 의한 변수에 대한 쓰기는 모든 프로세서에서 동일한 순서로 확인되어야 한다. 램포트(1979)의 정의에 따르면, "임의의 실행 결과가 모든 프로세서의 조작이 어떤 순서로 실행된 경우와 같으며, 개별 프로세서의 조작이 해당 프로그램에서 지정된 순서로 이 순서에 나타나는" 경우, 逐次 일관성이 충족된다[29]。
각 프로세서 내의 프로그램 순서와, 프로세서 간의 조작 순서는 유지되어야 한다. 프로세서 간의 실행 순서를 유지하기 위해서는 모든 조작이 다른 모든 프로세서에 대해 순간적 또는 불가분적으로 실행되고 있는 것처럼 보여야 한다. 정보를 즉시 전송하는 것은 물리적으로 불가능하므로, 이러한 조작은 완료된 것처럼 보이면 된다. 예를 들어, 단일 글로벌 공유 버스를 이용한 시스템에서는, 버스 라인에 정보가 게시되면, 모든 프로세서가 같은 순간에 해당 정보를 볼 수 있음이 보장된다. 따라서, 버스 라인에 정보를 전달함으로써, 모든 프로세서에 대해 실행이 완료되고, 실행된 것처럼 보인다. 캐시리스 아키텍처나, 인터커넥트 네트워크가 순간적이지 않은 캐시 아키텍처에서는, 프로세서와 메모리 사이에 슬로우 패스가 포함될 수 있다. 이러한 느린 경로에서는, 어떤 메모리가 다른 메모리보다 빠르게 브로드캐스트 데이터를 수신하므로, 순차적인 불일치가 발생할 수 있다.
逐次 일관성은 비결정적인 결과를 가져올 수 있다. 이는 프로세서 간의 逐次 조작 순서가 프로그램의 다른 실행 시에 다를 수 있기 때문이다. 모든 메모리 조작은 프로그램의 순서대로 수행될 필요가 있다.
선형화 가능성(불가분 일관성이라고도 불린다)은 逐次 일관성에 실시간 제약을 더한 것으로 정의할 수 있다.
2. 2. 완화된 모델의 등장
순차적 일관성의 요구 사항을 완화한 일관성 모델을 완화형 일관성 모델이라고 부른다[38]。이러한 모델은 하드웨어 수준에서 메모리 일관성을 제공하지 않기 때문에, 프로그래머가 직접 동기화 기술을 적용하여 메모리 일관성을 구현해야 한다.성능 향상을 위해 다양한 완화된 일관성 모델이 제안되었다. 그중 하나는 약한 순서(Weak Ordering) 모델이다. 이 모델에서는 메모리 연산을 데이터 연산과 동기화 연산의 두 가지 범주로 나눈다. 프로그램 순서를 유지하기 위해 프로그래머는 프로그램 내에 적어도 하나의 동기화 연산을 명시해야 한다. 동기화 연산은 프로그램 순서를 지키는 안전망 역할을 한다.
약한 순서 모델의 작동 방식은 다음과 같다. 동기화 연산 사이에 있는 데이터 영역에 대한 메모리 연산을 재정렬해도 프로그램 결과에 영향을 주지 않는다는 전제하에, 동기화 연산은 데이터 연산의 횟수를 카운터로 추적하고, 이 카운터가 0이 될 때까지 동기화 연산은 발행되지 않는다. 또한, 이전의 동기화 연산이 모두 완료되지 않는 한, 그 이상의 데이터 연산은 발행되지 않는다. 이렇게 함으로써 두 동기화 변수 사이에 있는 메모리 연산은 프로그램의 정확성에 영향을 주지 않고 중첩되거나 순서를 변경할 수 있다. 이 모델에서는 쓰기의 원자성이 항상 유지되므로, 약한 순서를 위한 추가적인 안전망은 필요하지 않다.
약한 순서 모델에서는 프로그래머가 원자적 잠금 명령(예: 테스트 & 설정, fetch-and-op, store-conditional, load-link)을 사용하거나, 동기화 변수에 레이블을 지정하거나, 펜스를 사용하여 명시적인 동기화를 수행해야 한다.
동기화 연산은 모든 프로세서에 의해 수행된 이전의 모든 연산이 완료되었음을 확인하기 위해 프로세서에 신호를 보낸다. 약한 순서를 유지하기 위해 동기화 연산 전의 쓰기 연산은 동기화 연산 전에 전역적으로 실행되어야 한다. 또한, 동기화 연산 후에 존재하는 연산은 동기화 연산이 완료된 후에만 실행되어야 한다. 따라서 동기화 변수에 대한 접근은 순차적으로 일관성이 있으며, 읽기 및 쓰기는 이전 동기화 연산이 완료된 후에만 실행되어야 한다.
3. 주요 일관성 모델
다양한 일관성 모델은 업데이트의 가시성과 순서에 대한 규칙을 정의하며, 이들은 연속체 상에 존재하고 상충 관계를 갖는다.[2] 일관성 모델을 정의하고 분류하는 방법에는 '이슈'와 '뷰' 두 가지가 있다.[2]
- 이슈: 프로세스가 연산을 발행하는 방법에 대한 제한을 설명한다.
- 뷰: 프로세스에 보이는 연산 순서를 정의한다.
예를 들어, 어떤 일관성 모델은 프로세스가 이전에 발행된 모든 연산이 완료될 때까지 연산을 발행할 수 없도록 정의할 수 있다. 더 강력한 일관성 모델은 해당 모델의 모든 조건과 추가 조건을 요구한다. 즉, 제약 조건이 적은 모델은 더 약한 일관성 모델로 간주된다.[2]
이러한 모델은 하드웨어 배치 방식과 프로그래머의 코딩 방식을 높은 수준에서 정의하며, 컴파일러의 명령어 재정렬 방식에도 영향을 미친다. 일반적으로 명령어 간 제어 종속성이 있거나 동일 위치에 대한 쓰기가 정렬되면 컴파일러는 필요에 따라 재정렬할 수 있다. 그러나 아래에 설명된 모델에 따라 로드 전에 쓰기를 재정렬할 수 있는 경우도 있고 그렇지 않은 경우도 있다.[2]
Tanenbaum 외(2007)는 일관성 모델을 소프트웨어(프로세스)와 메모리 구현(데이터 저장소) 사이의 계약으로 정의한다.[40] 이 모델은 소프트웨어가 특정 규칙을 따르면 메모리가 올바르게 작동함을 보장한다.
주요 일관성 모델은 다음과 같다.
- 엄격 일관성 (Strict Consistency): 가장 강력한 모델로, 모든 쓰기는 즉시 모든 프로세서에 반영된다.
- 순차적 일관성 (Sequential Consistency): 쓰기는 즉시 반영될 필요는 없지만, 모든 프로세서에서 동일한 순서로 나타나야 한다.
- 인과적 일관성 (Causal Consistency): 인과적으로 관련된 쓰기만 모든 프로세스에서 동일한 순서로 나타나야 한다.
- 프로세서 일관성 (Processor Consistency): 동일 메모리 위치에 대한 모든 쓰기는 다른 모든 프로세스에서 동일한 순서로 나타나야 한다.
- PRAM 일관성 (Pipelined RAM Consistency, FIFO Consistency): 단일 프로세스의 연산은 해당 프로세스가 발행한 순서대로 보이지만, 다른 프로세스에서 발행된 연산은 다른 순서로 보일 수 있다.
- 약한 순서 (Weak Ordering): 메모리 연산을 '데이터 연산'과 '동기화 연산'으로 분류하고, 동기화 연산을 통해 프로그램 순서를 강제한다.
- 릴리스 일관성 (Release Consistency): 진입(획득) 및 종료(해제) 동기화 연산을 구분하여 약한 일관성 모델을 완화한다.
- 최종 일관성 (Eventual Consistency): 업데이트가 오랫동안 발생하지 않으면 모든 복제본이 결국 일관성을 갖게 되는 약한 일관성 모델이다.
3. 1. 엄격 일관성 (Strict Consistency)
엄격 일관성은 가장 강력한 일관성 모델이다. 이 모델에서는 임의의 프로세서가 변수에 쓰는 모든 쓰기는 모든 프로세서에 의해 즉시 확인되어야 한다.[2]엄밀 모델의 그림과 비엄밀 모델의 그림은 시간 제약인 "순간"을 나타낸다. 이는 마치 글로벌 클록이 존재하고 모든 쓰기가 해당 클록 기간 말까지 모든 프로세서의 캐시에 반영되어야 하는 것처럼 이해할 수 있다. 다음 작업은 다음 클록 기간에만 수행되어야 한다.
| 시퀀스 | 엄밀한 모델 | 비엄밀한 모델 | ||
|---|---|---|---|---|
| P1 | P2 | P1 | P2 | |
| 1 | W(x)1 | W(x)1 | ||
| 2 | R(x)1 | R(x)0 | ||
| 3 | R(x)1 | |||
이것은 가장 엄격한 모델이다. 이 모델에서는 프로그래머가 기대한 결과가 매번 반환된다. 따라서 결정론적 모델이다. 순간적인 메시지 교환은 불가능하므로, 실용적인 관련성은 사고 실험과 형식 논리에 국한된다. 또한 동시 쓰기가 불가능하다는 것을 전제로 하기 때문에, 동일한 데이터 항목에 대한 동시 쓰기의 충돌 해결 문제에도 도움이 되지 않는다.[2]
3. 2. 순차적 일관성 (Sequential Consistency)
순차적 일관성 모델은 램포트(1979)가 제안한 것으로, 엄격한 일관성 모델보다 약한 메모리 모델이다.[3] 변수에 대한 쓰기는 즉시 반영될 필요는 없지만, 서로 다른 프로세서에 의한 변수 쓰기는 모든 프로세서에서 동일한 순서로 나타나야 한다. 램포트에 따르면, "모든 프로세서의 연산(읽기 및 쓰기)이 어떤 순차적 순서로 데이터 저장소에서 실행되고, 각 개별 프로세서의 연산이 해당 프로그램에서 지정한 순서대로 이 시퀀스에 나타나는 경우" 순차적 일관성이 충족된다.[3][24]순차적 일관성에서는 시간이나 가장 최근 쓰기 연산이라는 개념은 없다. 모든 프로세스에 대해 동일한 몇 가지 연산 인터리빙이 존재한다. 프로세스는 모든 프로세스의 쓰기 연산을 볼 수 있지만, 자신의 읽기 연산만 볼 수 있다. 각 프로세서 내의 프로그램 순서와 프로세서 간 연산의 순차적 순서를 유지해야 한다. 프로세서 간 실행의 순차적 순서를 유지하려면, 모든 연산은 다른 모든 프로세서에 대해 즉시 또는 원자적으로 실행되는 것처럼 보여야 한다.
이러한 연산은 정보를 즉시 보낼 수 없기 때문에 완료된 것처럼 "보여야" 한다. 예를 들어, 단일 전역 공유 버스를 사용하는 시스템에서 버스 라인에 정보가 게시되면 모든 프로세서가 동시에 정보를 보게 된다는 것이 보장된다. 따라서 정보를 버스 라인으로 전달하면 모든 프로세서에 대해 실행이 완료되고 실행된 것처럼 보인다. 인스턴트가 아닌 상호 연결 네트워크가 있는 캐시 없는 아키텍처 또는 캐시된 아키텍처는 프로세서와 메모리 사이에 느린 경로를 포함할 수 있다. 이러한 느린 경로는 일부 메모리가 다른 메모리보다 브로드캐스트 데이터를 더 빨리 수신하기 때문에 순차적 불일치를 초래할 수 있다.
순차적 일관성은 비결정적 결과를 생성할 수 있다. 이는 프로세서 간 순차적 연산의 시퀀스가 프로그램의 서로 다른 실행 중에 다를 수 있기 때문이다. 모든 메모리 연산은 프로그램 순서대로 발생해야 한다.
애드브와 가라초를루(1996)는 순차적 일관성을 구현하기 위한 두 가지 요구 사항으로 프로그램 순서와 쓰기 원자성을 정의한다.[4]
- 프로그램 순서: 각 프로세스가 프로그램에 의해 정렬된 메모리 요청을 발행하도록 보장한다.
- 쓰기 원자성: 메모리 요청이 단일 FIFO 큐의 순서를 기반으로 처리되도록 정의한다.
선형성(원자적 일관성 또는 원자적 메모리라고도 함)[5][18]은 각 연산에 시작 시간과 종료 시간을 고려하여 실시간 제약 조건이 있는 순차적 일관성으로 정의할 수 있다. 실행은 선형 가능한 순서로 각 연산을 실행하여 시작 시간과 종료 시간 사이에 점을 배치하고 순차적 일관성을 보장하는 경우 선형 가능하다고 한다.
모델 검사를 통한 순차적 일관성의 검증은 유한 상태의 캐시 일관성 프로토콜의 경우에도 일반적으로 결정 불가능 문제이다.[6]
3. 3. 인과적 일관성 (Causal Consistency)
인과적 일관성(Causal consistency)은 1990년 Hutto와 Ahamad가 정의한 것으로,[11] 사건을 인과적으로 관련된 사건과 그렇지 않은 사건으로 분류하여, 인과적으로 관련된 쓰기 연산만 모든 프로세스에서 동일한 순서로 볼 필요가 있다고 정의한다.[24] 예를 들어, 사건 b가 이전 사건 a의 영향을 받는 경우, 인과적 일관성은 모든 프로세스가 사건 a 이후에 사건 b를 보게 됨을 보장한다.2007년 Tanenbaum et al.은 다음과 같은 더 엄격한 정의를 제시했다.[24]
- 잠재적으로 인과적으로 관련된 쓰기는 모든 프로세스에서 동일한 순서로 보여야 한다.
- 동시 쓰기는 서로 다른 시스템에서 다른 순서로 보일 수 있다.
이 모델은 프로세서의 동시 쓰기 및 인과적으로 관련되지 않은 쓰기에 대해 순차적 일관성을 완화한다. 두 쓰기는 변수에 대한 한 번의 쓰기가 두 번째 쓰기를 수행하는 프로세서가 첫 번째 쓰기를 읽은 경우, 어떤 변수에 대한 이전 쓰기에 종속되는 경우 인과적으로 관련될 수 있다. 두 쓰기는 동일한 프로세서 또는 다른 프로세서에서 수행되었을 수 있다.
순차적 일관성과 마찬가지로, 읽기는 즉시 변경 사항을 반영할 필요는 없지만, 변수에 대한 모든 변경 사항을 순차적으로 반영해야 한다.
다음은 Hutto와 Ahamad의 정의에 따라 인과적 일관성을 가지는 예시이다. (W(x)2와 W(x)3이 모든 프로세스에 대해 동일한 순서로 보이지 않기 때문에 Tanenbaum et al.의 정의는 아니다.) 그러나 R(x)2와 R(x)3은 P3과 P4에서 다른 순서로 발생하므로 이 예는 순차적으로 일관되지 않는다.[7]
| 순서 | 프로세서 1 | 프로세서 2 | 프로세서 3 | 프로세서 4 |
|---|---|---|---|---|
| 1 | W(x)1 | R(x)1 | R(x)1 | R(x)1 |
| 2 | W(x)2 | |||
| 3 | W(x)3 | R(x)3 | R(x)2 | |
| 4 | R(x)2 | R(x)3 |
W(x)2는 W(x)2 전에 P2가 x를 읽었기 때문에 W(x)1 다음에 발생한다.
다음과 같은 사례를 통해 인과적 일관성 모델이 클라이언트 A가 수행한 기록을 클라이언트 B가 보고 있는지 여부를 판단하는 것을 알 수 있다.[28]
- 행 X는 노드 M과 N에 복제된다.
- 클라이언트 A가 노드 M에 행 X를 기록한다.
- 일정 시간 t 후, 클라이언트 B가 노드 N에서 행 X를 읽어낸다.
3. 4. 프로세서 일관성 (Processor Consistency)
프로세서 일관성 모델은 PRAM 일관성 모델과 유사하지만, 동일한 메모리 위치에 대한 모든 쓰기가 다른 모든 프로세스에서 동일한 순차적 순서로 표시되어야 한다는 더욱 강력한 조건을 가진다.[8] 프로세서 일관성은 순차적 일관성보다는 약하지만 PRAM 일관성 모델보다 강하다.데이터의 일관성을 유지하고 모든 프로세서가 자체 메모리를 갖춘 확장 가능한 프로세서 시스템을 구축하기 위해 프로세서 일관성 모델이 도출되었다.[7] 모든 프로세서는 한 프로세서가 수행한 쓰기를 보는 순서와 서로 다른 프로세서가 동일한 위치에 대한 쓰기를 보는 방식(일관성 유지)에서 일관성을 유지해야 한다. 그러나 서로 다른 프로세서가 서로 다른 위치에 쓰는 경우에는 일관성을 유지할 필요가 없다.
모든 쓰기 연산은 모든 메모리에 대한 여러 하위 쓰기로 나눌 수 있다. 이러한 메모리 중 하나에서 읽는 작업은 이 메모리에 대한 쓰기가 완료되기 전에 발생할 수 있다. 따라서 읽은 데이터가 오래될 수 있다. 따라서 PC 환경의 프로세서는 이전 저장 작업이 중단되어야 할 때 더 최근의 로드를 실행할 수 있다. 쓰기 전 읽기, 읽기 후 읽기, 쓰기 전 쓰기 순서는 이 모델에서도 여전히 유지된다.
스탠퍼드 DASH 멀티프로세서 시스템은 Goodman의 정의와 비교할 수 없는(더 약하지도, 강하지도 않은) 프로세서 일관성의 변형을 구현한다.[10] 모든 프로세서는 한 프로세서가 수행한 쓰기를 보는 순서와 서로 다른 프로세서가 동일한 위치에 대한 쓰기를 보는 방식에서 일관성을 유지해야 한다. 그러나 서로 다른 프로세서가 서로 다른 위치에 쓰는 경우에는 일관성을 유지할 필요가 없다.
3. 5. PRAM 일관성 (Pipelined RAM Consistency, FIFO Consistency)
PRAM 일관성(파이프라인 RAM 일관성)은 1988년 립튼(Lipton)과 샌드버그(Sandberg)가 처음 제시한 일관성 모델 중 하나이다.[9] 비공식적인 정의로 인해 아하마드(Ahamad) 등이 제시한 구현 방식과 모스버거(Mosberger)가 제시한 구현 방식, 이렇게 최소 두 가지의 미묘하게 다른 구현 방식이 존재한다.[10]PRAM 일관성에서 모든 프로세스는 단일 프로세스의 연산을 해당 프로세스가 발행한 순서와 동일하게 본다. 하지만 다른 프로세스에서 발행된 연산은 다른 프로세스에서 다른 순서로 볼 수 있다. PRAM 일관성은 프로세서 일관성보다 약한데, 모든 프로세서에서 특정 위치에 대한 일관성을 유지할 필요가 없기 때문이다. 즉, 어떤 변수에 대한 읽기 연산은 해당 프로세서 내에서 쓰기 연산보다 먼저 실행될 수 있다. 이 모델에서는 읽기 전 쓰기, 읽기 후 읽기, 쓰기 전 쓰기 순서는 유지된다.
| 순서 | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| 1 | W(x)1 | |||
| 2 | R(x)1 | |||
| 3 | W(x)2 | |||
| 4 | R(x)1 | R(x)2 | ||
| 5 | R(x)2 | R(x)1 |
3. 6. 약한 순서 (Weak Ordering)
약한 순서 모델은 메모리 연산을 '데이터 연산'과 '동기화 연산' 두 가지로 분류한다. 프로그래머는 프로그램 순서를 강제하기 위해 최소한 하나의 동기화 연산을 사용해야 한다. 동기화 연산은 모든 프로세서가 이전 연산을 완료하고 확인했음을 알리는 신호 역할을 한다. 프로그램 순서와 원자성은 동기화 연산에서만 유지되며, 이는 임계 구역 내 연산이 완료될 때까지 모든 프로세서에 보이지 않도록 하는 개념에서 비롯되었다.[13]이 방식은 동기화 연산 사이의 데이터 영역에 대한 메모리 연산 순서를 변경해도 프로그램 결과에 영향을 미치지 않는다는 가정에 기반한다. 다중 프로세서 시스템에서 실행되는 프로그램은 데이터 경합이 발생하지 않고 순차적 일관성(SC) 결과를 생성하도록 동기화가 필요하다는 점을 이용한다.[13]
이 모델에서 일관성은 완화되지 않는다. 동기화 연산 이전의 쓰기 연산은 동기화 연산 전에 전역적으로 수행되어야 하며, 동기화 연산 이후의 연산은 동기화 연산이 완료된 후에만 수행되어야 한다. 동기화 변수에 대한 접근은 순차적으로 일관되며, 모든 읽기 또는 쓰기는 이전 동기화 연산이 완료된 후에만 수행된다.
약한 순서 모델에서 프로그래머는 원자적 잠금 지침(테스트 및 설정, 가져오기 및 연산, 조건부 저장, 링크 로드 등)을 사용하거나, 동기화 변수를 레이블 지정하거나, 울타리를 사용하여 명시적인 동기화를 수행해야 한다.[13]
(참고: 예시 테이블은 원본 소스에 내용이 있으나, 약한 순서 모델의 일반적인 내용을 설명하는 데 필수적이지 않고, 테이블의 내용이 추상적이어서 삭제함.)
3. 7. 릴리스 일관성 (Release Consistency)
릴리스 일관성 모델은 진입 동기화 연산과 종료 동기화 연산을 구분하여 약한 일관성 모델을 완화한다. 약한 정렬에서는 동기화 연산을 보려면, 동기화 연산이 완료되고 프로세서가 진행되기 전에 모든 프로세서의 모든 연산이 보여야 한다. 그러나 릴리스 일관성 모델에서는 임계 구역에 진입하는 동안, 즉 "획득(acquire)"이라고 하는 연산에서 로컬 메모리 변수에 관한 모든 연산이 완료되어야 한다. "해제(release)"라고 하는 종료 연산 동안에는 로컬 프로세서가 변경한 모든 사항을 다른 모든 프로세서로 전파해야 한다. 일관성은 여전히 유지된다.[36]획득 연산은 임계 구역에 접근하기 위해 수행되는 로드/읽기 연산이다. 해제 연산은 다른 프로세서가 공유 변수를 사용할 수 있도록 허용하기 위해 수행되는 저장/쓰기 연산이다.
동기화 변수 중 순차적 일관성 또는 프로세서 일관성을 유지할 수 있다. 순차적 일관성을 사용하면 모든 경쟁 동기화 변수를 순서대로 처리해야 한다. 그러나 프로세서 일관성을 사용하면 경쟁 변수 쌍만 이 순서를 따라야 한다. 오래된 해제 전에 더 젊은 획득이 발생하도록 허용할 수 있다.[36]
릴리스 일관성에는 순차적 일관성을 가진 릴리스 일관성(RCsc)과 프로세서 일관성을 가진 릴리스 일관성(RCpc)의 두 가지 유형이 있다. 후자의 유형은 아래에 특별하다고 지정된 연산에 적용되는 일관성의 유형을 나타낸다.
특별(일반 연산과 대조) 메모리 연산이 있으며, 이들은 다시 두 가지 연산 클래스, 즉 ''sync'' 또는 ''nsync'' 연산으로 구성된다. 후자는 동기화에 사용되지 않는 연산이고, 전자는 동기화에 사용되며 ''획득(acquire)'' 및 ''해제(release)'' 연산으로 구성된다. 획득은 특정 공유 위치에 대한 접근 권한을 얻기 위해 사용되는 메모리 읽기 연산과 같다. 반면에, 해제는 공유 위치에 대한 접근 권한을 부여하기 위해 수행되는 쓰기 연산이다.
순차적 일관성과 릴리스 일관성(RCsc)의 경우, 제약 조건은 다음과 같다.
- 획득 → 모든 연산
- 모든 연산 → 해제
- 특별 연산 → 특별 연산
프로세서 일관성과 릴리스 일관성(RCpc)에서는 쓰기-읽기 프로그램 순서가 완화되어 다음과 같은 제약 조건이 적용된다.
- 획득 → 모든 연산
- 모든 연산 → 해제
- 특별 연산 → 특별 연산 (특별 쓰기가 특별 읽기를 따르는 경우 제외).
참고: 위의 표기 A → B는 프로그램 순서에서 연산 A가 B보다 먼저 오는 경우 프로그램 순서가 적용됨을 의미한다.
3. 8. 최종 일관성 (Eventual Consistency)
결정적 일관성[24]은 동시 업데이트가 없는 시스템에서의 약한 일관성 모델이다. 업데이트가 오랫동안 발생하지 않으면 모든 복제본이 결국 일관성을 갖게 된다고 정의한다.대부분의 공유 분산 데이터베이스는 BASE(기본적으로 사용 가능, 소프트 상태, 결정적 일관성) 모델 또는 ACID와 BASE의 조합인 SALT(순차적, 합의된, 원장, 변조 방지) 모델을 사용하며, SALT는 대칭적, 관리자 불필요, 원장, 시간 합의적 속성을 갖기도 한다.[15][16][17]
다음과 같은 사례를 상정할 수 있다.[28]
- 행 X는 노드 M과 N에 복제된다.
- 클라이언트 A가 노드 M에 행 X를 기록한다.
- 일정 시간 t 후, 클라이언트 B가 노드 N에서 행 X를 읽어낸다.
일관성 모델은 클라이언트 A가 수행한 기록을 클라이언트 B가 보고 있는지 여부를 판단해야 한다.
결과 일관성은 동시 업데이트가 없는 시스템에서 약한 일관성 모델이다. 업데이트가 없는 상태가 매우 오랫동안 지속되면 모든 레플리카가 최종적으로 일관성을 갖게 된다고 정의한다.
대부분의 공유 분산 데이터베이스는 BASE (기본적으로 사용 가능, 유연한 상태, 최종적으로 일관성) 모델, 또는 ACID와 BASE를 결합한 SALT (순차적, 합의된, 유도된, 변조 불가, 또한 대칭적, 관리자 없음, 유도된, 시간적으로 합의된) 모델 중 하나인 최종 일관성 모델을 가진다.
4. 완화된 메모리 일관성 모델 (Relaxed Memory Consistency Models)
완화된 메모리 일관성 모델은 하드웨어 수준에서 메모리 접근 순서를 완화하여 성능을 향상시킨다. 프로그래머는 동기화를 통해 일관성을 보장해야 한다.
순차적 일관성의 요구 사항인 프로그램 순서와 쓰기 원자성을 완화하여 다양한 완화된 일관성 모델을 얻을 수 있다. 이는 성능 향상을 위해 수행되지만, 프로그래머는 동기화 기술을 적용하고 하드웨어를 잘 이해해야 한다.
프로그램 순서 완화:
- 쓰기 → 읽기 프로그램 순서 완화: 쓰기 연산의 지연 시간을 숨기기 위해 읽기가 쓰기보다 먼저 완료될 수 있도록 허용한다.
- IBM 370: 가장 엄격한 모델이다. 읽기는 다른 주소에 대한 이전 쓰기 전에 완료될 수 있지만, 모든 프로세서가 쓰기를 보기 전에는 쓰기 값을 반환할 수 없다.
- SPARC V8 전체 저장 순서(TSO): IBM 370 모델을 부분적으로 완화하여, 프로세서가 다른 프로세서보다 먼저 자신의 쓰기 값을 읽을 수 있다.
- 프로세서 일관성(PC): 가장 완화된 모델이다. 읽기가 다른 프로세서에 표시되기 전에도 이전 쓰기보다 먼저 완료될 수 있다.
- 쓰기 → 쓰기 프로그램 순서 완화:
- SPARC V8 부분 저장 순서(PSO): 동일 프로세서에서 서로 다른 위치에 대한 쓰기를 파이프라인 및 중첩할 수 있다. 명시적 `STBAR` 명령어를 사용하여 쓰기 간 프로그램 순서를 유지한다.
- 읽기 → 읽기, 읽기 → 쓰기 프로그램 순서 완화:
- 약한 순서 (Weak Ordering): 메모리 연산을 데이터 연산과 동기화 연산으로 분류한다. 동기화 연산 사이에서 데이터 연산의 순서는 변경될 수 있다.
- 릴리스 일관성 (RCsc 및 RCpc): 약한 순서와 유사하게 동기화 연산을 사용하여 일관성을 유지한다.
- Alpha, RMO (Relaxed Memory Order), PowerPC: 명시적 펜스 명령어를 사용하여 메모리 연산 간 프로그램 순서를 강제한다.
쓰기 원자성 완화:
- TSO, PSO, PC 모델은 프로세서가 자신의 쓰기 값을 다른 프로세서보다 먼저 읽을 수 있도록 허용한다.
- Alpha, RMO, PowerPC 모델은 읽기가 완료되기 전에 쓰기를 볼 수 있도록 허용하여 쓰기 원자성을 더욱 완화한다.
상용 아키텍처:
- Digital Alpha: `MB` (메모리 장벽) 및 `WMB` (쓰기 메모리 장벽) 펜스 명령어를 제공한다.
- SPARC V9 RMO: `MEMBAR` 명령어를 제공하여 메모리 연산 순서를 제어한다.
- IBM PowerPC: `SYNC` 펜스 명령어를 사용하며, 읽기가 프로그램 순서를 벗어나 발생할 수 있는 예외가 있다.
주의:
- 완화된 모델에서는 컴파일러 최적화가 제한될 수 있다.
- 프로그래머는 동기화 (원자적 잠금 명령어, 펜스 등)를 사용하여 일관성을 유지해야 한다.
5. 트랜잭션 메모리 모델 (Transactional Memory Models)
트랜잭션 메모리 모델[18]은 소프트웨어나 하드웨어에서 지원하는 공유 메모리 시스템을 위한 통신 모델로, 캐시 일관성 및 메모리 일관성 모델을 결합한 것이다. 트랜잭션 메모리 모델은 메모리 일관성과 캐시 일관성을 모두 제공한다. 트랜잭션은 프로세스에 의해 실행되어 데이터를 하나의 일관된 상태에서 다른 상태로 변환하는 일련의 연산이다. 트랜잭션은 충돌이 없으면 커밋되거나 중단된다. 커밋에서는 트랜잭션이 완료되면 모든 변경 사항이 다른 모든 프로세스에 표시되지만, 중단 시에는 모든 변경 사항이 폐기된다. 완화된 일관성 모델에 비해 트랜잭션 모델은 사용하기 쉽고 순차적 일관성 모델보다 더 높은 성능을 제공할 수 있다.
6. 클라이언트 중심 일관성 모델 (Client-Centric Consistency Models)
1994년 논문에서 단일 사용자 또는 애플리케이션만 데이터를 수정하는 상황에 초점을 맞춘 4가지 일관성 모델이 제안되었다.[12] 동시 업데이트가 없는 일부 특수한 데이터 저장소에서, 클라이언트 중심 일관성 모델은 순차적 일관성보다 덜 비싼 방식으로 불일치를 처리할 수 있다.[24]
느린 일관성[39]은 어떤 프로세스가 메모리 위치에 이전에 기록된 값을 읽으면, 그 후 해당 위치에서 이전 값을 읽을 수 없다는 것을 의미한다. 또한, 어떤 프로세스가 수행한 쓰기는 해당 프로세스가 즉시 볼 수 있다. 느린 일관성은 PRAM이나 캐시 일관성보다 약한 모델이다.
'''예:''' 느린 메모리 그림은 느린 일관성의 예를 보여준다. 첫 번째 프로세스가 메모리 위치 X에 1을 쓰고, 다음으로 메모리 위치 Y에 1을 쓴다. 두 번째 프로세스가 Y에서 1을 읽고, X가 Y보다 먼저 쓰여졌음에도 불구하고, X에서 0을 읽는다.
Hutto, Phillip W.와 Mustaque Ahamad(1990)[34]는 적절한 프로그래밍을 통해, 슬로우 메모리(일관성)가 표현력과 효율성을 가질 수 있음을 설명했다. 그들은 슬로우 메모리는 2가지 가치 있는 특성을 가지고 있다고 말한다. 그것은 국소성과 불가분 메모리로부터의 감소를 지원하는 것이다. 그들은 슬로우 메모리의 표현력을 보여주기 위해 2가지 알고리즘을 제안했다.
다음은 클라이언트 중심 일관성 모델의 몇 가지 예시이다:[24]
- '''단조 읽기 (Monotonic Reads):''' 프로세스가 데이터 항목 x의 값을 읽으면, 해당 프로세스에 의한 x에 대한 후속 읽기 작업은 항상 동일한 값 또는 더 최근의 값을 반환한다.[24] 즉, 어떤 프로세스가 시각 t에 데이터 항목 x의 값을 읽은 후, 해당 데이터 항목의 더 오래된 값을 보지 않음을 보장한다.
- '''단조 쓰기 (Monotonic Writes):''' 프로세스가 데이터 항목 X에 대한 쓰기 연산은 동일한 프로세스에 의한 X에 대한 모든 후속 쓰기 연산 전에 완료된다.[24]
- '''Read-your-writes:''' 프로세스가 데이터 항목 X에 기록한 값은 동일한 프로세스가 데이터 항목 X에 대해 수행하는 후속 읽기 작업에서 항상 사용할 수 있다.[24]
- '''Writes-follows-reads:''' 프로세스가 동일한 프로세스에 의한 x에 대한 이전 읽기 작업에 따라 데이터 항목 x에 대한 쓰기 작업은 읽었던 x의 동일하거나 더 최근의 값에서 수행되도록 보장된다.[24] 즉, 업데이트가 이전 읽기 연산을 실행한 후에 전파된다.
7. 일관성과 복제 (Consistency and Replication)
데이터 복제는 성능과 신뢰성을 향상시키지만, 여러 사본 간의 일관성 문제를 야기할 수 있다. 복제는 신뢰성과 성능을 위한 주요 이유로 정의된다.[24] 신뢰성은 현재 복제본에 장애가 발생했을 때 다른 복제본으로 전환하여 달성할 수 있다. 또한 복제는 데이터의 여러 사본을 제공하여 데이터 손상을 방지한다. 작업을 분담하여 성능을 향상시킬 수도 있다. 여러 사본은 읽기 작업이 모든 사본에서 동일한 값을 반환하고, 쓰기 작업이 단일 원자적 작업(트랜잭션)으로 모든 사본을 업데이트하는 경우 일관성이 유지된다.[24] 이러한 유형의 일관성을 엄격한 일관성이라고 하며, 동기식 복제를 통해 제공된다. 그러나 모든 사본의 일관성을 유지하기 위한 전역 동기화는 비용이 많이 들기 때문에, 일관성 제약을 완화하여 성능을 향상시킬 수 있다.
일관성 모델은 소프트웨어(프로세스)와 메모리 구현(데이터 저장소) 간의 계약으로 정의된다.[24] 이 모델은 소프트웨어가 특정 규칙을 따르면 메모리가 올바르게 작동함을 보장한다. 전역 시계가 없는 시스템에서는 쓰기 작업 중 마지막 작업을 정의하기 어렵기 때문에, 읽기 작업에서 반환될 수 있는 값에 몇 가지 제한을 적용할 수 있다. 데이터 중심 일관성 모델의 목표는 프로세스가 동시 업데이트를 수행할 수 있는 데이터 저장소에 대한 일관된 보기를 제공하는 것이다.
순차적 일관성 및 인과적 일관성과 같은 일부 일관성 모델은 공유 복제 데이터에 대한 연산 순서를 다루며, 모든 복제본은 업데이트에 대한 일관된 전역 순서에 동의해야 한다.
일관성 유지를 위한 복제 프로토콜에는 프라이머리 기반 프로토콜과 복제 쓰기 프로토콜이 있다.
- 프라이머리 기반 프로토콜: 데이터 항목에 대한 쓰기 연산을 조정하기 위해 각 데이터 항목에 관련된 프라이머리가 존재한다.[24] 구현이 더 간단한 일관성 프로토콜의 한 종류로 간주될 수 있다.
- 복제 쓰기 프로토콜: [기본 프로토콜]과는 달리 모든 업데이트가 모든 복제본에 적용된다.
일관성 모델의 정의와 분류에는 발행 방식과 관찰 방식 두 가지가 있다.[28]
# 발행 방식에서는 프로세스가 연산을 발행하는 방법을 정의하는 제한을 기술한다.
# 프로세스에서 보이는 연산의 순서를 정의하는 관찰 방식.
예를 들어, 일관성 모델에서는 이전에 발행된 연산이 모두 완료될 때까지 프로세스가 연산을 발행할 수 없다고 정의할 수 있다. 일관성 모델에 따라 적용되는 조건은 다르다. 어떤 일관성 모델은 해당 모델의 모든 조건과 그 이상의 조건을 필요로 하는 경우, 다른 모델보다 강하다고 생각할 수 있다. 다시 말해, 제약 조건이 적은 모델은 약한 일관성 모델로 간주될 수 있다.
8. 일관성 프로토콜 (Consistency Protocols)
일관성 모델의 구현은 일관성 프로토콜에 의해 정의된다.[24]
Yu와 Vahdat(2000)[25]가 소개한 연속적 일관성 모델은 응용 프로그램 내의 conit을 사용하여 응용 프로그램의 일관성 의미를 설명한다. 일관성 요구 사항은 응용 프로그램의 의미에 따라 다를 수 있으므로, 미리 정의된 균일한 일관성 모델이 적절한 접근 방식이 아닐 수 있다고 Yu와 Vahdat(2000)[25]은 생각했다. 응용 프로그램은 응용 프로그램의 의미를 만족하는 일관성 요구 사항을 지정해야 한다. 이 모델에서, 응용 프로그램은 각 일관성 요구 사항을 conit(일관성 단위의 약자)으로 지정한다. Conit은 물리적 또는 논리적 일관성이 될 수 있으며, 일관성을 측정하는 데 사용된다.[24]
응용 프로그램에서 허용될 수 있는 세 가지 불일치는 다음과 같다.
; 수치 값의 편차:[25] 수치적 편차는 conit 값과 마지막 업데이트의 상대적 값 간의 차이를 제한한다. 특정 응용 프로그램에서 쓰기의 중요성을 정의하는 가중치를 쓰기에 할당할 수 있다. conit에 대한 아직 보이지 않은 쓰기의 총 가중치는 응용 프로그램에서 수치적 편차로 정의될 수 있다. 수치적 편차에는 절대적 수치 편차와 상대적 수치 편차의 두 가지 유형이 있다.
; 순서의 편차:[25] 순서 편차는 복제본에서 쓰기의 로컬 순서와 최종 이미지에서 상대적 순서 간의 불일치이다.
; 복제본 간의 오래됨 편차:[25] 오래됨 편차는 로컬에서 보이지 않은 conit에서 가장 오래된 쓰기의 시간과 현재 시간 간의 차이를 제한하여 가장 오래된 쓰기의 유효성을 정의한다. 각 서버에는 실제 순서를 결정하고 conit에 적용해야 하는 불확실한 쓰기의 로컬 큐가 있다. 불확실한 쓰기 큐의 최대 길이는 순서 편차의 경계이다. 쓰기 수가 한도를 초과하면, 서버는 새로운 제출된 쓰기를 수락하는 대신, 쓰기가 실행되어야 하는 순서에 따라 다른 서버와 통신하여 불확실한 쓰기를 커밋하려고 시도한다.
세 가지 편차 경계가 모두 0으로 설정되면, 연속적 일관성 모델은 강한 일관성이 된다.
프라이머리 기반 프로토콜[24]은 구현이 더 간단한 일관성 프로토콜의 한 종류로 간주될 수 있다. 예를 들어, 연산의 일관된 순서가 중요한 경우 순차적 정렬이 널리 사용되는 일관성 모델이다. 순차적 정렬은 프라이머리 기반 프로토콜로 결정될 수 있다. 이 프로토콜에서는 데이터 항목에 대한 쓰기 연산을 조정하기 위해 데이터 저장소의 각 데이터 항목에 관련된 프라이머리가 있다.
참조
[1]
논문
Multiprocessors Should Support Simple Memory Consistency Models
http://digital.libra[...]
1998-08
[2]
웹사이트
Design Patterns for Distributed Non-Relational Databases
http://cloudera-todd[...]
2011-03-24
[3]
논문
How to make a multiprocessor computer that correctly executes multiprocess programs.
1979-09
[4]
논문
Shared Memory Consistency Models: A Tutorial
http://www.hpl.hp.co[...]
2008-05-28
[5]
논문
"Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems
1990-07
[6]
논문
Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking
2003-08
[7]
웹사이트
Memory Consistency Models
https://www-vs.infor[...]
2016-11-17
[8]
논문
Cache consistency and sequential consistency
1991
[9]
간행물
PRAM: A scalable shared memory
[10]
학위논문
Operational Characterization of Weak Memory Consistency Models
https://es.cs.uni-kl[...]
University of Kaiserslautern
2013
[11]
서적
Proceedings.,10th International Conference on Distributed Computing Systems
IEEE
1990
[12]
서적
Proceedings of 3rd International Conference on Parallel and Distributed Information Systems
IEEE Computer Society Press
1994-10-01
[13]
웹사이트
Shared Memory Consistency Models : A tutorial
http://www.hpl.hp.co[...]
2008-05-28
[14]
논문
Advanced concepts in operating systems.
https://archive.org/[...]
1994
[15]
웹사이트
SALT: A Descriptive Model For Blockchain
https://medium.com/@[...]
Collin Cusce
2018
[16]
문서
"Not ACID, not BASE, but SALT: A Transaction Processing Perspective on Blockchains"
http://www.ise.tu-be[...]
Stefan Tai, Jacob Eberhardt, and Markus Klems
2017
[17]
문서
"Salt: Combining ACID and BASE in a Distributed Database"
https://web.archive.[...]
Chao Xie, Chunzhi Su, Manos Kapritsos, Yang Wang, Navid Yaghmazadeh, Lorenzo Alvisi, Prince Mahajan
[18]
문서
CSG280: Parallel Computing Memory Consistency Models: A Survey in Past and Present Research
2007
[19]
논문
A unified theory of shared memory consistency.
2004
[20]
웹사이트
Don't Settle for Eventual:Scalable Causal Consistency for Wide-Area Storage with COPS
https://www.cs.cmu.e[...]
[21]
서적
Proceedings of the 8th ACM European Conference on Computer Systems
[22]
웹사이트
Strong and Efficient Consistency with Consistency-Aware Durability
https://www.usenix.o[...]
[23]
논문
Consistency in Non-Transactional Distributed Storage Systems
2016
[24]
논문
Distributed systems
2007
[25]
논문
Design and evaluation of a continuous consistency model for replicated services.
2000
[26]
논문
Multiprocessors Should Support Simple Memory Consistency Models
http://digital.libra[...]
1998-08
[27]
논문
Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking
2003-08
[28]
웹사이트
Design Patterns for Distributed Non-Relational Databases
http://cloudera-todd[...]
2011-03-24
[29]
논문
How to make a multiprocessor computer that correctly executes multiprocess programs.
1979-09
[30]
웹사이트
Memory Consistency Models
https://www-vs.infor[...]
2021-07-28
[31]
논문
Cache consistency and sequential consistency
1991
[32]
간행물
PRAM: A scalable shared memory
[33]
학위논문
Operational Characterization of Weak Memory Consistency Models
https://es.cs.uni-kl[...]
University of Kaiserslautern
2013
[34]
서적
Slow memory: Weakening consistency to enhance concurrency in distributed shared memories.
1990
[35]
웹사이트
Shared Memory Consistency Models : A tutorial
http://www.hpl.hp.co[...]
2021-07-28
[36]
서적
Fundamentals of Parallel Computer Architecture
Solihin Books
[37]
간행물
Advanced concepts in operating systems.
https://archive.org/[...]
1994
[38]
간행물
CSG280: Parallel Computing Memory Consistency Models: A Survey in Past and Present Research
2007
[39]
간행물
A unified theory of shared memory consistency.
2004
[40]
간행물
Distributed systems
2007
[41]
간행물
Shared Memory Consistency Models: A Tutorial
http://www.hpl.hp.co[...]
1996-12
[42]
간행물
"Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems
1990-07
[43]
저널
Multiprocessors Should Support Simple Memory Consistency Models
http://digital.libra[...]
1998-08
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com