node.go

Documentation: go.etcd.io/etcd/server/v3/etcdserver/api/v2store

     1  // Copyright 2015 The etcd Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package v2store
    16  
    17  import (
    18  	"path"
    19  	"sort"
    20  	"time"
    21  
    22  	"go.etcd.io/etcd/server/v3/etcdserver/api/v2error"
    23  
    24  	"github.com/jonboulle/clockwork"
    25  )
    26  
    27  // explanations of Compare function result
    28  const (
    29  	CompareMatch = iota
    30  	CompareIndexNotMatch
    31  	CompareValueNotMatch
    32  	CompareNotMatch
    33  )
    34  
    35  var Permanent time.Time
    36  
    37  // node is the basic element in the store system.
    38  // A key-value pair will have a string value
    39  // A directory will have a children map
    40  type node struct {
    41  	Path string
    42  
    43  	CreatedIndex  uint64
    44  	ModifiedIndex uint64
    45  
    46  	Parent *node `json:"-"` // should not encode this field! avoid circular dependency.
    47  
    48  	ExpireTime time.Time
    49  	Value      string           // for key-value pair
    50  	Children   map[string]*node // for directory
    51  
    52  	// A reference to the store this node is attached to.
    53  	store *store
    54  }
    55  
    56  // newKV creates a Key-Value pair
    57  func newKV(store *store, nodePath string, value string, createdIndex uint64, parent *node, expireTime time.Time) *node {
    58  	return &node{
    59  		Path:          nodePath,
    60  		CreatedIndex:  createdIndex,
    61  		ModifiedIndex: createdIndex,
    62  		Parent:        parent,
    63  		store:         store,
    64  		ExpireTime:    expireTime,
    65  		Value:         value,
    66  	}
    67  }
    68  
    69  // newDir creates a directory
    70  func newDir(store *store, nodePath string, createdIndex uint64, parent *node, expireTime time.Time) *node {
    71  	return &node{
    72  		Path:          nodePath,
    73  		CreatedIndex:  createdIndex,
    74  		ModifiedIndex: createdIndex,
    75  		Parent:        parent,
    76  		ExpireTime:    expireTime,
    77  		Children:      make(map[string]*node),
    78  		store:         store,
    79  	}
    80  }
    81  
    82  // IsHidden function checks if the node is a hidden node. A hidden node
    83  // will begin with '_'
    84  // A hidden node will not be shown via get command under a directory
    85  // For example if we have /foo/_hidden and /foo/notHidden, get "/foo"
    86  // will only return /foo/notHidden
    87  func (n *node) IsHidden() bool {
    88  	_, name := path.Split(n.Path)
    89  
    90  	return name[0] == '_'
    91  }
    92  
    93  // IsPermanent function checks if the node is a permanent one.
    94  func (n *node) IsPermanent() bool {
    95  	// we use a uninitialized time.Time to indicate the node is a
    96  	// permanent one.
    97  	// the uninitialized time.Time should equal zero.
    98  	return n.ExpireTime.IsZero()
    99  }
   100  
   101  // IsDir function checks whether the node is a directory.
   102  // If the node is a directory, the function will return true.
   103  // Otherwise the function will return false.
   104  func (n *node) IsDir() bool {
   105  	return n.Children != nil
   106  }
   107  
   108  // Read function gets the value of the node.
   109  // If the receiver node is not a key-value pair, a "Not A File" error will be returned.
   110  func (n *node) Read() (string, *v2error.Error) {
   111  	if n.IsDir() {
   112  		return "", v2error.NewError(v2error.EcodeNotFile, "", n.store.CurrentIndex)
   113  	}
   114  
   115  	return n.Value, nil
   116  }
   117  
   118  // Write function set the value of the node to the given value.
   119  // If the receiver node is a directory, a "Not A File" error will be returned.
   120  func (n *node) Write(value string, index uint64) *v2error.Error {
   121  	if n.IsDir() {
   122  		return v2error.NewError(v2error.EcodeNotFile, "", n.store.CurrentIndex)
   123  	}
   124  
   125  	n.Value = value
   126  	n.ModifiedIndex = index
   127  
   128  	return nil
   129  }
   130  
   131  func (n *node) expirationAndTTL(clock clockwork.Clock) (*time.Time, int64) {
   132  	if !n.IsPermanent() {
   133  		/* compute ttl as:
   134  		   ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
   135  		   which ranges from 1..n
   136  		   rather than as:
   137  		   ( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
   138  		   which ranges 1..n+1
   139  		*/
   140  		ttlN := n.ExpireTime.Sub(clock.Now())
   141  		ttl := ttlN / time.Second
   142  		if (ttlN % time.Second) > 0 {
   143  			ttl++
   144  		}
   145  		t := n.ExpireTime.UTC()
   146  		return &t, int64(ttl)
   147  	}
   148  	return nil, 0
   149  }
   150  
   151  // List function return a slice of nodes under the receiver node.
   152  // If the receiver node is not a directory, a "Not A Directory" error will be returned.
   153  func (n *node) List() ([]*node, *v2error.Error) {
   154  	if !n.IsDir() {
   155  		return nil, v2error.NewError(v2error.EcodeNotDir, "", n.store.CurrentIndex)
   156  	}
   157  
   158  	nodes := make([]*node, len(n.Children))
   159  
   160  	i := 0
   161  	for _, node := range n.Children {
   162  		nodes[i] = node
   163  		i++
   164  	}
   165  
   166  	return nodes, nil
   167  }
   168  
   169  // GetChild function returns the child node under the directory node.
   170  // On success, it returns the file node
   171  func (n *node) GetChild(name string) (*node, *v2error.Error) {
   172  	if !n.IsDir() {
   173  		return nil, v2error.NewError(v2error.EcodeNotDir, n.Path, n.store.CurrentIndex)
   174  	}
   175  
   176  	child, ok := n.Children[name]
   177  
   178  	if ok {
   179  		return child, nil
   180  	}
   181  
   182  	return nil, nil
   183  }
   184  
   185  // Add function adds a node to the receiver node.
   186  // If the receiver is not a directory, a "Not A Directory" error will be returned.
   187  // If there is an existing node with the same name under the directory, a "Already Exist"
   188  // error will be returned
   189  func (n *node) Add(child *node) *v2error.Error {
   190  	if !n.IsDir() {
   191  		return v2error.NewError(v2error.EcodeNotDir, "", n.store.CurrentIndex)
   192  	}
   193  
   194  	_, name := path.Split(child.Path)
   195  
   196  	if _, ok := n.Children[name]; ok {
   197  		return v2error.NewError(v2error.EcodeNodeExist, "", n.store.CurrentIndex)
   198  	}
   199  
   200  	n.Children[name] = child
   201  
   202  	return nil
   203  }
   204  
   205  // Remove function remove the node.
   206  func (n *node) Remove(dir, recursive bool, callback func(path string)) *v2error.Error {
   207  	if !n.IsDir() { // key-value pair
   208  		_, name := path.Split(n.Path)
   209  
   210  		// find its parent and remove the node from the map
   211  		if n.Parent != nil && n.Parent.Children[name] == n {
   212  			delete(n.Parent.Children, name)
   213  		}
   214  
   215  		if callback != nil {
   216  			callback(n.Path)
   217  		}
   218  
   219  		if !n.IsPermanent() {
   220  			n.store.ttlKeyHeap.remove(n)
   221  		}
   222  
   223  		return nil
   224  	}
   225  
   226  	if !dir {
   227  		// cannot delete a directory without dir set to true
   228  		return v2error.NewError(v2error.EcodeNotFile, n.Path, n.store.CurrentIndex)
   229  	}
   230  
   231  	if len(n.Children) != 0 && !recursive {
   232  		// cannot delete a directory if it is not empty and the operation
   233  		// is not recursive
   234  		return v2error.NewError(v2error.EcodeDirNotEmpty, n.Path, n.store.CurrentIndex)
   235  	}
   236  
   237  	for _, child := range n.Children { // delete all children
   238  		child.Remove(true, true, callback)
   239  	}
   240  
   241  	// delete self
   242  	_, name := path.Split(n.Path)
   243  	if n.Parent != nil && n.Parent.Children[name] == n {
   244  		delete(n.Parent.Children, name)
   245  
   246  		if callback != nil {
   247  			callback(n.Path)
   248  		}
   249  
   250  		if !n.IsPermanent() {
   251  			n.store.ttlKeyHeap.remove(n)
   252  		}
   253  	}
   254  
   255  	return nil
   256  }
   257  
   258  func (n *node) Repr(recursive, sorted bool, clock clockwork.Clock) *NodeExtern {
   259  	if n.IsDir() {
   260  		node := &NodeExtern{
   261  			Key:           n.Path,
   262  			Dir:           true,
   263  			ModifiedIndex: n.ModifiedIndex,
   264  			CreatedIndex:  n.CreatedIndex,
   265  		}
   266  		node.Expiration, node.TTL = n.expirationAndTTL(clock)
   267  
   268  		if !recursive {
   269  			return node
   270  		}
   271  
   272  		children, _ := n.List()
   273  		node.Nodes = make(NodeExterns, len(children))
   274  
   275  		// we do not use the index in the children slice directly
   276  		// we need to skip the hidden one
   277  		i := 0
   278  
   279  		for _, child := range children {
   280  
   281  			if child.IsHidden() { // get will not list hidden node
   282  				continue
   283  			}
   284  
   285  			node.Nodes[i] = child.Repr(recursive, sorted, clock)
   286  
   287  			i++
   288  		}
   289  
   290  		// eliminate hidden nodes
   291  		node.Nodes = node.Nodes[:i]
   292  		if sorted {
   293  			sort.Sort(node.Nodes)
   294  		}
   295  
   296  		return node
   297  	}
   298  
   299  	// since n.Value could be changed later, so we need to copy the value out
   300  	value := n.Value
   301  	node := &NodeExtern{
   302  		Key:           n.Path,
   303  		Value:         &value,
   304  		ModifiedIndex: n.ModifiedIndex,
   305  		CreatedIndex:  n.CreatedIndex,
   306  	}
   307  	node.Expiration, node.TTL = n.expirationAndTTL(clock)
   308  	return node
   309  }
   310  
   311  func (n *node) UpdateTTL(expireTime time.Time) {
   312  	if !n.IsPermanent() {
   313  		if expireTime.IsZero() {
   314  			// from ttl to permanent
   315  			n.ExpireTime = expireTime
   316  			// remove from ttl heap
   317  			n.store.ttlKeyHeap.remove(n)
   318  			return
   319  		}
   320  
   321  		// update ttl
   322  		n.ExpireTime = expireTime
   323  		// update ttl heap
   324  		n.store.ttlKeyHeap.update(n)
   325  		return
   326  	}
   327  
   328  	if expireTime.IsZero() {
   329  		return
   330  	}
   331  
   332  	// from permanent to ttl
   333  	n.ExpireTime = expireTime
   334  	// push into ttl heap
   335  	n.store.ttlKeyHeap.push(n)
   336  }
   337  
   338  // Compare function compares node index and value with provided ones.
   339  // second result value explains result and equals to one of Compare.. constants
   340  func (n *node) Compare(prevValue string, prevIndex uint64) (ok bool, which int) {
   341  	indexMatch := prevIndex == 0 || n.ModifiedIndex == prevIndex
   342  	valueMatch := prevValue == "" || n.Value == prevValue
   343  	ok = valueMatch && indexMatch
   344  	switch {
   345  	case valueMatch && indexMatch:
   346  		which = CompareMatch
   347  	case indexMatch && !valueMatch:
   348  		which = CompareValueNotMatch
   349  	case valueMatch && !indexMatch:
   350  		which = CompareIndexNotMatch
   351  	default:
   352  		which = CompareNotMatch
   353  	}
   354  	return ok, which
   355  }
   356  
   357  // Clone function clone the node recursively and return the new node.
   358  // If the node is a directory, it will clone all the content under this directory.
   359  // If the node is a key-value pair, it will clone the pair.
   360  func (n *node) Clone() *node {
   361  	if !n.IsDir() {
   362  		newkv := newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ExpireTime)
   363  		newkv.ModifiedIndex = n.ModifiedIndex
   364  		return newkv
   365  	}
   366  
   367  	clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ExpireTime)
   368  	clone.ModifiedIndex = n.ModifiedIndex
   369  
   370  	for key, child := range n.Children {
   371  		clone.Children[key] = child.Clone()
   372  	}
   373  
   374  	return clone
   375  }
   376  
   377  // recoverAndclean function help to do recovery.
   378  // Two things need to be done: 1. recovery structure; 2. delete expired nodes
   379  //
   380  // If the node is a directory, it will help recover children's parent pointer and recursively
   381  // call this function on its children.
   382  // We check the expire last since we need to recover the whole structure first and add all the
   383  // notifications into the event history.
   384  func (n *node) recoverAndclean() {
   385  	if n.IsDir() {
   386  		for _, child := range n.Children {
   387  			child.Parent = n
   388  			child.store = n.store
   389  			child.recoverAndclean()
   390  		}
   391  	}
   392  
   393  	if !n.ExpireTime.IsZero() {
   394  		n.store.ttlKeyHeap.push(n)
   395  	}
   396  }
   397
View as plain text