$30 off During Our Annual Pro Sale. View Details »

Argus Papers We Love

Argus Papers We Love

Caitie McCaffrey

January 20, 2017
Tweet

More Decks by Caitie McCaffrey

Other Decks in Technology

Transcript

  1. Distributed Programming
    in Argus
    Barbara Liskov
    Papers We Love SF - January 2017

    View Slide

  2. Caitie McCaffrey
    @caitie
    Distributed Systems Engineer
    CaitieM.com

    View Slide

  3. 1988

    View Slide

  4. “Technological advances have made it
    cost effective to construct large
    systems from collections of computer
    connected via networks. To support
    such systems, there is a growing need
    for effective way to organize and
    maintain distributed programs”
    Guardians and Actions: Linguistic Support for Robust, Distributed Programs

    View Slide

  5. Atomicity
    RPC
    &

    View Slide

  6. Guardians and Actions: Linguistic Support for Robust, Distributed Programs
    “We believe that the most desirable
    form of communication is the paired
    send and reply”
    Remote Procedure Calls

    View Slide

  7. Guardians and Actions: Linguistic Support for Robust, Distributed Programs
    “We believe the form of communication
    that is needed is remote procedure call
    with at-most-once semantics”
    Remote Procedure Calls

    View Slide

  8. Argus
    RPC
    In

    View Slide

  9. “a special kind of abstract object whose
    purpose is to encapsulate a resource”
    Guardians
    Distributed Programming in Argus

    View Slide

  10. “it permits its resource to be accessed
    by means of special procedures, called
    handlers”
    Handlers
    Distributed Programming in Argus

    View Slide

  11. Argus
    Banking
    with

    View Slide

  12. Branch Guardian
    Open (a: account_number)
    Close (a: account_number)
    Deposit (a: account_number, amt: int)
    Withdraw (a: account_number, amt: int)
    Total()
    Handlers

    View Slide

  13. Branch A Branch B
    Account 123 : $100
    Account 456: $50
    Account 789: $250
    Open (123)
    Deposit(123, 100)
    Open (456)
    Deposit(456, 50)
    Open (789)
    Deposit(789, 250)

    View Slide

  14. Atomicity
    RPC
    &

    View Slide

  15. “An adequate language must provide a
    modular, reasonably automatic method
    for achieving consistency ”
    Atomicity
    Distributed Programming in Argus

    View Slide

  16. Guardians and Actions: Linguistic Support for Robust, Distributed Programs
    “Our solution to the problem of
    maintaining consistent distributed data
    in the face of concurrent, potentially
    interfering activities, and in the face of
    system failures such as node crashes
    and network disruptions while these
    activities are running is to make
    activities atomic”
    Atomicity

    View Slide

  17. Argus
    Atomicity
    In

    View Slide

  18. Serializable
    Actions
    Total (abort or commit)

    View Slide

  19. Atomic Abstract Data Type
    Atomic Objects
    Argus Provides: atomic arrays, records,
    variants, characters, and integers

    View Slide

  20. Read Write Lock
    Locking Rules
    Multiple Readers are Allowed
    Readers Exclude Writers
    Writer Exclude other Writers & Readers

    View Slide

  21. Distributed Programing in Argus
    “Computation in Argus starts as a top
    action at some guardian. The
    computation spreads to other
    guardians by means of handler calls.
    Execution of a handler call may cause
    some objects at the handler’s guardian
    to be modified, and may in turn lead to
    further calls”

    View Slide

  22. Argus
    Banking
    with

    View Slide

  23. Branch A Branch B
    Account 123 : $100
    Account 456: $50
    Account 789: $250
    Transfer( amt: int,
    from: account_number, to: account_number)

    View Slide

  24. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    SubAction: Deposit (123, 50)
    Transfer Action
    SubAction: Withdraw(789, 50)
    Transfer
    Deposit Withdraw

    View Slide

  25. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    SubAction: Deposit (123, 50)
    Transfer Action
    SubAction: Withdraw(789, 50)
    Transfer
    Deposit Withdraw
    enter topaction
    coenter
    action
    branchA.Deposit(123, 50)
    action
    branchB.Withdraw(789, 50)
    end
    end

    View Slide

  26. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    Deposit (123, 50)
    Transfer Action
    Withdraw(789, 50)

    View Slide

  27. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    Deposit (123, 50)
    Transfer Action
    Withdraw(789, 50)
    Account 123 : $150 Account 789: $200
    V1 V1

    View Slide

  28. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    Deposit
    Success
    Transfer Action
    Withdraw
    Success
    Account 123 : $150 Account 789: $200
    V1 V1

    View Slide

  29. Branch B
    Account 789: $250
    Branch A
    Account 123 : $100
    Account 456: $50
    Transfer Action
    Account 123 : $150 Account 789: $200
    V1 V1
    Commit Top Level Action
    2PC Transfer
    Deposit Withdraw

    View Slide

  30. Branch B
    Branch A
    Prepare
    Transfer Action
    Prepare
    Commit Top Level Action
    2PC: Phase 1
    V1 V1
    Account 789: $250
    Account 123 : $100
    Account 456: $50
    Account 123 : $150 Account 789: $200

    View Slide

  31. Branch B
    Branch A
    Prepare
    Success
    Transfer Action
    Prepare
    Success
    Commit Top Level Action
    2PC: Phase 1
    V1 V1
    Account 789: $250
    Account 123 : $100
    Account 456: $50
    Account 123 : $150 Account 789: $200

    View Slide

  32. Branch B
    Branch A
    Account 456: $50
    Commit
    Transfer Action
    Commit
    Account 123 : $150 Account 789: $200
    Commit Top Level Action
    2PC : Phase 2

    View Slide

  33. Branch B
    Branch A
    Account 456: $50
    Commit
    Success
    Transfer Action
    Commit
    Success
    Account 123 : $150 Account 789: $200
    Commit Top Level Action
    2PC : Complete

    View Slide

  34. Argus
    Banking
    with

    View Slide

  35. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    SubAction: Deposit (123, 100)
    Transfer Action
    SubAction: Withdraw(456, 100)
    Transfer
    Deposit Withdraw

    View Slide

  36. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    Deposit (123, 100)
    Transfer Action
    Withdraw(456, 100)

    View Slide

  37. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    Deposit Success
    Transfer Action
    Withdraw Abort
    V1 Account 123 : $250
    Transfer
    Deposit Withdraw

    View Slide

  38. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    Abort Deposit
    Transfer Action
    V1 Account 123 : $250
    Abort Top Level Action
    2PC : Abort

    View Slide

  39. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    Deposit
    Aborted
    Transfer Action
    Abort Top Level Action
    2PC : Abort

    View Slide

  40. Branch B
    Account 789: $200
    Branch A
    Account 123 : $150
    Account 456: $50
    Transfer Action

    View Slide

  41. Sub-Actions
    “Argus allows
    actions to be
    nested; thus an
    action can have one
    or more sub-actions“
    Distributed Programming in Argus
    Transfer
    Deposit Withdraw

    View Slide

  42. Sub-Actions
    Replicate
    Action
    Replica A Replica B

    View Slide

  43. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B

    View Slide

  44. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B

    View Slide

  45. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B

    View Slide

  46. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B
    Abort

    View Slide

  47. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B

    View Slide

  48. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B

    View Slide

  49. Sub-Actions
    Replicate
    Deposit
    Replica A Replica B
    Transfer
    Deposit Withdraw
    Replicate
    Withdraw
    Replica A Replica B
    2PC: Abort

    View Slide

  50. Sub-Actions
    “Argus runs every handler call as a
    sub-action…this extra action
    ensures that calls have a zero or
    one semantics.“
    Distributed Programming in Argus

    View Slide

  51. What if Sub-Actions
    try to access the
    same atomic object?

    View Slide

  52. What if Sub-Actions
    try to access the
    same atomic object?

    View Slide

  53. Read Lock: All holders of write locks on
    x must be ancestors of S
    Write Lock: All holders of write locks
    on x must be ancestors of S.
    Locking Rules for Sub-Actions
    Distributed Programming in Argus

    View Slide

  54. Commit: S’s parent acquires S’s lock on x.
    If S holds a write lock on x, then S’s version
    becomes S’s parent version
    Abort: S’s lock and version (if any) are
    discarded
    Version Management Rules
    for Sub Actions
    Distributed Programming in Argus

    View Slide

  55. Sub Action Locking
    Account Balance Object
    $200
    Value
    X
    Y
    Z
    1.5%
    Interest
    2%
    Interest
    Read
    Balance

    View Slide

  56. Account Balance Object
    $200
    V1 $203
    Value
    X
    Y
    Z
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    X: Write Lock (V1)
    Sub Action Locking

    View Slide

  57. Account Balance Object
    $200
    V1 $203
    V2 $207.06
    Value
    X
    Y
    Z
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    X: Write Lock (V1)
    Y: Write Lock (V2)
    Sub Action Locking

    View Slide

  58. Account Balance Object
    $200
    V1 $203
    V2 $207.06
    Value
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    X: Write Lock (V1)
    Y: Write Lock (V2)
    Z: Read Lock (V2)
    Sub Action Locking

    View Slide

  59. Account Balance Object
    $200
    V1 $203
    V2
    V3
    $207.06
    $208.10
    Value
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    X: Write Lock (V1)
    Y: Write Lock (V2)
    Z: Read Lock (V2)
    W: Write Lock (V3)
    Sub Action Locking

    View Slide

  60. Account Balance Object
    $200
    V1 $203
    X: Write Lock (V1)
    V2
    V3
    $207.06
    $208.10
    Value
    Y: Write Lock (V2)
    Z: Write Lock (V3)
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    Sub Action Locking

    View Slide

  61. Account Balance Object
    $200
    V1 $203
    X: Write Lock (V1)
    V2
    V3
    $207.06
    $208.10
    Value
    Y: Write Lock (V3)
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    Sub Action Locking

    View Slide

  62. Account Balance Object
    $200
    V1 $203
    X: Write Lock (V3)
    V2
    V3
    $207.06
    $208.10
    Value
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    Sub Action Locking

    View Slide

  63. Account Balance Object
    $200
    V1 $203
    X: Write Lock (V3)
    V2
    V3
    $207.06
    $208.10
    Value
    Y: Write Lock (V3)
    Z: Write Lock (V3)
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    Sub Action Locking
    Two Phase Commit

    View Slide

  64. Account Balance Object
    $208.10
    Value
    X
    Y
    Z
    W
    1.5%
    Interest
    2%
    Interest
    Read
    Balance
    .5%
    Interest
    Sub Action Locking

    View Slide

  65. Problems with
    Argus

    View Slide

  66. “The concurrency that is built in to the mail system
    can lead to a number of deadlock situations”
    Guardians and Actions: Linguistic Support for Robust, Distributed Programs
    “As implemented most of the handlers can deadlock
    with other concurrent operations”
    Distributed Programming in Argus
    Deadlocks

    View Slide

  67. Deadlocks
    “The programmer must think about
    deadlocks and starvation and
    implement the code to avoid them
    when possible"
    Distributed Programming in Argus

    View Slide

  68. Blocking Calls
    “A new process is created to perform an incoming
    handler call …[so guardians can] have the ability to
    execute many request concurrently … if the guardian
    is running on a single-processor node, then only one
    process will be running at a time”
    Guardians and Actions: Linguistic Support for Robust, Distributed Programs

    View Slide

  69. Blocking Calls
    “A new process is created to perform an incoming
    handler call …[so guardians can] have the ability to
    execute many request concurrently … if the guardian
    is running on a single-processor node, then only one
    process will be running at a time”
    Guardians and Actions: Linguistic Support for Robust, Distributed Programs
    Promises:
    linguistic support for efficient asynchronous procedure
    calls in distributed systems
    B. Liskov, L.Shrira
    1988

    View Slide

  70. So where do we go
    from here?

    View Slide

  71. “Guardians allow programs to be
    decomposed into units of tightly
    coupled data and processing”
    Distributed Programming in Argus
    Guardians

    View Slide

  72. Microservices

    View Slide

  73. “Atomic actions are an important tool
    both for understanding what a system
    should do and for implementing it
    correctly”
    Distributed Programming in Argus

    View Slide

  74. 2014

    View Slide

  75. Halo 4:
    Statistics Service

    View Slide

  76. 2015

    View Slide

  77. 2015
    “We focus our study on the
    common use of feral or a
    pplication-level, mechanisms for
    maintaining database integrity”

    View Slide

  78. 2015

    View Slide

  79. CRDT
    * Stolen from Chris Meiklejohn
    in practice

    View Slide

  80. 2012

    View Slide

  81. 2012
    “ Spanner is the first
    system to distribute
    data at global scale and
    support externally-consistent
    distributed transaction”

    View Slide

  82. 2016

    View Slide

  83. View Slide

  84. Conclusion

    View Slide

  85. Thank You!
    @caitie

    View Slide