Distributed Datastore Basics

Basics:

1. Distributed DB is divided into different nodes & Data is spread across the nodes. 
2. There is no Master/Slave config in distributed DB. 
3. Every machine is given the responsibility of saving part of the data based on some logic.
4. If some node goes down its fine since some of its data is captured into some other node. 
5. Primary responsibility of a node is to store all the data. Secondary responsibility of another node(backup) will be to store part of that data. So a primary node will store all the data and several secondary nodes will store parts of the data. In case of loss, data will be retrieved from several secondary nodes.
6. Consistent hashing concept is used to distribute the data across several nodes.
1. It will determine the hash of data and spread it across different partition keys. 
7. Primary datastore will take care of hashing the partition key and finding the respective node for storing it.
8. In No-SQL datastores like Cassandra there is a replication factor, which is usually a number. Let's say replication factor is 3 then the data will be stored onto 3 different nodes. 
1. Let's say the backup strategy is to store the data into the next available node. So in that case the data will be stored in the computed node, then next available node, then next available. 
2. So its a combination of consistent hashing and backing up the data into different nodes. 
9. To handle more load extra nodes will be added. This will automatically assign the responsibility of the distributing the data across new and existing nodes using Gossip protocol. 
1. All nodes talk to each other so they everything about each other. 
2. If a node goes down it will not hear or talk anything. When other will communicate to it there will be no response. They'll understand that the node is down so they will share the responsibility amongst themselves automatically. Another node will become primary node to hold the data of that range let's say 10-20k. 
10. Similar strategies are implemented in Redis, HDFS, Cassandra, 
1. HDFS has master node/name node and data node. Data resides in the data node. 
2. In such cases ZooKeeper can take care of assigning responsibilities to slave nodes if master goes down. 
11. Commodity computers are like normal desktop that we use at home but with extra capabilities. 
    
    
    
    Why you need to scale?
    Performance is degraded as customers are complaining that requests are taking more time.
    
    
    Vertical Scaling: 
    Upgrade the server to handle volume of requests easily. Upgrading single server's capability much more. 
    
    
    Horizontal Scaling:
    1. Add more machines to the cluster. 
    2. Cheaper than vertical scaling. 
    3. If service is not heavily used then more machines can be removed from the cluster. Service is not impacted since you are adding more machines to direct the traffic and removing the machines so requests are served by some or the other machine at any given point.
    4. Moreover, we can store the machines in different continents. 

    Conclusion:
    1. Vertical scaling is cost efficient in short term as you are buy less H/W. Horizontal scaling is cost efficient in long run. 
    2. Vertical scaling is not fault tolerant as its only one machine. 
    
    
    Advantages of distributed systems: 
    1. Fault tolerance:
    1. If server in a country goes down then requests can be directed to another server in another country.
    2. User will see more latency but the service remains available. 
    2. Low Latency:
    1. You can place the server near to where most requests are originating in case of HS but in VS there is only few servers so users will wait for their response. 
    2. Time taken to send and receive the request will go down. Only time consumed will be the time taken by the service. 

    
    

You might also like:

Distributed datastores basics

Find a string using binary search

Description: 

1. Binary search searches either the left side or right side of the array depending on the search element. 
2. The elements in the input array are always sequential. 
3. Middle element is looked up if the element to be searched ‘x’ is < then mid element then left hand side of the array is searched. 
4. If ‘x’ is > then mid element then the right hand side of the array is searched. 
5. If mid element is ‘x’ then it is outputted
6. This occurs recursively until the element is either found or array is exhausted. 

Algorithm:

Step 1: Declare and initialize a string array ‘s’ with the given sorted set of elements.
(Binary search works only on a sorted collection).

      0          1            2           3            4            5           6           7     

“at”

“”

“ball”

“”

“cat”

“”

“dog”

“”

Step 2: Declare and initialize a string variable ‘search’ with the target string value “dog” to
be searched for.

