1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
use arc_swap::ArcSwapOption;
use std::sync::Arc;
use crate::data::*;
use crate::membership::{Ring, System};
use crate::table::*;
#[derive(Clone)]
pub struct TableFullReplication {
pub write_factor: usize,
pub write_quorum: usize,
neighbors: ArcSwapOption<Neighbors>,
}
#[derive(Clone)]
struct Neighbors {
ring: Arc<Ring>,
neighbors: Vec<UUID>,
}
impl TableFullReplication {
pub fn new(write_factor: usize, write_quorum: usize) -> Self {
TableFullReplication {
write_factor,
write_quorum,
neighbors: ArcSwapOption::from(None),
}
}
fn get_neighbors(&self, system: &System) -> Vec<UUID> {
let neighbors = self.neighbors.load_full();
if let Some(n) = neighbors {
if Arc::ptr_eq(&n.ring, &system.ring.borrow()) {
return n.neighbors.clone();
}
}
// Recalculate neighbors
let ring = system.ring.borrow().clone();
let my_id = system.id.clone();
let mut nodes = vec![];
for (node, _) in ring.config.members.iter() {
let node_ranking = hash(&[node.as_slice(), my_id.as_slice()].concat());
nodes.push((node.clone(), node_ranking));
}
nodes.sort_by(|(_, rank1), (_, rank2)| rank1.cmp(rank2));
let mut neighbors = nodes
.drain(..)
.map(|(node, _)| node)
.filter(|node| *node != my_id)
.take(self.write_factor)
.collect::<Vec<_>>();
neighbors.push(my_id);
self.neighbors.swap(Some(Arc::new(Neighbors {
ring,
neighbors: neighbors.clone(),
})));
neighbors
}
}
impl TableReplication for TableFullReplication {
// Full replication schema: all nodes store everything
// Writes are disseminated in an epidemic manner in the network
// Advantage: do all reads locally, extremely fast
// Inconvenient: only suitable to reasonably small tables
fn read_nodes(&self, _hash: &Hash, system: &System) -> Vec<UUID> {
vec![system.id.clone()]
}
fn read_quorum(&self) -> usize {
1
}
fn write_nodes(&self, _hash: &Hash, system: &System) -> Vec<UUID> {
self.get_neighbors(system)
}
fn write_quorum(&self) -> usize {
self.write_quorum
}
fn max_write_errors(&self) -> usize {
self.write_factor - self.write_quorum
}
fn epidemic_writes(&self) -> bool {
true
}
fn replication_nodes(&self, _hash: &Hash, ring: &Ring) -> Vec<UUID> {
ring.config.members.keys().cloned().collect::<Vec<_>>()
}
fn split_points(&self, _ring: &Ring) -> Vec<Hash> {
let mut ret = vec![];
ret.push([0u8; 32].into());
ret.push([0xFFu8; 32].into());
ret
}
}
|
