๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“š ์ „๊ณต ๊ณต๋ถ€/DB๊ธฐ์ดˆ

[DB] ๋™์‹œ์„ฑ ์ œ์–ด

728x90

Concurrency Control Techniques

Concurrency Control Protocols : guarantee serializability (์ง๋ ฌํ™” ๋ณด์žฅ)

  • Locking
  • Timestamps
  • multiversion CC protocols
  • Optimistic protocols
  • Multiple granularity concurrency control protocol

Two-phase Locking Techniques : ์ด์ค‘ ๋ผํ‚น

lock ์ƒํƒœ 1, unlock ์ƒํƒœ๋Š” 0

 

Lock table : lock ์ •๋ณด๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” ์„œ๋ธŒ์‹œ์Šคํ…œ

  • plus a queue for transactions that are waiting to access item

Shared/Exclusive (or Read/Write) Locks : ๊ณต์œ (read lock), ๋ฐฐํƒ€(write lock)

  • Multiple-mode lock

Shared locking protocol

  1. ์–ด๋–ค ์•„์ดํ…œ์„ ์ฝ๊ธฐ ์ „์— read lock ๋˜๋Š” write lock์„ ํ•œ๋‹ค
  2. ์–ด๋–ค ์•„์ดํ…œ์„ ์“ฐ๊ธฐ์ „์—๋Š” Write lock ํ•„์š”
  3. ์ฝ๊ฑฐ๋‚˜ ์“ด ์ดํ›„ unlock
  4. ๋‹ค๋ฅธ ํŠธ๋žœ์ ์…˜์— ์˜ํ•ด unlock๋  ์ˆ˜ ์—†์Œ

Locking ๋งŒ์œผ๋กœ๋Š” ์ง๋ ฌํ™” ๋ณด์žฅ์ด ๋ถˆ๊ฐ€๋Šฅ

 

Lock table

<์•„์ดํ…œ ์ด๋ฆ„, LOCK, no_of_reads, Locking_transaction>

LOCK(X) = write-locked : ๋ฐฐํƒ€ lock์„ ์œ ์ง€ํ•˜๋Š” ๋‹จ์ผ ํŠธ๋žœ์ ์…˜

LOCK(X) = read-locked : ๊ณต์œ  lock์„ ์œ ์ง€ํ•˜๋Š” ํ•˜๋‚˜ ์ด์ƒ์˜ ํŠธ๋žœ์ ์…˜

2๋‹จ๊ณ„ ๋ผํ‚น ํ”„๋กœํ† ์ฝœ

two phase locking protocol (2PLP)

  1. growing phase : lock ๊ฑธ๊ธฐ ์‹œ์ž‘ํ•˜๋ฉด ๊ณ„์† ๊ฑธ์–ด์•ผํ•จ
  2. shrinking phase : unlock ์‹œ์ž‘ ํ›„ lock ์ƒ์„ฑ๋ถˆ๊ฐ€

์ง๋ ฌ๊ฐ€๋Šฅํ•œ ์Šค์ผ€์ค„์˜ ์ถฉ๋ถ„์กฐ๊ฑด์ด์ง€๋งŒ ํ•„์š”์กฐ๊ฑด์€ ์•„๋‹˜

< Basic 2PL >

  1. Conservative 2PL (= static 2PL) : ๋ณด์ˆ˜์ /์ •์  2PL
    • ๋ชจ๋“  lock์„ ์‹œ์ž‘๋ถ€๋ถ„์— ๋ฏธ๋ฆฌ ์„ ์–ธํ•˜๊ธฐ
    • deadlock-free!
  2. Strict 2PL : ์—„๊ฒฉํ•œ 2PL
    • ์ปค๋ฐ‹๋ ๋•Œ๊นŒ์ง€ ์“ฐ๊ธฐ์—ฐ์‚ฐ unlock ๋ถˆ๊ฐ€๋Šฅ
    • recoverablity → dirty read ์—†์Œ
    • not deadlock-free
  3. Rigorous 2PL : ์ฒ ์ €ํ•œ 2PL
    • strict ์Šค์ผ€์ค„ ๋ณด์žฅ
    • ์ปค๋ฐ‹๋ ๋•Œ๊นŒ์ง€ ์“ฐ๊ธฐ & ์ฝ๊ธฐ์—ฐ์‚ฐ unlock ๋ถˆ๊ฐ€๋Šฅ
    • ๊ตฌํ˜„์€ ๋” ์‰ฝ์ง€๋งŒ ์œตํ†ต์„ฑ์ด ๋–จ์–ด์ง

Dealing with Deadlock and Starvation

  • deadlock : ์ž ๊ธด ํ•ญ๋ชฉ์„ ๋ฌดํ•œ๋Œ€๊ธฐ์ค‘์ธ ์ƒํƒœ
  • starvation : abort, restart ๋ฐ˜๋ณตํ•˜๋Š” ๊ธฐ์•„ ์ƒํƒœ

