Deadlock 데드락

데드락

[!tip] 데드락은 프로세스 2개, 자원 2개만 기억하면 된다.
데드락에는 프로세스 2개, 자원 2개가 필요하다는 사실만 기억하면 케이스를 만들어 낼 수 있다.

교착 상태 조건 4가지

다음 4가지 조건을 모두 만족하면 데드락이 발생한다.

1. Mutual Exclusion : 상호 배제. 프로세스가 타겟 자원을 요구 시 타 프로세스를 배제하고 배타적으로 요구한다. (자원을 혼자 쓰겠다.)
2. Hold & Wait : 자원 하나 홀드 한 상태에서, 다른 자원이 반환되기를 기다린다.
3. No Preemption : 비선점. 다른 프로세스가 가지고 있는 자원을 선점할 수 없다.[=뺏어올 수 없다] (반대 케이스는 내가 우선순위가 높으면 선점 가능한 경우.)
4. Circular Wait : 대기가 환형으로 발생하는 경우.

DB 데드락

DB Lock이 걸리는 범위?

• tx 시작하면서 모든 관련 테이블의 관련 row에 update lock을 걸고 시작하는게 아니라, 쿼리를 수행할 때 마다 순차적으로 lock을 획득하게 된다.
• WHERE에서 key column(index)에 대해 거르면 해당 row에 대해서만 lock이 걸린다.
• index가 걸려있다면, 선택한 row들만 lock이 걸린다.
• index가 안걸려 있어 전체 테이블을 서치하는 경우, 테이블 전체에 lock이 걸린다.

(Transaction) lost update problem과 deadlock

• (Transaction) lost update problem과 deadlock
• isolation level을 잘못 줘서 데드락 발생하는 케이스로, update lock을 획득하면 해결된다.

데드락은 한 테이블을 대상으로 하는 UPDATE, DELETE 에서도 발생 할 수 있다.

1. transaction (lock row1)
2. UPDATE (lock row2, waiting row1)
3. transaction (waiting row2)

• 1 update / 1 tx가 deadlock을 유발
• 통상 2개 이상의 테이블이 있어야 데드락이 발생할 것이라고 예상하게 되는데, 단일 update에서 업데이트 대상 row들의 lock을 한꺼번에 획득하는게 아니기 때문에 여기서도 데드락 발생 할 수 있다.
  • 일시에, 한꺼번에 획득하는게 아니라, row lock을 하나씩 순차적으로 획득하게 된다.
  • row1, row2에 대해 lock을 획득해야 하는데, row1에 이미 lock이 걸려 있으면, free 상태인 row2의 lock만 먼저 획득하고 row1이 release 될 때 까지 대기.

그렇다면 2개의 update가 동시에 실행 되었을 때에도 deadlock이 발생 할 수 있나?

• [1 update / 1 tx] 상황에서 데드락이 발생 할 수 있음은 자명한데, [1 update / 1 update] 상황에서도 데드락이 발생 할 수 있나?
• stackoverflow - Dale K 댓글은 헛소리니까 무시하고 Charlieface의 댓글 참조
  • If the rows are accessed in a different order, then of course you can get a deadlock… but you will not normally get a deadlock.
• https://dba.stackexchange.com/questions/234947/deadlock-on-two-update-statements-on-the-same-page
  • 서로 다른 index를 타는 경우 접근 순서가 달라 deadlock 생길 수 있다고 얘기 하고 있다.

=> 단일 update문 2개를 실행 했을 때, row에 대한 접근 순서가 다르면 데드락이 생길 수 있다.

Q. 하지만 경쟁적으로 lock을 획득한다면 다른 순서로 접근하든 같은 순서로 접근하든 deadlock에 걸릴 수 있는 것 아닌가? 싶은데… 아래와 같은 시나리오가 가능하지 않은지?

-- session1. lock(A, B)
UPDATE TBL SET NO = 1 WHERE KEY IN ('A', 'B');

-- session2. session1 release 하는 순간 lock(A) 획득
UPDATE TBL SET NO = 2 WHERE KEY IN ('A', 'B');

-- session3. session1 release 하는 순간 lock(B) 획득
UPDATE TBL SET NO = 3 WHERE KEY IN ('A', 'B');

=> 아마도 이를 방지하기 위해 먼저 요청한 statement 쪽에 release 된 row들을 몰아준다든가 하는 방식(queue?)을 사용 할 것 같은데, 발생하는 경우를 한 번도 못봐서 이 정도로 정리. DBMS 마다 동작이 다를 것 같기도 하다.

Lock

Lock을 release 하는 시점은 트랜잭션의 격리 수준 (isolation level)에 따라 결정된다.

• javadocs - isolation levels and concurrency
  • javadocs - SELECT만 해도 shared lock을 획득한다
