forked from etcd-io/etcd
-
Notifications
You must be signed in to change notification settings - Fork 0
/
node.go
365 lines (291 loc) · 8.64 KB
/
node.go
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
package store
import (
"path"
"sort"
"time"
etcdErr "github.com/coreos/etcd/error"
)
var Permanent time.Time
// node is the basic element in the store system.
// A key-value pair will have a string value
// A directory will have a children map
type node struct {
Path string
CreatedIndex uint64
ModifiedIndex uint64
Parent *node `json:"-"` // should not encode this field! avoid circular dependency.
ExpireTime time.Time
ACL string
Value string // for key-value pair
Children map[string]*node // for directory
// A reference to the store this node is attached to.
store *store
}
// newKV creates a Key-Value pair
func newKV(store *store, nodePath string, value string, createdIndex uint64,
parent *node, ACL string, expireTime time.Time) *node {
return &node{
Path: nodePath,
CreatedIndex: createdIndex,
ModifiedIndex: createdIndex,
Parent: parent,
ACL: ACL,
store: store,
ExpireTime: expireTime,
Value: value,
}
}
// newDir creates a directory
func newDir(store *store, nodePath string, createdIndex uint64, parent *node,
ACL string, expireTime time.Time) *node {
return &node{
Path: nodePath,
CreatedIndex: createdIndex,
ModifiedIndex: createdIndex,
Parent: parent,
ACL: ACL,
ExpireTime: expireTime,
Children: make(map[string]*node),
store: store,
}
}
// IsHidden function checks if the node is a hidden node. A hidden node
// will begin with '_'
// A hidden node will not be shown via get command under a directory
// For example if we have /foo/_hidden and /foo/notHidden, get "/foo"
// will only return /foo/notHidden
func (n *node) IsHidden() bool {
_, name := path.Split(n.Path)
return name[0] == '_'
}
// IsPermanent function checks if the node is a permanent one.
func (n *node) IsPermanent() bool {
// we use a uninitialized time.Time to indicate the node is a
// permanent one.
// the uninitialized time.Time should equal zero.
return n.ExpireTime.IsZero()
}
// IsDir function checks whether the node is a directory.
// If the node is a directory, the function will return true.
// Otherwise the function will return false.
func (n *node) IsDir() bool {
return !(n.Children == nil)
}
// Read function gets the value of the node.
// If the receiver node is not a key-value pair, a "Not A File" error will be returned.
func (n *node) Read() (string, *etcdErr.Error) {
if n.IsDir() {
return "", etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.Index())
}
return n.Value, nil
}
// Write function set the value of the node to the given value.
// If the receiver node is a directory, a "Not A File" error will be returned.
func (n *node) Write(value string, index uint64) *etcdErr.Error {
if n.IsDir() {
return etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.Index())
}
n.Value = value
n.ModifiedIndex = index
return nil
}
func (n *node) ExpirationAndTTL() (*time.Time, int64) {
if !n.IsPermanent() {
/* compute ttl as:
ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
which ranges from 1..n
rather than as:
( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
which ranges 1..n+1
*/
ttlN := n.ExpireTime.Sub(time.Now())
ttl := ttlN / time.Second
if (ttlN % time.Second) > 0 {
ttl++
}
return &n.ExpireTime, int64(ttl)
}
return nil, 0
}
// List function return a slice of nodes under the receiver node.
// If the receiver node is not a directory, a "Not A Directory" error will be returned.
func (n *node) List() ([]*node, *etcdErr.Error) {
if !n.IsDir() {
return nil, etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.Index())
}
nodes := make([]*node, len(n.Children))
i := 0
for _, node := range n.Children {
nodes[i] = node
i++
}
return nodes, nil
}
// GetChild function returns the child node under the directory node.
// On success, it returns the file node
func (n *node) GetChild(name string) (*node, *etcdErr.Error) {
if !n.IsDir() {
return nil, etcdErr.NewError(etcdErr.EcodeNotDir, n.Path, n.store.Index())
}
child, ok := n.Children[name]
if ok {
return child, nil
}
return nil, nil
}
// Add function adds a node to the receiver node.
// If the receiver is not a directory, a "Not A Directory" error will be returned.
// If there is a existing node with the same name under the directory, a "Already Exist"
// error will be returned
func (n *node) Add(child *node) *etcdErr.Error {
if !n.IsDir() {
return etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.Index())
}
_, name := path.Split(child.Path)
_, ok := n.Children[name]
if ok {
return etcdErr.NewError(etcdErr.EcodeNodeExist, "", n.store.Index())
}
n.Children[name] = child
return nil
}
// Remove function remove the node.
func (n *node) Remove(dir, recursive bool, callback func(path string)) *etcdErr.Error {
if n.IsDir() {
if !dir {
// cannot delete a directory without recursive set to true
return etcdErr.NewError(etcdErr.EcodeNotFile, n.Path, n.store.Index())
}
if len(n.Children) != 0 && !recursive {
// cannot delete a directory if it is not empty and the operation
// is not recursive
return etcdErr.NewError(etcdErr.EcodeDirNotEmpty, n.Path, n.store.Index())
}
}
if !n.IsDir() { // key-value pair
_, name := path.Split(n.Path)
// find its parent and remove the node from the map
if n.Parent != nil && n.Parent.Children[name] == n {
delete(n.Parent.Children, name)
}
if callback != nil {
callback(n.Path)
}
if !n.IsPermanent() {
n.store.ttlKeyHeap.remove(n)
}
return nil
}
for _, child := range n.Children { // delete all children
child.Remove(true, true, callback)
}
// delete self
_, name := path.Split(n.Path)
if n.Parent != nil && n.Parent.Children[name] == n {
delete(n.Parent.Children, name)
if callback != nil {
callback(n.Path)
}
if !n.IsPermanent() {
n.store.ttlKeyHeap.remove(n)
}
}
return nil
}
func (n *node) Repr(recurisive, sorted bool) *NodeExtern {
if n.IsDir() {
node := &NodeExtern{
Key: n.Path,
Dir: true,
ModifiedIndex: n.ModifiedIndex,
CreatedIndex: n.CreatedIndex,
}
node.Expiration, node.TTL = n.ExpirationAndTTL()
if !recurisive {
return node
}
children, _ := n.List()
node.Nodes = make(NodeExterns, len(children))
// we do not use the index in the children slice directly
// we need to skip the hidden one
i := 0
for _, child := range children {
if child.IsHidden() { // get will not list hidden node
continue
}
node.Nodes[i] = child.Repr(recurisive, sorted)
i++
}
// eliminate hidden nodes
node.Nodes = node.Nodes[:i]
if sorted {
sort.Sort(node.Nodes)
}
return node
}
node := &NodeExtern{
Key: n.Path,
Value: n.Value,
ModifiedIndex: n.ModifiedIndex,
CreatedIndex: n.CreatedIndex,
}
node.Expiration, node.TTL = n.ExpirationAndTTL()
return node
}
func (n *node) UpdateTTL(expireTime time.Time) {
if !n.IsPermanent() {
if expireTime.IsZero() {
// from ttl to permanent
// remove from ttl heap
n.store.ttlKeyHeap.remove(n)
} else {
// update ttl
n.ExpireTime = expireTime
// update ttl heap
n.store.ttlKeyHeap.update(n)
}
} else {
if !expireTime.IsZero() {
// from permanent to ttl
n.ExpireTime = expireTime
// push into ttl heap
n.store.ttlKeyHeap.push(n)
}
}
}
func (n *node) Compare(prevValue string, prevIndex uint64) bool {
compareValue := (prevValue == "" || n.Value == prevValue)
compareIndex := (prevIndex == 0 || n.ModifiedIndex == prevIndex)
return compareValue && compareIndex
}
// Clone function clone the node recursively and return the new node.
// If the node is a directory, it will clone all the content under this directory.
// If the node is a key-value pair, it will clone the pair.
func (n *node) Clone() *node {
if !n.IsDir() {
return newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ACL, n.ExpireTime)
}
clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ACL, n.ExpireTime)
for key, child := range n.Children {
clone.Children[key] = child.Clone()
}
return clone
}
// recoverAndclean function help to do recovery.
// Two things need to be done: 1. recovery structure; 2. delete expired nodes
// If the node is a directory, it will help recover children's parent pointer and recursively
// call this function on its children.
// We check the expire last since we need to recover the whole structure first and add all the
// notifications into the event history.
func (n *node) recoverAndclean() {
if n.IsDir() {
for _, child := range n.Children {
child.Parent = n
child.store = n.store
child.recoverAndclean()
}
}
if !n.ExpireTime.IsZero() {
n.store.ttlKeyHeap.push(n)
}
}