Argus Papers We Love

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