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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//! The object-storage contract every durable backend must satisfy (§5.1).
//!
//! The trait is small on purpose. Only two properties are load-bearing, and
//! both are properties a provider either has or does not:
//!
//! 1. **Real conditional operations.** [`Backend::put_bytes_if_absent`] must be
//! an atomic create and [`Backend::replace_if_match`] an atomic
//! compare-and-swap. Simulating either with a read followed by a write is
//! not a weaker implementation, it is a broken one: the window between the
//! two is exactly where two writers both conclude they are the only writer.
//! 2. **Streaming.** A checkpoint is a full database archive. Requiring it to
//! pass through a `Vec<u8>` puts a ceiling on database size that has nothing
//! to do with the database. So checkpoints move as files and readers; only
//! the head and WAL segments — both bounded by the protocol — move as bytes.
//!
//! A third property is expressed in the return values rather than the methods:
//! every mutating call can answer "ambiguous". A request whose response was lost
//! is not a failure, and reporting it as one would make a caller retry a commit
//! that already happened. The state machine resolves ambiguity by re-reading
//! (§5.8), which is only possible if the backend admits it.
//!
//! Deleting is absent by design: V1 has no destroy and no garbage collection, so
//! nothing in the protocol has the authority to remove an object.
use Read;
use Path;
use Digest;
use Result;
/// The result of a conditional create.
/// The result of a conditional replace.
/// One object read whole, with the CAS token describing that same version.
/// A key/value store scoped to one object's prefix.
///
/// Keys are relative, `/`-separated and validated by
/// [`is_valid_object_key`](super::is_valid_object_key): they arrive from a
/// `head.json` that came out of object storage, so they are untrusted input,
/// and an implementation that resolves them against a directory must refuse a
/// traversal rather than trust the caller.
///
/// `Option` distinguishes an absent key from a failure. Absence is a normal,
/// expected answer at nearly every call site — a cold object, a probe for a
/// head — and a caller that has to unwrap an error to learn something ordinary
/// eventually forgets to.
///
/// An implementation is shared across the heartbeat thread and the caller's, so
/// it has to be `Send + Sync`.