Deadlock prevention protocols : ๋ฐ๋“œ๋ฝ ์˜ˆ๋ฐฉ

  1. Conservative 2PL (๋ณด์ˆ˜์  2pl, ๋ชจ๋“  lock ๋ฏธ๋ฆฌ ์„ ์–ธ)
  2. Ordering all the items
  3. Transaction timestamp TS(T) : ์‹œ์ž‘ ์ˆœ์„œ์— ๋”ฐ๋ผ ์ •๋ ฌ
  4. Deadlock preventoin schemes ⇒ wait-die / wound-wait

wait-die : ์•„์ดํ…œ ๋บ์œผ๋ ค๋Š” ์• ๊ฐ€ older → ๊ธฐ๋‹ค๋ฆผ

  • younger → abort

wound-wait : ์•„์ดํ…œ ๊ฐ–๊ณ ์žˆ๋˜ ์• ๊ฐ€ younger → ๊ธฐ๋‹ค๋ฆผ

  • ์•„์ดํ…œ ๊ฐ–๊ณ ์žˆ๋˜ ์• ๊ฐ€ older → ๊ฐ–๊ณ ์žˆ๋Š” ์• ๊ฐ€ abort (๋บ๊น€)

Deadlock prevention protocol without timestamps

  • no waiting algorithm
    • if ํŠธ๋žœ์ ์…˜์ด lock์— ์ ‘๊ทผํ•  ์ˆ˜ ์—†์œผ๋ฉด ๋ฐ”๋กœ abort&restart
    • no checking on deadlock
    • ๊ทผ๋ฐ ๋ถˆํ•„์š”ํ•œ abort๊ฐ€ ๋งŽ์•„์ ธ์„œ ๋น„ํšจ์œจ์ 
  • Cautious waiting algorithm
    • ๋ถˆํ•„์š”ํ•œ abort๋ฅผ ๊ฐ์†Œ
    • if ํŠธ๋žœ์ ์…˜์ด lock์— ์ ‘๊ทผํ• ๋•Œ, lockํ•œ ํŠธ๋žœ์ ์…˜์ด ๋‹ค๋ฅธ ์•„์ดํ…œ์„ ๊ธฐ๋‹ค๋ฆฌ๊ณ  ์žˆ๋‹ค๋ฉด (blocked ์ƒํƒœ) : abort
      • lockํ•œ ๋†ˆ์ด not blocked : wait
    • deadlock-free
    • ๋‘˜ ๋‹ค ๊ธฐ๋‹ค๋ฆฌ๋Š” ๊ฒฝ์šฐ, block ์‹œ๊ฐ„์œผ๋กœ ์ •๋ ฌ๋˜๋ฏ€๋กœ ์ˆœ์ฐจ์‹คํ–‰ ๊ฐ€๋Šฅ

Deadlock Detection : ๋ฐ๋“œ๋ฝ ํƒ์ง€

  • victim selection : abortํ•  ํฌ์ƒ์–‘์„ ๊ณ ๋ฅด๊ธฐ
  • wait-for graph : if has cycle → deadlock
  • Timeout
    • ์ผ์ • ์‹œ๊ฐ„์ด ์ง€๋‚˜๋ฉด abort&restart
    • no deadlock check
  • Recovery
    • minimum cost๋ฅผ ํฌ์ƒ์–‘์œผ๋กœ.
    • rollback : abort & restart. ๋ถ€๋ถ„ ๋กค๋ฐฑ์€ ๋ถˆ๊ฐ€๋Šฅ
    • starvation (livelock)
      • ๊ฐ™์€ ํฌ์ƒ์–‘์ด ๊ณ„์†๋œ๋‹ค๋ฉด ๊ทธ๊ฒŒ never completes
      • first come first served

Granularity of data items and multiple granularity locking : ์•„์ดํ…œ ์„ธ๋ถ„ํ™”์™€ ๋‹ค์ค‘์„ธ๋ถ„ํ™” ๋ผํ‚น

  • locking ๋‹จ์œ„๊ฐ€ ์ž‘์„์ˆ˜๋ก ์˜ค๋ฒ„ํ—ค๋“œ ํ™•๋ฅ ์ด ๋†’๋‹ค.
  • locking ๋‹จ์œ„๊ฐ€ ํด์ˆ˜๋ก ๋™์‹œ์„ฑ ์ˆ˜์ค€์€ ๋‚ฎ๋‹ค.

Multiple Granularity level locking

์ƒ์œ„ ๋ฐ์ดํ„ฐ lock ์‹œ๋„ ์‹œ, ๋ฐ์ดํ„ฐ ์ „์ฒด๋ฅผ ๋’ค์ ธ์„œ sub item ์ค‘์— lock์ด ์—†๋‹ค๋ฉด ํ—ˆ์šฉ ๊ฐ€๋Šฅ.

 

Timestamp Mechanism : ํƒ€์ž„์Šคํƒฌํ”„ ๋ฉ”์ปค๋‹ˆ์ฆ˜

  • deadlock-free
  • cascading rollback
  • cyclic restart (starvation)

Multiversion Scheme

  • ์›๋ณธ๊ณผ ์—ฌ๋Ÿฌ ๋ฒ„์ „์„ ๋งŒ๋“ ๋‹ค.
  • deadlock-free
  • ๋Œ€์‹  ๋ฒ„์ „ ๊ด€๋ฆฌ๊ฐ€ ํ•„์š”ํ•จ
728x90