Saturday, 22 August 2026

Redis cluster - Horizontal scaling + High Availability

 ### Redis Cluster


Main purpose:


> **Horizontal scaling + High Availability**


Data is distributed across multiple masters using hash slots.


```text

             Redis Cluster


       ┌─────────┐

       │ Master 1│

       └─────────┘

        slots 0-5000


       ┌─────────┐

       │ Master 2│

       └─────────┘

       slots 5001-10000


       ┌─────────┐

       │ Master 3│

       └─────────┘

       slots ...

```


Each master can have replicas.


### Remember:


```text

Sentinel → HA / automatic failover


Cluster → Sharding + HA

```


---


# 8. Sentinel does NOT store your Redis data


Very important.


```text

Redis Master

    ↓

Actual data

```


Sentinel:


```text

Sentinel

    ↓

Monitoring + coordination + failover

```


Sentinel doesn't act like another Redis database.


---


# 9. Why 3 Sentinels?


Suppose you have only:


```text

Sentinel 1

```


It says:


> Master is down.


But maybe Sentinel itself has a network problem.


With three:


```text

Sentinel 1 → Down

Sentinel 2 → Down

Sentinel 3 → Down

```


Now you have stronger agreement.


A common production setup is **3 or 5 Sentinels**, depending on availability requirements.


### Why odd numbers?


For quorum/majority decisions:


```text

3 → majority = 2

5 → majority = 3

```


This avoids ties more easily.


---


# 10. Java/Spring Boot Architecture


Your typical architecture could be:


```text

                 Spring Boot

                     |

              Lettuce/Jedis

                     |

              Redis Sentinel

              /      |      \

             /       |       \

            ↓        ↓        ↓

       Sentinel1 Sentinel2 Sentinel3

                     |

              Redis deployment

                 /        \

                ↓          ↓

             Master      Replica

```


Application doesn't need to know permanently:


```text

"Redis-B is master"

```


Sentinel handles master discovery.


---


# 11. Failure scenario — Interview Favorite ⭐


Interviewer:


> "Redis master suddenly goes down. What happens?"


Answer step-by-step:


```text

1. Sentinel monitors Redis nodes

              ↓

2. Sentinel detects master failure

              ↓

3. S_DOWN

              ↓

4. Other Sentinels confirm

              ↓

5. O_DOWN

              ↓

6. Sentinels elect a leader

              ↓

7. Leader selects suitable replica

              ↓

8. Replica is promoted

              ↓

9. New master announced

              ↓

10. Redis clients discover new master

```


That's the complete flow.


---


# 🔥 Sentinel vs Cluster — Memorize This


| Feature                 | Sentinel            | Redis Cluster |

| ----------------------- | ------------------- | ------------- |

| Monitoring              | ✅                   | ✅             |

| Automatic failover      | ✅                   | ✅             |

| Replication             | Uses Redis replicas | Uses replicas |

| Sharding                | ❌                   | ✅             |

| Horizontal data scaling | ❌                   | ✅             |

| Multiple masters        | ❌                   | ✅             |

| Main purpose            | HA                  | Scaling + HA  |


---


# 🧠 Ramesh Memory Trick


Think of a company:


```text

Redis Master = CEO

Redis Replica = Deputy CEO

Sentinels = Board members

```


CEO dies:


```text

CEO ❌

   ↓

Board detects

   ↓

Board agrees

   ↓

Deputy promoted

   ↓

New CEO

```


That's **Redis Sentinel**.


### One-line interview answer:


> **"Redis Sentinel is a distributed monitoring and failover mechanism for Redis. It monitors master and replicas, detects failures, reaches quorum, elects a Sentinel leader, promotes an appropriate replica to master, and allows clients to discover the new master."**


For your **Spring Boot + Redis + Kubernetes architecture**, one additional point is important: **Sentinel and Kubernetes solve different layers of the problem**. Kubernetes can restart/reschedule Redis containers, while Sentinel provides Redis-aware master election and failover.


Uploading: 113904 of 113904 bytes uploaded.


-------

Redis - distributed system


APS - SV,OX,TP

    - REDIS SV, REDIS OX, RESIS TP
Distributed charactistic - 

Persistence ( RDB Snapshot, AOF commands)
-----------------------------------------------

Replication - Master - Slave Toplogy  - redis sentinel

3 servers, 1 - master, 2 - replicas

-----------------------------------------------

Partition -


SV - 1Master, 2 Replicas - every 128 gb

TP - 1Master, 2 Replicas - every 128 gb

OX-  1Master, 2 Replicas - every 128 gb

Data coming 500 GB, without partition all the data will distribute either sv,tp,ox, then it will not handle all load


After introduce partion - Keys of A-F  SV, G-M TP, N-Z OX, after partition my cluster will handle more load.

-----
Redis sentinel
----
Redis Cluster






-----------------------------------------------

Topology:


SV - APS noconnection CDF 

OX - APS -> CDF  

TP - APS -> CDF 

CDF AutoFailover - BG thREAD 1 SECS - APS to cdf connectin, eisconnectionmap.xml aps -> cdf ox
  


Redis Sentinel - Monitoring identify master

 

🔥 Redis Sentinel — Ramesh Style

Think of Redis Sentinel as a security guard/manager for Redis.

Its main job is:

"If my Redis master dies, detect it, choose a replica, promote it to master, and tell clients where the new master is."


1. Problem without Sentinel

Suppose your architecture is:

Java Application
       |
       ↓
   Redis Master
       |
       ↓
   Redis Replica

Master crashes:

Java Application
       |
       ↓
   ❌ Redis Master
       
Redis Replica
       ↑
     Still alive

But who tells the application:

"Master is dead. Use the replica now."

That's where Sentinel comes in.


2. Architecture

Typically:

                    Java Applications
                           |
                           ↓
                    Redis Sentinel
                 /        |        \
                /         |         \
               ↓          ↓          ↓
         Sentinel 1  Sentinel 2  Sentinel 3
                \         |         /
                 \        |        /
                  ↓       ↓       ↓
                 Redis Cluster/Group
                     |
              ┌──────┴──────┐
              ↓             ↓
           Master        Replica
          Redis-A        Redis-B

Actually, Sentinel is a separate monitoring/control layer, not a proxy sitting in the request path.

That's important.


3. What does Sentinel do?

Remember these 4 responsibilities:

M → Monitor
E → Election
F → Failover
N → Notify

① Monitor 👀

Sentinel continuously checks Redis nodes.

Sentinel
   |
   ├── Ping Master
   ├── Ping Replica
   └── Ping other Sentinels

Suppose:

Master → ❌

Sentinel detects the failure.


4. Subjective vs Objective Down

This is a very important interview topic.

SDown — Subjectively Down

One Sentinel thinks:

"Master is not responding."

That's Subjective Down.

Sentinel 1
    ↓
Master not responding
    ↓
S_DOWN

But we don't immediately fail over.

Why?

Because maybe Sentinel 1 itself has a network problem.


ODown — Objectively Down

Multiple Sentinels agree:

Sentinel 1 → Master down
Sentinel 2 → Master down
Sentinel 3 → Master down

Now:

S_DOWN
   +
Quorum agreement
   ↓
O_DOWN

Then failover can begin.

Easy memory:

S = Somebody thinks it's down
O = Others agree it's down


5. What happens during Failover?

Suppose:

             Master
            Redis-A
               |
               ↓
            Replica
            Redis-B

