트랜잭션의 동시성을 높이면 발생할 수 있는 문제와 이를 감지하는 방법

데이터베이스 시스템에서 여러 트랜잭션을 순서대로 처리하는 것은 바람직하지 않습니다. 단위 시간당 처리량이 낮을 뿐만 아니라 각 요청에 대한 응답 시간이 길어질 수도 있기 때문입니다. 따라서 데이터베이스 시스템은 여러 트랜잭션을 동시에 처리하는데요. 이때 발생할 수 있는 문제점에 대해 알아보고 문제를 미리 감지할 수 있는 방법에 대해 알아보도록 하겠습니다.

동시성을 높이면 문제가 발생할 수도 있다

앞서 언급했듯 데이터베이스 시스템은 단위 시간당 처리량(throughput)을 늘리기 위하여 여러 트랜잭션을 동시에 처리합니다. 그러나 이는 race condition을 유발할 수 있습니다. 예를 들어 보겠습니다.

우선 트랜잭션을 순서대로 실행하는 스케쥴(serial schedule)의 결과입니다. 트랜잭션이 끝난 이후에 다른 트랜잭션이 실행되어 최종적으로 A의 값이 900이 되었습니다.

다음은 동시성을 높인 스케쥴(concurrent schedule)입니다. 싱글 코어에서 멀티 프로그래밍을 통해 위와 같이 동작했다고 가정하였습니다. 그러나 serial schedule과 비교하면 예상하지 않은 결과가 나타났습니다. 각 트랜잭션이 50과 100을 빼서 850이 되어야하지만 그렇지 않습니다. 왜냐하면 A에 대하여 race condition이 발생했기 때문입니다.

Serializable schedule

따라서 우리는 concurrent schedule이 serial schedule과 동일한 결과를 만드는 지 확인해야합니다. 만약 concurrent schedule이 serial schedule과 동일한 결과를 만든다면 concurrent schedule을 직렬화 가능하다(serializable)고 표현합니다.

한편, 우리는 여러 트랜잭션이 주어질 때 트랜잭션의 순서를 섞어 경우의 수를 만들어 낼 수 있습니다. 그럼 그 경우의 수 중에서 serializable schedule은 어떻게 알 수 있을까요?

가장 간단한 방법은 가능한 트랜잭션의 경우를 모두 고려해보는 것입니다. 그러나 이 방법의 시간 복잡도는 $O(n!)$으로 트랜잭션의 수가 조금만 많아지면 실행할 수 없어집니다. 따라서 우리는 좀 더 효율적인 방법을 찾아야합니다.

Conflict Serializability

시간 복잡도를 줄이는 핵심적인 아이디어는 모든 경우의 수를 구하는 것이 아닌 연산의 순서를 바꿔보는 것입니다. 기본적으로 트랜잭션은 읽기 연산과 쓰기 연산으로 구성되어있는데요. 이때, 연산 순서에 따라 다음과 같이 분류할 수 있습니다.

• Read and Read: not conflict
• Read and Write: conflict
• Write and Read: conflict
• Write and Write: conflict

만약 not conflict한 작업의 순서를 변경하여 스케쥴이 serializable 하다면 이를 conflict serializable이라고 표현합니다.

Precedence graph

그러나 이 방법 역시 작업의 순서를 변경해야하며 실제로 값을 구해야만 판단할 수 있습니다. 하지만 그래프를 이용한다며 여기서 더 최적화를 할 수 있는데요. 바로 트랜잭션 사이에 나타나는 conflict 연산에 대하여 방향성 그래프를 정의하고 cycle이 발생하는지 검사하는 것입니다.

만약 cycle이 발생하지 않는다면 해당 스케쥴은 conflict serializable하다고 할 수 있습니다. 예시와 함께 보겠습니다.

위 그림은 스케쥴 2에서 conflict 연산의 관계를 표현하였습니다. 최종적으로 T1에서 T2으로의 흐름만 존재하므로 위 스케쥴은 conflict serializable 하다고 할 수 있습니다.

한편 스케쥴 3의 경우 T1과 T2 사이의 사이클이 발생하므로 위 스케쥴은 serializable 하지 않습니다.

Precedence graph의 한계점

그래프의 사이클로 serializable를 판단하는 방법은 매우 효율적이나 한 가지 한계점이 있습니다. 바로 실제로 serializable한 스케쥴을 serializable 하지 않다고 판단하는 것인데요. 예시와 함께 보겠습니다.

스케쥴 4의 경우 사이클이 발생하였으나 데이터 A, B를 각각 본다면 순차적으로 실행하고 있으므로 serializable 합니다. 따라서 이렇게 억울한 스케쥴이 serializable 하지 않다고 판단할 수 있습니다.

따라서 precedence graph를 이용한 방법은 시간 복잡도와 정확성에 대한 trade-off 관계에 있습니다. 그렇지만 serializable에 대한 판단은 절대 틀리지 않으며 성능 또한 비약적으로 상승 시킬 수 있으므로 적절한 개선안이라고 생각합니다.

마무리하며

이번 글에서는 트랜잭션을 동시에 처리하면 발생할 수 있는 동기화 문제를 알아보고 동기화 문제가 발생하지 않는 serializable schedule에 대해 알아보았습니다. 이후 동기화 문제를 미리 감지하기 위한 conflict serializable schedule과 이를 빠르게 확인할 수 있는 precedence graph까지 알아보았습니다. 이번 글이 트랜잭션 동시성 문제에 대한 이해를 높일 수 있었길 바랍니다. 😁