Image for post
Image for post
Courtesy: linuxscriptshub.com

Note: On October 04, 2017, I published a small article on redis hash table internals. But I think, there are lot more details to cover on redis dictionary topic. Hence as an extension to the previous one, I decided to write this new article which is more comprehensive.

Redis is a very well known in-memory ( persistence can also be enabled for fault tolerance ) data structure store which serves usual key value pairs, List, Set, Sorted Set, HyperLogLog, Geo Spatial structures etc. Redis trades off memory to achieve speed, it performs all client operations in a single thread & usually operations are very fast. …


Image for post
Image for post
Courtesy: Unsplash

We discussed Raft replication in details in part 2 of this series. That becomes prerequisite for this article. Please head over to part 2 if you haven’t already.

We’ll simulate some scenarios in this article & see how Raft behaves in such cases. It’ll build a better understanding of the algorithms in your mind.

Case 1: Replicate a client command successfully with majority

Let’s see the happiest case first. It will help you to get a fair understanding of the life cycle of data replication process in Raft.

The leader node S2 gets a command from the client. It adds the entry to its own log at index 1( The logs in the following diagrams are 1-based ). The dotted line around the rectangle at position 1 in S2 bucket represents that the entry is uncommitted. The orange colour arrows indicate that the leader is sending AppendEntries RPC to the rest of the nodes with the intention to store the data in the majority of the nodes. …


Image for post
Image for post
Courtesy: Unsplash

In the part 1 of this series, we got the basics of Raft. Please go through that part first if you have not already.

In this part, we’ll concentrate on detailed Raft replication technique. The concepts explained here are very important & core to Raft.

Raft Replication

The core idea behind any consensus algorithm is that for a given data ( key ), at any point in time, either all or majority of the cluster members should return the same value. Raft uses replication technique to achieve it. Replication has been used to build fault tolerance & redundancy in distributed systems since ages. …


Image for post
Image for post
Courtesy: Unsplash

Goal of The Series

There are many articles on Raft however most of them are short, theoretical & not detailed. Consensus algorithms is an area where shortcut analysis does not work as the topic is pretty hard to understand. While reading the raft paper & many articles, I found out that no code & not playing with a Raft simulator makes it even harder to understand.

So this series of articles intends to be more natural & lucid from engineering perspective — it thoroughly explains concepts, core algorithms with code and simulates some important use cases. …


Image for post
Image for post
Courtesy: shutterstock.com

Introduction

We use real time location search services all the time in our real life — whether it’s a food ordering app or on-demand cab booking service, it’s everywhere nowadays. The intention of this article is to look into how to design the back end infrastructure for a Geo-spatial index in real life.

We will explore how several companies in relevant space have solved the problem, what are the pros & cons of different approaches & how you can approach the problem. Also we will see how to approach the problem in a System & Architecture Design Technical Interview perspective.

Some Real Life Use Cases

  1. Real time cab booking service like Uber, Lyft, Bolt. …


Consider the following scenario.

You have to design a generic vending machine which can provide you different variants of Coffee, Hot Water, Hot Milk, Coke, Lemonade & what not. How will you design that vending machine software?

This post is not about designing the complete vending machine, rather it discusses only one portion of the machine — how to support different variants of beverages, customers will browse all product & choose any one as per their choice. Remember, going forward you may be asked to add support for say fruit juice, tea or some variety of milk shake, chocolate shake etc. …


Image for post
Image for post

In the first part of this series, we have seen networking & TCP basics which are necessary to understand the advanced stuffs discussed in this article. We saw what a TCP segment is, how it gets transferred through different network layers & how devices communicate with each other to transfer network data. We will now discuss what happens on the way when a segment is getting transferred, what kind of challenges are there, what kind of optimizations TCP apply for fast transmission & error control, what kind of optimization we developers can apply while developing applications.

Data Transmission Challenge: Network Congestion

Not all nodes connected to the internet have same link bandwidth. Hence the rate at which server sends data through the network may quickly overflow the buffer of intermediate nodes causing delay in round trip time of a segment & segment drop / unreliability in the network. Hosts may send the same packet several times to the receiver eventually some copy of each packets arrives at the destination. This is called Congestion collapse. …


Image for post
Image for post

When we hear of networking & related topics like connection, protocols, data transfer, the dreaded university lectures & boring slides come to our mind (probably to most of us). As software engineers, we can’t be fearful of technical details of networking, all of us may not be network engineers, still we need to know enough details so that we can make proper decision with minimum & appropriate trade-offs while designing a system architecture.

Most of the networking books or slides are fat, very serious, covers many topics in minute details. This post is designed exactly opposite to that, it explains few networking concepts & TCP in a top-down fashion from a software engineer’s perspective in simple English accompanied by enough technical details so that once you go through it, you get a clear picture of how, what & why of different aspects of TCP. …


Image for post
Image for post

In 2010, Jeff Dean from Google gave a wonderful talk in Standford & he discussed few numbers of computing systems, he got really famous for that. Peter Norvig published those numbers for the first time in the internet. Time passes away, so the numbers also change. I found a very good interactive web UI of those numbers which roughly tell how much those numbers have changed over the years as a function of time.

This article is a compilation of not only Jeff Dean’s estimated data, rather of all such numbers from different sources which may help you as a system designer & architect. …


Image for post
Image for post

There are lot of articles online describing database scalability patterns, but they are mostly scattered articles —just techniques are defined haphazardly without much context, they are not defined in a step by step manner i.e; when to choose which scaling option, which scaling options are feasible in practise & why. Moreover I am planing to discuss some of the techniques in details in future articles, so I feel it’s better if I discuss step by step techniques with some context in my own way. This article is high level article — I will not discuss scaling techniques in details here.

Assume you have built a startup which offers ride sharing at cheap cost. Initially when you start, you target a city & hardly you have tens of customers after initial advertisement. You save all customer, trip, locations, bookings data, customer trip history in the same database or most likely in a single physical machine, there is no fancy caching or big data pipeline to solve problems since your app is very new. …

About

Kousik Nath

Deep discussions on problem solving, distributed systems, computing concepts, real life systems designing. Developer @PayPal. https://in.linkedin.com/in/kousikn

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store