Redis-A crashes:

Redis-A ❌

Redis-B ✅

Sentinels detect it.

Then Sentinel starts a leader election among Sentinels.

One Sentinel becomes the coordinator for the failover.

Conceptually:

Sentinel 1
Sentinel 2  → Election → Sentinel 2 becomes leader
Sentinel 3

The elected Sentinel chooses a suitable replica.

Old Master
    ❌

Replica
    ↓
PROMOTE
    ↓
New Master

So:

Before:

Master
  ↓
Replica


After:

Old Master ❌

Replica
   ↓
New Master

6. What happens to the Java application?

This is where Sentinel becomes useful for your Spring Boot/Java architecture.

Your application should not hardcode:

redis-master.company.com

as the only source of truth.

Instead, the Redis client can use Sentinel configuration.

Conceptually:

Java Application
       |
       | "Who is current master?"
       ↓
   Sentinel
       |
       ↓
 Redis Master

If failover happens:

Java
 |
 | ask Sentinel
 ↓
Sentinel
 |
 ↓
New Master

The Redis client updates its connection information.

Modern Redis Java clients such as Lettuce support Sentinel-based master discovery/failover.


7. Sentinel is NOT Redis Cluster

This is a very common interview question.

Sentinel

Main purpose:

High Availability

Master
   ↓
Replica

Master dies
   ↓
Replica becomes Master

Redis Cluster

Main purpose:

Horizontal scaling + High Availability

Data is distributed across multiple masters using hash slots.

             Redis Cluster

       ┌─────────┐
       │ Master 1│
       └─────────┘
        slots 0-5000

       ┌─────────┐
       │ Master 2│
       └─────────┘
       slots 5001-10000

       ┌─────────┐
       │ Master 3│
       └─────────┘
       slots ...

Each master can have replicas.

Remember:

Sentinel → HA / automatic failover

Cluster → Sharding + HA

8. Sentinel does NOT store your Redis data

Very important.

Redis Master
    ↓
Actual data

Sentinel:

Sentinel
    ↓
Monitoring + coordination + failover

Sentinel doesn't act like another Redis database.


9. Why 3 Sentinels?

Suppose you have only:

Sentinel 1

It says:

Master is down.

But maybe Sentinel itself has a network problem.

With three:

Sentinel 1 → Down
Sentinel 2 → Down
Sentinel 3 → Down

Now you have stronger agreement.

A common production setup is 3 or 5 Sentinels, depending on availability requirements.

Why odd numbers?

For quorum/majority decisions:

3 → majority = 2
5 → majority = 3

This avoids ties more easily.


10. Java/Spring Boot Architecture

Your typical architecture could be:

                 Spring Boot
                     |
              Lettuce/Jedis
                     |
              Redis Sentinel
              /      |      \
             /       |       \
            ↓        ↓        ↓
       Sentinel1 Sentinel2 Sentinel3
                     |
              Redis deployment
                 /        \
                ↓          ↓
             Master      Replica

Application doesn't need to know permanently:

"Redis-B is master"

Sentinel handles master discovery.


11. Failure scenario — Interview Favorite ⭐

Interviewer:

"Redis master suddenly goes down. What happens?"

Answer step-by-step:

1. Sentinel monitors Redis nodes
              ↓
2. Sentinel detects master failure
              ↓
3. S_DOWN
              ↓
4. Other Sentinels confirm
              ↓
5. O_DOWN
              ↓
6. Sentinels elect a leader
              ↓
7. Leader selects suitable replica
              ↓
8. Replica is promoted
              ↓
9. New master announced
              ↓
10. Redis clients discover new master

That's the complete flow.


🔥 Sentinel vs Cluster — Memorize This

FeatureSentinelRedis Cluster
Monitoring
Automatic failover
ReplicationUses Redis replicasUses replicas
Sharding
Horizontal data scaling
Multiple masters
Main purposeHAScaling + HA

🧠 Ramesh Memory Trick

Think of a company:

Redis Master = CEO
Redis Replica = Deputy CEO
Sentinels = Board members

CEO dies:

CEO ❌
   ↓
Board detects
   ↓
Board agrees
   ↓
Deputy promoted
   ↓
New CEO

That's Redis Sentinel.

One-line interview answer:

"Redis Sentinel is a distributed monitoring and failover mechanism for Redis. It monitors master and replicas, detects failures, reaches quorum, elects a Sentinel leader, promotes an appropriate replica to master, and allows clients to discover the new master."

For your Spring Boot + Redis + Kubernetes architecture, one additional point is important: Sentinel and Kubernetes solve different layers of the problem. Kubernetes can restart/reschedule Redis containers, while Sentinel provides Redis-aware master election and failover.




Tuesday, 18 August 2026

Java Streams - Quick Reference for Interviews


🚀 Java Streams & Functional Programming — Interview Prep

1. Lambda Expression — Foundation

Traditional:

List<String> names = Arrays.asList("Ramesh", "John", "David");

for (String name : names) {
    System.out.println(name);
}

Functional:

names.forEach(name -> System.out.println(name));

Even simpler:

names.forEach(System.out::println);

Interview question

What is a lambda?

A lambda is an anonymous function that allows us to pass behavior as a value.

(a, b) -> a + b

2. Functional Interface

A functional interface contains exactly one abstract method.

@FunctionalInterface
interface Calculator {
    int calculate(int a, int b);
}

Usage:

Calculator addition = (a, b) -> a + b;

System.out.println(addition.calculate(10, 20));

Output:

30

Important built-in functional interfaces:

InterfaceMethodExample
Predicate<T>test()filtering
Function<T,R>apply()transformation
Consumer<T>accept()processing
Supplier<T>get()supplying
UnaryOperator<T>apply()T → T
BinaryOperator<T>apply()T,T → T

3. Predicate — Filtering

Predicate<Integer> isEven = n -> n % 2 == 0;

System.out.println(isEven.test(10));

Output:

true

Stream example:

List<Integer> numbers = List.of(10, 15, 20, 25, 30);

List<Integer> result = numbers.stream()
        .filter(n -> n % 2 == 0)
        .toList();

System.out.println(result);

Output:

[10, 20, 30]

Interview phrase

filter() uses a Predicate because it evaluates a condition and returns true or false.


4. map() — Most Important

Suppose:

List<String> names =
        List.of("ramesh", "john", "david");

Convert to uppercase:

List<String> result = names.stream()
        .map(String::toUpperCase)
        .toList();

Result:

[RAMESH, JOHN, DAVID]

Think:

Input
  ↓
map()
  ↓
Transformation
  ↓
Output

Another example

List<Integer> numbers = List.of(1, 2, 3, 4);

List<Integer> squares = numbers.stream()
        .map(n -> n * n)
        .toList();

Result:

[1, 4, 9, 16]

5. filter() + map()

Very common interview question.

Find squares of even numbers.

List<Integer> result = List.of(1, 2, 3, 4, 5, 6)
        .stream()
        .filter(n -> n % 2 == 0)
        .map(n -> n * n)
        .toList();

Result:

[4, 16, 36]

Pipeline:

1 2 3 4 5 6
      ↓
    filter
      ↓
   2 4 6
      ↓
     map
      ↓
   4 16 36

6. reduce() — Very Important

Find sum:

int sum = List.of(10, 20, 30, 40)
        .stream()
        .reduce(0, Integer::sum);

Result:

100

