diff options
author | John Lee <64482439+algojohnlee@users.noreply.github.com> | 2020-08-07 10:02:02 -0400 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-08-07 10:02:02 -0400 |
commit | a7718244dc2ffdf0d1ae2c7b553bba315610a77d (patch) | |
tree | cf6914a7fa1fcdb83286c597dc2e869228a83967 | |
parent | 890f535b4af50fd9112446c204ccc504b080fe32 (diff) | |
parent | d60e1c9690642a44068b42916fcaad5f743bdedb (diff) |
Merge pull request #1353 from onetechnical/onetechnical/relstable2.0.9v2.0.9-stable
Onetechnical/relstable2.0.9
-rw-r--r-- | buildnumber.dat | 2 | ||||
-rw-r--r-- | crypto/merkletrie/cache.go | 12 | ||||
-rw-r--r-- | crypto/merkletrie/cache_test.go | 119 | ||||
-rw-r--r-- | crypto/merkletrie/trie_test.go | 1 |
4 files changed, 130 insertions, 4 deletions
diff --git a/buildnumber.dat b/buildnumber.dat index 45a4fb75d..ec635144f 100644 --- a/buildnumber.dat +++ b/buildnumber.dat @@ -1 +1 @@ -8 +9 diff --git a/crypto/merkletrie/cache.go b/crypto/merkletrie/cache.go index 9cba7c19a..db60a21a9 100644 --- a/crypto/merkletrie/cache.go +++ b/crypto/merkletrie/cache.go @@ -72,7 +72,7 @@ type merkleTrieCache struct { // a list of the pages priorities. The item in the front has higher priority and would not get evicted as quickly as the item on the back pagesPrioritizationList *list.List - // the list element of each of the priorities + // the list element of each of the priorities. The pagesPrioritizationMap maps a page id to the page priority list element. pagesPrioritizationMap map[uint64]*list.Element // the page to load before the nextNodeID at init time. If zero, then nothing is being reloaded. deferedPageLoad uint64 @@ -145,8 +145,9 @@ func (mtc *merkleTrieCache) getNode(nid storedNodeIdentifier) (pnode *node, err return } -// prioritizeNode make sure to move the priorities of the pages according to -// the accessed node identifier +// prioritizePage make sure to adjust the priority of the given node id. +// a new page would be placed on front, and an older page would get moved +// to the front. func (mtc *merkleTrieCache) prioritizeNode(nid storedNodeIdentifier) { page := uint64(nid) / uint64(mtc.nodesPerPage) @@ -350,6 +351,9 @@ func (mtc *merkleTrieCache) commit() error { element := mtc.pagesPrioritizationMap[uint64(page)] if element != nil { mtc.pagesPrioritizationList.Remove(element) + delete(mtc.pagesPrioritizationMap, uint64(page)) + mtc.cachedNodeCount -= len(mtc.pageToNIDsPtr[uint64(page)]) + delete(mtc.pageToNIDsPtr, uint64(page)) } } @@ -440,6 +444,7 @@ func (mtc *merkleTrieCache) encodePage(nodeIDs map[storedNodeIdentifier]*node) [ // evict releases the least used pages from cache until the number of elements in cache are less than cachedNodeCountTarget func (mtc *merkleTrieCache) evict() (removedNodes int) { removedNodes = mtc.cachedNodeCount + for mtc.cachedNodeCount > mtc.cachedNodeCountTarget { // get the least used page off the pagesPrioritizationList element := mtc.pagesPrioritizationList.Back() @@ -448,6 +453,7 @@ func (mtc *merkleTrieCache) evict() (removedNodes int) { } mtc.pagesPrioritizationList.Remove(element) pageToRemove := element.Value.(uint64) + delete(mtc.pagesPrioritizationMap, pageToRemove) mtc.cachedNodeCount -= len(mtc.pageToNIDsPtr[pageToRemove]) delete(mtc.pageToNIDsPtr, pageToRemove) } diff --git a/crypto/merkletrie/cache_test.go b/crypto/merkletrie/cache_test.go new file mode 100644 index 000000000..5f84bebb3 --- /dev/null +++ b/crypto/merkletrie/cache_test.go @@ -0,0 +1,119 @@ +// Copyright (C) 2019-2020 Algorand, Inc. +// This file is part of go-algorand +// +// go-algorand is free software: you can redistribute it and/or modify +// it under the terms of the GNU Affero General Public License as +// published by the Free Software Foundation, either version 3 of the +// License, or (at your option) any later version. +// +// go-algorand is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Affero General Public License for more details. +// +// You should have received a copy of the GNU Affero General Public License +// along with go-algorand. If not, see <https://www.gnu.org/licenses/>. + +package merkletrie + +import ( + "testing" + + "github.com/stretchr/testify/require" + + "github.com/algorand/go-algorand/crypto" +) + +func verifyCacheNodeCount(t *testing.T, trie *Trie) { + count := 0 + for _, pageNodes := range trie.cache.pageToNIDsPtr { + count += len(pageNodes) + } + require.Equal(t, count, trie.cache.cachedNodeCount) + + // make sure that the pagesPrioritizationMap aligns with pagesPrioritizationList + require.Equal(t, len(trie.cache.pagesPrioritizationMap), trie.cache.pagesPrioritizationList.Len()) + + for e := trie.cache.pagesPrioritizationList.Back(); e != nil; e = e.Next() { + page := e.Value.(uint64) + _, has := trie.cache.pagesPrioritizationMap[page] + require.True(t, has) + _, has = trie.cache.pageToNIDsPtr[page] + require.True(t, has) + } +} + +func TestCacheEviction1(t *testing.T) { + var memoryCommitter InMemoryCommitter + mt1, _ := MakeTrie(&memoryCommitter, defaultTestEvictSize) + // create 13000 hashes. + leafsCount := 13000 + hashes := make([]crypto.Digest, leafsCount) + for i := 0; i < len(hashes); i++ { + hashes[i] = crypto.Hash([]byte{byte(i % 256), byte((i / 256) % 256), byte(i / 65536)}) + } + + for i := 0; i < defaultTestEvictSize; i++ { + mt1.Add(hashes[i][:]) + } + + for i := defaultTestEvictSize; i < len(hashes); i++ { + mt1.Add(hashes[i][:]) + mt1.Evict(true) + require.GreaterOrEqual(t, defaultTestEvictSize, mt1.cache.cachedNodeCount) + verifyCacheNodeCount(t, mt1) + } +} + +func TestCacheEviction2(t *testing.T) { + var memoryCommitter InMemoryCommitter + mt1, _ := MakeTrie(&memoryCommitter, defaultTestEvictSize) + // create 20000 hashes. + leafsCount := 20000 + hashes := make([]crypto.Digest, leafsCount) + for i := 0; i < len(hashes); i++ { + hashes[i] = crypto.Hash([]byte{byte(i % 256), byte((i / 256) % 256), byte(i / 65536)}) + } + + for i := 0; i < defaultTestEvictSize; i++ { + mt1.Add(hashes[i][:]) + } + + for i := defaultTestEvictSize; i < len(hashes); i++ { + mt1.Delete(hashes[i-2][:]) + mt1.Add(hashes[i][:]) + mt1.Add(hashes[i-2][:]) + + if i%(len(hashes)/20) == 0 { + mt1.Evict(true) + require.GreaterOrEqual(t, defaultTestEvictSize, mt1.cache.cachedNodeCount) + verifyCacheNodeCount(t, mt1) + } + } +} + +func TestCacheEviction3(t *testing.T) { + var memoryCommitter InMemoryCommitter + mt1, _ := MakeTrie(&memoryCommitter, defaultTestEvictSize) + // create 200000 hashes. + leafsCount := 200000 + hashes := make([]crypto.Digest, leafsCount) + for i := 0; i < len(hashes); i++ { + hashes[i] = crypto.Hash([]byte{byte(i % 256), byte((i / 256) % 256), byte(i / 65536)}) + } + + for i := 0; i < defaultTestEvictSize; i++ { + mt1.Add(hashes[i][:]) + } + + for i := defaultTestEvictSize; i < len(hashes); i++ { + mt1.Delete(hashes[i-500][:]) + mt1.Add(hashes[i][:]) + + if i%(len(hashes)/20) == 0 { + mt1.Evict(true) + require.GreaterOrEqual(t, defaultTestEvictSize, mt1.cache.cachedNodeCount) + verifyCacheNodeCount(t, mt1) + } + } +} diff --git a/crypto/merkletrie/trie_test.go b/crypto/merkletrie/trie_test.go index fe6f9fc18..171e23529 100644 --- a/crypto/merkletrie/trie_test.go +++ b/crypto/merkletrie/trie_test.go @@ -133,6 +133,7 @@ func TestRandomAddingAndRemoving(t *testing.T) { if (i % (1 + int(processesHash[0]))) == 42 { err := mt.Commit() require.NoError(t, err) + verifyCacheNodeCount(t, mt) } } } |