>Digital-flame

✅ 1. Understand the Goals

Requirement	Description
⏱️ High availability	Keep the application running with minimal disruption
💾 Data integrity	Avoid data loss (use sync replication if needed)
🔄 Automatic switch	Detect failure and switch to standby quickly
🔁 Failback	Optionally return to the original primary after recovery

---

🧱 2. Choose the Right Failover Setup

🧭 Replication Strategy

Type	Primary Use	Notes
Synchronous	Strong consistency	May increase write latency
Asynchronous	Better performance	Possible data loss
Semi-sync	Middle ground	Acknowledged after 1 replica gets the write

---

🛠️ 3. Implementing Failover – Key Components

🔍 A. Health Checks & Monitoring

• Regularly check if the primary is reachable.
• Tools: Keepalived, Patroni, Consul, pg_auto_failover, custom scripts

🧠 B. Failover Manager / Orchestrator

Automatically promotes a replica if the primary fails.

DB	Tool	Function
PostgreSQL	Patroni, pg_auto_failover	Automatic leader election
MySQL	MHA, Orchestrator	Monitor & promote
MongoDB	Built-in	Replica sets handle this
Cloud DBs	AWS RDS, GCP SQL	Managed failover

📦 C. Virtual IP or Proxy Layer

• So clients don’t need to know which DB is active
• Use tools like HAProxy, pgpool-II, or ProxySQL
• These reroute traffic to the active node

💽 D. Application Logic

• Use retry logic and connection pooling
• Support failover-aware drivers (e.g., JDBC with multiple hosts)

💡 4. Example: PostgreSQL + Patroni + etcd + HAProxy

[App] ⇄ [HAProxy]
            ⇄ Primary (Postgres Node 1)
            ⇄ Replica (Postgres Node 2)

[Patroni + etcd cluster]
 ⇨ Monitors nodes, triggers failover, updates HAProxy

🔁 5. Manual Failover (Fallback Plan)

If automation fails:

1. Promote a replica manually:

pg_ctl promote /var/lib/postgresql/data

Update connection strings or proxy config.

Restart apps if needed.

Resync the old primary as a new replica.

📋 6. Test Regularly

• Simulate failure (kill primary node, cut network).
• Measure failover time and check data consistency.
• Have runbooks for manual failover.

🧠 Summary

Database failover is a critical part of high availability.
It requires replication, health checks, automatic promotion, and application resilience. The goal is to recover fast with minimal data loss.

The Saga pattern is a design pattern used to manage distributed transactions in microservices or distributed systems, where traditional ACID transactions are not feasible across services or databases.

🧠 What Problem Does It Solve?

In distributed systems:

• A single business process often spans multiple services.
• You can’t use a traditional database transaction across them (too slow or impossible).
• You need a way to ensure consistency, even if one service fails.

✅ Saga pattern breaks the big transaction into a sequence of smaller, local transactions, and manages rollback through compensating actions if something fails.

---

🧩 Example: Flight Booking System

Business Process:

1. Book a flight
2. Reserve a hotel
3. Rent a car

If car rental fails:

• Cancel the hotel
• Cancel the flight
  🔁 That’s the Saga — a set of forward actions + their corresponding rollbacks.

🔄 Two Types of Sagas

1. Choreography (Decentralized)

• Each service listens for events and triggers the next step.
• No central coordinator.

[Flight Service] → emits "FlightBooked"
↓
[Hotel Service] → emits "HotelReserved"
↓
[Car Service] → fails → emits "CarBookingFailed"
↓
[Hotel Service] → compensates → "CancelHotel"
↓
[Flight Service] → compensates → "CancelFlight"

✅ Simple
❌ Hard to track/debug

2. Orchestration (Centralized)

• A central controller (orchestrator) coordinates the entire saga.

[Saga Orchestrator]
→ call FlightService.book()
→ call HotelService.reserve()
→ call CarService.rent()
← if failure, call compensating methods in reverse

✅ Easier to control and debug
❌ More tightly coupled

🔐 Compensating Transactions

Each forward step needs a compensating (undo) transaction:

• chargeCustomer() ⇨ refundCustomer()
• reserveInventory() ⇨ releaseInventory()

---

🔧 Common Use Cases

Domain	Example
E-commerce	Order creation, payment, stock
Travel booking	Flight, hotel, rental car
Banking	Money transfer across institutions

✅ Summary

The Saga pattern is how you build reliable, eventually consistent workflows across multiple services when traditional distributed transactions aren’t an option.

It trades strong consistency for availability and resilience through compensating actions.

ACID compliance in distributed systems is a major challenge because you’re trying to guarantee strong consistency across multiple machines, each of which may fail independently, lose connectivity, or process operations at different speeds.

---

🧪 What is ACID?

ACID stands for:

Property	Meaning
Atomicity	A transaction is all-or-nothing
Consistency	The system moves from one valid state to another
Isolation	Concurrent transactions don’t interfere with each other
Durability	Once committed, the transaction survives crashes

🔧 How Distributed Systems Handle ACID

1. Atomicity (A)

To make a transaction atomic across nodes:

• Use Two-Phase Commit (2PC):
  • Prepare phase: All participants agree they can commit.
  • Commit phase: If all say yes, the coordinator tells them to commit.
  • ❌ Problem: blocking and coordinator failure.
• Or use Three-Phase Commit (3PC) (non-blocking but more complex).

Alternatives:

• Saga pattern (for long-running transactions): break big transactions into smaller, reversible ones.

2. Consistency (C)

Each node must validate its part of the transaction.

• Enforced via application-level invariants, foreign key checks, etc.
• Usually traded off for eventual consistency in AP systems (see CAP theorem).

3. Isolation (I)

• Hard to enforce strict isolation (e.g., serializable) across nodes.
• Often implemented via distributed locks, MVCC, or snapshot isolation.
• High-isolation levels reduce throughput and increase complexity.

4. Durability (D)

• Achieved via write-ahead logging, replication, and acknowledgments.
• Data is often written to multiple nodes before confirming success.

🧩 CAP Theorem vs ACID

• CAP: You can only guarantee 2 of 3 — Consistency, Availability, Partition tolerance.
• ACID is hard to achieve in systems that favor Availability and Partition Tolerance (AP).

So distributed databases often choose:

• ✅ BASE model: Basically Available, Soft state, Eventual consistency
• Instead of strict ACID, unless you’re okay with sacrificing availability (e.g., Spanner, CockroachDB use TrueTime or consensus protocols for global ACID).

✅ Real-World Examples

System	ACID Support	Notes
PostgreSQL (single-node)	✅ Full ACID	Reliable, but not distributed
MySQL Group Replication	⚠️ Partial ACID	Delays for strong consistency
Google Spanner	✅ Global ACID	Uses atomic clocks (TrueTime)
CockroachDB	✅ Serializable isolation	Uses Raft consensus
Cassandra, DynamoDB	❌ Not ACID	Focus on availability (AP)

---

🧠 Summary

ACID in distributed systems is achievable, but often at the cost of performance and availability. Systems that implement it usually rely on consensus protocols (like Paxos/Raft), global clocks, or complex coordination logic.

🧠 Key Concept

A Bloom filter is a bit array of fixed size, with multiple hash functions. You use it to:

• Insert: Map an item to a few bit positions and set those to 1.
• Query: Check if all the bit positions for an item are 1.

This means:

• If even one bit is 0, the item is definitely not in the set.
• If all bits are 1, the item might be in the set (→ false positive possible).

---

⚙️ Structure:

• Bit array bits[] of size m (e.g., 10,000 bits, all initialized to 0).
• k independent hash functions (e.g., 3 different hashes per item).

---

✅ Example — Step-by-Step

Let’s say:

• Bit array size m = 10
• Number of hash functions k = 3
• Hash functions output indexes from 0 to 9

---

1. Insert item “apple”

Suppose the 3 hash functions give:

• hash1("apple") % 10 = 1
• hash2("apple") % 10 = 4
• hash3("apple") % 10 = 7

Now set bits at positions 1, 4, and 7:

Index:   0 1 2 3 4 5 6 7 8 9
Bits:    0 1 0 0 1 0 0 1 0 0

2. Insert item “grape”

Hash outputs:

• hash1("grape") % 10 = 2
• hash2("grape") % 10 = 4
• hash3("grape") % 10 = 5

Set bits at positions 2, 4, and 5:

Index:   0 1 2 3 4 5 6 7 8 9
Bits:    0 1 1 0 1 1 0 1 0 0

3. Check if “apple” is in the set

Compute same hashes:

• 1, 4, 7 → bits are 1, 1, 1 → ✅ Might be in set (probably is)

4. Check if “peach” is in the set

Hash outputs:

• hash1("peach") % 10 = 3 → bit 3 is 0

So: ❌ “peach” is definitely not in the set

🔄 Why False Positives?

Now suppose you check “lemon” and the hash values happen to hit 1, 2, 4 — all of which are 1 due to other elements, not because of “lemon”. So:

→ Bloom filter returns “maybe in the set”, even though “lemon” was never added.

This is called a false positive.

🧮 Formula for False Positive Probability

The false positive rate can be approximated by:

Where:

• n = number of inserted elements
• k = number of hash functions
• m = number of bits

💡 Real World Usage:

• Web browsers: “Have I seen this URL before?”
• Databases: “Should I even try looking on disk?”
• Distributed systems: Avoid network requests for absent keys
• Blockchain: Bitcoin uses it to filter transactions

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It is fast and memory-efficient, but allows false positives (it may say “yes” even if the element isn’t in the set) — however, false negatives are impossible (if it says “no”, the element is definitely not in the set).

---

🔧 How it works:

1. A Bloom filter uses:
   • A bit array of size m (initially all 0s).
   • k independent hash functions, each maps an input to one of the m bits.
2. To add an item:
   • Hash the item with each of the k hash functions.
   • Set each resulting bit position in the array to 1.
3. To check if an item is in the set:
   • Hash the item with the same k functions.
   • If all k corresponding bits are 1, the item may be in the set.
   • If any bit is 0, the item is definitely not in the set.

---

✅ Example:

• Add “apple” → hash1, hash2, …, set bits 10, 23, 45 to 1.
• Add “banana” → set bits 7, 23, 90.
• Check “apple” → bits 10, 23, 45 → all 1 → “maybe in set”
• Check “grape” → bit 18 is 0 → “definitely not in set”

---

⚖️ Pros and Cons:

Pros	Cons
Very space-efficient	Allows false positives
Fast insert and lookup	Cannot delete elements (basic version)
No need to store actual data	Needs tuning for optimal m and k

🧠 Applications:

• Database systems (e.g., avoid unnecessary disk reads)
• Web caching
• Spell checkers
• Network intrusion detection
• Big data systems (e.g., Apache HBase, Apache Cassandra, Google Bigtable)

A Bloom filter helps optimize databases and storage systems by answering this question very efficiently:

🔍 “Does this item possibly exist?”
(with a small chance of false positives, but zero false negatives)

---

🧠 What Is a Bloom Filter?

A Bloom filter is a space-efficient, probabilistic data structure that can quickly tell you if an item:

• ❌ Definitely does not exist, or
• ✅ Might exist

It never misses existing data, but might occasionally lie and say something exists when it doesn’t.

🧰 How It’s Used in Databases

Bloom filters are used to avoid unnecessary disk reads, scans, or lookups by filtering out impossible matches early.

🔹 1. Index Optimization (Skip False Lookups)

In databases like Cassandra or HBase, Bloom filters are used to check:

“Should I even look in this file/SSTable for this key?”

• If no, skip the file — saves expensive I/O.
• If maybe, do the actual read.

✅ Improves read performance, especially in large datasets or LSM-tree-based stores.

🔹 2. Join Optimization

In distributed systems:

• A Bloom filter of keys from one table can be sent to another node to reduce data shuffling.

📦 Used in: Apache Spark, Hive

🔹 3. Caching Layer Efficiency

Before querying a slower database/cache, a Bloom filter helps:

• Avoid lookup if the key is definitely not in cache.
• Prevents cache misses from triggering unnecessary queries.

🔹 4. Partition Pruning

In partitioned databases, a Bloom filter can help determine:

“Should I scan this partition at all?”

Used in engines like Presto or BigQuery.

🔬 How It Works (Briefly)

• Uses k hash functions and a bit array.
• To add an item:
  • Hash the item k times and set corresponding bits to 1.
• To check:
  • Hash the item again k times. If any bit is 0, it’s definitely not in the set.

⚠️ Trade-offs

Pros	Cons
✅ Super space-efficient	❌ False positives (tunable rate)
✅ Fast membership checks	❌ Can’t delete items easily
✅ Great for read-heavy workloads	❌ Doesn’t store actual data

---

🛠️ Real-World Usage

System	Bloom Filter Use
Apache Cassandra	Avoid unnecessary SSTable reads
Google Bigtable	Filter unnecessary I/O during scans
Presto, Hive	Prune partitions before querying
RocksDB, LevelDB	Check if a key exists before disk read
Spark	Optimize joins and shuffles

---

✅ Summary

Bloom filters help databases skip work — especially disk reads and network operations — by saying “this key definitely doesn’t exist” in a fast, memory-efficient way.

To implement full-text search (FTS) in SQL, you need to go beyond simple LIKE queries and use built-in text indexing and search functions that support:

• Tokenization (splitting into words)
• Ranking / relevance
• Stemming / stop words
• Boolean logic (AND, OR, NOT)

Here’s how to do it in popular databases:

---

🧰 1. PostgreSQL: Best-in-Class Native FTS

✅ Step-by-step:

-- Create a table
CREATE TABLE articles (
  id SERIAL PRIMARY KEY,
  title TEXT,
  body TEXT,
  tsv tsvector -- preprocessed searchable vector
);

-- Populate the tsvector column
UPDATE articles SET tsv = 
  to_tsvector('english', coalesce(title, '') || ' ' || coalesce(body, ''));

-- Add an index
CREATE INDEX idx_articles_fts ON articles USING GIN(tsv);

-- Search
SELECT id, title
FROM articles
WHERE tsv @@ to_tsquery('english', 'search & term');

🔍 Explanation:

• to_tsvector = tokenize and normalize text
• to_tsquery = parse a query string ('cat & dog', 'run | jump')
• GIN index = fast inverted index for full-text search

🚀 Bonus: Auto-update tsv using a trigger

CREATE TRIGGER tsv_update BEFORE INSERT OR UPDATE
ON articles FOR EACH ROW EXECUTE FUNCTION
tsvector_update_trigger(tsv, 'pg_catalog.english', title, body);

🧰 2. MySQL (InnoDB since 5.6)

✅ Step-by-step:

-- Create table with full-text index
CREATE TABLE articles (
  id INT PRIMARY KEY AUTO_INCREMENT,
  title TEXT,
  body TEXT,
  FULLTEXT(title, body)
);

-- Search using MATCH ... AGAINST
SELECT id, title
FROM articles
WHERE MATCH(title, body) AGAINST ('+search +term' IN BOOLEAN MODE);

🔍 Notes:

• Use IN BOOLEAN MODE for advanced searches (+must, -exclude, *wildcards)
• Relevance ranking is returned with MATCH(...) AGAINST(...) AS score
• Works best on InnoDB with proper indexing

🧰 3. SQLite

Since v3.9, SQLite has FTS5 extension:

-- Create a virtual table
CREATE VIRTUAL TABLE articles USING fts5(title, body);

-- Insert data
INSERT INTO articles (title, body) VALUES ('PostgreSQL Guide', 'Learn full-text search');

-- Search
SELECT * FROM articles WHERE articles MATCH 'full +text';

🔍 When NOT to use Full-Text in SQL

For complex needs (e.g., fuzzy search, typo tolerance, multi-language stemming), consider:

• 🟡 Elasticsearch
• 🟡 Apache Solr
• 🟡 Meilisearch

These are search engines designed for more advanced full-text capabilities.

✅ Summary