Conceptually:

0 + 10 + 20 + 30 + 40

Another example:

int max = List.of(10, 50, 20, 80, 30)
        .stream()
        .reduce(Integer.MIN_VALUE, Integer::max);

Result:

80

Interview question

Difference between map() and reduce()?

map() transforms each element.

reduce() combines multiple elements into a single result.


7. sorted()

List<Integer> result = List.of(50, 10, 30, 20)
        .stream()
        .sorted()
        .toList();

Output:

[10, 20, 30, 50]

Descending:

List<Integer> result = numbers.stream()
        .sorted(Comparator.reverseOrder())
        .toList();

8. distinct()

List<Integer> numbers =
        List.of(10, 20, 10, 30, 20, 40);

List<Integer> result = numbers.stream()
        .distinct()
        .toList();

Output:

[10, 20, 30, 40]

9. limit() and skip()

List<Integer> result = numbers.stream()
        .skip(2)
        .limit(3)
        .toList();

Very useful for pagination-like processing, although for database-backed pagination you should generally paginate at the database/query level rather than loading everything into memory first.


10. anyMatch / allMatch / noneMatch

boolean result = numbers.stream()
        .anyMatch(n -> n > 100);

Other examples:

numbers.stream()
       .allMatch(n -> n > 0);
numbers.stream()
       .noneMatch(n -> n < 0);

Interview tip

These are short-circuiting terminal operations.

The stream may stop processing as soon as the answer is known.


11. findFirst() / findAny()

Optional<Integer> result = numbers.stream()
        .filter(n -> n > 50)
        .findFirst();

Always remember:

Optional<T>

rather than assuming a value exists.


12. flatMap() ⭐⭐⭐

This is a very common senior-level interview question.

Suppose:

List<List<Integer>> numbers = List.of(
        List.of(1, 2, 3),
        List.of(4, 5),
        List.of(6, 7)
);

We want:

1 2 3 4 5 6 7

Use:

List<Integer> result = numbers.stream()
        .flatMap(List::stream)
        .toList();

map() vs flatMap()

map():

List<List<Integer>>
        ↓
List<Stream<Integer>>

flatMap():

List<List<Integer>>
        ↓
List<Integer>

Real-world example

List<Employee> employees;

Each employee has:

List<String> skills;

Get all unique skills:

List<String> skills = employees.stream()
        .flatMap(e -> e.getSkills().stream())
        .distinct()
        .sorted()
        .toList();

This is a great interview example.


13. Collectors.groupingBy() ⭐⭐⭐

Suppose:

class Employee {
    String name;
    String department;
    double salary;
}

Group employees by department:

Map<String, List<Employee>> employeesByDept =
        employees.stream()
                .collect(Collectors.groupingBy(
                        Employee::getDepartment
                ));

Result conceptually:

IT       → [Ramesh, John]
Finance  → [David, Peter]
HR       → [Sita]

Count employees by department

Map<String, Long> countByDept =
        employees.stream()
                .collect(Collectors.groupingBy(
                        Employee::getDepartment,
                        Collectors.counting()
                ));

14. Grouping + Summing

Total salary by department:

Map<String, Double> salaryByDept =
        employees.stream()
                .collect(Collectors.groupingBy(
                        Employee::getDepartment,
                        Collectors.summingDouble(
                                Employee::getSalary
                        )
                ));

This is a very good Java 8 interview problem.


15. PartitioningBy()

Unlike grouping, partitioning creates two groups based on true/false.

Example:

Map<Boolean, List<Integer>> result =
        numbers.stream()
                .collect(Collectors.partitioningBy(
                        n -> n % 2 == 0
                ));

Conceptually:

true  → even numbers
false → odd numbers

16. Find Highest Salary

Optional<Employee> employee =
        employees.stream()
                .max(Comparator.comparing(
                        Employee::getSalary
                ));

Safely:

employee.ifPresent(e ->
        System.out.println(e.getName()));

17. Second Highest Salary ⭐⭐⭐

Classic interview question.

Optional<Double> secondHighest =
        employees.stream()
                .map(Employee::getSalary)
                .distinct()
                .sorted(Comparator.reverseOrder())
                .skip(1)
                .findFirst();

Pipeline:

Employees
   ↓
Salary
   ↓
Distinct
   ↓
Descending sort
   ↓
Skip highest
   ↓
Second highest

18. Convert List → Map

Map<Long, Employee> employeeMap =
        employees.stream()
                .collect(Collectors.toMap(
                        Employee::getId,
                        Function.identity()
                ));

Duplicate keys

Important interview trap.

This can fail:

Collectors.toMap(
    Employee::getDepartment,
    Function.identity()
)

if multiple employees have the same department.

Handle it:

Collectors.toMap(
    Employee::getDepartment,
    Function.identity(),
    (e1, e2) -> e1
)

19. String Frequency — Classic Coding Question

String input = "banana";

Map<Character, Long> frequency =
        input.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(
                        Function.identity(),
                        Collectors.counting()
                ));

Result:

b → 1
a → 3
n → 2

20. Remove Duplicate Characters

String result = "programming"
        .chars()
        .mapToObj(c -> String.valueOf((char) c))
        .distinct()
        .collect(Collectors.joining());

21. Functional Composition ⭐⭐⭐

Suppose:

Function<Integer, Integer> multiplyBy2 =
        n -> n * 2;

Function<Integer, Integer> add10 =
        n -> n + 10;

Compose:

Function<Integer, Integer> result =
        multiplyBy2.andThen(add10);
System.out.println(result.apply(5));

Output:

20

Because:

5 × 2 = 10
10 + 10 = 20

22. Method References

Instead of:

names.forEach(name -> System.out.println(name));

Use:

names.forEach(System.out::println);

Types:

String::toUpperCase
Employee::getName
System.out::println
Integer::sum

23. Stream Pipeline — Interview Concept ⭐⭐⭐⭐⭐

Remember:

SOURCE
  ↓
INTERMEDIATE OPERATIONS
  ↓
TERMINAL OPERATION

Example:

employees.stream()                 // Source
        .filter(e -> e.getSalary() > 100000)  // Intermediate
        .map(Employee::getName)              // Intermediate
        .sorted()                            // Intermediate
        .toList();                           // Terminal

Important

Intermediate operations are generally lazy.

Nothing actually happens until a terminal operation triggers evaluation.


24. Streams Are Not Collections

Excellent interview question:

Is Stream a data structure?

No.

A Collection stores data.

A Stream represents a pipeline for processing data.

Collection
   ↓
Stream
   ↓
Processing
   ↓
Result

A stream normally doesn't modify the original collection.


25. Parallel Stream — Architect-Level Question ⭐⭐⭐⭐⭐

numbers.parallelStream()
       .map(...)
       .toList();

Don't say:

"Parallel stream is always faster."

That's wrong.

Parallel streams use the ForkJoinPool/common pool by default and introduce overhead.

Good candidates for parallelism:

  • CPU-intensive operations

  • Large datasets

  • Independent operations

Poor candidates:

  • Small collections

  • Blocking I/O

  • DB calls

  • Network calls

  • Operations with shared mutable state

Dangerous

List<Integer> result = new ArrayList<>();

numbers.parallelStream()
       .forEach(result::add);

This introduces unsafe shared mutation.

Prefer:

List<Integer> result =
        numbers.parallelStream()
               .map(...)
               .toList();

