동시성 제어
정보기술과 컴퓨터 과학, 특히 컴퓨터 프로그래밍, 운영 체제, 멀티프로세서, 데이터베이스 분야에서 동시성 제어(concurrency control)는 병행 작업에 대해 올바른 결과를 생성하는 동시에, 그 결과를 가능한 한 빠르게 얻도록 보장하는 것을 말한다.
소프트웨어와 컴퓨터 하드웨어를 포함한 컴퓨터 시스템은 모듈 또는 구성 요소로 이루어져 있다. 각 구성 요소는 올바르게 작동하도록, 즉 특정 일관성 규칙을 따르거나 충족하도록 설계된다. 병행하게 작동하는 구성 요소들이 메시지 전달이나 (주기억장치 또는 기억 장치 내의) 액세스된 데이터 공유를 통해 상호작용할 때, 한 구성 요소의 일관성이 다른 구성 요소에 의해 훼손될 수 있다. 동시성 제어의 일반적인 영역은 상호작용하며 병행 작동하는 구성 요소들의 일관성, 나아가 전체 시스템의 일관성과 정확성을 유지하기 위한 규칙, 방법, 설계 방법론 및 과학 이론을 제공한다. 시스템에 동시성 제어를 도입한다는 것은 일반적으로 성능 저하를 초래하는 작업 제약을 적용함을 의미한다. 작업의 일관성과 정확성은 성능을 합리적인 수준 이하로 떨어뜨리지 않으면서 가능한 한 좋은 효율성으로 달성되어야 한다. 동시성 제어는 단순한 순차 알고리즘에 비해 병행 알고리즘에서 상당한 추가 복잡성과 오버헤드를 요구할 수 있다.
예를 들어, 동시성 제어의 실패는 데이터 손상을 초래할 수 있다.
데이터베이스의 동시성 제어
[편집]비고:
- 이 섹션은 모든 트랜잭션 시스템, 즉 데이터베이스 트랜잭션(원자적 트랜잭션. 예: 시스템 관리 및 전용 데이터베이스 시스템을 구현하는 스마트폰 네트워크의 트랜잭션 객체)을 사용하는 모든 시스템에 적용되며, 범용 데이터베이스 관리 시스템(DBMS)에만 국한되지 않는다.
- DBMS는 데이터베이스 트랜잭션에만 특유한 것이 아니라 일반적인 운영 체제와 관련된 동시성 제어 문제도 다루어야 한다. 이러한 문제(예: 아래의 운영 체제의 동시성 제어 참조)는 이 섹션의 범위를 벗어난다.
데이터베이스 관리 시스템(DBMS; 예: Bernstein 등 1987, Weikum 및 Vossen 2001), 기타 트랜잭션 객체 및 관련 분산 애플리케이션(그리드 컴퓨팅 및 클라우드 컴퓨팅 등)에서의 동시성 제어는 각 데이터베이스의 데이터 무결성을 해치지 않으면서 데이터베이스 트랜잭션이 병행으로 수행되도록 보장한다. 따라서 동시성 제어는 시간이 겹쳐 실행되는 둘 이상의 데이터베이스 트랜잭션이 동일한 데이터에 액세스할 수 있는 모든 시스템(사실상 거의 모든 범용 데이터베이스 시스템)에서 정확성을 위한 필수 요소이다. 결과적으로 1970년대 초 데이터베이스 시스템이 등장한 이래 방대한 관련 연구가 축적되어 왔다. 데이터베이스 시스템을 위해 잘 확립된 동시성 제어 과학 이론이 위에서 언급된 참고 문헌에 요약되어 있다. 바로 직렬화 가능성 이론으로, 이는 동시성 제어 방법과 메커니즘을 효과적으로 설계하고 분석할 수 있게 해준다. 추상 자료형에 대한 원자적 트랜잭션의 동시성 제어를 위한 대안 이론이 (Lynch 등 1993)에서 제시되었으나 아래에서는 활용되지 않는다. 이 이론은 더 정교하고 복잡하며 범위가 넓지만, 고전적인 이론에 비해 데이터베이스 문헌에서 덜 활용되어 왔다. 각 이론은 장단점과 강조점, 통찰이 있다. 어느 정도는 서로 보완적이며, 이들을 병합하는 것이 유용할 수 있다.
정확성을 보장하기 위해 DBMS는 일반적으로 애플리케이션의 정확성이 손상되지 않는 경우에 성능 향상을 위해 의도적으로 직렬화 가능성을 완화하는 경우를 제외하고는, 오직 직렬화 가능한 트랜잭션 스케줄만 생성되도록 보장한다. (여러 이유로 언제든 발생할 수 있는) 실패한(중단된) 트랜잭션의 경우에도 정확성을 유지하기 위해 스케줄은 (중단으로부터의) 복구 가능성 속성을 가져야 한다. 또한 DBMS는 커밋된 트랜잭션의 효과가 사라지지 않고, 중단된(롤백된) 트랜잭션의 효과가 관련 데이터베이스에 남지 않도록 보장한다. 전반적인 트랜잭션 특성은 보통 아래의 ACID 규칙으로 요약된다. 데이터베이스가 분산 데이터베이스화되거나 분산 환경에서 협력할 필요가 생기면서(예: 1990년대 초의 연합 데이터베이스 및 현재의 클라우드 컴퓨팅), 동시성 제어 메커니즘의 효과적인 분산이 특별한 주목을 받아왔다.
데이터베이스 트랜잭션과 ACID 규칙
[편집]
데이터베이스 트랜잭션(또는 원자적 트랜잭션)의 개념은 언제든 충돌이 발생할 수 있는 결함이 있는 환경에서 잘 이해된 데이터베이스 시스템 동작을 가능하게 하고, 충돌로부터 잘 이해된 데이터베이스 상태로 복구할 수 있도록 진화해 왔다. 데이터베이스 트랜잭션은 작업의 단위로, 일반적으로 데이터베이스에 대한 일련의 작업(예: 데이터베이스 객체 읽기, 쓰기, 락 획득 등)을 캡슐화하며, 이는 데이터베이스 및 기타 시스템에서 지원되는 추상화이다. 각 트랜잭션은 어떤 프로그램/코드 실행이 해당 트랜잭션에 포함되는지에 대해 잘 정의된 경계를 가진다(트랜잭션 프로그래머가 특별한 트랜잭션 명령을 통해 결정함). 모든 데이터베이스 트랜잭션은 다음 규칙을 따른다(데이터베이스 시스템의 지원을 통해 보장됨):
- 원자성(Atomicity) - 트랜잭션이 완료(각각 커밋 또는 중단)될 때 모든 작업의 효과가 남거나 혹은 전혀 남지 않아야 한다("모두 아니면 전무" 의미론). 즉, 외부 세계에서 볼 때 커밋된 트랜잭션은 (데이터베이스에 미치는 영향에 의해) 분할할 수 없는(원자적인) 것으로 보이며, 중단된 트랜잭션은 데이터베이스에 전혀 영향을 주지 않는다.
- 일관성(Consistency) - 모든 트랜잭션은 데이터베이스를 일관된(올바른) 상태로 남겨두어야 한다. 즉, 데이터베이스의 미리 정해진 무결성 규칙(데이터베이스 객체 내 및 객체 간의 제약 조건)을 유지해야 한다. 트랜잭션은 데이터베이스를 하나의 일관된 상태에서 다른 일관된 상태로 변환해야 한다(단, 트랜잭션 자체가 올바른지, 즉 애플리케이션 관점에서 의도한 바를 정확히 수행하는지 확인하는 것은 트랜잭션 프로그래머의 책임이며, 미리 정의된 무결성 규칙은 DBMS에 의해 강제된다). 따라서 데이터베이스는 정상적으로 트랜잭션에 의해서만 변경될 수 있으므로, 데이터베이스의 모든 상태는 일관된다.
- 독립성(Isolation) - 트랜잭션은 (실행의 최종 결과로서) 서로 간섭할 수 없다. 또한 보통(동시성 제어 방법에 따라) 완료되지 않은 트랜잭션의 효과는 다른 트랜잭션에 보이지 않는다. 고립성을 제공하는 것이 동시성 제어의 주요 목표이다.
- 내구성(Durability) - 성공적인(커밋된) 트랜잭션의 효과는 충돌 중에도 지속되어야 한다(일반적으로 트랜잭션의 효과와 커밋 이벤트를 비휘발성 메모리에 기록함으로써 달성됨).
원자적 트랜잭션의 개념은 수년에 걸쳐 실제로 워크플로의 유형을 구현하며 원자적이지 않은 비즈니스 트랜잭션으로 확장되었다. 그러나 이러한 향상된 트랜잭션도 일반적으로 원자적 트랜잭션을 구성 요소로 활용한다.
왜 동시성 제어가 필요한가?
[편집]트랜잭션이 직렬로, 즉 시간상 겹침 없이 순차적으로 실행된다면 트랜잭션 동시성은 존재하지 않는다. 그러나 작업이 교차되는 병행 트랜잭션이 제어되지 않은 방식으로 허용되면 다음과 같은 예기치 않은 바람직하지 않은 결과가 발생할 수 있다:
- 수정 손실(lost update) 문제: 두 번째 트랜잭션이 첫 번째 병행 트랜잭션이 쓴 데이터 항목의 값 위에 두 번째 값을 덮어쓰고, 첫 번째 값은 선행 순서에 따라 그 값을 읽어야 하는 다른 병행 트랜잭션들에게 손실된다. 잘못된 값을 읽은 트랜잭션은 부정확한 결과로 끝난다.
- 더티 리드(dirty read) 문제: 트랜잭션이 나중에 중단된 트랜잭션이 쓴 값을 읽는다. 이 값은 중단 시 데이터베이스에서 사라지며, 어떤 트랜잭션도 읽지 않았어야 한다("더티 리드"). 읽기 작업을 수행한 트랜잭션은 부정확한 결과로 끝난다.
- 부정확한 요약 문제: 한 트랜잭션이 반복되는 데이터 항목의 모든 인스턴스 값에 대해 요약을 수행하는 동안, 두 번째 트랜잭션이 해당 데이터 항목의 일부 인스턴스를 업데이트한다. 결과 요약은 두 트랜잭션 사이의 (보통 정확성을 위해 필요한) 어떤 선행 순서도 반영하지 못하고, 업데이트 타이밍이나 특정 업데이트 결과가 요약에 포함되었는지 여부에 따른 무작위적인 결과를 나타낸다.
대부분의 고성능 트랜잭션 시스템은 성능 요구 사항을 충족하기 위해 트랜잭션을 병행으로 실행해야 한다. 따라서 동시성 제어 없이는 이러한 시스템은 올바른 결과를 제공할 수도 없고 데이터베이스를 일관되게 유지할 수도 없다.
동시성 제어 메커니즘
[편집]카테고리
[편집]동시성 제어 메커니즘의 주요 카테고리는 다음과 같다:
- 낙관적 - 트랜잭션이 (읽기, 쓰기) 작업을 차단하지 않고 진행하도록 허용하며("...규칙이 충족될 것이라고 낙관함..."), 각 트랜잭션의 커밋 시점에만 원하는 무결성 규칙(예: 직렬화 성질 및 복구 가능성)의 위반 여부를 확인한다. 커밋 시 위반이 감지되면 트랜잭션은 중단되고 재시작된다. 이 접근 방식은 중단되는 트랜잭션이 적을 때 매우 효율적이다.
- 비관적 - 규칙 위반을 일으킬 가능성이 있는 경우, 위반 가능성이 사라질 때까지 트랜잭션의 작업을 차단한다. 작업 차단은 일반적으로 성능 저하를 수반한다.
- 반낙관적 - 위반의 유형과 감지 속도에 따라 비관적 또는 낙관적으로 대응한다.
트랜잭션 유형의 혼합, 컴퓨팅의 병렬화 수준 및 기타 요인에 따라 카테고리별로 서로 다른 성능, 즉 평균 트랜잭션 완료율(처리량)을 제공한다. 트레이드오프에 대한 선택과 지식이 있다면 최고의 성능을 제공하는 카테고리와 방법을 선택해야 한다.
두 트랜잭션(각자가 상대방을 차단함) 또는 그 이상의 상호 차단은 교착 상태를 유발하며, 관련된 트랜잭션들은 멈춰서 완료에 도달할 수 없게 된다. 차단을 사용하는 대부분의 비낙관적 메커니즘은 교착 상태에 빠지기 쉬우며, 이는 멈춘 트랜잭션을 의도적으로 중단(교착 상태의 다른 트랜잭션들을 해제함)하고 즉시 재시작 및 재실행함으로써 해결된다. 교착 상태의 발생 가능성은 일반적으로 낮다.
차단, 교착 상태, 중단 모두 성능 저하를 초래하며, 이것이 카테고리 간의 트레이드오프이다.
방법
[편집]동시성 제어를 위한 많은 방법이 존재한다. 대부분은 위의 주요 카테고리 내에서 구현될 수 있다. 각각 많은 변형이 있고 경우에 따라 겹치거나 결합될 수 있는 주요 방법들은 다음과 같다:[1]
- 로킹 (예: 2단계 로킹 - 2PL) - 데이터에 할당된 락을 통해 데이터 액세스를 제어한다. 다른 트랜잭션에 의해 잠긴 데이터 항목(데이터베이스 객체)에 대한 트랜잭션의 액세스는 락이 해제될 때까지 (락 유형과 액세스 작업 유형에 따라) 차단될 수 있다.
- 직렬화 그래프 확인 (직렬화 가능성, 충돌, 또는 선행 그래프 확인이라고도 함) - 스케줄의 유향 그래프에서 순환을 확인하고 중단을 통해 이를 끊는다.
- 타임스탬프 순서 (TO) - 트랜잭션에 타임스탬프를 할당하고, 타임스탬프 순서에 따라 데이터 액세스를 제어하거나 확인한다.
위의 방법들과 함께 활용되는 다른 주요 동시성 제어 유형은 다음과 같다:
- 다중 버전 동시성 제어 (MVCC) - 객체가 기록될 때마다 데이터베이스 객체의 새 버전을 생성하고, 스케줄링 방법에 따라 트랜잭션의 읽기 작업이 최근의 여러 관련 버전(각 객체에 대해)을 읽을 수 있도록 허용함으로써 동시성과 성능을 높인다.
- 인덱스 동시성 제어 - 사용자 데이터가 아닌 인덱스에 대한 액세스 작업을 동기화한다. 특화된 방법들이 상당한 성능 향상을 제공한다.
- 개인 작업 공간 모델 (지연 업데이트) - 각 트랜잭션은 액세스한 데이터에 대해 개인 작업 공간을 유지하며, 변경된 데이터는 커밋 시점에만 트랜잭션 외부로 가시화된다(예: Weikum 및 Vossen 2001). 이 모델은 여러 경우에 이점이 있는 다른 동시성 제어 동작을 제공한다.
1970년대 초창기부터 데이터베이스 시스템에서 가장 일반적인 메커니즘 유형은 강격격 2단계 로킹(SS2PL; 엄격한 스케줄링 또는 엄격한 2PL이라고도 함)으로, 이는 2단계 로킹(2PL)의 특수한 사례(변형)이다. 이것은 비관적이다. (역사적인 이유로 인한) 긴 이름에도 불구하고 SS2PL 메커니즘의 아이디어는 간단하다. "트랜잭션에 의해 적용된 모든 락은 트랜잭션이 종료된 후에만 해제한다." SS2PL(또는 Rigorousness)은 또한 이 메커니즘에 의해 생성될 수 있는 모든 스케줄 집합의 이름이기도 하다. 즉, 이러한 SS2PL(또는 Rigorous) 스케줄은 SS2PL(또는 Rigorousness) 속성을 가진다.
동시성 제어 메커니즘의 주요 목표
[편집]동시성 제어 메커니즘은 우선 올바르게 작동해야 한다. 즉, 트랜잭션이 병행 실행되는 동안 각 트랜잭션의 (동시성과 관련된) 무결성 규칙을 유지해야 하며, 결과적으로 전체 트랜잭션 시스템의 무결성을 유지해야 한다. 정확성은 가능한 한 좋은 성능과 함께 달성되어야 한다. 또한 트랜잭션이 프로세스, 컴퓨터, 컴퓨터 망에 걸쳐 분산되어 있는 동안 효과적으로 작동해야 할 필요성이 점점 커지고 있다. 동시성 제어에 영향을 줄 수 있는 다른 주제로는 복구와 복제가 있다.
정확성
[편집]직렬화 가능성
[편집]정확성을 위해 대부분의 동시성 제어 메커니즘의 공통적인 주요 목표는 직렬화 성질을 가진 스케줄을 생성하는 것이다. 직렬화 가능성이 없으면 바람직하지 않은 현상이 발생할 수 있다. 예를 들어 계좌에서 돈이 사라지거나 아무데서나 생겨날 수 있다. 스케줄의 직렬화 가능성은 동일한 트랜잭션들을 가진 어떤 직렬 스케줄(즉, 트랜잭션들이 시간상 겹침 없이 순차적이며, 따라서 서로 완전히 독립된 상태: 두 트랜잭션이 동일한 데이터에 병행 액세스하는 것이 불가능함)과 (결과 데이터베이스 값에서) 동등함을 의미한다. 직렬화 가능성은 데이터베이스 트랜잭션 간의 가장 높은 수준의 독립성으로 간주되며, 병행 트랜잭션의 주요 정확성 기준이다. 어떤 경우에는 더 나은 성능을 위해(스냅샷 격리 메커니즘 등) 또는 고도의 분산 시스템에서 가용성 요구 사항을 충족하기 위해(궁극적 일관성 참조) 타협된, 완화된 형태의 직렬화 가능성이 허용되기도 하지만, 이는 애플리케이션의 정확성이 완화에 의해 훼손되지 않는 경우에만 가능하다(예: 돈 트랜잭션의 경우 완화로 인해 돈이 사라지거나 생겨날 수 있으므로 완화가 허용되지 않는다).
구현된 거의 모든 동시성 제어 메커니즘은 효율적으로 구현될 수 있고 대부분의 직렬화 가능한 스케줄을 포함하는 광범위한 특수 사례인 충돌 직렬화 가능성을 제공함으로써 직렬화 가능성을 달성한다.
복구 가능성
[편집]동시성 제어는 또한 중단된 트랜잭션(여러 이유로 항상 발생할 수 있음)의 경우에도 정확성을 유지하기 위해 일반적으로 스케줄의 복구 가능성 속성을 보장한다. (중단으로부터의) 복구 가능성은 스케줄 내의 어떤 커밋된 트랜잭션도 중단된 트랜잭션이 쓴 데이터를 읽지 않았음을 의미한다. 그러한 데이터는 (중단 시) 데이터베이스에서 사라지며 부정확한 데이터베이스 상태의 일부가 된다. 그러한 데이터를 읽는 것은 ACID의 일관성 규칙을 위반하는 것이다. 직렬화 가능성과 달리 복구 가능성은 어떤 경우에도 타협하거나 완화할 수 없는데, 왜냐하면 어떤 완화든 중단 시 즉각적인 데이터베이스 무결성 위반을 초래하기 때문이다. 위에 나열된 주요 방법들은 직렬화 가능성 메커니즘을 제공한다. 일반적인 형태의 그 어떤 방법도 자동으로 복구 가능성을 제공하지 않으며, 복구 가능성을 지원하기 위한 특별한 고려 사항과 메커니즘 향상이 필요하다. 흔히 활용되는 복구 가능성의 특수한 사례는 엄격성으로, 이는 실패로부터의 효율적인 데이터베이스 복구를 가능하게 한다(단, 낙관적 구현은 제외됨).
분산
[편집]컴퓨팅의 빠른 기술 발전으로 인해 저지연 컴퓨터 망이나 버스를 통한 로컬 컴퓨팅과 분산 컴퓨팅의 차이가 모호해지고 있다. 따라서 컴퓨터 클러스터나 멀티 코어 프로세서와 같은 분산 환경에서 로컬 기술을 효과적으로 활용하는 것이 일반적이다. 그러나 로컬 기술은 한계가 있으며 확장을 위해 멀티프로세서(또는 멀티 코어)가 지원하는 다중 프로세스(또는 스레드)를 사용한다. 트랜잭션 자체가 다중 프로세스에 걸쳐 있어야 하는 경우, 이는 종종 트랜잭션을 분산 트랜잭션으로 만든다. 이러한 경우 대부분의 로컬 동시성 제어 기술은 확장이 잘 되지 않는다.
복구
[편집]모든 시스템은 실패하기 마련이며, 실패로부터의 복구 처리는 필수적이다. 동시성 제어 메커니즘에 의해 결정되는 생성된 스케줄의 속성은 복구의 효과와 효율성에 영향을 줄 수 있다. 예를 들어, 위 섹션 복구 가능성에서 언급된 엄격성 속성은 효율적인 복구를 위해 종종 바람직하다.
레플리케이션
[편집]높은 가용성을 위해 데이터베이스 객체는 종종 복제된다. 동일한 데이터베이스 객체의 복제본(레플리카) 업데이트는 동기화된 상태를 유지해야 한다. 이는 동시성 제어가 수행되는 방식에 영향을 줄 수 있다(예: 짐 그레이 등 1996[2]).
운영 체제의 동시성 제어
[편집]다중작업 운영 체제, 특히 실시간 운영체제는 운영 체제가 실행되는 하드웨어의 제한으로 인해 실제로는 특정 순간에 하나 또는 소수의 작업만 실행되고 있음에도 불구하고, 그 위에서 실행되는 모든 작업이 동시에 실행되고 있다는 환상을 유지해야 한다. 모든 작업이 서로 독립적일 때 이러한 다중 작업은 상당히 간단하다. 그러나 여러 작업이 동일한 리소스를 사용하려고 하거나 작업들이 정보를 공유하려고 할 때 혼란과 불일치가 발생할 수 있다. 병행 컴퓨팅의 과제는 이 문제를 해결하는 것이다. 일부 솔루션은 데이터베이스에서 사용되는 락과 유사한 "락"을 포함하지만, 이는 교착 상태와 같은 자체적인 문제를 일으킬 위험이 있다. 다른 솔루션으로는 비차단 알고리즘과 RCU(Read-copy-update)가 있다.
같이 보기
[편집]참고 자료
[편집]- Andrew S. Tanenbaum, Albert S Woodhull (2006): Operating Systems Design and Implementation, 3rd Edition, Prentice Hall, ISBN 0-13-142938-8
- Silberschatz, Avi; Galvin, Peter; Gagne, Greg (2008). 《Operating Systems Concepts, 8th edition》. John Wiley & Sons. ISBN 978-0-470-12872-5.
각주
[편집]- ↑ Philip A. Bernstein, Eric Newcomer (2009): Principles of Transaction Processing, 2nd Edition 보관됨 2010-08-07 - 웨이백 머신, Morgan Kaufmann (Elsevier), June 2009, ISBN 978-1-55860-623-4 (page 145)
- ↑ Gray, J.; Helland, P.; O'Neil, P.; Shasha, D. (1996). 《Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data》. The dangers of replication and a solution (PDF). 173–182쪽. doi:10.1145/233269.233330.[깨진 링크(과거 내용 찾기)]
| 유형 | |
|---|---|
| 개념 | |
| 객체 | |
| 구성 요소 | |
| 기능 | |
| 관련 주제 | |