• 격리 수준에 따른 SELECT 시 lock acquire/release 차이는 아래와 같다.

TRANSACTION_READ_UNCOMMITTED

• SELECT 시 shared lock
  • 걸지 않는다.
• tx 간섭
  • tx A가 commit 하지 않아도, tx A에서 변경한 값이 다른 tx의 읽기 결과에 반영된다. (dirty read)

TRANSACTION_READ_COMMITTED (default)

• SELECT 시 shared lock
  • shared lock을 걸었다가, 다음 row로 넘어갈 때 곧바로 해제한다.
• tx 간섭
  • tx A가 commit하는 순간, tx A에서 변경한 값이 다른 tx의 읽기 결과에 반영된다.
  • 따라서 한 tx 내에서 SELECT 할 때 마다 반환되는 값이 바뀔 수 있다. (REPETABLE READ 보장 안됨)

TRANSACTION_REPEATABLE_READ

• SELECT 시 shared lock
  • shared lock을 걸고, commit 할 때 까지 계속 잡고 있는다.
  • 따라서 commit 하기 전 까지, 다른 tx에서 exclusive lock을 획득 할 수 없다.
  • tx 안에서 SELECT+UPDATE 하는 경우, deadlock 유발 가능성 있음 사례
• tx 간섭
  • tx A가 commit해도, tx A에서 변경한 컬럼이 다른 tx의 읽기 결과에 반영되지 않는다.
  • 단, tx A에서 추가된 row는 다른 tx의 읽기 결과에 반영된다. (phantom read)

TRANSACTION_SERIALIZABLE

• SELECT 시 shared lock
  • TRANSACTION_REPEATABLE_READ와 같다.

[!warning] exclusive lock이 걸려 있는 row에 대한 SELECT는 직관적으로는 불가능 할 것 같지만,
실제로는 DBMS마다, isolation level 마다 다르다.

oracle의 isolation level과 동작은 조금 다르다.

• oracle의 isolation level
  • READ_COMMITTED, SERIALIZABLE 설정만 지원한다.
  • REPEATABLE_READ 는 SELECT ... FOR UPDATE로 간접 지원한다.
    • update lock을 걸어주면 해당 row들이 tx 진행 도중 갑자기 변경되는 일은 없을 것이므로 repeatable read를 만족한다.
    • phantom read는 여전히 발생 할 수 있으므로 이를 막으려면 SERIALIZABLE 설정 해야 한다.
  • READ_UNCOMMITTED는 아예 없다.
• 오라클은 SELECT 시 shared lock을 걸지 않는다. (isolation level과 무관하게,)
• exclusive lock을 가지고 있는 row에 대한 읽기(SELECT)가 가능하다.
• http://www.gurubee.net/lecture/2396#.Lock4

deadlock 방지

• 여러 테이블, 여러 row에 lock이 필요한 상황이고, 이로 인해 데드락이 발생하고 있을 때
• 해결 방법은
  1. table 접근 순서(lock 획득 순서)를 일치시킨다.
  2. 필요한 전체 lock을 한 번에 atomic 하게 획득한다. (DB lock을 획득하기 위한 단일 redis lock)
  3. tx 진입 시점에 SELECT ... FOR UPDATE NOWAIT 사용해서 lock을 모두 획득한다. (경합으로 인한 실패는 여전히 발생 가능하나 조기 실패 목적.)

app 단 lock VS DB 단 lock

앱단 lock은 redis로 특정 key에 대해서만 lock을 거는 방식을 많이 사용하게 된다.

• 보통 인메모리 Map<Key, Lock> 보다는 redis를 활용한다. (서버가 n대 이므로)
• SELECT - UPDATE 작업이 어떤 Key와 관계된다면, redis를 사용해 같은 회원에 대한 동시 작업은 막고, 서로 다른 회원에 대한 동시 작업은 가능하게끔 만들 수 있다.
  • e.g., 회원 정보 업데이트같이 회원 키로 SELECT하고 해당 레코드를 UPDATE하는 상황
• 여러 테이블에 걸쳐 일어나는 tx 작업에 사용 할 수 있다.
• API call 같이 DB와 무관한 작업에 대한 동시성을 제어 할 수 있어 활용도가 높다.
• 구조가 심플한 것도 장점이다.

[!info] 물론 DB lock도 여러 테이블에 걸쳐 사용 가능하지만, 테이블 접근 순서가 다른 2개의 tx가 동시에 수행되면 lock 획득 순서에 따라 데드락에 빠질 수 있다.

Lock Free는 CAS instruction 지원이 필요하다.

https://effectivesquid.tistory.com/m/entry/Lock-Free-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Non-Blocking-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98