🧠 10 Questions You Should Practice Before Monday

  1. map vs flatMap?

  2. map vs filter?

  3. Intermediate vs terminal operations?

  4. Why are Streams lazy?

  5. Can a Stream be reused?

  6. Stream vs Collection?

  7. Sequential vs parallel Stream?

  8. How does groupingBy() work?

  9. How do you handle duplicate keys in toMap()?

  10. Why should we avoid side effects in Streams?

⭐ Senior Architect answer

If asked "What is the biggest advantage of functional programming?", don't just say "less code."

Say:

Functional programming encourages declarative, composable and side-effect-minimized code. This makes transformations easier to reason about, test and compose, and can make parallel processing safer when operations are stateless and independent.

That sounds much more Senior Architect level than simply explaining filter() and map().

Sunday, 9 August 2026

🚀 Redis Scaling — Ramesh Style

 Absolutely. This chapter is essentially “How do we take Redis from one machine to a production-scale distributed system?” I’ll explain it in your Ramesh style: concept → why → architecture → example → interview point → real-world trade-off.

The chapter covers Persistence, Replication, Partitioning, Hash Partitioning, Presharding, Consistent Hashing, Tagging, and Twemproxy.


1. First understand the BIG picture

Imagine you have:

                Application
                     |
                     v
              +-------------+
              |    Redis    |
              |   1 Server  |
              +-------------+

Initially this is very fast.

But production grows:

  • 100 GB → 500 GB → 2 TB data

  • 10K requests/sec → 100K → 1M

  • One server becomes a bottleneck

  • Server failure becomes a major problem

So Redis scaling has 3 fundamental dimensions:

                  Redis Scaling
                       |
       +---------------+---------------+
       |               |               |
       v               v               v
 Persistence       Replication     Partitioning
       |               |               |
   Don't lose      Don't depend     Spread data
     data           on one node      across nodes

Ramesh formula:

Persistence = Don't lose data
Replication = Don't lose availability
Partitioning = Don't overload one machine


2. Persistence — “Redis memory is temporary”

Redis primarily stores data in memory.

Suppose:

Redis RAM

user:101 → Ramesh
user:102 → Sudha
user:103 → Yagna

Suddenly:

Redis crashes 💥

RAM disappears.

Therefore:

RAM = Fast
Disk = Durable

Redis provides two major persistence mechanisms:

             Persistence
                 |
        +--------+--------+
        |                 |
        v                 v
       RDB               AOF
   Snapshot           Write Log

The file explicitly describes RDB and AOF as the two Redis persistence mechanisms, which can also be enabled together.


3. RDB — “Take a photograph 📸”

Think of RDB as taking a snapshot of Redis.

At 10:00:

Redis:

A = 100
B = 200
C = 300

Redis creates:

dump.rdb

That file represents the dataset at that point in time.

Example

10:00 → Snapshot
10:05 → Snapshot
10:10 → Snapshot

If Redis crashes at:

10:12

You may restore from:

10:10 snapshot

But:

10:10 → 10:12

changes may be lost.

Ramesh rule

RDB = Fast recovery + possible recent-data loss


4. SAVE vs BGSAVE

This is an important interview question.

SAVE

Redis Main Process
      |
      | SAVE
      v
Disk

Redis blocks while creating the snapshot.

Therefore:

❌ Don't use SAVE casually in production.

BGSAVE

             Redis
               |
            fork()
           /      \
          /        \
   Main Process   Child
      |             |
  Serve users     RDB
                  Disk

BGSAVE creates the snapshot in a child process so the main process can continue serving requests.

But there is a hidden cost:

Copy-on-Write

Suppose:

Parent
100 GB

Child is creating RDB.

Meanwhile application modifies memory.

Redis may need additional memory for changed pages.

So:

Memory usage
     ↑
     |
100GB|        + changed pages
     |       /
     |______/

Interview point:

BGSAVE is non-blocking from the application's perspective, but fork + copy-on-write can increase memory pressure.


5. Redis Snapshot Configuration

The file gives examples such as:

save 900 1
save 300 10
save 60 10000

Meaning:

ConditionSnapshot
1 change within 15 minRDB
10 changes within 5 minRDB
10,000 changes within 1 minRDB

Ramesh interpretation

This is not:

“Save every 60 seconds.”

It is:

“If enough writes happen within the specified interval, take a snapshot.”


6. AOF — “Write down every transaction 📝”

RDB:

Take photograph

AOF:

Record the commands

Suppose application executes:

SET user:1 Ramesh
SET user:2 Sudha
INCR pageview
INCR pageview

AOF records the write commands.

After restart:

Redis
  |
  v
Read AOF
  |
  v
Replay commands
  |
  v
Rebuild dataset

The file describes AOF as an append-only command log that can rebuild Redis state by replaying commands in order.


7. AOF fsync — VERY important

AOF has three important policies:

appendfsync

       |
 +-----+------+ 
 |            |
no         everysec       always

no

Redis → OS → Disk

OS decides when to flush.

✅ Fast
❌ More potential data loss

everysec

Redis
  |
  +---- flush every second

✅ Good balance
⭐ Common default in the source material

always

Every write
     |
     v
fsync
     |
     v
Disk

✅ Strongest durability
❌ Slowest

The source explicitly describes no as fastest, always as safest but slowest, and everysec as a performance/durability balance.

Interview answer

RDB optimizes snapshot-based recovery; AOF prioritizes durability by recording writes.


8. RDB vs AOF — Ramesh Table

FeatureRDBAOF
ConceptSnapshotCommand log
FileBinaryAppend-only log
RecoveryFasterUsually slower
Data lossPossible between snapshotsDepends on fsync policy
File sizeSmallerCan become larger
Main useBackup / DRDurability
PerformanceGenerally betterMore overhead
Can coexist?YesYes

An important point from the source: when both exist, AOF takes precedence during startup because of its durability characteristics.


9. Replication — “One Redis is not enough”

Now imagine:

              Application
                   |
                   v
               MASTER
              Redis-1

Redis-1 crashes.

Game over.

So create replicas:

                 MASTER
                Redis-1
               /       \
              /         \
             v           v
        Replica-1     Replica-2

Writes:

Application
     |
     v
 MASTER
  |
  +--------> Replica 1
  |
  +--------> Replica 2

Redis replication allows one master to have multiple replicas.


10. Why Replication?

Three major reasons:

① Read scaling

                MASTER
             writes only
                  |
          +-------+-------+
          |               |
          v               v
       Replica          Replica
        reads            reads

Instead of:

1 Redis → 100K reads

you can distribute:

Master → writes
Replica1 → reads
Replica2 → reads
Replica3 → reads

The source specifically identifies replicas as a way to handle read operations separately from writes.

② High availability

If master dies:

MASTER 💥

Replica
   |
   v
Promote → MASTER

③ Data redundancy

Multiple copies exist.


11. But replication has a BIG problem

Replication alone does not automatically mean failover in the single-instance setup described by the chapter.

Example:

Master A
   |
   +---- Replica B
   +---- Replica C

Master A dies.

You manually need:

B → Master
C → replicate B
Clients → connect B

The source notes that automatic failover is the role of Redis Sentinel, covered in the following chapter.

Ramesh rule

Replication gives copies. Sentinel gives automatic failover.

And later:

Redis Cluster gives distributed data + cluster management.


12. Partitioning — THE BIG SCALING CONCEPT

Suppose:

