diff options
author | John Lee <64482439+algojohnlee@users.noreply.github.com> | 2023-11-17 09:09:33 -0500 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-11-17 09:09:33 -0500 |
commit | c724cd311dd7e86d73d65da4e2faaa6a8c100216 (patch) | |
tree | 761b2a86e8c4d12667a486f814c217be3291b3a2 | |
parent | fd6e88c223cdbf722cc292cdf9ee41d7d20d8a3f (diff) | |
parent | d22419d91a2e5bdab6da18c980003d44545baed9 (diff) |
Merge pull request #5837 from Algo-devops-service/relbeta3.20.0v3.20.0-beta
-rw-r--r-- | catchup/service.go | 24 | ||||
-rw-r--r-- | crypto/statetrie/nibbles/nibbles.go | 161 | ||||
-rw-r--r-- | crypto/statetrie/nibbles/nibbles_test.go | 218 |
3 files changed, 399 insertions, 4 deletions
diff --git a/catchup/service.go b/catchup/service.go index d755a3d55..bcf204b13 100644 --- a/catchup/service.go +++ b/catchup/service.go @@ -49,6 +49,8 @@ const uncapParallelDownloadRate = time.Second // this should be at least the number of relays const catchupRetryLimit = 500 +const followLatestBackoff = 100 * time.Millisecond + // ErrSyncRoundInvalid is returned when the sync round requested is behind the current ledger round var ErrSyncRoundInvalid = errors.New("requested sync round cannot be less than the latest round") @@ -93,6 +95,12 @@ type Service struct { prevBlockFetchTime time.Time blockValidationPool execpool.BacklogPool + // followLatest is set to true if this is a follower node: meaning there is no + // agreement service to follow the latest round, so catchup continuously runs, + // polling for new blocks as they appear. This enables a different behavior + // to avoid aborting the catchup service once you get to the tip of the chain. + followLatest bool + // suspendForLedgerOps defines whether we've run into a state where the ledger is currently busy writing the // catchpoint file or flushing accounts. If so, we want to suspend the catchup process until the catchpoint file writing is complete, // and resume from there without stopping the catchup timer. @@ -131,6 +139,7 @@ func MakeService(log logging.Logger, config config.Local, net network.GossipNode s = &Service{} s.cfg = config + s.followLatest = s.cfg.EnableFollowMode s.ledger = ledger s.net = net s.auth = auth @@ -321,11 +330,18 @@ func (s *Service) fetchAndWrite(ctx context.Context, r basics.Round, prevFetchCo failureRank = peerRankNoBlockForRound // remote peer doesn't have the block, try another peer // quit if the the same peer peer encountered errNoBlockForRound more than errNoBlockForRoundThreshold times - if count := peerErrors[peer]; count > errNoBlockForRoundThreshold { - s.log.Infof("fetchAndWrite(%d): remote peers do not have the block. Quitting", r) - return false + if s.followLatest { + // back off between retries to allow time for the next block to appear; + // this will provide 50s (catchupRetryLimit * followLatestBackoff) of + // polling when continuously running catchup instead of agreement. + time.Sleep(followLatestBackoff) + } else { + if count := peerErrors[peer]; count > errNoBlockForRoundThreshold { + s.log.Infof("fetchAndWrite(%d): remote peers do not have the block. Quitting", r) + return false + } + peerErrors[peer]++ } - peerErrors[peer]++ } s.log.Debugf("fetchAndWrite(%v): Could not fetch: %v (attempt %d)", r, err, i) peerSelector.rankPeer(psp, failureRank) diff --git a/crypto/statetrie/nibbles/nibbles.go b/crypto/statetrie/nibbles/nibbles.go new file mode 100644 index 000000000..8a8409b6b --- /dev/null +++ b/crypto/statetrie/nibbles/nibbles.go @@ -0,0 +1,161 @@ +// Copyright (C) 2019-2023 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 nibbles + +import ( + "bytes" + "errors" +) + +// Nibbles are 4-bit values stored in an 8-bit byte arrays +type Nibbles []byte + +const ( + // oddIndicator for serialization when the last nibble in a byte array + // is not part of the nibble array. + oddIndicator = 0x01 + // evenIndicator for when it is. + evenIndicator = 0x03 +) + +// Pack the nibble array into a byte array. +// Return the byte array and a bool indicating if the last byte is a full byte or +// only the high 4 bits are part of the encoding +// the last four bits of a oddLength byte encoding will always be zero. +// Allocates a new byte slice. +// +// [0x1, 0x2, 0x3] -> [0x12, 0x30], true +// [0x1, 0x2, 0x3, 0x4] -> [0x12, 0x34], false +// [0x1] -> [0x10], true +// [] -> [], false +func Pack(nyb Nibbles) ([]byte, bool) { + length := len(nyb) + data := make([]byte, length/2+length%2, length/2+length%2+1) + for i := 0; i < length; i++ { + if i%2 == 0 { + data[i/2] = nyb[i] << 4 + } else { + data[i/2] = data[i/2] | nyb[i] + } + } + + return data, length%2 != 0 +} + +// Equal returns true if the two nibble arrays are equal +// [0x1, 0x2, 0x3], [0x1, 0x2, 0x3] -> true +// [0x1, 0x2, 0x3], [0x1, 0x2, 0x4] -> false +// [0x1, 0x2, 0x3], [0x1] -> false +// [0x1, 0x2, 0x3], [0x1, 0x2, 0x3, 0x4] -> false +// [], [] -> true +// [], [0x1] -> false +func Equal(nyb1 Nibbles, nyb2 Nibbles) bool { + return bytes.Equal(nyb1, nyb2) +} + +// ShiftLeft returns a slice of nyb1 that contains the Nibbles after the first +// numNibbles +func ShiftLeft(nyb1 Nibbles, numNibbles int) Nibbles { + if numNibbles <= 0 { + return nyb1 + } + if numNibbles > len(nyb1) { + return nyb1[:0] + } + + return nyb1[numNibbles:] +} + +// SharedPrefix returns a slice from nyb1 that contains the shared prefix +// between nyb1 and nyb2 +func SharedPrefix(nyb1 Nibbles, nyb2 Nibbles) Nibbles { + minLength := len(nyb1) + if len(nyb2) < minLength { + minLength = len(nyb2) + } + for i := 0; i < minLength; i++ { + if nyb1[i] != nyb2[i] { + return nyb1[:i] + } + } + return nyb1[:minLength] +} + +// Serialize returns a byte array that represents the Nibbles +// an empty nibble array is serialized as a single byte with value 0x3 +// as the empty nibble is considered to be full width +// +// [0x1, 0x2, 0x3] -> [0x12, 0x30, 0x01] +// [0x1, 0x2, 0x3, 0x4] -> [0x12, 0x34, 0x03] +// [] -> [0x03] +func Serialize(nyb Nibbles) (data []byte) { + p, h := Pack(nyb) + if h { + // 0x01 is the odd length indicator + return append(p, oddIndicator) + } + // 0x03 is the even length indicator + return append(p, evenIndicator) +} + +// Deserialize returns a nibble array from the byte array. +func Deserialize(encoding []byte) (Nibbles, error) { + var ns Nibbles + length := len(encoding) + if length == 0 { + return nil, errors.New("invalid encoding") + } + if encoding[length-1] == oddIndicator { + if length == 1 { + return nil, errors.New("invalid encoding") + } + ns = makeNibbles(encoding[:length-1], true) + } else if encoding[length-1] == evenIndicator { + ns = makeNibbles(encoding[:length-1], false) + } else { + return nil, errors.New("invalid encoding") + } + return ns, nil +} + +// makeNibbles returns a nibble array from the byte array. If oddLength is true, +// the last 4 bits of the last byte of the array are ignored. +// +// [0x12, 0x30], true -> [0x1, 0x2, 0x3] +// [0x12, 0x34], false -> [0x1, 0x2, 0x3, 0x4] +// [0x12, 0x34], true -> [0x1, 0x2, 0x3] <-- last byte last 4 bits ignored +// [], false -> [] +// never to be called with [], true +// Allocates a new byte slice. +func makeNibbles(data []byte, oddLength bool) Nibbles { + length := len(data) * 2 + if oddLength { + length = length - 1 + } + ns := make([]byte, length) + + j := 0 + for i := 0; i < length; i++ { + if i%2 == 0 { + ns[i] = data[j] >> 4 + } else { + ns[i] = data[j] & 0x0f + j++ + } + } + return ns +} diff --git a/crypto/statetrie/nibbles/nibbles_test.go b/crypto/statetrie/nibbles/nibbles_test.go new file mode 100644 index 000000000..c088f1dd8 --- /dev/null +++ b/crypto/statetrie/nibbles/nibbles_test.go @@ -0,0 +1,218 @@ +// Copyright (C) 2019-2023 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 nibbles + +import ( + "bytes" + "fmt" + "math/rand" + "testing" + "time" + + "github.com/stretchr/testify/require" + + "github.com/algorand/go-algorand/test/partitiontest" +) + +func TestNibblesRandom(t *testing.T) { + partitiontest.PartitionTest(t) + t.Parallel() + + seed := time.Now().UnixNano() + localRand := rand.New(rand.NewSource(seed)) + defer func() { + if t.Failed() { + t.Logf("The seed was %d", seed) + } + }() + + for i := 0; i < 1_000; i++ { + length := localRand.Intn(8192) + 1 + data := make([]byte, length) + localRand.Read(data) + half := localRand.Intn(2) == 0 // half of the time, we have an odd number of nibbles + if half && localRand.Intn(2) == 0 { + data[len(data)-1] &= 0xf0 // sometimes clear the last nibble, sometimes do not + } + nibbles := makeNibbles(data, half) + + data2 := Serialize(nibbles) + nibbles2, err := Deserialize(data2) + require.NoError(t, err) + require.Equal(t, nibbles, nibbles2) + + if half { + data[len(data)-1] &= 0xf0 // clear last nibble + } + packed, odd := Pack(nibbles) + require.Equal(t, odd, half) + require.Equal(t, packed, data) + unpacked := makeNibbles(packed, odd) + require.Equal(t, nibbles, unpacked) + + packed, odd = Pack(nibbles2) + require.Equal(t, odd, half) + require.Equal(t, packed, data) + unpacked = makeNibbles(packed, odd) + require.Equal(t, nibbles2, unpacked) + } +} + +func TestNibblesDeserialize(t *testing.T) { + partitiontest.PartitionTest(t) + t.Parallel() + enc := []byte{0x01} + _, err := Deserialize(enc) + require.Error(t, err, "should return invalid encoding error") +} + +func TestNibbles(t *testing.T) { + partitiontest.PartitionTest(t) + t.Parallel() + + sampleNibbles := []Nibbles{ + {0x0, 0x1, 0x2, 0x3, 0x4}, + {0x4, 0x1, 0x2, 0x3, 0x4}, + {0x0, 0x0, 0x2, 0x3, 0x5}, + {0x0, 0x1, 0x2, 0x3, 0x4, 0x5}, + {}, + {0x1}, + } + + sampleNibblesPacked := [][]byte{ + {0x01, 0x23, 0x40}, + {0x41, 0x23, 0x40}, + {0x00, 0x23, 0x50}, + {0x01, 0x23, 0x45}, + {}, + {0x10}, + } + + sampleNibblesShifted1 := []Nibbles{ + {0x1, 0x2, 0x3, 0x4}, + {0x1, 0x2, 0x3, 0x4}, + {0x0, 0x2, 0x3, 0x5}, + {0x1, 0x2, 0x3, 0x4, 0x5}, + {}, + {}, + } + + sampleNibblesShifted2 := []Nibbles{ + {0x2, 0x3, 0x4}, + {0x2, 0x3, 0x4}, + {0x2, 0x3, 0x5}, + {0x2, 0x3, 0x4, 0x5}, + {}, + {}, + } + + for i, n := range sampleNibbles { + b, oddLength := Pack(n) + if oddLength { + // require that oddLength packs returns a byte slice with the last nibble set to 0x0 + require.Equal(t, b[len(b)-1]&0x0f == 0x00, true) + } + + require.Equal(t, oddLength == (len(n)%2 == 1), true) + require.Equal(t, bytes.Equal(b, sampleNibblesPacked[i]), true) + + unp := makeNibbles(b, oddLength) + require.Equal(t, bytes.Equal(unp, n), true) + + } + for i, n := range sampleNibbles { + require.Equal(t, bytes.Equal(ShiftLeft(n, -2), sampleNibbles[i]), true) + require.Equal(t, bytes.Equal(ShiftLeft(n, -1), sampleNibbles[i]), true) + require.Equal(t, bytes.Equal(ShiftLeft(n, 0), sampleNibbles[i]), true) + require.Equal(t, bytes.Equal(ShiftLeft(n, 1), sampleNibblesShifted1[i]), true) + require.Equal(t, bytes.Equal(ShiftLeft(n, 2), sampleNibblesShifted2[i]), true) + } + + sampleSharedNibbles := [][]Nibbles{ + {{0x0, 0x1, 0x2, 0x9, 0x2}, {0x0, 0x1, 0x2}}, + {{0x4, 0x1}, {0x4, 0x1}}, + {{0x9, 0x2, 0x3}, {}}, + {{0x0}, {0x0}}, + {{}, {}}, + } + for i, n := range sampleSharedNibbles { + shared := SharedPrefix(n[0], sampleNibbles[i]) + require.Equal(t, bytes.Equal(shared, n[1]), true) + shared = SharedPrefix(sampleNibbles[i], n[0]) + require.Equal(t, bytes.Equal(shared, n[1]), true) + } + + sampleSerialization := []Nibbles{ + {0x0, 0x1, 0x2, 0x9, 0x2}, + {0x4, 0x1}, + {0x4, 0x1, 0x4, 0xf}, + {0x4, 0x1, 0x4, 0xf, 0x0}, + {0x9, 0x2, 0x3}, + {}, + {0x05}, + {}, + } + + for _, n := range sampleSerialization { + nbytes := Serialize(n) + n2, err := Deserialize(nbytes) + require.NoError(t, err) + require.True(t, bytes.Equal(n, n2)) + require.Equal(t, len(nbytes), len(n)/2+len(n)%2+1, fmt.Sprintf("nbytes: %v, n: %v", nbytes, n)) + if len(n)%2 == 0 { + require.Equal(t, nbytes[len(nbytes)-1], uint8(evenIndicator)) + } else { + require.Equal(t, nbytes[len(nbytes)-1], uint8(oddIndicator)) + require.Equal(t, nbytes[len(nbytes)-2]&0x0F, uint8(0)) + } + } + + makeNibblesTestExpected := Nibbles{0x0, 0x1, 0x2, 0x9, 0x2} + makeNibblesTestData := []byte{0x01, 0x29, 0x20} + mntr := makeNibbles(makeNibblesTestData, true) + require.Equal(t, bytes.Equal(mntr, makeNibblesTestExpected), true) + makeNibblesTestExpectedFW := Nibbles{0x0, 0x1, 0x2, 0x9, 0x2, 0x0} + mntr2 := makeNibbles(makeNibblesTestData, false) + require.Equal(t, bytes.Equal(mntr2, makeNibblesTestExpectedFW), true) + + sampleEqualFalse := [][]Nibbles{ + {{0x0, 0x1, 0x2, 0x9, 0x2}, {0x0, 0x1, 0x2, 0x9}}, + {{0x0, 0x1, 0x2, 0x9}, {0x0, 0x1, 0x2, 0x9, 0x2}}, + {{0x0, 0x1, 0x2, 0x9, 0x2}, {}}, + {{}, {0x0, 0x1, 0x2, 0x9, 0x2}}, + {{0x0}, {}}, + {{}, {0x0}}, + {{}, {0x1}}, + } + for _, n := range sampleEqualFalse { + ds := Serialize(n[0]) + us, e := Deserialize(ds) + require.NoError(t, e) + require.Equal(t, Equal(n[0], us), true) + require.Equal(t, Equal(n[0], n[0]), true) + require.Equal(t, Equal(us, n[0]), true) + require.Equal(t, Equal(n[0], n[1]), false) + require.Equal(t, Equal(us, n[1]), false) + require.Equal(t, Equal(n[1], n[0]), false) + require.Equal(t, Equal(n[1], us), false) + } + + _, e := Deserialize([]byte{}) + require.Error(t, e) + _, e = Deserialize([]byte{0x02}) + require.Error(t, e) +} |