search = “dog”

Step 3: Declare and initialize ‘high’ and ‘low’ integer variables according to the length of the
given string array.

int low = 0

int high = 7

Step 4: Declare and initialize a variable ‘flag’ to find whether the target string is found or not.

Step 5: Using while loop, repeat step 6, step 7 and step 8 till the condition fails.

Step 6: Find the middle value, If it is an empty string then increment the middle value to the
next non-empty string.

Step 7: Compare the middle value with the given string using
targetString.compare(currentMiddleValue) method. This method,
1. returns 0(zero) if the target string is matched with the current middle value.
2. returns 1 if the target is greater than the current middle value
3. returns -1 if the target is less than the current middle value.

Step 8: If the compare() method’s return value is,

0 => Print “String found” and the index value. Then set the flag to 1 and break the loop.

1 => Set the low to the value next to the middle one. (Right part of the array)

-1=> Set the high to the value before to the middle one. (Left part of the array)

Step 9: Finally check whether the flag value is equal to 0, If the condition is true then print
“String not found” to the console.

Iteration 1: (step 5)

search = “dog”, low = 0, high = 7, flag = 0

0 < 7   -> Condition true

mid = (0+7)/2 (step 6)

mid = 7/2

mid = 3

    0           1           2           3           4           5           6           7

“at”

“”

“ball”

“”

“cat”

“”

“dog”

“”

(Left part)              mid               (Right part)

s[3] = “”

“”.empty() == true   -> Condition true

mid = 4 (Incremented by one)

    0           1           2           3           4           5           6           7

“at”

“”

“ball”

“”

“cat”

“”

“dog”

“”

          (Left part)               mid         (Right part)

s[4] = “cat”

i = “dog”.compare(“cat”) (step 7)

i = 1 (“dog” is greater than “cat”)

IF : 1==0   -> Condition false (step 8)

IF : 1==1   -> Condition true

Low = 5   (Right part)

IF : 1==-1   -> Condition false

Iteration 2: (step 5)

search = “dog”, low = 5, high = 7, flag = 0

5 < 7   -> Condition true

mid = (5+7)/2 (step 6)

mid = 12/2

mid = 6

    5           6           7

“”

“dog”

“”

  (Left)      mid     (Right)

s[6] = “dog”

“dog”.empty() == true   -> Condition false

i = “dog”.compare(“dog”) (step 7)

i = 0 (“dog” is equal “dog”)

IF : 0==0   -> Condition true (step 8)

Print “String found” to the console.

Print “Location: 7” to the console.

Set flag=1

Then break

Terminate the loop.

IF : flag = 1 (step 9)

1 == 0   -> Condition false.

Implementation:

//Searching the set of strings using binary search

#include <iostream>

#include <conio.h>

#include <stdio.h>

#include <string>

using namespace std;

int main()

{

string s[10];

s[0] = "at";

s[1] = "";

s[2] = "ball";

s[3] = "";

s[4] = "cat";

s[5] = "";

s[6] = "dog";

s[7] = "";

string search = "dog";

int i;

int high = 7, low = 0,mid, flag = 0;

while(low <high)

{

mid = (low + high)/2;

//If the string is empty then go to the next non-empty string

if(s[mid].empty() == true)

mid++;

//Compare. 0 for true, -1 for smaller first char, 1 for bigger first char

i = search.compare(s[mid]);

//Found the string

if(i==0)

{

cout<<"String found\n";

cout<<"Location: "<<mid+1<<endl;

flag = 1;

break;

}

if(i==1)

{

//If the target is bigger than the current then go to the right part of the array

low = mid + 1;

}

if(i==-1)

{

//If the target is smaller than the current then go to the left part of the array

high = mid -1;

}

}

if(flag == 0)

cout<<"String not found";

getch();

return 0;

}

Output:

String found

Location: 7

Algorithm Complexity:

O(log n)