System Design Interview — Popular Techniques/Algorithms every developer should know

If interviewer wanted to deep dive in System Design Interview, here are few top techniques/algorithms every developer should know for cracking system design interview.

Consistence Hashing

Patterns of Data Partitioning(Fixed Partitions, Key-Range Partitions)

Patterns of Cluster Management

Bloom Filters

Two-Phase Commit

Skip Lists

B-Tree

Write-Ahead Log

Segmented Log

Replicated Log

LRU and MFU

Reverse Index

Trie Algorithms

Rsync Algorithm

Leaky bucket / Token bucket

Leader Election (Leader and Followers)

Leader election is a distributed computing concept where a group of nodes in a network dynamically selects a leader among them. The leader is responsible for coordinating and making decisions on behalf of the group. Leader election is crucial for achieving coordination and maintaining consistency in distributed systems.

Node A  <---- Leader
   /  |  \
B    C    D

Leader Election Techniques and Algorithms:

Bully Algorithm:

• Idea: Nodes with higher priorities challenge lower-priority nodes to become the leader.
• Real-world Implementation: Used in various network protocols.

Ring Algorithm:

• Idea: Nodes are organized in a logical ring, and the one with the highest priority becomes the leader.
• Real-world Implementation: Chord distributed hash table (DHT) uses a ring-based structure.

Zookeeper Leader Election:

• Idea: Uses a variant of the Paxos algorithm to elect a leader in a Zookeeper ensemble.
• Real-world Implementation: Apache ZooKeeper.

HeartBeat

Mutual Exclusion

Clock Synchronisation

Replica Management

Consensus Algorithms(Paxos and Raft)

Consensus is a more general concept that involves a group of nodes reaching an agreement on a single value or decision. This agreement is crucial for maintaining consistency across distributed systems, even in the presence of failures or communication delays.

Node A  <---- Consensus
   /  |  \
B    C    D

Consensus Techniques and Algorithms:

Paxos Algorithm:

• Idea: Nodes propose values, and a majority must agree for consensus. It handles faults and ensures safety.
• Real-world Implementation: Google’s Chubby, Apache ZooKeeper.

Raft Algorithm:

• Idea: Simplifies Paxos and is easier to understand. It elects leaders and ensures consensus.
• Real-world Implementation: etcd, Consul.

Practical Byzantine Fault Tolerance (PBFT):

• Idea: Designed to handle Byzantine faults, where nodes may act maliciously. It ensures consensus in the presence of faulty nodes.
• Real-world Implementation: Hyperledger Fabric (blockchain platform).