Database	FTS Support	Notes
PostgreSQL	✅ Excellent	tsvector, tsquery, GIN indexes
MySQL	✅ Good	MATCH ... AGAINST, limited stemming
SQLite	✅ Light	FTS5 extension
SQL Server	✅ Yes	Full-text catalog & CONTAINS/ FREETEXT

✅ Short Answer:

MVCC is a form of optimistic concurrency control, but not all optimistic locking is MVCC.

---

🧠 Detailed Comparison

Feature	MVCC	Optimistic Locking (manual)
Type	System-level concurrency control	Application or ORM-level concurrency control
Uses versions?	✅ Yes — creates versions for each write	✅ Yes — usually uses a version number or timestamp
Conflict detection	Implicit — via visibility rules in DB engine	Explicit — you check version before writing
Locks used?	❌ No locks for reads	❌ No locks — check happens only at write time
When conflicts are handled	At commit time or during snapshot evaluation	When updating the row and version doesn’t match

---

🧩 Example

🔹 MVCC (e.g., in PostgreSQL):

• Transaction A starts and reads snapshot.
• Transaction B updates the row and commits.
• A doesn’t see B’s changes until it finishes or restarts.
• If A tries to write based on old data, conflict may arise.

🔹 Optimistic Locking (custom or ORM-based):

• Row has a version or updated_at column.
• You read: version = 1
• You write: UPDATE ... WHERE id = ? AND version = 1
• If version was incremented by someone else, 0 rows updated → conflict.

---

🏗️ MVCC = Optimistic at Engine Level

• MVCC handles versioning and snapshot isolation internally (transparent to you).
• It works great for systems with many reads and few write conflicts.
• MVCC is automated, while optimistic locking often requires manual setup in app logic.

---

✅ Summary:

MVCC is a built-in, low-level implementation of optimistic concurrency control, while optimistic locking usually refers to a higher-level, manual strategy implemented in application logic (e.g., via Hibernate, Spring Data, etc.).

Multi-Version Concurrency Control (MVCC) is a concurrency control method used in databases to allow multiple users to read and write to the database without blocking each other.

Instead of locking data for every read/write, MVCC keeps multiple versions of a data item, so readers and writers can operate concurrently and consistently.

---

🧠 Key Idea:

When a transaction reads data, it sees a snapshot of the database — the most recent version that was committed before it started.
When a transaction writes, it creates a new version rather than modifying the existing one.

---

🔄 Example:

Imagine a row in a table:
User(id=1, name="Alice")

1. Transaction A starts and reads the name: sees "Alice".
2. Transaction B starts after A and updates the name to "Alicia", then commits.
3. Transaction A, still running, reads the name again — it still sees "Alice" (its snapshot).
4. Later transactions will see "Alicia" — the new committed version.

---

📚 How It Works (Simplified)

Each row stores:

• Created version (Xmin): the transaction ID that created this version.
• Deleted version (Xmax): the transaction ID that invalidated it (if any).

When a transaction reads data:

• It checks whether a version was visible at the time the transaction started.

When writing:

• It creates a new row version and marks the old one as outdated (but doesn’t delete it immediately).

---

✅ Benefits

• Non-blocking reads: readers don’t block writers and vice versa.
• Consistent snapshots: every transaction sees a consistent view of the data.
• Good performance for read-heavy workloads.

---

⚠️ Trade-offs

• More storage: due to multiple versions.
• Garbage collection needed: old versions must be cleaned up (e.g., PostgreSQL’s VACUUM).
• Complex logic to manage version visibility.

---

🛠️ Used In:

Database	MVCC Support	Notes
PostgreSQL	✅	Full MVCC, VACUUM cleans old tuples
MySQL (InnoDB)	✅	Uses undo logs for old versions
Oracle	✅	Uses rollback segments
SQLite	✅	Since version 3.7.0

---

🧪 MVCC vs Locking

Feature	MVCC	Lock-Based Control
Read performance	High (no blocking)	Readers may wait for locks
Write contention	Handled via versioning	Handled via locks
Complexity	Higher internals	Simpler conceptually
Snapshot isolation	Easy	Hard