Redis Server = 128 GB RAM

Your dataset becomes:

500 GB

Replication won't solve the capacity problem.

Why?

Because:

Master = 128 GB
Replica = copy of 128 GB
Replica = copy of 128 GB

You still need a machine capable of holding the entire dataset.

So we need:

SHARDING

The source defines partitioning as breaking data up and distributing it across hosts; in Redis, horizontal partitioning means distributing keys across instances.


13. Horizontal Partitioning

Imagine:

Redis Cluster

Server 1
user:1
user:2
user:3

Server 2
user:4
user:5
user:6

Server 3
user:7
user:8
user:9

Data is split by keys.

This is:

Horizontal partitioning = Sharding


14. Vertical Partitioning

Different idea:

User data

Profile
Orders
Payments
Activity

Could distribute different parts across servers.

Conceptually:

Redis-1 → Profile
Redis-2 → Orders
Redis-3 → Payments

The source distinguishes horizontal partitioning by keys from vertical partitioning by key values.


15. Range Partitioning

Very simple.

Suppose:

user:1
user:2
...
user:5000

Divide:

Redis-1 → 1–1000
Redis-2 → 1001–2000
Redis-3 → 2001–3000
Redis-4 → 3001–5000

The source uses exactly this type of incremental-ID example.

Problem #1 — Hotspot / uneven distribution

Suppose:

Redis-1 → 1 million keys
Redis-2 → 10,000 keys
Redis-3 → 10,000 keys

Bad distribution.

Problem #2 — Adding a server

Originally:

1 → Redis A
2 → Redis B
3 → Redis C

Add Redis D.

Ranges may need significant restructuring.

Therefore:

Range partitioning = simple, but difficult to rebalance.


16. Hash Partitioning

Now we become smarter.

Instead of:

key range → server

we do:

hash(key) % numberOfServers

Example:

hash("user:101") = 15

15 % 3 = 0

→ Redis-0

The source shows this exact basic formula.

Architecture:

             user:101
                 |
                 v
             hash()
                 |
                 v
               15
                 |
              % 3
                 |
        +--------+--------+
        |        |        |
       0         1        2
        |        |        |
       R1        R2       R3

Usually distribution becomes much more balanced than naive ranges.


17. BUT Hash Partitioning has a killer problem

Suppose:

3 Redis servers

Then:

hash(key) % 3

Now add:

Redis-4

It becomes:

hash(key) % 4

For many keys:

old server ≠ new server

So keys move.

For a cache:

Old:
user:100 → Redis-2

New:
user:100 → Redis-4

Redis-4 doesn't have it.

Result:

CACHE MISS 💥

The source reports that changing the number of instances can invalidate a large portion of data; its example saw 75% invalidated after adding two servers.


18. Presharding — clever workaround

Idea:

Don't wait until you need more nodes. Create many logical partitions upfront.

For example:

Server 1
 ├── Redis 6379
 ├── Redis 6380
 ├── Redis 6381
 ├── Redis 6382
 └── Redis 6383

Server 2
 ├── Redis 6379
 ├── Redis 6380
 ...

Instead of:

3 partitions

create:

15 partitions

Then later:

Small Server → Big Server

instead of changing:

15 partitions → 20 partitions

The source calls this presharding and explains that multiple Redis instances can be run per physical server.

Advantage

Hash mapping stays stable.

Disadvantage

More instances
     ↓
More monitoring
     ↓
More operational complexity

And it isn't truly elastic.


19. ⭐ Consistent Hashing — THE MOST IMPORTANT CONCEPT

This is the concept you were asking about earlier.

Normal hashing:

hash(key) % N

Problem:

N changes
↓
mapping changes massively

Consistent hashing says:

When nodes change, move only a small amount of data.

The source explains the idealized remapping as roughly K/n keys, where K is the number of keys and n is the number of servers.


20. Hash Ring — Think Like a Clock 🕐

Instead of:

0
1
2
3

imagine a circle:

             Server B
                ●
          .-------------.
       .                   .
      .                     .
Server A ●                 ● Server C
      .                     .
       .                   .
          '-------------'

This is the:

HASH RING

Both:

Servers
Keys

are hashed onto the ring.


21. Consistent Hashing Example

Suppose:

Server-1 → hash 3
Server-2 → hash 7
Server-3 → hash 11

Keys:

key1 → 3
key2 → 4
key3 → 8
key4 → 12

Now clockwise:

0 ---- 3 ---- 7 ---- 11 ---- 15
      S1      S2      S3

key1 = 3

Exactly at S1:

key1 → S1

key2 = 4

Next server clockwise:

4 → 7 → S2

key3 = 8

Next server:

8 → 11 → S3

key4 = 12

No server after 12.

So wrap around:

12 → 3 → S1

This is the same routing logic described in the source.


22. Why Adding a Server Is Better

Current:

       S1       S2       S3
-------●--------●--------●------

Add:

             S4
              ●

Only keys in the region immediately affected by S4 need to move.

Not everything.

That's the BIG WIN

Normal Hashing

Node added
    ↓
Many mappings change
    ↓
Many cache misses


Consistent Hashing

Node added
    ↓
Small portion moves
    ↓
Most cache mappings remain

23. Virtual Nodes — Very Important

Suppose only one point per server:

S1 ●

S2                 ●

S3                              ●

Distribution may be poor.

So create multiple points:

S1 → S1-1 S1-2 S1-3 S1-4 ...
S2 → S2-1 S2-2 S2-3 S2-4 ...
S3 → S3-1 S3-2 S3-3 S3-4 ...

These are:

Virtual Nodes / VNodes

The source's implementation defaults to 256 virtual nodes per client in its example.

Why?

To make distribution more uniform.

Physical Server
       |
       +-- vnode1
       +-- vnode2
       +-- vnode3
       ...

This is extremely important in distributed systems.


24. Consistent Hashing — Java Architect View

Think:

server = ring.getNextNode(hash(key));

Not:

server = servers.get(hash(key) % servers.size());

The difference:

Modulo hashing
      ↓
Node count is critical


Consistent hashing
      ↓
Ring position is critical

25. Tagging — Redis Multi-Key Problem

This is another very important Redis Cluster concept.

Suppose:

user:1
user:2

Hashing may send them to different nodes.

But what if you execute:

SINTER user:1 user:2

Redis needs both keys on the same Redis instance for this kind of operation.

Solution:

Hash Tags

Use:

user:1{users}
user:2{users}
user:3{users}

Redis hashes:

{users}

instead of the entire key.

Therefore:

user:1{users} ──┐
user:2{users} ──┼──> same Redis node
user:3{users} ──┘

The source specifically describes curly-brace tags as a way to force related keys onto the same instance.

Ramesh rule

If multiple keys must participate in one Redis operation, give them the same hash tag.


26. Cache vs Data Store — VERY IMPORTANT DESIGN DECISION

This is probably the most architect-level section.

Redis as CACHE

Database
   ↑
   |
Redis Cache

If cache data disappears:

Cache miss
   ↓
Database
   ↓
Reload cache

Therefore:

Cache can tolerate remapping.

Recommended:

Redis Cache
     ↓
Consistent Hashing

The source explicitly recommends consistent hashing for Redis cache workloads to minimize cache misses.


27. Redis as PRIMARY DATA STORE

Now imagine Redis contains:

Customer account balance
Payment information
Order state

You cannot casually move:

user:101

from Redis-1 to Redis-2.

