index_test.go

Documentation: go.etcd.io/etcd/server/v3/mvcc

     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 mvcc
    16  
    17  import (
    18  	"reflect"
    19  	"testing"
    20  
    21  	"github.com/google/btree"
    22  	"go.uber.org/zap"
    23  )
    24  
    25  func TestIndexGet(t *testing.T) {
    26  	ti := newTreeIndex(zap.NewExample())
    27  	ti.Put([]byte("foo"), revision{main: 2})
    28  	ti.Put([]byte("foo"), revision{main: 4})
    29  	ti.Tombstone([]byte("foo"), revision{main: 6})
    30  
    31  	tests := []struct {
    32  		rev int64
    33  
    34  		wrev     revision
    35  		wcreated revision
    36  		wver     int64
    37  		werr     error
    38  	}{
    39  		{0, revision{}, revision{}, 0, ErrRevisionNotFound},
    40  		{1, revision{}, revision{}, 0, ErrRevisionNotFound},
    41  		{2, revision{main: 2}, revision{main: 2}, 1, nil},
    42  		{3, revision{main: 2}, revision{main: 2}, 1, nil},
    43  		{4, revision{main: 4}, revision{main: 2}, 2, nil},
    44  		{5, revision{main: 4}, revision{main: 2}, 2, nil},
    45  		{6, revision{}, revision{}, 0, ErrRevisionNotFound},
    46  	}
    47  	for i, tt := range tests {
    48  		rev, created, ver, err := ti.Get([]byte("foo"), tt.rev)
    49  		if err != tt.werr {
    50  			t.Errorf("#%d: err = %v, want %v", i, err, tt.werr)
    51  		}
    52  		if rev != tt.wrev {
    53  			t.Errorf("#%d: rev = %+v, want %+v", i, rev, tt.wrev)
    54  		}
    55  		if created != tt.wcreated {
    56  			t.Errorf("#%d: created = %+v, want %+v", i, created, tt.wcreated)
    57  		}
    58  		if ver != tt.wver {
    59  			t.Errorf("#%d: ver = %d, want %d", i, ver, tt.wver)
    60  		}
    61  	}
    62  }
    63  
    64  func TestIndexRange(t *testing.T) {
    65  	allKeys := [][]byte{[]byte("foo"), []byte("foo1"), []byte("foo2")}
    66  	allRevs := []revision{{main: 1}, {main: 2}, {main: 3}}
    67  
    68  	ti := newTreeIndex(zap.NewExample())
    69  	for i := range allKeys {
    70  		ti.Put(allKeys[i], allRevs[i])
    71  	}
    72  
    73  	atRev := int64(3)
    74  	tests := []struct {
    75  		key, end []byte
    76  		wkeys    [][]byte
    77  		wrevs    []revision
    78  	}{
    79  		// single key that not found
    80  		{
    81  			[]byte("bar"), nil, nil, nil,
    82  		},
    83  		// single key that found
    84  		{
    85  			[]byte("foo"), nil, allKeys[:1], allRevs[:1],
    86  		},
    87  		// range keys, return first member
    88  		{
    89  			[]byte("foo"), []byte("foo1"), allKeys[:1], allRevs[:1],
    90  		},
    91  		// range keys, return first two members
    92  		{
    93  			[]byte("foo"), []byte("foo2"), allKeys[:2], allRevs[:2],
    94  		},
    95  		// range keys, return all members
    96  		{
    97  			[]byte("foo"), []byte("fop"), allKeys, allRevs,
    98  		},
    99  		// range keys, return last two members
   100  		{
   101  			[]byte("foo1"), []byte("fop"), allKeys[1:], allRevs[1:],
   102  		},
   103  		// range keys, return last member
   104  		{
   105  			[]byte("foo2"), []byte("fop"), allKeys[2:], allRevs[2:],
   106  		},
   107  		// range keys, return nothing
   108  		{
   109  			[]byte("foo3"), []byte("fop"), nil, nil,
   110  		},
   111  	}
   112  	for i, tt := range tests {
   113  		keys, revs := ti.Range(tt.key, tt.end, atRev)
   114  		if !reflect.DeepEqual(keys, tt.wkeys) {
   115  			t.Errorf("#%d: keys = %+v, want %+v", i, keys, tt.wkeys)
   116  		}
   117  		if !reflect.DeepEqual(revs, tt.wrevs) {
   118  			t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs)
   119  		}
   120  	}
   121  }
   122  
   123  func TestIndexTombstone(t *testing.T) {
   124  	ti := newTreeIndex(zap.NewExample())
   125  	ti.Put([]byte("foo"), revision{main: 1})
   126  
   127  	err := ti.Tombstone([]byte("foo"), revision{main: 2})
   128  	if err != nil {
   129  		t.Errorf("tombstone error = %v, want nil", err)
   130  	}
   131  
   132  	_, _, _, err = ti.Get([]byte("foo"), 2)
   133  	if err != ErrRevisionNotFound {
   134  		t.Errorf("get error = %v, want ErrRevisionNotFound", err)
   135  	}
   136  	err = ti.Tombstone([]byte("foo"), revision{main: 3})
   137  	if err != ErrRevisionNotFound {
   138  		t.Errorf("tombstone error = %v, want %v", err, ErrRevisionNotFound)
   139  	}
   140  }
   141  
   142  func TestIndexRangeSince(t *testing.T) {
   143  	allKeys := [][]byte{[]byte("foo"), []byte("foo1"), []byte("foo2"), []byte("foo2"), []byte("foo1"), []byte("foo")}
   144  	allRevs := []revision{{main: 1}, {main: 2}, {main: 3}, {main: 4}, {main: 5}, {main: 6}}
   145  
   146  	ti := newTreeIndex(zap.NewExample())
   147  	for i := range allKeys {
   148  		ti.Put(allKeys[i], allRevs[i])
   149  	}
   150  
   151  	atRev := int64(1)
   152  	tests := []struct {
   153  		key, end []byte
   154  		wrevs    []revision
   155  	}{
   156  		// single key that not found
   157  		{
   158  			[]byte("bar"), nil, nil,
   159  		},
   160  		// single key that found
   161  		{
   162  			[]byte("foo"), nil, []revision{{main: 1}, {main: 6}},
   163  		},
   164  		// range keys, return first member
   165  		{
   166  			[]byte("foo"), []byte("foo1"), []revision{{main: 1}, {main: 6}},
   167  		},
   168  		// range keys, return first two members
   169  		{
   170  			[]byte("foo"), []byte("foo2"), []revision{{main: 1}, {main: 2}, {main: 5}, {main: 6}},
   171  		},
   172  		// range keys, return all members
   173  		{
   174  			[]byte("foo"), []byte("fop"), allRevs,
   175  		},
   176  		// range keys, return last two members
   177  		{
   178  			[]byte("foo1"), []byte("fop"), []revision{{main: 2}, {main: 3}, {main: 4}, {main: 5}},
   179  		},
   180  		// range keys, return last member
   181  		{
   182  			[]byte("foo2"), []byte("fop"), []revision{{main: 3}, {main: 4}},
   183  		},
   184  		// range keys, return nothing
   185  		{
   186  			[]byte("foo3"), []byte("fop"), nil,
   187  		},
   188  	}
   189  	for i, tt := range tests {
   190  		revs := ti.RangeSince(tt.key, tt.end, atRev)
   191  		if !reflect.DeepEqual(revs, tt.wrevs) {
   192  			t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs)
   193  		}
   194  	}
   195  }
   196  
   197  func TestIndexCompactAndKeep(t *testing.T) {
   198  	maxRev := int64(20)
   199  	tests := []struct {
   200  		key     []byte
   201  		remove  bool
   202  		rev     revision
   203  		created revision
   204  		ver     int64
   205  	}{
   206  		{[]byte("foo"), false, revision{main: 1}, revision{main: 1}, 1},
   207  		{[]byte("foo1"), false, revision{main: 2}, revision{main: 2}, 1},
   208  		{[]byte("foo2"), false, revision{main: 3}, revision{main: 3}, 1},
   209  		{[]byte("foo2"), false, revision{main: 4}, revision{main: 3}, 2},
   210  		{[]byte("foo"), false, revision{main: 5}, revision{main: 1}, 2},
   211  		{[]byte("foo1"), false, revision{main: 6}, revision{main: 2}, 2},
   212  		{[]byte("foo1"), true, revision{main: 7}, revision{}, 0},
   213  		{[]byte("foo2"), true, revision{main: 8}, revision{}, 0},
   214  		{[]byte("foo"), true, revision{main: 9}, revision{}, 0},
   215  		{[]byte("foo"), false, revision{10, 0}, revision{10, 0}, 1},
   216  		{[]byte("foo1"), false, revision{10, 1}, revision{10, 1}, 1},
   217  	}
   218  
   219  	// Continuous Compact and Keep
   220  	ti := newTreeIndex(zap.NewExample())
   221  	for _, tt := range tests {
   222  		if tt.remove {
   223  			ti.Tombstone(tt.key, tt.rev)
   224  		} else {
   225  			ti.Put(tt.key, tt.rev)
   226  		}
   227  	}
   228  	for i := int64(1); i < maxRev; i++ {
   229  		am := ti.Compact(i)
   230  		keep := ti.Keep(i)
   231  		if !(reflect.DeepEqual(am, keep)) {
   232  			t.Errorf("#%d: compact keep %v != Keep keep %v", i, am, keep)
   233  		}
   234  		wti := &treeIndex{tree: btree.New(32)}
   235  		for _, tt := range tests {
   236  			if _, ok := am[tt.rev]; ok || tt.rev.GreaterThan(revision{main: i}) {
   237  				if tt.remove {
   238  					wti.Tombstone(tt.key, tt.rev)
   239  				} else {
   240  					restore(wti, tt.key, tt.created, tt.rev, tt.ver)
   241  				}
   242  			}
   243  		}
   244  		if !ti.Equal(wti) {
   245  			t.Errorf("#%d: not equal ti", i)
   246  		}
   247  	}
   248  
   249  	// Once Compact and Keep
   250  	for i := int64(1); i < maxRev; i++ {
   251  		ti := newTreeIndex(zap.NewExample())
   252  		for _, tt := range tests {
   253  			if tt.remove {
   254  				ti.Tombstone(tt.key, tt.rev)
   255  			} else {
   256  				ti.Put(tt.key, tt.rev)
   257  			}
   258  		}
   259  		am := ti.Compact(i)
   260  		keep := ti.Keep(i)
   261  		if !(reflect.DeepEqual(am, keep)) {
   262  			t.Errorf("#%d: compact keep %v != Keep keep %v", i, am, keep)
   263  		}
   264  		wti := &treeIndex{tree: btree.New(32)}
   265  		for _, tt := range tests {
   266  			if _, ok := am[tt.rev]; ok || tt.rev.GreaterThan(revision{main: i}) {
   267  				if tt.remove {
   268  					wti.Tombstone(tt.key, tt.rev)
   269  				} else {
   270  					restore(wti, tt.key, tt.created, tt.rev, tt.ver)
   271  				}
   272  			}
   273  		}
   274  		if !ti.Equal(wti) {
   275  			t.Errorf("#%d: not equal ti", i)
   276  		}
   277  	}
   278  }
   279  
   280  func restore(ti *treeIndex, key []byte, created, modified revision, ver int64) {
   281  	keyi := &keyIndex{key: key}
   282  
   283  	ti.Lock()
   284  	defer ti.Unlock()
   285  	item := ti.tree.Get(keyi)
   286  	if item == nil {
   287  		keyi.restore(ti.lg, created, modified, ver)
   288  		ti.tree.ReplaceOrInsert(keyi)
   289  		return
   290  	}
   291  	okeyi := item.(*keyIndex)
   292  	okeyi.put(ti.lg, modified.main, modified.sub)
   293  }
   294
View as plain text