分散式系統的 CAP

每次看完就會重新想起來，然後一段時間之後又會忘記定義，所以想說整理一下推導這個概念的過程。

CAP 分別代表的是以下三個概念：

• 一致性（Consistency）
• 可用性（Availability）
• 分區容錯性（Partition tolerance）：我個人認為白話來說就是是否允許系統中有節點與其他節點完全斷線。

最重要的關鍵在於 Partition tolerance 的問題，也就是當節點間的連線被切斷了的時候，狀況會變成如何？

1. 滿足 AP 時無法滿足 C－如果節點連線被切斷了，例如被切割成 A 群和 B 群節點，但整個分散式系統的所有節點依然都能夠繼續提供服務，這時就滿足了 Availability 和 Partition tolerance。但因為 A 群和 B 群互相連不上對方，因此在 A 群當中做的變更，將無法反應在 B 群中。亦即此時 Consistency 就無法被滿足了。在 GlusterFS 當中，這個現象被稱為 split brain，就是系統存在兩顆大腦，兩顆大腦會同時做不同的思考。
2. 滿足 CP 時無法滿足 A－如果節點連線被切斷了，變成 A 群和 B 群節點，但因為要確保整個系統資料的一致性，因此依照某些規則決定把被認為斷線的那個部份停用，例如認為 A 群才是 master，把 B 群暫時停用，直到 B 群重新連上 A 群為止。此時能夠保證 Consistency 和 Partition tolerance，但是因為在被分區的這個當下，部份節點會處於不可用的狀態，因此就無法滿足 Availability 了。
3. 滿足 CA 時無法滿足 P－如果永遠要確保在系統中所有節點的資料一致，而且所有節點都要保證可用，那麼可想而知，就不能允許發生像上面講到的，網路斷線產生兩群節點互相連不上對方的狀況（因為一旦發生斷線，只要雙方都持續提供服務，則一定會 split brain；要不 split brain 只能選擇停用其中一方）。也就是這時就無法滿足 Partition tolerance 了。

Cross-Origin Resource Sharing

(書籤) Java Memory Model

很久沒用到，覺得已經不太記得細節了…。一般在工作上會優先架構成能夠允許最終一致性的狀況，不過如果遇到強一致性的多執行緒需求，還是必須考慮到 Java Memory Model。

大體上來說，因為硬體上 Thread 會有自己的本地快取，因此在不同 Thread 間對同個物件的「視野」可能是不同的。概念上很像是在資料庫上會遇到兩個 Transaction 看見的內容不同的那種狀況。由於硬體終究會將本地快取 flush 回主記憶體，所以最終還是會保持一致性，只是在過程中不見得永遠會滿足執行緒間的一致性，這時就需要 volatile 登場了。

參考資料

1. Wikipedia - Java memory model
2. Java Memory Model
3. 深入理解 Java 内存模型（一）——基础
4. Stack Memory and Heap Space in Java
5. Difference between volatile and synchronized in Java
6. JAVA多執行緒之volatile 與 synchronized 的比較
7. Volatile vs Static in Java

Dependency Injection 與 static

最近一直在思考 Spring 與 static 之間的關係。一般來說，Spring 會管理由它生成的 Bean，不過如果類別本身是以 static 形式呼叫（例如程式碼呼叫 MyClass.callStaticMethod() 這種方式）的話，正常來說就不會被 Spring 所管理，自然在類別內的自動注入（如果有的話）也不會生效。雖然是有一些小技巧可以姑且繞過問題，不過感覺上從 Spring 的角度，好像應該用別種思考模式來思考這個問題。

關於這個問題，在請教 qrtt1 大神之後獲得了解惑，請大家一起膜拜 qrtt1 大神～（拜）。不過其實概念也並不困難，只是不知道為什麼原本一直想不通。

PostgreSQL 的索引：B-tree

開這篇之前，其實本來是想要了解 PostgreSQL 10 裡實現索引的原理，畢竟在了解原理的情況下，比較容易想像在什麼情況下索引能夠具有優勢、什麼情況索引幫不上忙。不過花了一段時間搜尋…也不能說沒有找到，但沒有找到我想要的類型。所以這篇雖然標題在講 PostgreSQL 的 B-tree 索引，但實際上會先紀錄的是一般關聯式資料庫以 B-tree 做索引時的狀況。如果想參考看看我找到的其他在談 PostgreSQL B-tree 原理的文章，可以看看 [1-5]。

這篇當中實際會紀錄到的東西，有很大一部份並非來自 PostgreSQL 的官方文件，因此這並不一定完全就是 PostgreSQL 實現的方法，嚴格來說其實這個標題並不是太合適。不過理想上….應該不會差太多….吧！此外這篇文章紀錄的事項，除了我個人的觀點以外，有許多部份是來自 USE THE INDEX, LUKE! [7] 這個網站的解說。因此如果想要有條理地細讀，推薦可以直接去閱讀這個網站的內容。

然後呢，理想上我是想要依序了解所有 PostgreSQL 的索引結構，並分別做點紀錄。所以它有可能會是個系列文，這篇作為系列文的第一篇就會參雜一些奇怪的廢話了。但…也不保證真的會寫出來就是，以前有編號的系列文絕大多數都虎頭蛇尾了 Orz，所以這次索性不編號了。

(書籤) Hibernate 的 JOIN FETCH

參考資料

1. How to fetch entities multiple levels deep with Hibernate
2. Join用法，HQL的方法，Hibernate中的fetch
3. Hibernate Best Practices

演算法的細緻之處…

在 LeetCode 上有個簡單的題目：Two Sum [1]，題目很單純，就是給定一個陣列以及一個目標值，找出能夠滿足相加會等於目標值的兩個數字。

這個問題最容易想到的自然是暴力破解，暴力破解的複雜度是 O(n²)。而另一種想法大概是左右逼近，但這存在一個前提是陣列必須是已排序的陣列，所以考慮排序的話，複雜度會是 O(nlogn)（實際來說複雜度可能是 O(nlogn + 2n) 吧）。然後如果有想到可以用空間換取時間的話，利用 HashMap 就可以達到 O(n)。

接著三種解法都送出的話，想像上效能應該是 O(n) > O(nlogn) > O(n²)，不過實際上呢？（但我沒有嘗試送出 O(nlogn) 的版本，所以時間直接引用 [2]）

idle in transaction

在 PostgreSQL 中，如果因為某些因素必須要關閉部份的 transaction，需要判斷一個 transaction 是否可以被安全地關閉。這時可以從 pg_stat_activity 裡面觀察 transaction 的狀態，主要觀察的對象是兩個參數：backend_xid 和 backend_xmin。比較詳細的描述可以參考 [1]。