4 个版本

0.1.3	2019 年 10 月 26 日
0.1.2	2019 年 10 月 25 日
0.1.1	2019 年 10 月 24 日
0.1.0	2019 年 10 月 24 日

#4 in #vector-clock

MIT 许可证

18KB
392 行代码

逻辑时钟

clocks 实现了现代逻辑时钟的一些功能（向量时钟和点版本向量）。

逻辑时钟是一种在分布式系统中捕获时间顺序和因果关系（原因和结果，事件 A 导致事件 B，也称为 发生之前 关系）的机制。

给定分布式系统多个节点中的任何两个事件，逻辑时钟有助于回答诸如“事件 A 是否 发生之前 B”或“事件 B 是否与事件 A 并发”等问题。

点版本向量的实现基于论文 Scalable and Accurate Causality Tracking for Eventually Consistent Stores

向量时钟与版本向量对比

尽管它们具有相同的数据结构表示，但它们解决不同的问题。

向量时钟用于分布式系统中任意两个事件之间的部分顺序，而版本向量仅用于部分顺序更改数据的事件（例如，您想保留多个同时更新的相同键的版本）。

有关差异的更多详细信息，请参阅这篇文章这里

用法（一个简单的键值存储，模拟多个客户端）

use logical_clock::{VersionVector, Dot};
use std::collections::HashMap;

type Key = String;

#[derive(Clone, Debug)]
struct Value{
    val:i64,
    dot:Dot
}

struct KVStore {
    store:HashMap<Key, Vec<Value>>,
    vv:VersionVector,
	
}

impl KVStore {
    fn new() -> KVStore {
	KVStore{
	    store: HashMap::new(),
	    vv: VersionVector::new(),
	}
    }

    fn get(&self, key: &str) -> (Option<Vec<Value>>, VersionVector) {
	match self.store.get(key) {
	    None => (None, self.vv.clone()),
	    Some(v) => (Some(v.clone()), self.vv.clone())
	}
    }

    fn set(mut self, client_id:&str, context: &VersionVector, key: &str, val: i64) -> Self{
	// if incoming request context descends from local clock, just overwrite.
	if context.descends(&self.vv) {
	    self.vv = self.vv.inc(client_id);
	    let dot = self.vv.get_dot(client_id);
	    let new_obj = Value{val: val, dot: dot};
	    
	    // overwrite all the siblings
	    self.store.insert(key.to_string(), vec![new_obj]);
	    return self
	}

	let mut frontier = self.vv.merge(&context);
	frontier = frontier.inc(client_id);
	let dot = frontier.get_dot(client_id);
	let new_obj = Value{val: val, dot: dot};
	self.vv = frontier;
	return self.merge_siblings(key, new_obj)
    }

    fn merge_siblings(mut self, key: &str, new_val: Value) -> Self{
	// replace values that dominated by given value's dot
	let (old, _) = self.get(key);

	match old {
	    None => {
		self.store.insert(key.to_string(), vec![new_val]);
		return self
	    },
	    Some(values) => {
		let mut updated = Vec::new();
		for v in values {
		    if new_val.dot.descends(&v.dot) {
			continue;
		    }
		    updated.push(v);
		}
		updated.push(new_val);
		self.store.insert(key.to_string(), updated);
		return self
	    }
	}
    }
}

fn main() {
    let mut kv = KVStore::new();

    // always get before put - Semantics followed in any High Available Key value store

    // Client A and Client B
    let (_, ctx_a) = kv.get("x");
    let (_, ctx_b) = kv.get("x");

    
    kv = kv.set("A", &ctx_a, "x", 10); // A try to write x=10 with empty context
    kv = kv.set("B", &ctx_b, "x", 15); // B try to write x=12 with same empty context

    // both are concurrent from the client views, so both values should be kept
    assert_eq!(2, kv.store["x"].len());

    // Client C comes in.
    let (_, ctx_c) = kv.get("x");
    // now client C knows all the causal contex, so it replaces the key with all causal past.
    kv = kv.set("C", &ctx_c, "x", 20);
    assert_eq!(1, kv.store["x"].len());
    
    // now B set with old empty context.
    kv = kv.set("B", &ctx_b, "x", 30); // I know contex is empty just set it as 30.

    // From client views latest B write is concurrent to C latest write. so both should be kept.
    assert_eq!(2, kv.store["x"].len());
    
    for (k, v) in kv.store {
	println!("key: {}, values: {:?}", k, v)
	    // val: {}, dot: {:?}", k, v, v.dot);
    }
    println!("vv: {:?}", kv.vv);

}

实时逻辑时钟

Go 竞态检测器使用向量时钟来检测 go 线程之间的数据竞态。基本思想是每个 go 线程都有自己的向量时钟，当多个 go 线程访问共享内存时，它们的向量时钟被比较以确定它们是否并发！https://www.slideshare.net/InfoQ/looking-inside-a-race-detector
Riak 键值存储使用点版本向量来跟踪多个副本中同一键的并发版本。https://riak.com/posts/technical/vector-clocks-revisited-part-2-dotted-version-vectors/index.html?p=9929.html

logical_clock