設計 Key-Value Store

# 每個 Key 被分配到 Hash 環上順時針方向的第一個節點
# 資料複製到順時針方向的 N 個不同節點
 
class DistributedKVStore:
    def __init__(self, nodes: list[str], replicas: int = 3):
        self.consistent_hash = ConsistentHash(nodes)
        self.replicas = replicas
 
    def get_responsible_nodes(self, key: str) -> list[str]:
        """取得負責儲存此 Key 的 N 個節點"""
        primary = self.consistent_hash.get_node(key)
        nodes = [primary]
        # 順時針找下 N-1 個不同的節點
        current = primary
        while len(nodes) < self.replicas:
            current = self.consistent_hash.get_next_node(current)
            if current not in nodes:
                nodes.append(current)
        return nodes

public class QuorumKVStore
{
    private readonly int N = 3; // 副本數
    private readonly int W = 2; // 寫入成功需確認數
    private readonly int R = 2; // 讀取需查詢數
 
    // W + R > N → 保證 Strong Consistency
    // W = 1, R = 1 → Eventual Consistency（最快）
 
    public async Task<bool> Put(string key, byte[] value)
    {
        var nodes = GetResponsibleNodes(key); // 取得 N 個節點
        var tasks = nodes.Select(n => n.WriteAsync(key, value));
        var results = await Task.WhenAll(tasks);
        var successCount = results.Count(r => r);
        return successCount >= W; // 至少 W 個寫入成功
    }
 
    public async Task<byte[]?> Get(string key)
    {
        var nodes = GetResponsibleNodes(key);
        var tasks = nodes.Select(n => n.ReadAsync(key));
        var results = await Task.WhenAll(tasks);
        // 至少 R 個讀取成功，取最新版本
        var valid = results.Where(r => r != null).ToList();
        if (valid.Count < R) throw new Exception("Not enough replicas");
        return valid.OrderByDescending(r => r!.Timestamp).First()?.Data;
    }
}

type VectorClock = Record<string, number>; // { "nodeA": 3, "nodeB": 1 }
 
function merge(vc1: VectorClock, vc2: VectorClock): VectorClock {
  const result = { ...vc1 };
  for (const [node, count] of Object.entries(vc2)) {
    result[node] = Math.max(result[node] ?? 0, count);
  }
  return result;
}
 
function isConflict(vc1: VectorClock, vc2: VectorClock): boolean {
  // 如果互相都有對方沒有的更新 → 衝突（需要客戶端解決）
  let vc1Ahead = false, vc2Ahead = false;
  const allNodes = new Set([...Object.keys(vc1), ...Object.keys(vc2)]);
  for (const node of allNodes) {
    if ((vc1[node] ?? 0) > (vc2[node] ?? 0)) vc1Ahead = true;
    if ((vc2[node] ?? 0) > (vc1[node] ?? 0)) vc2Ahead = true;
  }
  return vc1Ahead && vc2Ahead; // 同時為 true = 衝突
}