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과 Isolation level

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

• 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와 같다.

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

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

• oracle의 isolation level
  • READ_COMMITTED, SERIALIZABLE 설정만 지원한다.
  • READ_UNCOMMITTED는 아예 없다.
  • REPEATABLE_READ 는 SELECT ... FOR UPDATE로 간접 지원한다.
    • update lock을 걸어주면 해당 row들이 tx 진행 도중 갑자기 변경되는 일은 없을 것이므로 repeatable read를 만족한다.
    • phantom read는 여전히 발생 할 수 있으므로 이를 막으려면 SERIALIZABLE 설정 해야 한다.
• 오라클은 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을 미리 모두 획득하고, 경합으로 인한 획득 불가 시 대기하지 않고 바로 실패하여 deadlock을 예방한다.

app 단 lock VS DB 단 lock

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

• 보통 인메모리 Map<Key, Lock> 보다는 redis를 활용한다. (서버가 n대 이므로)
• SELECT - UPDATE 작업이 어떤 Key와 관계된다면, redis를 사용해 같은 회원에 대한 동시 작업은 막고, 서로 다른 회원에 대한 동시 작업은 가능하게끔 만들 수 있다.
  • e.g., 회원 정보 업데이트같이 회원 키로 SELECT하고 해당 레코드를 UPDATE하는 상황
• 새로 INSERT 하는 경우, 아직 DB에 row가 없어 lock을 걸 대상이 없는데, redis는 이런 경우에도 사용 가능하다.
• 여러 테이블에 걸쳐 일어나는 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