Art of Disorderly programming - Avoiding cost of correctness.

50 %
50 %
Information about Art of Disorderly programming - Avoiding cost of correctness.

Published on March 2, 2016

Author: ShripadAgashe


1. Art of disorderly programming Shripad Agashe Twitter: @shripadagashe Blog: ThoughtWorks

2. Order • The arrangement or disposition of people or things in relation to each other according to a particular sequence, pattern, or method. • The sequence used is often time

3. Disorder source:

4. Life with ambiguous order int i = 5; i = ( ++ i + ++ i) assert ( i ==13 ) Absence of sequencing leads to undefined behavior even in a single process

5. Role of Time • Time is a free monotonic function on every computer • Programmers can easily relate with time instead of a random monotonic function • But Time is not that useful for time alone • Causal ordering of event • Failure detector i.e. knowing when upper bound on message deliver is breached • Consistent snapshot

6. But there is no “Now” • The time elapsed between when I said that sentence and when you hear it will be at least a couple of micro seconds. • Typical x86 clocks vary their speeds depending on all kinds of unpredictable environmental factors, such as load, heat, and power. Even the difference between the top and bottom of the same rack can lead to a variance in skew. • If the best that can be done in a wildly expensive environment like Google's is to live with an uncertainty of several milliseconds, most of us should assume that our own clocks are off by much more than that. Source:

7. Models of enforcing order • Program order • Total order Possible end state = {3} Possible end states = {5,3,7} or {3,5,7} or {7,5,3}…..

8. Sometimes deterministic outcome is required

9. Downside of locking Amdahl’s law takes over σ P

10. More on Amdahl’s law

11. JVM with Lock Method Time (ms) Single thread 300 Single thread with lock 10,000 Two threads with lock 224,000 Single thread with CAS 5,700 Two threads with CAS 30,000 Single thread with volatile write 4,700 Source:

12. So we need to relax consistency

13. Shades of consistency Eventual Consistency Consistent Prefix Monotonic Reads Bounded Staleness Read My Writes Strong Consistency Source:

14. But consistency guarantees are difficult

15. The logical answer • The hidden cost of forfeiting consistency, which is the need to know the system’s invariants. • The subtle beauty of a consistent system is that the invariants tend to hold even when the designer does not know what they are. • In EC solutions, one must be explicit about all the invariants, which is both challenging and prone to error.

16. Is eventual consistency even applicable • Without formal techniques it is very difficult to reason about constraints in presence of temporal non determinism • Often EC will require business process change making it even more challenging • The questions one need to answer is • Will it ever be consistent • Will it ever break business constraints • What is the cost of breaking business constraints if any

17. CALM • CALM stands for consistency as logical monotonicity. • Operations which can be modeled as sets and expressed as selection, projection and join can be implemented as eventually consistent. • Operations such as aggregation or anti-join can only be implemented via blocking operation.

18. Lets understand monotonic logic • Monotonic logic is ever increasing set of facts • Emergence of new fact will not invalidate earlier inferences • As more facts emerge it tends to converge with consistent state

19. Non monotonic logic • Anti Join i.e. Negation Logic • Evidence of absence is not absence of Evidence • Aggregation • The entire input set has to be known to arrive at consistent and accurate answer.

21. In conclusion • Even a smallest of serial path can limit scalability • Polling rather than blocking at client side works better • Monotonic set based operations open up possibility of giving variety of answer. We can choose the level of correctness in the system.

Add a comment

Related pages

Disorderly!programming!! for!adistributed!world!

Disorderly!Programming! 2. ... The!state!of!the!art ... • Model^theoreFc!Correctness!Criteriafor!Distributed!Systems! ...
Read more

Bloom: Disorderly Programming for a Distributed World ...

Bloom: Disorderly Programming for a ... to reduce the download time or cost, ... analysis framework for analyzing the correctness and consistency of ...
Read more

const (computer programming) - Wikipedia, the free ...

... and others avoiding it. ... An enhancement request ticket for implementing const correctness exists ... "Const and Invariant" from D programming ...
Read more

Architectural Programming | Whole Building Design Guide

Architectural programming ... Efficiencies gained by avoiding redesign and more redesign as requirements emerge during architectural design. The most cost ...
Read more

Knuth: Computer Programming as an Art - Paul Graham

... we know that we could in principle construct formal proofs of their correctness if ... real costs of computing are ... computer programming is an art ...
Read more

Computer programming - Wikipedia, the free encyclopedia

Computer programming ... Due to the high labor cost of programmers in these countries, ... System programming; The Art of Computer Programming;
Read more

Political Correctness Gone Rampant: Use These 3 ...

Political Correctness Gone Rampant: Use These 3 Communications Tips To Survive ... there is no avoiding the fact that in public communications, ...
Read more

Introduction to Software Engineering/Project Management ...

Introduction to Software Engineering/Project Management. ... avoiding the risk, reducing the ... which includes a cost-benefit analysis as well as a list ...
Read more

Developing Parallel Programs

This allows avoiding contention when all ... Correctness of parallel programs can be established via ... Portable Parallel Programming with the ...
Read more