You need:

Data ownership
Replication
Failover
Routing
Consistency
Recovery

That's where:

Redis Cluster

becomes much more appropriate.

The source recommends Redis Cluster or an equivalent replicated routing solution when Redis is used as a data store.


28. Client vs Proxy vs Query Router

There are three places where sharding logic can live:

              Sharding
                 |
       +---------+---------+
       |         |         |
       v         v         v
    Client     Proxy    Query Router

① Client-side

Application decides:

key → Redis node
Application
     |
     +--> Redis-1
     +--> Redis-2
     +--> Redis-3

② Proxy

Application thinks there is one Redis:

Application
     |
     v
  Proxy
 /  |  \
R1  R2  R3

Proxy decides where the key goes.

③ Query Router

Redis cluster itself handles routing.

Application
     |
     v
Redis Cluster
     |
 +---+---+---+
 R1  R2  R3

The source describes these three layers and notes that Redis Cluster acts as the query-routing layer.


29. Twemproxy

Twemproxy is essentially:

A proxy sitting between application and Redis servers to perform sharding.

Architecture:

                 Application
                      |
                      v
                 Twemproxy
                /    |    \
               /     |     \
             R1      R2      R3

Application doesn't need to know:

Which key → which Redis

Twemproxy handles it.

The source describes twemproxy as a lightweight Redis/Memcached proxy supporting multiple hashing modes including consistent hashing.


30. BUT Twemproxy has a SPOF

Imagine:

Application
     |
     v
 Twemproxy 💥
     |
  X  X  X
 Redis Redis Redis

Redis servers are healthy.

But application can't reach them.

Therefore:

Proxy itself must be highly available.

Better:

                 Load Balancer
                 /            \
                v              v
           Twemproxy-1    Twemproxy-2
              |  |  |        |  |  |
             R1 R2 R3       R1 R2 R3

The source explicitly identifies a single twemproxy process as a single point of failure and proposes a load balancer in front of multiple proxy instances.


🧠 Ramesh Master Architecture

Now put everything together.

                         CLIENTS
                            |
                            v
                     Load Balancer
                            |
              +-------------+-------------+
              |                           |
              v                           v
         Redis Proxy 1              Redis Proxy 2
              |                           |
              +-------------+-------------+
                            |
                     Redis Cluster
                            |
          +-----------------+-----------------+
          |                 |                 |
          v                 v                 v
       Shard-1           Shard-2           Shard-3
          |                 |                 |
        Master             Master            Master
        /    \             /    \            /    \
       R1     R2           R1     R2          R1     R2

And persistence:

Redis Master/Replica
       |
   +---+---+
   |       |
  RDB     AOF
   |       |
 Backup   Durable log

🔥 Ramesh Interview Cheat Sheet

ConceptOne-line meaning
RDBSnapshot of Redis
AOFRecord Redis write commands
ReplicationCopy data to other Redis nodes
ReplicaRead scaling + redundancy
FailoverPromote replica to master
PartitioningSplit data across machines
ShardingDistribute keys across nodes
Range partitioningKey range → server
Hash partitioninghash(key) % N
PreshardingCreate many partitions upfront
Consistent hashingAdd/remove nodes with minimal remapping
Hash ringCircular hash space
Virtual nodeMultiple logical positions for one server
TaggingForce related keys onto same shard
ProxyRouting layer outside Redis
TwemproxyRedis/Memcached sharding proxy
SentinelAutomatic failover/monitoring
Redis ClusterDistributed Redis with sharding + cluster management

⭐ The Most Important Mental Model

Remember this sequence:

             REDIS SCALING
                  |
       +----------+----------+
       |          |          |
       v          v          v
   PERSISTENCE  REPLICA   SHARDING
       |          |          |
       v          v          v
    RDB/AOF    Read/HA    Split data
                             |
                  +----------+----------+
                  |                     |
                  v                     v
              Hashing             Consistent
              Hash % N              Hashing
                                       |
                                       v
                                  Hash Ring
                                       |
                                       v
                                    VNodes
                                       |
                                       v
                                    Tags

And the Ramesh Golden Rule:

RDB/AOF solves DATA LOSS.
Replication solves READ SCALE + REDUNDANCY.
Sentinel solves FAILOVER.
Sharding solves DATA SIZE + WRITE SCALE.
Consistent Hashing solves NODE CHANGE + CACHE MISS.
Hash Tags solve MULTI-KEY OPERATIONS.
Redis Cluster brings distributed Redis together.

This chapter concludes with exactly these major themes—persistence, replication, partitioning, presharding, consistent hashing, and twemproxy—before moving into Redis Sentinel and Redis Cluster.

Saturday, 1 August 2026

Gossip - Protocol - System Design Fundamentals

 

Gossip Protocol in Dynamo Explained (Ramesh Style)

Think like this:

"If there is no Team Lead in a company, how does everyone know who is on leave?"

This is exactly the problem Dynamo solves.


Problem Statement

Suppose we have 100 Dynamo nodes.

Node A
Node B
Node C
...
Node Z

There is NO Master Server.

No Leader.

No Coordinator.

Every node is equal.

Now imagine

Node 37 crashes.

Question:

How do the remaining 99 nodes know Node37 is dead?


First Idea (Bad Solution)

Every node checks every other node.

A → B

A → C

A → D

....

A → Z

Similarly

B → A
B → C
B → D

Every node sends heartbeat to every other node.

Heartbeat

"I'm alive."

every second.


Total Messages

Suppose

100 nodes

Every node sends

99 messages

Total

100 × 99

≈ 9900 messages

Every second!

Huge network traffic.

This is

O(N²)

Very expensive.


Dynamo's Brilliant Solution

Instead of talking to everyone...

Every node talks to ONE RANDOM NODE.

That is Gossip.


Real Life Example

Imagine

100 friends in WhatsApp.

Instead of sending

"I got married"

to all 100 people...

You tell

Friend A

Friend A tells

Friend B

Friend B tells

Friend C

Friend C tells

Friend D

Soon...

Everyone knows.

Nobody informed everyone directly.

This is exactly Gossip Protocol.


Example

Cluster

A
B
C
D
E
F

Initially

Only

A

knows

Node X crashed

Round 1

A randomly picks

D
A ---> D

Node X crashed

Now

A knows
D knows

Round 2

A randomly picks

B
A ---> B

D randomly picks

F
D ---> F

Now

A
B
D
F

know.


Round 3

B tells

E

F tells

C

Now

Everyone knows.

No central server.

No broadcasting.

Only random communication.


Visualization

Initially

      A

Round 1

A ------> D

Round 2

A ---> B

D ---> F

Round 3

B ---> E

F ---> C

Finally

A B C D E F

Information spreads like a virus.


Why is it called Gossip?

Because humans gossip exactly like this.

A says

"Did you hear?"

↓

B says

"I heard..."

↓

C says

"Really?"

↓

Soon

Whole office knows.

What information is exchanged?

Each node sends

Node Status

Alive

Dead

Joining

Leaving

Also

Hash Ring Information

Token Ranges

Replication Info

Version Number

Basically,

Cluster Metadata

Example

Node A stores

Node1 Alive

Node2 Alive

Node3 Dead

Node4 Alive

Node B stores

Node1 Alive

Node2 Alive

Node3 Alive

Node4 Alive

When

A gossips with B

they compare.

B

"Oh...

Node3 is dead?"

