DEV Community: saurabh.v

Eventual vs Strong Consistency in Distributed Databases

saurabh.v — Mon, 31 Jul 2017 16:28:02 +0000

Explanation of this topic starts with an analogy, taking an example from real life to understand the concept better.

I have the habit of writing something I call Tech Notes on my laptop daily to summarize technical concepts that I learn. It helps me to recollect them in an easier way whenever I want to.

But sometimes I used to worry about my laptop being stolen or what if it crashes. I will lose all these Tech Notes so I started backing them up on my external Hard Disk. To further reduce the possibility of losing them, I also purchased a subscription of Dropbox.

Every fortnight, I update my external Hard Disk with revised and newly written Tech Notes and Dropbox gets updated as soon as I connect my laptop to the internet.

Here, I am using Hard Disk and Dropbox as a source of reading Tech Notes while the laptop is being used for reading as well writing them. (Master-Slave Model)

Redundancy introduces Reliability.

Now let’s get to the point.

Case 1: Eventual Consistency
Whenever we use multiple replicas of a database to store data and let’s say a write request comes to one of the replicas. In such a situation, Databases had to discover a strategy to make this write request at one replica reach other replicas as well so that they all could write data of the request and become consistent.

Consistency here means that a read request for an entity made to any of the nodes of the database should return the same data.

Eventual consistency makes sure that data of each node of the database gets consistent eventually. Time taken by the nodes of the database to get consistent may or may not be defined.

Data getting consistent eventually means it will take time for updates to reach other replicas. So what?
This implies that if someone reads from a replica which is not updated yet (since replicas are updated eventually) then it may return stale data.

My Hard Disk also keeps stale data for a period of 15 days as it gets updated fortnightly. Let’s assume John, my friend comes after few days of updation and asks for my Hard Disk.

John: I want your hard disk to read your Tech Notes.

I: Sure, why not. But it has not been updated since last few days.

John: I am fine with it.

Now Hard Disk was supplied to John immediately (low latency) at the risk of having stale data in it. But I am sure about the fact that it will get updated when the next fortnight starts.

Eventual consistency offers low latency at the risk of returning stale data

While on the other hand, we have something known as Strong Consistency.

Case 2: Strong Consistency
It says data will get passed on to all the replicas as soon as a write request comes to one of the replicas of the database.
But during the time these replicas are being updated with new data, response to any subsequent read/write requests by any of the replicas will get delayed as all replicas are busy in keeping each other consistent.

As soon as they become consistent, they start to take care of the requests that have come at their door.

This time my friend Veronica comes and asks for my Tech Notes.

Veronica: I want your latest Tech Notes.

I: Sure, why not. I will share a Dropbox link with you.
   But Veronica, access it after few minutes as I have written a
   new Tech Note on the laptop which will get synced with my 
   Dropbox account.

Now Veronica was able to access up-to-date Tech Notes but after few minutes of delay.

Conclusion

Strong Consistency offers up-to-date data but at the cost of high latency.
While Eventual consistency offers low latency but may reply to read requests with stale data since all nodes of the database may not have the updated data.

If you liked the article, please share it with others.
This article was first published on Medium. You can take a look at it here.

Time of check to time of use (TOCTOU): A race condition

saurabh.v — Fri, 02 Jun 2017 16:13:13 +0000

This article was first published on Medium. You can take a look at it here.

Explanation of this topic starts with an analogy taking an example from real life to understand the concept better.

It was afternoon when John was going to the office and he told his wife Shahana that he will come by 5:00 in the evening. He told her to keep tea ready by then.

Shahana cared for her husband. So the first thing that she did was to check if all ingredients required for making tea are there. Everything was fine except sugar which was in less quantity but it was enough to make tea for her husband.

She felt satisfied and went to have sleep for few hours before her husband comes. While she was sleeping, their maid came and performed her regular household tasks.

After completing her tasks, she felt tired and so she thought to have a cup of tea. Usually, she asks Shahana before using anything from kitchen but since Shahana was sleeping she proceeded with making a cup of tea for herself.

She saw that everything required for making tea was available in the kitchen. It took few minutes for the tea to be ready. She drank and left.

Till this point, story looked bit plain but problem starts now.

Shahana woke up and since she was sure that there is enough quantity of each ingredient for making the tea, she started making it.

In between the process of making, she realised that the sugar is not there.
OH, MY GOD !!
WHAT SHALL SHE DO NOW?

This is where the concept of TOCTOU (TIME OF CHECK TO TIME OF UPDATE) kicks in.

WHAT IS TOCTOU?
Wikipedia states that

In software development, time of check to time of use (TOCTTOU or TOCTOU, pronounced “TOCK too”) is a class of software bug caused by changes in a system between the checking of a condition (such as a security credential) and the use of the results of that check. This is one example of a race condition.

TOCTOU states that race condition can occur if the state of the system changes between the moment when some condition was checked by a process and the moment when the action was taken based on that condition by the same process.

How is above-written example relevant?

If we see the above example, shahana and maid are 2 processes which are trying to access the common resource which is sugar.

Same situation can occur in concurrent programming environment when there is a single resource (object/ variable) being accessed and modified by more than one process.