🧠 1. Understand the Use Case

Eventual consistency is useful when:

• High availability is critical.
• Temporary stale reads are acceptable (e.g., social media likes, shopping carts).
• You want to keep writing during network partitions.

⚙️ 2. Key Techniques for Eventual Consistency

🔁 a) Asynchronous Replication

• Writes are sent to one or more nodes.
• The system acknowledges the write before all replicas are updated.
• Background processes replicate the data eventually.

Example:
In Cassandra, a write can go to one node (QUORUM, ONE, etc.) and be propagated to others later.

📦 b) Versioning with Vector Clocks or Timestamps

• Each version of data is tagged with a vector clock or timestamp.
• When conflicting writes happen, the system can:
  • Auto-resolve (e.g., “last-write-wins”)
  • Expose conflicts to the application to resolve

Used in: Amazon Dynamo, Riak.

📬 c) Read Repair

• When a client reads from a replica, it may compare data with other replicas.
• If it detects inconsistencies, it can update out-of-date replicas in the background.

Example: Cassandra performs read repair behind the scenes.

🔎 d) Anti-Entropy Mechanisms (e.g., Merkle Trees)

• Periodically compare data across nodes to detect divergence.
• Only synchronize what’s different to reduce bandwidth.

Used in: Dynamo, Cassandra.

⚖️ e) Conflict-Free Replicated Data Types (CRDTs)

• Data structures that resolve concurrent updates deterministically.
• Guarantees convergence without coordination.

Used in: Redis CRDTs, Riak.

💡 3. Practical Implementation Sketch

Let’s say you’re building a custom distributed key-value store:

1. Write Process
   • Client sends a write to Node A.
   • Node A stores the data with a timestamp and returns success.
   • Node A asynchronously replicates the write to Nodes B and C.
2. Read Process
   • Client reads from Node C.
   • Node C compares version with A and B (if possible).
   • If stale, returns value + triggers background sync (read repair).
3. Background Anti-Entropy
   • Nodes periodically compare data via Merkle Trees.
   • Only update changed keys.

---

✅ Real-World Systems

System	Strategy
Cassandra	Tunable consistency, read repair, hints
DynamoDB	Last-write-wins, vector clocks
Couchbase	Conflict resolution via timestamps
Riak	Vector clocks, CRDTs
MongoDB	Replica sets with tunable read/write concern

---

⚠️ Challenges

• Conflict resolution logic can be complex.
• Data staleness needs to be acceptable for your use case.
• Testing eventual consistency is harder than strong consistency.

Eventual consistency is a consistency model used in distributed systems to ensure that, given enough time and no new updates, all replicas of a piece of data will converge to the same value.

✅ In Simple Terms:

• When you update data, that change might not appear instantly on all servers or nodes.
• But if you wait long enough, and no more updates are made, all nodes will eventually show the same result.

📦 Example:

Imagine a system with 3 database replicas across the world (New York, London, Tokyo):

1. You update your profile name from “Stan” to “Stanley” via the New York server.
2. London and Tokyo may still show “Stan” for a few seconds.
3. After replication catches up, all three servers show “Stanley”.

🧠 Why Use Eventual Consistency?

Because it enables:

• High availability: systems don’t block waiting for global agreement.
• Partition tolerance: systems can still work even if some nodes are unreachable.
• Performance: faster writes due to asynchronous replication.

💡 Real-World Examples:

System	Behavior
Amazon DynamoDB	Updates are propagated eventually across regions.
Cassandra	Uses tunable consistency — you can opt for eventual.
S3 / Cloud Storage	Writes may not be instantly visible in other regions.
Social Media Feeds	A like might not appear to all users immediately.

⚠️ Trade-offs:

Pros	Cons
Fast writes, high availability	You may see stale data temporarily
Works well at large scale	Conflict resolution can be tricky

🔁 Comparison:

Model	Guarantees
Strong Consistency	All users see the same data at the same time.
Eventual Consistency	All users will eventually see the same data.
Causal Consistency	Order of related operations is preserved.