Dynamo

Cassandra 使用稱為一致性雜湊的特殊雜湊形式，將資料分割到儲存節點上。在單純資料雜湊中，您通常會透過對金鑰進行雜湊模組桶數，將金鑰分配到桶中。例如，如果您想使用單純雜湊將資料分發到 100 個節點，您可能會將每個節點指定到 0 到 100 之間的桶，將輸入金鑰模組 100 進行雜湊，然後將資料儲存在相關聯的桶中。然而，在此單純的架構中，新增一個節點可能會使幾乎所有對應無效。

Cassandra 反而將每個節點對應到連續雜湊環上的至少一個令牌，並透過將金鑰雜湊到環上，然後沿著一個方向「遍歷」環，類似於Chord演算法，來定義擁有權。一致性雜湊與單純資料雜湊的主要差異在於，當雜湊到的節點（桶）數量發生變化時，一致性雜湊只需要移動一小部分金鑰。

例如，如果我們有一個具有均勻間隔令牌的八節點叢集，以及 3 的複製因子 (RF)，則要找出一個金鑰的所有者節點，我們首先對該金鑰進行雜湊以產生一個令牌（這只不過是金鑰的雜湊），然後我們以順時針方式「走」環，直到遇到三個不同的節點，此時我們已經找到了該金鑰的所有複本。以下可以視覺化 gRF=3 的八節點叢集範例

您會看到在類似 Dynamo 的系統中，金鑰範圍（也稱為令牌範圍）會對應到相同的實體節點組。在此範例中，所有落在令牌範圍內（不包含令牌 1，包含令牌 2）的令牌（grange(t1, t2]) 都儲存在節點 2、3 和 4 上。

如果有很多實體節點可以散佈資料，則單一令牌一致性雜湊運作良好，但對於均勻間隔的令牌和少數實體節點，增量擴充（只新增少數容量節點）很困難，因為沒有令牌選取可以讓新節點保持環平衡。Cassandra 會避免令牌不平衡，因為不均勻的令牌範圍會導致不均勻的請求負載。例如，在先前的範例中，沒有辦法新增第九個令牌而不造成不平衡；相反地，我們必須在現有範圍的中點插入8個令牌。

Dynamo 論文主張使用「虛擬節點」來解決這個不平衡問題。虛擬節點透過將令牌環中的多個令牌指定給每個實體節點來解決問題。透過允許單一實體節點在環中佔據多個位置，我們可以讓小型叢集看起來更大，因此即使只新增一個實體節點，我們也可以讓它看起來像新增了更多節點，當我們新增一個節點時，實際上從更多環鄰居那裡取得許多較小塊的資料。

Cassandra 引入一些術語來處理這些概念

將令牌對應到端點會產生令牌對應，Cassandra 在其中追蹤哪些環位置對應到哪些實體端點。例如，在以下圖中，我們可以使用僅有四個實體節點的八個節點叢集，方法是將兩個令牌指定給每個節點

每個實體節點的令牌越多，會提供以下好處

但是，多個令牌也可能帶來缺點

請注意，在 Cassandra 2.x 中，唯一可用的令牌配置演算法是挑選隨機令牌，這表示為了保持平衡，每個節點的預設令牌數必須相當高，為 256。這會將許多實體端點結合在一起，增加不可用的風險。這就是為什麼在 3.x + 中新增了一個新的確定性令牌配置器，它會智慧地挑選令牌，使環得到最佳平衡，同時需要每個實體節點的令牌數更少。

Cassandra 支援可插入的複製策略，它會決定哪些實體節點會作為特定令牌範圍的複本。資料的每個鍵空間都有自己的複製策略。所有生產部署都應使用NetworkTopologyStrategy，而SimpleStrategy 複製策略僅適用於測試叢集，其中您還不知道叢集的資料中心配置。

Cassandra 使用變動時間戳版本控管來保證資料的最終一致性。特別是，進入系統的所有變動都會附帶一個時間戳，這個時間戳可以由客戶端時鐘提供，或者在沒有客戶端提供時間戳的情況下，由協調節點的時鐘提供。更新會根據最後寫入獲勝的衝突解決規則進行解決。Cassandra 的正確性確實仰賴這些時鐘，因此請確認有執行適當的時間同步程序，例如 NTP。

Cassandra 會對 CQL 分割中每個列的每個欄位套用不同的變動時間戳。列保證會透過主鍵保持唯一性，而列中的每個欄位會根據最後寫入獲勝的衝突解決規則解決同時變動。這表示對分割中不同主鍵的更新實際上可以在沒有衝突的情況下解決！此外，CQL 集合類型（例如映射和集合）使用相同的無衝突機制，表示對映射和集合的同時更新也保證會解決。