Operating system can put a running process on hold and allow another process to use CPU for some time.

Now it can happen that the new process is also modifying the same resource which was being accessed by the former process and hence the chances of occurrence of race condition erupt!!

If you liked the article, please share it with others.

Functional Programming is Fun!! (PartÂ 1)

saurabh.v — Tue, 16 May 2017 17:20:30 +0000

This article was first published on Medium. You can take a look at it here.

Actually Functional programming is more than just being fun.

Functional programming concepts are important even if someone programs in imperative or object oriented languages.

It has many concepts which can be used in the program irrespective of the language a person programs in.
Let’s take it one by one.

When are functions called pure?

A function is called pure if it always returns the same result for same argument values.
Let’s understand it through an example

x = 5    # global variable

sum_impure(y){
    y = x+ y    # adds the value of global variable
    return y
}

Code Block 2

sum_pure(a, b){
    return a + b
}

Above written 2 functions may look similar but they are not.
Following example explains the difference:

x = 5 
sum_impure(3)    # returns 8

x = 6            # changed value of global variable to 6
sum_impure(3)    # returns 9

sum_impure is an impure function because giving same input 3 as argument to it, it gives different output in each call.

But this is not the case with sum_pure function.

sum_pure(4, 9): 13
sum_pure(4, 9): 13

Given 4, 9 as arguments to the sum_pure, it will always return 13 no matter when and where it is being called in the program.

Do you get the difference between sum_impure and sum_pure function?

sum_impure function uses the value of global variable to calculate output but if some part of the program changes the value of global variable, the output of the sum_impure function also changes for same input.

sum_pure’s output does not depend on the state of the program. It just acts on the input without requiring any information other than arguments to it from the program in which it is being called.

But why shall I make my functions pure?

Easier Testing

It is not easy to test sum_impure function because sum_impure function has to know the value of global variable x to execute. This is also known as state or context associated with a function.

Secondly, you can’t compare sum_impure’s result with some fixed value because it’s return value will change depending on the value of global variable x.

Now are you getting why we mock databases?

If a database read/write is there in a function definition, we can’t test that function without mocking the database.
Databases are like state and the result of the function doing database read/write depends on what is there in the database during execution.

Impure functions need state to run and test.

Predictability

We can reason about what a pure function is doing because its results are predictable. Given same input, it always give same output.

Result of a pure function does not depend on the state of the program.

Result of sum_impure(3) is unpredictable. So if sum_impure is being called at 2 places in the program with same arguments, it may happen that it gives different results at these 2 places.

x = 4
sum_impure(3)    # returns 7

x = 7
sum_impure(3)    # returns 10

There are many more advantages like parallelization, memoization associated with pure functions which we will learn in next article of this series.

If you liked the article, please share it with others.

Shared Mutability: Handle with care!!

saurabh.v — Fri, 31 Mar 2017 15:28:46 +0000

This article was first published on Medium. You can take a look at it here.

Let's bifurcate these 2 words and understand them one by one.
Shared and Mutability

Sharing
Sharing in computer science means sharing of resource like I/O, data etc between multiple processes. In case of data as a resource, sharing may mean permission to read and/or update it by multiple processes.

Shared Reading
Multiple processes are allowed to read a common resource but only one process can modify it at a time.
Shared Modification
Multiple processes can read as well as modify a particular resource at a time.

Mutability
Mutability means ability to change. In computer science terms, it may mean any of the following:

Changing value of some variable

a = 5
a = 10        # changing the value of variable

Modifying a data structure
In the example below, some nodes of binary tree are removed.
Modifying data kept in a data structure
In the example below, value of fourth node of linked list is changed from 100 to 50.

Mutability is fine as long as single process is allowed to modify the data at a time. Sharing is fine as long as multiple processes do shared reading but not shared modification.

Problems come when the above mentioned 2 keywords Sharing and Mutability come together.
In other words, problems arise when multiple processes are allowed to read as well as modify a common piece of data.

How ????
Let's understand it with the help of an example:
There is a grocery store

groceries = [apple, banana, orange, strawberries, cherries]

and as in every grocery store, there is a basket

basket = []

and a function to get groceries from grocery store

def get_groceries():
    for item in groceries:
        if item not in basket:
            basket.append(item)
        print basket

Looks like a fine piece of code !!
Tom comes | picks up the basket | starts picking groceries from groceries array | puts it in basket.

Life of tom is full of happiness !!

While he was purchasing groceries, Jerry came and met tom. Tom asked Jerry to help him to get groceries. Jerry also started using the get_groceries function to put groceries in Tom's basket.

By analysing the above example, we can see that since both Tom and Jerry were using the same basket they both saw that banana is not in the basket and hence both of them put banana in it.
Now we have 2 bananas in the basket.

Basket acts as a shared resource which is being accessed by multiple processes like Tom and Jerry.

If Jerry would have taken the responsibility of only picking the basket and not putting anything in it then Tom would be only one adding groceries in it.In such a case, above mentioned problem wouldn't have occurred. [analogous to Shared Reading]

Mutability by single process at a time

Not only both processes were sharing the basket (common resource) but also mutating it (adding groceries in the basket) at the same time. [analogous to Shared Modification]

Hence the term Shared Mutability !!