Update completed.


Java Design

Let's design it.


Node Class

class Node {

    String nodeId;

    Map<String, NodeStatus> clusterInfo = new HashMap<>();

}

NodeStatus

class NodeStatus {

    String nodeId;

    boolean alive;

    long heartbeatVersion;

}

Gossip Message

class GossipMessage {

    Map<String, NodeStatus> clusterInfo;

}

Gossip Algorithm

Every second

Pick Random Node

↓

Send Cluster Metadata

↓

Receiver merges

↓

Done

Java Example

public class GossipNode {

    private final String nodeId;

    private final Map<String, NodeStatus> state = new HashMap<>();

    private final List<GossipNode> cluster;

    public GossipNode(String nodeId, List<GossipNode> cluster) {
        this.nodeId = nodeId;
        this.cluster = cluster;
    }

    public void gossip() {

        Random random = new Random();

        GossipNode target =
                cluster.get(random.nextInt(cluster.size()));

        if (target != this) {

            target.receive(state);

            System.out.println(nodeId +
                    " gossiped with "
                    + target.nodeId);
        }
    }

    public void receive(Map<String, NodeStatus> remoteState) {

        remoteState.forEach((id, remoteStatus) -> {

            NodeStatus local = state.get(id);

            if (local == null ||
                    remoteStatus.version > local.version) {

                state.put(id, remoteStatus);

            }
        });
    }
}

Merge Logic

Suppose

Node A

Node3 Version = 12

Node B

Node3 Version = 15

Obviously

15

is newer.

After gossip

Node A

updates to Version 15

Newest information always wins.


Heartbeat

Every node periodically updates

myStatus.version++;

Example

Node A

Heartbeat

Version

1

2

3

4

5

If it crashes

Version stops increasing.

Other nodes notice

Heartbeat timeout

↓

Dead Node

Scheduler

Every second

ScheduledExecutorService scheduler =
        Executors.newScheduledThreadPool(1);

scheduler.scheduleAtFixedRate(
        node::gossip,
        0,
        1,
        TimeUnit.SECONDS);

Every second

Random node selected.

Information exchanged.


Time Complexity

Without Gossip

Every node talks

to every node

O(N²)

With Gossip

One random node

O(N)

Much cheaper.


Advantages

FeatureBenefit
No Master NodeNo single point of failure
Random CommunicationLow network traffic
Eventually ConsistentEvery node learns the latest state over time
ScalableSuitable for clusters with thousands of nodes
Fault TolerantCluster continues even when nodes fail

Real-World Systems Using Gossip

SystemPurpose
Amazon DynamoMembership and cluster state
Apache CassandraNode discovery and failure detection
RiakCluster synchronization
ScyllaDBMembership management
HashiCorp SerfService discovery
Consul (internally)Membership and health dissemination

Interview Questions

QuestionAnswer
Why doesn't Dynamo use a master node?To eliminate a single point of failure and improve scalability.
Why not use heartbeats between every pair of nodes?It generates O(N²) messages, which doesn't scale.
What does Gossip Protocol exchange?Node status, heartbeat versions, hash ring information, replication metadata, and cluster membership.
Does Gossip guarantee immediate consistency?No. It provides eventual consistency for cluster metadata.
Why choose a random node?Random peer selection spreads information efficiently with minimal network overhead.

🎯 Ramesh Interview One-Liner

"Gossip Protocol is a decentralized peer-to-peer communication mechanism where each node periodically shares its view of the cluster with one randomly selected node. Over successive rounds, membership, heartbeat, and hash-ring information propagate throughout the cluster, enabling scalable and fault-tolerant cluster-state synchronization without requiring a central coordinator."

Friday, 31 July 2026

Rolling Hash in Java (Hash Collision Solving) – Part 2: Polynomial Hashing, Modulo Arithmetic, and Rabin–Karp (Interview Guide)

Author: Ramesh Vankayala


Introduction

In Part 1, we learned a simple rolling hash using the sum of ASCII values.

Hash = ASCII1 + ASCII2 + ASCII3

Although this helps us understand the concept, it is not suitable for real-world applications because many different strings can produce the same hash.

Example:

ABC

65 + 66 + 67 = 198

CAB

67 + 65 + 66 = 198

Different strings, same hash.

This is called a Hash Collision.

To reduce collisions, the Rabin-Karp algorithm uses Polynomial Rolling Hash.


Why Do We Need Polynomial Hashing?

Think of a vehicle registration number.

KA01AB1234

If we only added all digits together, many different registration numbers would produce the same total.

Instead, every position contributes differently.

The same idea is applied in polynomial hashing.

Characters appearing at different positions receive different weights.


Polynomial Hash Formula

The hash of a string is calculated as:

[
Hash = s_0 \times p^{m-1}

  • s_1 \times p^{m-2}

  • ...

  • s_{m-1} \times p^0
    ]

Where

SymbolMeaning
sCharacter value
pBase (31, 53, or 256 are common choices)
mLength of the string

Example

String

ABC

ASCII values

CharacterASCII
A65
B66
C67

Assume

Base = 31

Weights

CharacterWeight
A31²
B31¹
C31⁰

Step-by-Step Calculation

31² = 961

31¹ = 31

31⁰ = 1

CharacterFormulaValue
A65 × 96162,465
B66 × 312,046
C67 × 167

Final Hash

62465 + 2046 + 67

=64578

Unlike the simple ASCII sum, changing the order of the characters now changes the hash.


Why Choose Base 31?

Interviewers often ask:

"Why is the base usually 31?"

Reasons:

  • It is a prime number.

  • It distributes hash values well.

  • It reduces collisions.

  • Multiplication by 31 is computationally efficient.

  • Java's String.hashCode() also uses 31.


What is Modulo Arithmetic?

Imagine calculating the hash for a string with one million characters.

The number becomes extremely large.

Eventually, integer overflow occurs.

To avoid this, we keep the hash within a fixed range.

Instead of storing

98765432123456789

we store

98765432123456789 % 1,000,000,007

Why 1,000,000,007?

This number is frequently used because:

  • It is prime.

  • It fits within 32-bit integer calculations.

  • It minimizes collisions.

  • It is efficient for modular arithmetic.


Rolling Hash Formula

Suppose

ABCDE

Window size

3

Current window

ABC

Next window

BCD

Instead of recalculating the entire polynomial hash, we update it.

Conceptually:

Remove contribution of A

↓

Shift remaining characters

↓

Add D

This is why each window update is O(1).


Java Example

public class PolynomialHash {

    static final int BASE = 31;

    public static long calculateHash(String s) {

        long hash = 0;

        for (int i = 0; i < s.length(); i++) {
            hash = hash * BASE + s.charAt(i);
        }

        return hash;
    }

    public static void main(String[] args) {

        String s = "ABC";

        System.out.println(calculateHash(s));

    }
}

Output

64578

Rabin–Karp Algorithm

The complete algorithm follows these steps:

Pattern

↓

Calculate Pattern Hash

↓

Calculate First Window Hash

↓

Compare Hashes

↓

Different?

↓

Move Window

↓

Update Hash

↓

Compare Again

↓

Hash Match?

↓

Compare Characters

↓

Substring Found

Why Verify Characters?

Even polynomial hashes can collide.

Suppose

Hash(Window)

=

Hash(Pattern)

This does not guarantee the strings are identical.

Therefore, after a hash match, compare each character.

Hash Match

