# Caching Strategies ---  from https://web.dev/service-worker-caching-and-http-caching ---- - Local Caching - Run program on a single process and single thread - Storage Caching - Caching in Storage (Redis, ElasticSearch, Database) - Access from multip applications - Network Caching - The browser got data after the first request and response --- ## Local Caching - Run program on a single process and single thread ---- ```sequence Program->Cache:1. get data Cache->Program:2 no data Program->Program:3 calculate Program->Cache:4 update data ``` ---- ```sequence Program->Cache:1. get data Cache->Program:2 return data ``` ---- Example: Fibonacci Sequence - n: non-negative integer - f(n) = 0, for n = 0 - f(n) = 1, for n = 1 - f(n) = f(n-1) + f(n-2), n > 1 ---- |f(0)|f(1)|f(2)|f(3)|f(4)|f(5)|f(6)| |-|-|-|-|-|-|-| |0|1|1|2|3|5|8| ---- ```javascript= function fibonacci(n) { if (n === 0) { return 0; } else if (n === 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(6)); // output: 8 ``` ---- ```graphviz digraph hierarchy { f4_2[label=f4]; f3_2[label=f3]; f3_3[label=f3]; f2_2[label=f2]; f2_3[label=f2]; f2_4[label=f2]; f2_5[label=f2]; f1_2[label=f1]; f1_3[label=f1]; f1_4[label=f1]; f1_5[label=f1]; f1_6[label=f1]; f1_7[label=f1]; f1_8[label=f1]; f0_2[label=f0]; f0_3[label=f0]; f0_4[label=f0]; f0_5[label=f0]; f6->f5; f6->f4; f5->f4_2; f5->f3; f4->f3_2; f4->f2; f4_2->f3_3; f4_2->f2_2; f3->f2_3; f3->f1; f3_2->f2_4; f3_2->f1_2; f2->f1_3; f2->f0; f3_3->f2_5; f3_3->f1_4; f2_2->f1_5; f2_2->f0_2; f2_3->f1_6; f2_3->f0_3; f2_4->f1_7; f2_4->f0_4; f2_5->f1_8; f2_5->f0_5; } ``` - Time Complexity: O(2^n) ---- ```javascript= const cache = {}; function fibonacci(n) { if (cache[n]) { return cache[n]; } if (n === 0) { return 0; } else if (n === 1) { return 1; } const result = fibonacci(n - 1) + fibonacci(n - 2); cache[n] = resutl; return result; } ``` - Time Complexity: O(n) ---- #### Recap - Time Complexity vs. Space Complexity ---- #### Another Algorithm ```javascript= function fibonacci(n) { let n_1 = 1; let n_2 = 0; let result = 0; for (let i = 0; i <= n; i++) { if (i === 0) { result = 0; } else if (i === 1) { result = 1; } else { result = n_1 + n_2; n_1 = result; n_2 = n_1; } } return result; } ``` - Time Complexity: O(n) --- ## Storage Caching - Caching in Storage (Redis, ElasticSearch, Database) - Access from multip applications ---- ```mermaid graph LR app1[Application 1] app2[Application 2] app3[Application 3] cache[(Cache)] app1 & app2 & app3 --> cache ``` ---- - Time To Live (TTL) - Interval update cache - Update cache if the cache is expired - Active update cache if data changed or some event trigger ---- - Consistency - Eventual consistency - make sure the update execute in the correct order - Strong consistency - Atomtic Update - Database Lock - Lock Server - Cache Miss - Precache --- ## Network Caching - The browser got data after the first request and response ---- ```sequence Browser->Server:1. Request Server->Browser:2. Response Browser->Server:??? ``` ---- - Could the server tell the browser whether the data is up to date? ---- #### Expiration Time ```sequence Browser->Server:1. Request Server->Browser:2. Response with expiration time Browser->Browser:3. Get data from disk cache if not expire ``` ---- #### Revalidation ```sequence Browser->Server:1. Request Server->Browser:2. Response with ETag or last modified time Browser->Server:3. Second Request with ETag or last modified time Server->Browser:4. Response with 304 Not Modified Browser->Browser:5. Get data from disk cache ``` ---- - Http Caching - Expiration Time - Expires - Cache-Control and max-age - Revalidation - Last-Modified and If-Modified-Since - ETag and If-None-Match - Cache-Control or Pragma - private, public, no-cache... ---- #### Cache-Control  from https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching ---- - Integrity checking - Consistency Hash: MD5 or CRC32C - References: - https://blog.techbridge.cc/2017/06/17/cache-introduction/ ---- - Stale-while-revalidate  from https://web.dev/offline-cookbook/ ---- - UX - Show last updated time - Show rarely change data first - Request frequently change data ---- #### Recap - Local Caching - Time Complexity vs. Space Complexity - Storage Caching - TTL (Time to Live) - Data Consistency - Precaching - Network Caching - Http Caching - Expiration Time - Revalidation - Stale-while-revalidate ---- #### References - https://blog.techbridge.cc/2017/06/17/cache-introduction/ - https://web.dev/service-worker-caching-and-http-caching - https://web.dev/offline-cookbook/