# Caching

## Cache Invalidation

### **Write-through cache:**

> Under this scheme **data** is **written** into the **cache** and the corresponding **database** at the **same** **time**.
>
> Every **write** **operation** must be **done** **twice** **before** **returning** **success** to the **client**

#### Pros:

* (**Data Consistency**) The cached data allows for **fast retrieval**, and since the **same** **data** gets written in the **permanent** **storage**, we will have complete **data consistency** between **cache** and **storage**.
* (**Fault** **Tolerance**) This scheme ensures that nothing will get lost in case of a crash, power failure, or other system disruptions. It **minimizes** the **risk** of **data** **loss**.

#### Cons:

* (**Higher Latency**) higher **latency** for **write** operations

### **Write-around cache:**

> This technique is similar to write through cache, but data is written directly to permanent storage, bypassing the cache.

#### Pros:

* This can reduce the cache being flooded with write operations that will not subsequently be re-read, 

#### Cons:

* but has the disadvantage that a read request for recently written data will create a “cache miss” and must be read from slower back-end storage and experience higher latency.

### **Write-back cache:**

> Under this scheme, **data** is **written** to **cache** **alone**, and **completion** is **immediately** **confirmed** to the **client**.
>
> The **write** to the **permanent** **storage** is done **after** **specified** **intervals** or under **certain** **conditions**.

#### Pros:

* (**Low Latency & High Throughput**) This results in **low** **latency** and **high** **throughput** for **write-intensive** **applications**, 

#### Cons:

* (**Data Loss**) however, this speed comes with the **risk of data loss** in case of a crash or other adverse event because the **only copy** of the **written** **data** is in the **cache**.

Cache Invalidation Schemes Comparison

|             | Write-through cache | Write-around cache | Write-back cache |
| ----------- | ------------------- | ------------------ | ---------------- |
| Description |                     |                    |                  |
|             |                     |                    |                  |
| Pros        |                     |                    |                  |
| Cons        |                     |                    |                  |

## Cache Eviction Policies

| Cache Eviction Policies     | Description                                                                                                                       |
| --------------------------- | --------------------------------------------------------------------------------------------------------------------------------- |
| First In First Out (FIFO)   | The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before.         |
| Last In First Out (LIFO)    | The cache evicts the block accessed most recently first without any regard to how often or how many times it was accessed before. |
| Least Recently Used (LRU)   | Discards the least recently used items first.                                                                                     |
| Most Recently Used (MRU)    | Discards, in contrast to LRU, the most recently used items first.                                                                 |
| Least Frequently Used (LFU) | Counts how often an item is needed. Those that are used least often are discarded first.                                          |
| Random Replacement (RR)     | Randomly selects a candidate item and discards it to make space when necessary.                                                   |