Distributed systems: transactions

Distributed systems: transactions

1. Transaction Protocols

   • Need higher level abstraction
   • Transactions can be completed or be abandoned

2. Assumptions

   • Reliable communication
     • Lower layers handle lost messages
   • Have strong back up mechanisms (host crashes / disk failures)

3. Properties of transactions

   • Atomic
     • Transaction indivisible
       • Takes pace or doesn't happen at all
   • Consistent
     • Maintain system invariants
       • E.G. no seat booked for 2 people
   • Isolated
     • Concurrent transactions do not interfere
       • Sell 2 different seats at same time
   • Durable
     • Once transaction finished, changes are permanent
       • E.G. book confirmation

4. Implementation - two methods for working with data

   • Private workspace
     • Copy files to host executing the transaction
       • Copy results back afterwards
   • Writeahead log
     • Modify files locally and log changes
       • Can undo changes (unravel)

5. Two-phase commit protocol

   • AIM to achieve atomicity
     • Has coordinator that tells others whether they can enter the critical section
   • Have subordinate that is interested in critical section
     • Checks with co-ordinator that all others agree with request for entrance
   • Central log that has messages
     • "Prepare", "Ready" , "commit"

6. Concurrency control

   • File locking
     • Only one file process allowed to access file
     • Avoid inconsistency
       • First acquire all locks (growing phase), perform operations, release locks (shrinking phase)
     • Deadlock possible
       • Avoid using global order of files
       • If lock not available, release all others and wait for random interval
   • Optimistic concurrency control
     • Check which files have been written
       • Any files written twice then abort transaction
         • Use WA log
         • Detect problems before committing
     • Advantage: deadlock free and maximum parallelism (don't hold locks)
     • Refinement: Use timestamps and abort only if transaction with higher TS wants to write

7. Dealing with failure

   • DS should cope with failure of one site
     • Silent failure: host does not respond
     • Byzantine: host sends false information

8. Failure detection 2-way: handshake protocol

   • If answer exceeds timeout then try again
     • Give up after fixed number of attempts
   • Works for silent failure, not byzantine

9. Byzantine failure

   • Assume processots faulty but communication reliable
     • Need to achieve agreement between working processors
       • More than 2/3 processors need to be working
       • Majority voting
         • Every processor sends to other one value of local variable
           • Honest processors send real value, faulty ones can send junk
           • Processors pass on all values to all others
             • Values received judged by each processor based on majority (honest processors should be identified)

Bilder und Dateien der Mindmap