主要是這個人的影片 Jordan has no life
1: TinyURL + PasteBin | Systems Design Interview Questions With Ex-Google SWE (youtube.com)
針對這個議題來寫一下心得。
總之要設計一個 tinyURL + PasteBin
URL hash 方式設計
因為題目要求 1 trillion = 1,000,000,000,000 只要用 a-z0–9 -> 36⁸ 次方 所以 8 個位元可以代表
然後 因為是隨機，如果隨機到碰撞之後，可以直接使用類似 取下一位
例如 aaaaaaaa 碰撞 → aaaaaab 直到找到可以塞入的部分為止
為了增進寫進的效率，我們可以用 multi-leader/leaderless replication 嗎?
不行，有可能因為某個人同時碰撞，並且她本來的 url 網址被更改，就算我們發現這件事情。提醒使用者，而且因為網址通常都會貼上，那些被貼上的網址很難一一更改。(e.g. 貼到簡報上或是發送短網址給他人
同理，快取也是，不能用 write back，因為兩邊可能不知道是誰寫入 (write conflict)
Partion by hash ID
因為我們 url 已經被hash過一次了，所以分布應該是相對平均的，所以不用太擔心某個 shard 資料量特別多。consistent hash
網址寫入衝突如何解決
- Predicate locks 總之就是兩個人都寫看看，失敗那個人會，退回來再加一 (store procegure 可以避免兩次query
- materlizing conflict，總之就是類似把所有的 id 都寫進去然後設定 NULL 之類的，這樣就可以保證大家拿的時候，會是有LOCK。(因為本來沒有這個機制的話，你不能對一個空的東西拿LOCK)
影片提到兩個方法都可以解決，應該是採用方法 1
INDEX 結構選擇
- hash index 使用過多的memory 應該不可能採用。(hash index 必須要把所有的 key 存進 memory 裡面)
- LSM Tree → 寫入快，讀取慢
- B-Tree → 寫入慢 讀取快
Database選擇 → MYSQL
- Single leader replication
- Partition
- B-Tree Based
可以減少 loading 藉由 Replicas + multiple partitions
如果 replica 裡面沒有資料，可以考慮去 master 詢問，可是這樣有可能 overloading master，因為有人可能亂打 id。
cache 機制
- write back 剛剛提到過，不可能，有可能會有 conflict
- write through 有機會，可是可能會降低速度。因為需要讓 cache/db consisten 會有點麻煩
- write around，等 read cache miss，並且去 db 拿之後，再寫進 cache 並且用 LRU 機制來過期他
Click 數量 儲存🖱️🖱️🖱️🖱️🖱️🖱️🖱️
如果用 naive situation 會有 race condition 的狀況存在。
Stream Processing
- In memory message broker → super fast , not durable
- Log message borker → kafka (Write Ahead Log 讓他寫很快) , rabbitMQ
Conusumer Choose
- HDFS + Spark → Batch job to aggregate, click may be to infrequent。太慢不選擇 (不即時的意思
- Flink → Processes each event individualy, may send too many writes to the database.
- Spark Streaming → processes events in configurable mini-batch size
如何 確認 Idempontcy
可以在 count 後面加一個 id， e.g. url_id, original_url, count, Idempontcy_key
然後想像應該可以寫類似說
update xxx = xxx + 10 whree url_id = 'a' and Idempontcy_key != 'xxx'但是這個帶來另外一個問題是。
Q: 如果有多個 worker 怎麼辦?!
A: 只要確認每一個 url 只會被同一個 worker 處理到就行了 (partitioning kafka queu by short url_id) 這樣可以確保 在處理某一個 url_id 的時候，都是同一個 worekr (意義上就是只有一個 worker)
總之用以上的解法，就可以解決 race condition 的問題 + 不用 two phase commit (例如 grab lock)