Cassandra 支援透過一致性層級在每個操作中權衡一致性和可用性。Cassandra 的一致性層級是 Dynamo 的 R + W > N 一致性機制的版本，其中操作員可以設定參與讀取 (R) 和寫入 (W) 的節點數量大於複製因子 (N)。在 Cassandra 中，您可以從常見一致性層級的選單中選擇，讓操作員可以在不知道複製因子的情況下選擇 R 和 W 行為。通常，當讀取一致性層級包含足夠的節點以保證與寫入一致性層級的交集時，寫入會對後續讀取可見。

以下一致性層級可用

寫入操作總是傳送到所有複本，無論一致性層級為何。一致性層級僅控制協調器在回應客戶端之前等待多少回應。

對於讀取操作，協調器通常只向足夠的複本發出讀取命令以滿足一致性層級。唯一的例外是，如果原始複本未在指定的時間視窗內回應，推測重試可能會向額外複本發出重複讀取請求。

八卦是 Cassandra 如何傳播基本叢集引導資訊，例如端點成員資格和節點間網路協定版本。在 Cassandra 的八卦系統中，節點不僅交換有關它們自己的狀態資訊，還交換有關它們所知的其他節點的資訊。此資訊使用 (generation, version) 元組的向量時脈加上版本，其中世代是單調時間戳，而版本是大約每秒遞增一次的邏輯時脈。這些邏輯時脈允許 Cassandra 八卦僅透過檢查八卦訊息所呈現的邏輯時脈來忽略舊版本的叢集狀態。

Cassandra 叢集中的每個節點都獨立且定期執行八卦任務。每秒，叢集中的每個節點

當操作員第一次啟動 Cassandra 群集時，他們會指定特定節點為種子節點。任何節點都可以是種子節點，而種子節點與非種子節點之間唯一的差異在於種子節點可以在不看到任何其他種子節點的情況下啟動到環中。此外，一旦群集啟動，種子節點就會成為八卦傳播的熱點，這是因為上述步驟 4。

由於非種子節點必須能夠連線到至少一個種子節點才能啟動到群集中，因此通常會包含多個種子節點，通常每個機架或資料中心一個。種子節點通常使用現有的現成服務發現機制來選擇。

目前，八卦傳播也會傳播令牌元資料和架構版本資訊。此資訊形成排程資料移動和架構擷取的控制平面。例如，如果節點在八卦傳播狀態中看到架構版本不符，它會排程與其他節點的架構同步工作。由於令牌資訊會透過八卦傳播，因此它也是用於教導節點哪些端點擁有哪些資料的控制平面。

八卦傳播形成環節成員資格的基礎，但故障偵測器最終會決定節點是UP還是DOWN。Cassandra 中的每個節點都會執行Phi Accrual 故障偵測器的變體，其中每個節點都會持續獨立決定其對等節點是否可用。此決定主要是根據接收到的心跳狀態。例如，如果節點在一段時間內沒有看到來自節點的遞增心跳，故障偵測器會「判決」該節點，此時 Cassandra 會停止將讀取路由到該節點（寫入通常會寫入提示）。如果/當節點再次開始心跳時，Cassandra 會嘗試連線並建立連線，如果它可以開啟通訊管道，它會將該節點標記為可用。

Cassandra 絕不會在未經操作員明確指示的情況下，透過停用操作或使用 replace_address_first_boot 選項引導新節點，將節點從八卦狀態中移除。此選擇是故意的，目的是讓 Cassandra 節點在暫時失敗時，不會造成資料不必要的重新平衡。這也有助於防止同時範圍移動，也就是多個令牌範圍的複本同時移動，這可能會違反單調一致性，甚至造成資料遺失。

Cassandra 和 Dynamo 一樣，選擇不提供 SQL 關聯式資料庫管理系統 (RDBMS) 中常見的跨分區交易。這讓程式設計師有更簡單的讀寫 API，也讓 Cassandra 能更輕鬆地橫向擴充，因為跨越多個節點的多分區交易出了名的難以實作，而且通常會非常潛在。

相反地，Cassandra 選擇為單一分區操作提供快速、一致、在任何規模下的延遲，讓使用者能根據主鍵篩選器擷取整個分區或僅擷取分區的子集。此外，Cassandra 也支援透過輕量級交易 CQL API 比較和交換單一分區的功能。

Cassandra 稍微偏離 Dynamo，選擇比「簡單鍵值」儲存更精密的儲存介面，但比 SQL 關聯資料模型簡單許多。Cassandra 呈現廣欄儲存介面，其中資料分區包含多個列，每個列都包含一組彈性的個別型態欄。每個列都由分區鍵和一個或多個叢集鍵唯一識別，每個列都可以有任意數量的欄。

這讓使用者能彈性地將新欄新增至現有資料集，以符合新需求。架構變更僅涉及變更元資料，並與實際工作負載完全同時執行。因此，使用者可以安全地將欄新增至現有的 Cassandra 資料庫，同時確信查詢效能不會下降。