↓

Character Comparison

↓

Equal?

↓

Substring Found

Complexity

OperationComplexity
Pattern HashO(m)
First Window HashO(m)
Sliding Window UpdatesO(n)
Average OverallO(n + m)
Worst Case (many collisions)O(n × m)

Where:

  • n = length of the text

  • m = length of the pattern


Common Interview Questions

1. Why is Rabin–Karp faster than brute force?

Because it compares hash values instead of comparing every character in every window.


2. What is a Hash Collision?

Two different strings generating the same hash value.


3. Why verify characters after hash matching?

Because equal hashes do not always mean equal strings.


4. Why use modulo?

To prevent integer overflow and keep hash values within a manageable range.


5. Why is 31 commonly chosen?

  • Prime number

  • Better distribution

  • Lower collision probability

  • Used by Java's String.hashCode()


6. Where is Rabin–Karp used?

  • Search engines

  • Plagiarism detection

  • DNA sequence matching

  • Virus signature scanning

  • Text editors

  • Log analysis

  • Malware detection

  • Duplicate document detection


Interview Summary

A strong interview answer should include these points:

  1. Start with the brute-force solution and its O(n × m) complexity.

  2. Explain that hashing converts a string into a number.

  3. Introduce polynomial hashing to reduce collisions.

  4. Explain rolling hash for O(1) window updates.

  5. Mention modulo arithmetic to avoid overflow.

  6. Discuss hash collisions and character verification.

  7. Conclude that Rabin–Karp has an average time complexity of O(n + m).


Key Takeaways

  • Polynomial hashing is significantly more reliable than a simple ASCII sum.

  • Rolling hash avoids recomputing every window from scratch.

  • Modulo arithmetic prevents overflow and keeps hashes manageable.

  • Rabin–Karp combines rolling hash with character verification to efficiently solve substring search problems.

  • Understanding these concepts provides a solid foundation for advanced string algorithms such as KMP, suffix arrays, suffix automata, and string indexing.

A great follow-up article would be Part 3: "Rolling Hash Dry Run with Java Debugger", where every iteration is shown in a table with:

  • windowStart

  • windowEnd

  • oldHash

  • newHash

  • outgoing character

  • incoming character

  • hash comparison

  • character verification

  • decision (move/found)

This format is especially effective for interview preparation because it makes the algorithm's execution easy to visualize.

String Array Interview Techniq - Rolling Hash Explained in Java – How Rabin-Karp Solves the Substring Problem


Author: Ramesh Vankayala


Introduction

Finding whether a substring exists inside a larger string is one of the most common interview problems.

For example:

Text    = HELLOWORLD
Pattern = LOW

Expected Output:

Substring Found

The simplest solution is to compare every possible window character by character. However, this becomes slow for large strings.

The Rabin-Karp algorithm improves this by using a technique called Rolling Hash.


Brute Force Approach

We compare every possible window.

HELLOWORLD

HEL
ELL
LLO
LOW
OWO
WOR
ORL
RLD

Every window is compared character by character.

Time Complexity:

O(n × m)

n = Length of Text
m = Length of Pattern

Core Idea of Rolling Hash

Instead of comparing every character in every window,

convert every window into a single integer (Hash Value).

If hash values are different,

the strings are definitely different.

Only when hash values are equal do we compare the actual characters.

This reduces unnecessary comparisons.


Step 1 – Calculate Pattern Hash

Pattern

LOW

ASCII Values

CharacterASCII
L76
O79
W87

Pattern Hash

76 + 79 + 87 = 242

Store this value.


Step 2 – Calculate First Window Hash

Window

HEL

ASCII

CharacterASCII
H72
E69
L76

Hash

72 + 69 + 76 = 217

Compare

217 != 242

Not Found.

Move the window.


Step 3 – Rolling Hash

Previous Window

HEL

New Window

ELL

Instead of recalculating

69 + 76 + 76

Reuse the previous hash.

New Hash

= Previous Hash
- Outgoing Character
+ Incoming Character

=217-72+76

=221

This is called Rolling Hash.


Step-by-Step Execution

WindowHashPattern HashResult
HEL217242No
ELL221242No
LLO231242No
LOW242242Hash Matched

Now compare characters.

L == L

O == O

W == W

Substring Found.


Visual Representation

HELLOWORLD

HEL  -> 217

ELL  -> 221

LLO  -> 231

LOW  -> 242

Pattern

LOW ->242

Hash Match

↓

Compare Characters

↓

Substring Found

Java Program

public class RollingHashSubstring {

    public static void main(String[] args) {

        String text = "HELLOWORLD";
        String pattern = "LOW";

        int windowSize = pattern.length();

        // Pattern Hash
        int patternHash = 0;
        for (int i = 0; i < windowSize; i++) {
            patternHash += pattern.charAt(i);
        }

        // First Window Hash
        int windowHash = 0;
        for (int i = 0; i < windowSize; i++) {
            windowHash += text.charAt(i);
        }

        System.out.println("Pattern Hash : " + patternHash);
        System.out.println();

        for (int i = 0; i <= text.length() - windowSize; i++) {

            String window = text.substring(i, i + windowSize);

            System.out.println(
                    "Window : " + window +
                    "  Hash : " + windowHash);

            if (windowHash == patternHash) {

                boolean match = true;

                for (int j = 0; j < windowSize; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }

                if (match) {
                    System.out.println();
                    System.out.println("Substring Found at Index : " + i);
                    return;
                }
            }

            // Rolling Hash
            if (i < text.length() - windowSize) {
                windowHash =
                        windowHash
                        - text.charAt(i)
                        + text.charAt(i + windowSize);
            }
        }

        System.out.println("Substring Not Found");
    }
}

Program Output

Pattern Hash : 242

Window : HEL  Hash : 217

Window : ELL  Hash : 221

Window : LLO  Hash : 231

Window : LOW  Hash : 242

Substring Found at Index : 3

Why Rolling Hash is Faster

Without Rolling Hash

HEL

Calculate Again

ELL

Calculate Again

LLO

Calculate Again

LOW

Every window is calculated from scratch.

With Rolling Hash

Previous Hash

↓

Remove Left Character

↓

Add Right Character

↓

New Hash

Only two arithmetic operations are needed.


Important Interview Question

Q: If two different strings have the same hash, what happens?

Example

ABC

Hash =198

CAB

Hash =198

Both hashes are equal, but the strings are different.

This is called a Hash Collision.

Therefore, whenever hashes match, we must verify the actual characters before declaring success.


Time Complexity

ApproachTime Complexity
Brute ForceO(n × m)
Rolling Hash (Average)O(n)
Character VerificationOnly when hashes match

Interview Tips

  • Explain the brute-force solution first.

  • Mention its O(n × m) complexity.

  • Introduce hashing as a way to compare integers instead of characters.

  • Explain the rolling hash formula:

NewHash = OldHash - OutgoingCharacter + IncomingCharacter
  • Mention hash collisions and why character verification is required.

  • Finally, discuss how Rabin-Karp uses polynomial rolling hashes in real implementations to reduce collisions.


Key Takeaways

  • A string can be processed just like an array.

  • Rolling Hash reuses the previous computation instead of recalculating every window.

  • Rabin-Karp combines rolling hash with character verification.

  • The technique dramatically reduces repeated work and is a common interview topic at companies like Amazon, Microsoft, Google, Oracle, Walmart, and Wells Fargo.