Swarm MRUs: Adaptive frequency / Predictable lookups / API simplification (#17559)

* swarm/storage/mru: Adaptive Frequency

swarm/storage/mru/lookup: fixed getBaseTime
Added NewEpoch constructor

swarm/api/client: better error handling in GetResource()


swarm/storage/mru: Renamed structures.
Renamed ResourceMetadata to ResourceID. 
Renamed ResourceID.Name to ResourceID.Topic

swarm/storage/mru: Added binarySerializer interface and test tools

swarm/storage/mru/lookup: Changed base time to time and + marshallers

swarm/storage/mru:  Added ResourceID (former resourceMetadata)

swarm/storage/mru: Added ResourceViewId and serialization tests

swarm/storage/mru/lookup: fixed epoch unmarshaller. Added Epoch Equals

swarm/storage/mru: Fixes as per review comments

cmd/swarm: reworded resource create/update help text regarding topic

swarm/storage/mru: Added UpdateLookup and serializer tests

swarm/storage/mru: Added UpdateHeader, serializers and tests

swarm/storage/mru: changed UpdateAddr / epoch to Base()

swarm/storage/mru: Added resourceUpdate serializer and tests

swarm/storage/mru: Added SignedResourceUpdate tests and serializers

swarm/storage/mru/lookup: fixed GetFirstEpoch bug

swarm/storage/mru: refactor, comments, cleanup

Also added tests for Topic
swarm/storage/mru: handler tests pass

swarm/storage/mru: all resource package tests pass

swarm/storage/mru: resource test pass after adding
timestamp checking support

swarm/storage/mru: Added JSON serializers to ResourceIDView structures

swarm/storage/mru: Sever, client, API test pass

swarm/storage/mru: server test pass

swarm/storage/mru: Added topic length check

swarm/storage/mru: removed some literals,
improved "previous lookup" test case

swarm/storage/mru: some fixes and comments as per review

swarm/storage/mru: first working version without metadata chunk

swarm/storage/mru: Various fixes as per review

swarm/storage/mru: client test pass

swarm/storage/mru: resource query strings and manifest-less queries


swarm/storage/mru: simplify naming

swarm/storage/mru: first autofreq working version



swarm/storage/mru: renamed ToValues to AppendValues

swarm/resource/mru: Added ToValues / FromValues for URL query strings

swarm/storage/mru: Changed POST resource to work with query strings.
No more JSON.

swarm/storage/mru: removed resourceid

swarm/storage/mru: Opened up structures

swarm/storage/mru: Merged Request and SignedResourceUpdate

swarm/storage/mru: removed initial data from CLI resource create

swarm/storage/mru: Refactor Topic as a direct fixed-length array

swarm/storage/mru/lookup: Comprehensive GetNextLevel tests

swarm/storage/mru: Added comments

Added length checks in Topic
swarm/storage/mru: fixes in tests and some code comments

swarm/storage/mru/lookup: new optimized lookup algorithm

swarm/api: moved getResourceView to api out of server

swarm/storage/mru: Lookup algorithm working

swarm/storage/mru: comments and renamed NewLookupParams

Deleted commented code


swarm/storage/mru/lookup: renamed Epoch.LaterThan to After

swarm/storage/mru/lookup: Comments and tidying naming



swarm/storage/mru: fix lookup algorithm

swarm/storage/mru: exposed lookup hint
removed updateheader

swarm/storage/mru/lookup: changed GetNextEpoch for initial values

swarm/storage/mru: resource tests pass

swarm/storage/mru: valueSerializer interface and tests



swarm/storage/mru/lookup: Comments, improvements, fixes, more tests

swarm/storage/mru: renamed UpdateLookup to ID, LookupParams to Query

swarm/storage/mru: renamed query receiver var



swarm/cmd: MRU CLI tests

* cmd/swarm: remove rogue fmt

* swarm/storage/mru: Add version / header for future use

* swarm/storage/mru: Fixes/comments as per review

cmd/swarm: remove rogue fmt

swarm/storage/mru: Add version / header for future use-

* swarm/storage/mru: fix linter errors

* cmd/swarm: Speeded up TestCLIResourceUpdate

4 files changed, 744 insertions, 0 deletions

diff --git a/swarm/storage/mru/lookup/epoch.go b/swarm/storage/mru/lookup/epoch.go
new file mode 100644
index 000000000..bafe95477
--- /dev/null
+++ b/swarm/storage/mru/lookup/epoch.go
@@ -0,0 +1,91 @@
+// Copyright 2018 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library 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 Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+package lookup
+
+import (
+	"encoding/binary"
+	"errors"
+	"fmt"
+)
+
+// Epoch represents a time slot at a particular frequency level
+type Epoch struct {
+	Time  uint64 `json:"time"`  // Time stores the time at which the update or lookup takes place
+	Level uint8  `json:"level"` // Level indicates the frequency level as the exponent of a power of 2
+}
+
+// EpochID is a unique identifier for an Epoch, based on its level and base time.
+type EpochID [8]byte
+
+// EpochLength stores the serialized binary length of an Epoch
+const EpochLength = 8
+
+// MaxTime contains the highest possible time value an Epoch can handle
+const MaxTime uint64 = (1 << 56) - 1
+
+// Base returns the base time of the Epoch
+func (e *Epoch) Base() uint64 {
+	return getBaseTime(e.Time, e.Level)
+}
+
+// ID Returns the unique identifier of this epoch
+func (e *Epoch) ID() EpochID {
+	base := e.Base()
+	var id EpochID
+	binary.LittleEndian.PutUint64(id[:], base)
+	id[7] = e.Level
+	return id
+}
+
+// MarshalBinary implements the encoding.BinaryMarshaller interface
+func (e *Epoch) MarshalBinary() (data []byte, err error) {
+	b := make([]byte, 8)
+	binary.LittleEndian.PutUint64(b[:], e.Time)
+	b[7] = e.Level
+	return b, nil
+}
+
+// UnmarshalBinary implements the encoding.BinaryUnmarshaller interface
+func (e *Epoch) UnmarshalBinary(data []byte) error {
+	if len(data) != EpochLength {
+		return errors.New("Invalid data unmarshalling Epoch")
+	}
+	b := make([]byte, 8)
+	copy(b, data)
+	e.Level = b[7]
+	b[7] = 0
+	e.Time = binary.LittleEndian.Uint64(b)
+	return nil
+}
+
+// After returns true if this epoch occurs later or exactly at the other epoch.
+func (e *Epoch) After(epoch Epoch) bool {
+	if e.Time == epoch.Time {
+		return e.Level < epoch.Level
+	}
+	return e.Time >= epoch.Time
+}
+
+// Equals compares two epochs and returns true if they refer to the same time period.
+func (e *Epoch) Equals(epoch Epoch) bool {
+	return e.Level == epoch.Level && e.Base() == epoch.Base()
+}
+
+// String implements the Stringer interface.
+func (e *Epoch) String() string {
+	return fmt.Sprintf("Epoch{Time:%d, Level:%d}", e.Time, e.Level)
+}
diff --git a/swarm/storage/mru/lookup/epoch_test.go b/swarm/storage/mru/lookup/epoch_test.go
new file mode 100644
index 000000000..8c63ec6c2
--- /dev/null
+++ b/swarm/storage/mru/lookup/epoch_test.go
@@ -0,0 +1,57 @@
+package lookup_test
+
+import (
+	"testing"
+
+	"github.com/ethereum/go-ethereum/swarm/storage/mru/lookup"
+)
+
+func TestMarshallers(t *testing.T) {
+
+	for i := uint64(1); i < lookup.MaxTime; i *= 3 {
+		e := lookup.Epoch{
+			Time:  i,
+			Level: uint8(i % 20),
+		}
+		b, err := e.MarshalBinary()
+		if err != nil {
+			t.Fatal(err)
+		}
+		var e2 lookup.Epoch
+		if err := e2.UnmarshalBinary(b); err != nil {
+			t.Fatal(err)
+		}
+		if e != e2 {
+			t.Fatal("Expected unmarshalled epoch to be equal to marshalled onet.Fatal(err)")
+		}
+	}
+
+}
+
+func TestAfter(t *testing.T) {
+	a := lookup.Epoch{
+		Time:  5,
+		Level: 3,
+	}
+	b := lookup.Epoch{
+		Time:  6,
+		Level: 3,
+	}
+	c := lookup.Epoch{
+		Time:  6,
+		Level: 4,
+	}
+
+	if b.After(a) != true {
+		t.Fatal("Expected 'after' to be true, got false")
+	}
+
+	if b.After(b) != false {
+		t.Fatal("Expected 'after' to be false when both epochs are identical, got true")
+	}
+
+	if b.After(c) != true {
+		t.Fatal("Expected 'after' to be true when both epochs have the same time but the level is lower in the first one, but got false")
+	}
+
+}
diff --git a/swarm/storage/mru/lookup/lookup.go b/swarm/storage/mru/lookup/lookup.go
new file mode 100644
index 000000000..c98248d70
--- /dev/null
+++ b/swarm/storage/mru/lookup/lookup.go
@@ -0,0 +1,180 @@
+// Copyright 2018 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library 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 Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+/*
+Package lookup defines resource lookup algorithms and provides tools to place updates
+so they can be found
+*/
+package lookup
+
+const maxuint64 = ^uint64(0)
+
+// LowestLevel establishes the frequency resolution of the lookup algorithm as a power of 2.
+const LowestLevel uint8 = 0 // default is 0 (1 second)
+
+// HighestLevel sets the lowest frequency the algorithm will operate at, as a power of 2.
+// 25 -> 2^25 equals to roughly one year.
+const HighestLevel = 25 // default is 25 (~1 year)
+
+// DefaultLevel sets what level will be chosen to search when there is no hint
+const DefaultLevel = HighestLevel
+
+//Algorithm is the function signature of a lookup algorithm
+type Algorithm func(now uint64, hint Epoch, read ReadFunc) (value interface{}, err error)
+
+// Lookup finds the update with the highest timestamp that is smaller or equal than 'now'
+// It takes a hint which should be the epoch where the last known update was
+// If you don't know in what epoch the last update happened, simply submit lookup.NoClue
+// read() will be called on each lookup attempt
+// Returns an error only if read() returns an error
+// Returns nil if an update was not found
+var Lookup Algorithm = FluzCapacitorAlgorithm
+
+// ReadFunc is a handler called by Lookup each time it attempts to find a value
+// It should return <nil> if a value is not found
+// It should return <nil> if a value is found, but its timestamp is higher than "now"
+// It should only return an error in case the handler wants to stop the
+// lookup process entirely.
+type ReadFunc func(epoch Epoch, now uint64) (interface{}, error)
+
+// NoClue is a hint that can be provided when the Lookup caller does not have
+// a clue about where the last update may be
+var NoClue = Epoch{}
+
+// getBaseTime returns the epoch base time of the given
+// time and level
+func getBaseTime(t uint64, level uint8) uint64 {
+	return t & (maxuint64 << level)
+}
+
+// Hint creates a hint based only on the last known update time
+func Hint(last uint64) Epoch {
+	return Epoch{
+		Time:  last,
+		Level: DefaultLevel,
+	}
+}
+
+// GetNextLevel returns the frequency level a next update should be placed at, provided where
+// the last update was and what time it is now.
+// This is the first nonzero bit of the XOR of 'last' and 'now', counting from the highest significant bit
+// but limited to not return a level that is smaller than the last-1
+func GetNextLevel(last Epoch, now uint64) uint8 {
+	// First XOR the last epoch base time with the current clock.
+	// This will set all the common most significant bits to zero.
+	mix := (last.Base() ^ now)
+
+	// Then, make sure we stop the below loop before one level below the current, by setting
+	// that level's bit to 1.
+	// If the next level is lower than the current one, it must be exactly level-1 and not lower.
+	mix |= (1 << (last.Level - 1))
+
+	// if the last update was more than 2^highestLevel seconds ago, choose the highest level
+	if mix > (maxuint64 >> (64 - HighestLevel - 1)) {
+		return HighestLevel
+	}
+
+	// set up a mask to scan for nonzero bits, starting at the highest level
+	mask := uint64(1 << (HighestLevel))
+
+	for i := uint8(HighestLevel); i > LowestLevel; i-- {
+		if mix&mask != 0 { // if we find a nonzero bit, this is the level the next update should be at.
+			return i
+		}
+		mask = mask >> 1 // move our bit one position to the right
+	}
+	return 0
+}
+
+// GetNextEpoch returns the epoch where the next update should be located
+// according to where the previous update was
+// and what time it is now.
+func GetNextEpoch(last Epoch, now uint64) Epoch {
+	if last == NoClue {
+		return GetFirstEpoch(now)
+	}
+	level := GetNextLevel(last, now)
+	return Epoch{
+		Level: level,
+		Time:  now,
+	}
+}
+
+// GetFirstEpoch returns the epoch where the first update should be located
+// based on what time it is now.
+func GetFirstEpoch(now uint64) Epoch {
+	return Epoch{Level: HighestLevel, Time: now}
+}
+
+var worstHint = Epoch{Time: 0, Level: 63}
+
+// FluzCapacitorAlgorithm works by narrowing the epoch search area if an update is found
+// going back and forth in time
+// First, it will attempt to find an update where it should be now if the hint was
+// really the last update. If that lookup fails, then the last update must be either the hint itself
+// or the epochs right below. If however, that lookup succeeds, then the update must be
+// that one or within the epochs right below.
+// see the guide for a more graphical representation
+func FluzCapacitorAlgorithm(now uint64, hint Epoch, read ReadFunc) (value interface{}, err error) {
+	var lastFound interface{}
+	var epoch Epoch
+	if hint == NoClue {
+		hint = worstHint
+	}
+
+	t := now
+
+	for {
+		epoch = GetNextEpoch(hint, t)
+		value, err = read(epoch, now)
+		if err != nil {
+			return nil, err
+		}
+		if value != nil {
+			lastFound = value
+			if epoch.Level == LowestLevel || epoch.Equals(hint) {
+				return value, nil
+			}
+			hint = epoch
+			continue
+		}
+		if epoch.Base() == hint.Base() {
+			if lastFound != nil {
+				return lastFound, nil
+			}
+			// we have reached the hint itself
+			if hint == worstHint {
+				return nil, nil
+			}
+			// check it out
+			value, err = read(hint, now)
+			if err != nil {
+				return nil, err
+			}
+			if value != nil {
+				return value, nil
+			}
+			// bad hint.
+			epoch = hint
+			hint = worstHint
+		}
+		base := epoch.Base()
+		if base == 0 {
+			return nil, nil
+		}
+		t = base - 1
+	}
+}
diff --git a/swarm/storage/mru/lookup/lookup_test.go b/swarm/storage/mru/lookup/lookup_test.go
new file mode 100644
index 000000000..ca0bb73bb
--- /dev/null
+++ b/swarm/storage/mru/lookup/lookup_test.go
@@ -0,0 +1,416 @@
+// Copyright 2018 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library 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 Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+package lookup_test
+
+import (
+	"fmt"
+	"math/rand"
+	"testing"
+
+	"github.com/ethereum/go-ethereum/swarm/log"
+	"github.com/ethereum/go-ethereum/swarm/storage/mru/lookup"
+)
+
+type Data struct {
+	Payload uint64
+	Time    uint64
+}
+
+type Store map[lookup.EpochID]*Data
+
+func write(store Store, epoch lookup.Epoch, value *Data) {
+	log.Debug("Write: %d-%d, value='%d'\n", epoch.Base(), epoch.Level, value.Payload)
+	store[epoch.ID()] = value
+}
+
+func update(store Store, last lookup.Epoch, now uint64, value *Data) lookup.Epoch {
+	var epoch lookup.Epoch
+
+	epoch = lookup.GetNextEpoch(last, now)
+
+	write(store, epoch, value)
+
+	return epoch
+}
+
+const Day = 60 * 60 * 24
+const Year = Day * 365
+const Month = Day * 30
+
+func makeReadFunc(store Store, counter *int) lookup.ReadFunc {
+	return func(epoch lookup.Epoch, now uint64) (interface{}, error) {
+		*counter++
+		data := store[epoch.ID()]
+		var valueStr string
+		if data != nil {
+			valueStr = fmt.Sprintf("%d", data.Payload)
+		}
+		log.Debug("Read: %d-%d, value='%s'\n", epoch.Base(), epoch.Level, valueStr)
+		if data != nil && data.Time <= now {
+			return data, nil
+		}
+		return nil, nil
+	}
+}
+
+func TestLookup(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+	readFunc := makeReadFunc(store, &readCount)
+
+	// write an update every month for 12 months 3 years ago and then silence for two years
+	now := uint64(1533799046)
+	var epoch lookup.Epoch
+
+	var lastData *Data
+	for i := uint64(0); i < 12; i++ {
+		t := uint64(now - Year*3 + i*Month)
+		data := Data{
+			Payload: t, //our "payload" will be the timestamp itself.
+			Time:    t,
+		}
+		epoch = update(store, epoch, t, &data)
+		lastData = &data
+	}
+
+	// try to get the last value
+
+	value, err := lookup.Lookup(now, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	readCountWithoutHint := readCount
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	// reset the read count for the next test
+	readCount = 0
+	// Provide a hint to get a faster lookup. In particular, we give the exact location of the last update
+	value, err = lookup.Lookup(now, epoch, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	if readCount > readCountWithoutHint {
+		t.Fatalf("Expected lookup to complete with fewer or same reads than %d since we provided a hint. Did %d reads.", readCountWithoutHint, readCount)
+	}
+
+	// try to get an intermediate value
+	// if we look for a value in now - Year*3 + 6*Month, we should get that value
+	// Since the "payload" is the timestamp itself, we can check this.
+
+	expectedTime := now - Year*3 + 6*Month
+
+	value, err = lookup.Lookup(expectedTime, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	data, ok := value.(*Data)
+
+	if !ok {
+		t.Fatal("Expected value to contain data")
+	}
+
+	if data.Time != expectedTime {
+		t.Fatalf("Expected value timestamp to be %d, got %d", data.Time, expectedTime)
+	}
+
+}
+
+func TestOneUpdateAt0(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+
+	readFunc := makeReadFunc(store, &readCount)
+	now := uint64(1533903729)
+
+	var epoch lookup.Epoch
+	data := Data{
+		Payload: 79,
+		Time:    0,
+	}
+	update(store, epoch, 0, &data)
+
+	value, err := lookup.Lookup(now, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if value != &data {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", data, value)
+	}
+}
+
+// Tests the update is found even when a bad hint is given
+func TestBadHint(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+
+	readFunc := makeReadFunc(store, &readCount)
+	now := uint64(1533903729)
+
+	var epoch lookup.Epoch
+	data := Data{
+		Payload: 79,
+		Time:    0,
+	}
+
+	// place an update for t=1200
+	update(store, epoch, 1200, &data)
+
+	// come up with some evil hint
+	badHint := lookup.Epoch{
+		Level: 18,
+		Time:  1200000000,
+	}
+
+	value, err := lookup.Lookup(now, badHint, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if value != &data {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", data, value)
+	}
+}
+
+func TestLookupFail(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+
+	readFunc := makeReadFunc(store, &readCount)
+	now := uint64(1533903729)
+
+	// don't write anything and try to look up.
+	// we're testing we don't get stuck in a loop
+
+	value, err := lookup.Lookup(now, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if value != nil {
+		t.Fatal("Expected value to be nil, since the update should've failed")
+	}
+
+	expectedReads := now/(1<<lookup.HighestLevel) + 1
+	if uint64(readCount) != expectedReads {
+		t.Fatalf("Expected lookup to fail after %d reads. Did %d reads.", expectedReads, readCount)
+	}
+}
+
+func TestHighFreqUpdates(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+
+	readFunc := makeReadFunc(store, &readCount)
+	now := uint64(1533903729)
+
+	// write an update every second for the last 1000 seconds
+	var epoch lookup.Epoch
+
+	var lastData *Data
+	for i := uint64(0); i <= 994; i++ {
+		T := uint64(now - 1000 + i)
+		data := Data{
+			Payload: T, //our "payload" will be the timestamp itself.
+			Time:    T,
+		}
+		epoch = update(store, epoch, T, &data)
+		lastData = &data
+	}
+
+	value, err := lookup.Lookup(lastData.Time, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	readCountWithoutHint := readCount
+	// reset the read count for the next test
+	readCount = 0
+	// Provide a hint to get a faster lookup. In particular, we give the exact location of the last update
+	value, err = lookup.Lookup(now, epoch, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	if readCount > readCountWithoutHint {
+		t.Fatalf("Expected lookup to complete with fewer or equal reads than %d since we provided a hint. Did %d reads.", readCountWithoutHint, readCount)
+	}
+
+	for i := uint64(0); i <= 994; i++ {
+		T := uint64(now - 1000 + i) // update every second for the last 1000 seconds
+		value, err := lookup.Lookup(T, lookup.NoClue, readFunc)
+		if err != nil {
+			t.Fatal(err)
+		}
+		data, _ := value.(*Data)
+		if data == nil {
+			t.Fatalf("Expected lookup to return %d, got nil", T)
+		}
+		if data.Payload != T {
+			t.Fatalf("Expected lookup to return %d, got %d", T, data.Time)
+		}
+	}
+}
+
+func TestSparseUpdates(t *testing.T) {
+
+	store := make(Store)
+	readCount := 0
+	readFunc := makeReadFunc(store, &readCount)
+
+	// write an update every 5 years 3 times starting in Jan 1st 1970 and then silence
+
+	now := uint64(1533799046)
+	var epoch lookup.Epoch
+
+	var lastData *Data
+	for i := uint64(0); i < 5; i++ {
+		T := uint64(Year * 5 * i) // write an update every 5 years 3 times starting in Jan 1st 1970 and then silence
+		data := Data{
+			Payload: T, //our "payload" will be the timestamp itself.
+			Time:    T,
+		}
+		epoch = update(store, epoch, T, &data)
+		lastData = &data
+	}
+
+	// try to get the last value
+
+	value, err := lookup.Lookup(now, lookup.NoClue, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	readCountWithoutHint := readCount
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	// reset the read count for the next test
+	readCount = 0
+	// Provide a hint to get a faster lookup. In particular, we give the exact location of the last update
+	value, err = lookup.Lookup(now, epoch, readFunc)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if value != lastData {
+		t.Fatalf("Expected lookup to return the last written value: %v. Got %v", lastData, value)
+	}
+
+	if readCount > readCountWithoutHint {
+		t.Fatalf("Expected lookup to complete with fewer reads than %d since we provided a hint. Did %d reads.", readCountWithoutHint, readCount)
+	}
+
+}
+
+// testG will hold precooked test results
+// fields are abbreviated to reduce the size of the literal below
+type testG struct {
+	e lookup.Epoch // last
+	n uint64       // next level
+	x uint8        // expected result
+}
+
+// test cases
+var testGetNextLevelCases []testG = []testG{{e: lookup.Epoch{Time: 989875233, Level: 12}, n: 989875233, x: 11}, {e: lookup.Epoch{Time: 995807650, Level: 18}, n: 995598156, x: 19}, {e: lookup.Epoch{Time: 969167082, Level: 0}, n: 968990357, x: 18}, {e: lookup.Epoch{Time: 993087628, Level: 14}, n: 992987044, x: 20}, {e: lookup.Epoch{Time: 963364631, Level: 20}, n: 963364630, x: 19}, {e: lookup.Epoch{Time: 963497510, Level: 16}, n: 963370732, x: 18}, {e: lookup.Epoch{Time: 955421349, Level: 22}, n: 955421348, x: 21}, {e: lookup.Epoch{Time: 968220379, Level: 15}, n: 968220378, x: 14}, {e: lookup.Epoch{Time: 939129014, Level: 6}, n: 939128771, x: 11}, {e: lookup.Epoch{Time: 907847903, Level: 6}, n: 907791833, x: 18}, {e: lookup.Epoch{Time: 910835564, Level: 15}, n: 910835564, x: 14}, {e: lookup.Epoch{Time: 913578333, Level: 22}, n: 881808431, x: 25}, {e: lookup.Epoch{Time: 895818460, Level: 3}, n: 895818132, x: 9}, {e: lookup.Epoch{Time: 903843025, Level: 24}, n: 895609561, x: 23}, {e: lookup.Epoch{Time: 877889433, Level: 13}, n: 877877093, x: 15}, {e: lookup.Epoch{Time: 901450396, Level: 10}, n: 901450058, x: 9}, {e: lookup.Epoch{Time: 925179910, Level: 3}, n: 925168393, x: 16}, {e: lookup.Epoch{Time: 913485477, Level: 21}, n: 913485476, x: 20}, {e: lookup.Epoch{Time: 924462991, Level: 18}, n: 924462990, x: 17}, {e: lookup.Epoch{Time: 941175128, Level: 13}, n: 941175127, x: 12}, {e: lookup.Epoch{Time: 920126583, Level: 3}, n: 920100782, x: 19}, {e: lookup.Epoch{Time: 932403200, Level: 9}, n: 932279891, x: 17}, {e: lookup.Epoch{Time: 948284931, Level: 2}, n: 948284921, x: 9}, {e: lookup.Epoch{Time: 953540997, Level: 7}, n: 950547986, x: 22}, {e: lookup.Epoch{Time: 926639837, Level: 18}, n: 918608882, x: 24}, {e: lookup.Epoch{Time: 954637598, Level: 1}, n: 954578761, x: 17}, {e: lookup.Epoch{Time: 943482981, Level: 10}, n: 942924151, x: 19}, {e: lookup.Epoch{Time: 963580771, Level: 7}, n: 963580771, x: 6}, {e: lookup.Epoch{Time: 993744930, Level: 7}, n: 993690858, x: 16}, {e: lookup.Epoch{Time: 1018890213, Level: 12}, n: 1018890212, x: 11}, {e: lookup.Epoch{Time: 1030309411, Level: 2}, n: 1030309227, x: 9}, {e: lookup.Epoch{Time: 1063204997, Level: 20}, n: 1063204996, x: 19}, {e: lookup.Epoch{Time: 1094340832, Level: 6}, n: 1094340633, x: 7}, {e: lookup.Epoch{Time: 1077880597, Level: 10}, n: 1075914292, x: 20}, {e: lookup.Epoch{Time: 1051114957, Level: 18}, n: 1051114957, x: 17}, {e: lookup.Epoch{Time: 1045649701, Level: 22}, n: 1045649700, x: 21}, {e: lookup.Epoch{Time: 1066198885, Level: 14}, n: 1066198884, x: 13}, {e: lookup.Epoch{Time: 1053231952, Level: 1}, n: 1053210845, x: 16}, {e: lookup.Epoch{Time: 1068763404, Level: 14}, n: 1068675428, x: 18}, {e: lookup.Epoch{Time: 1039042173, Level: 15}, n: 1038973110, x: 17}, {e: lookup.Epoch{Time: 1050747636, Level: 6}, n: 1050747364, x: 9}, {e: lookup.Epoch{Time: 1030034434, Level: 23}, n: 1030034433, x: 22}, {e: lookup.Epoch{Time: 1003783425, Level: 18}, n: 1003783424, x: 17}, {e: lookup.Epoch{Time: 988163976, Level: 15}, n: 988084064, x: 17}, {e: lookup.Epoch{Time: 1007222377, Level: 15}, n: 1007222377, x: 14}, {e: lookup.Epoch{Time: 1001211375, Level: 13}, n: 1001208178, x: 14}, {e: lookup.Epoch{Time: 997623199, Level: 8}, n: 997623198, x: 7}, {e: lookup.Epoch{Time: 1026283830, Level: 10}, n: 1006681704, x: 24}, {e: lookup.Epoch{Time: 1019421907, Level: 20}, n: 1019421906, x: 19}, {e: lookup.Epoch{Time: 1043154306, Level: 16}, n: 1043108343, x: 16}, {e: lookup.Epoch{Time: 1075643767, Level: 17}, n: 1075325898, x: 18}, {e: lookup.Epoch{Time: 1043726309, Level: 20}, n: 1043726308, x: 19}, {e: lookup.Epoch{Time: 1056415324, Level: 17}, n: 1056415324, x: 16}, {e: lookup.Epoch{Time: 1088650219, Level: 13}, n: 1088650218, x: 12}, {e: lookup.Epoch{Time: 1088551662, Level: 7}, n: 1088543355, x: 13}, {e: lookup.Epoch{Time: 1069667265, Level: 6}, n: 1069667075, x: 7}, {e: lookup.Epoch{Time: 1079145970, Level: 18}, n: 1079145969, x: 17}, {e: lookup.Epoch{Time: 1083338876, Level: 7}, n: 1083338875, x: 6}, {e: lookup.Epoch{Time: 1051581086, Level: 4}, n: 1051568869, x: 14}, {e: lookup.Epoch{Time: 1028430882, Level: 4}, n: 1028430864, x: 5}, {e: lookup.Epoch{Time: 1057356462, Level: 1}, n: 1057356417, x: 5}, {e: lookup.Epoch{Time: 1033104266, Level: 0}, n: 1033097479, x: 13}, {e: lookup.Epoch{Time: 1031391367, Level: 11}, n: 1031387304, x: 14}, {e: lookup.Epoch{Time: 1049781164, Level: 15}, n: 1049781163, x: 14}, {e: lookup.Epoch{Time: 1027271628, Level: 12}, n: 1027271627, x: 11}, {e: lookup.Epoch{Time: 1057270560, Level: 23}, n: 1057270560, x: 22}, {e: lookup.Epoch{Time: 1047501317, Level: 15}, n: 1047501317, x: 14}, {e: lookup.Epoch{Time: 1058349035, Level: 11}, n: 1045175573, x: 24}, {e: lookup.Epoch{Time: 1057396147, Level: 20}, n: 1057396147, x: 19}, {e: lookup.Epoch{Time: 1048906375, Level: 18}, n: 1039616919, x: 25}, {e: lookup.Epoch{Time: 1074294831, Level: 20}, n: 1074294831, x: 19}, {e: lookup.Epoch{Time: 1088946052, Level: 1}, n: 1088917364, x: 14}, {e: lookup.Epoch{Time: 1112337595, Level: 17}, n: 1111008110, x: 22}, {e: lookup.Epoch{Time: 1099990284, Level: 5}, n: 1099968370, x: 15}, {e: lookup.Epoch{Time: 1087036441, Level: 16}, n: 1053967855, x: 25}, {e: lookup.Epoch{Time: 1069225185, Level: 8}, n: 1069224660, x: 10}, {e: lookup.Epoch{Time: 1057505479, Level: 9}, n: 1057505170, x: 14}, {e: lookup.Epoch{Time: 1072381377, Level: 12}, n: 1065950959, x: 22}, {e: lookup.Epoch{Time: 1093887139, Level: 8}, n: 1093863305, x: 14}, {e: lookup.Epoch{Time: 1082366510, Level: 24}, n: 1082366510, x: 23}, {e: lookup.Epoch{Time: 1103231132, Level: 14}, n: 1102292201, x: 22}, {e: lookup.Epoch{Time: 1094502355, Level: 3}, n: 1094324652, x: 18}, {e: lookup.Epoch{Time: 1068488344, Level: 12}, n: 1067577330, x: 19}, {e: lookup.Epoch{Time: 1050278233, Level: 12}, n: 1050278232, x: 11}, {e: lookup.Epoch{Time: 1047660768, Level: 5}, n: 1047652137, x: 17}, {e: lookup.Epoch{Time: 1060116167, Level: 11}, n: 1060114091, x: 12}, {e: lookup.Epoch{Time: 1068149392, Level: 21}, n: 1052074801, x: 24}, {e: lookup.Epoch{Time: 1081934120, Level: 6}, n: 1081933847, x: 8}, {e: lookup.Epoch{Time: 1107943693, Level: 16}, n: 1107096139, x: 25}, {e: lookup.Epoch{Time: 1131571649, Level: 9}, n: 1131570428, x: 11}, {e: lookup.Epoch{Time: 1123139367, Level: 0}, n: 1122912198, x: 20}, {e: lookup.Epoch{Time: 1121144423, Level: 6}, n: 1120568289, x: 20}, {e: lookup.Epoch{Time: 1089932411, Level: 17}, n: 1089932410, x: 16}, {e: lookup.Epoch{Time: 1104899012, Level: 22}, n: 1098978789, x: 22}, {e: lookup.Epoch{Time: 1094588059, Level: 21}, n: 1094588059, x: 20}, {e: lookup.Epoch{Time: 1114987438, Level: 24}, n: 1114987437, x: 23}, {e: lookup.Epoch{Time: 1084186305, Level: 7}, n: 1084186241, x: 6}, {e: lookup.Epoch{Time: 1058827111, Level: 8}, n: 1058826504, x: 9}, {e: lookup.Epoch{Time: 1090679810, Level: 12}, n: 1090616539, x: 17}, {e: lookup.Epoch{Time: 1084299475, Level: 23}, n: 1084299475, x: 22}}
+
+func TestGetNextLevel(t *testing.T) {
+
+	// First, test well-known cases
+	last := lookup.Epoch{
+		Time:  1533799046,
+		Level: 5,
+	}
+
+	level := lookup.GetNextLevel(last, last.Time)
+	expected := uint8(4)
+	if level != expected {
+		t.Fatalf("Expected GetNextLevel to return %d for same-time updates at a nonzero level, got %d", expected, level)
+	}
+
+	level = lookup.GetNextLevel(last, last.Time+(1<<lookup.HighestLevel)+3000)
+	expected = lookup.HighestLevel
+	if level != expected {
+		t.Fatalf("Expected GetNextLevel to return %d for updates set 2^lookup.HighestLevel seconds away, got %d", expected, level)
+	}
+
+	level = lookup.GetNextLevel(last, last.Time+(1<<last.Level))
+	expected = last.Level
+	if level != expected {
+		t.Fatalf("Expected GetNextLevel to return %d for updates set 2^last.Level seconds away, got %d", expected, level)
+	}
+
+	last.Level = 0
+	level = lookup.GetNextLevel(last, last.Time)
+	expected = 0
+	if level != expected {
+		t.Fatalf("Expected GetNextLevel to return %d for same-time updates at a zero level, got %d", expected, level)
+	}
+
+	// run a batch of 100 cooked tests
+	for _, s := range testGetNextLevelCases {
+		level := lookup.GetNextLevel(s.e, s.n)
+		if level != s.x {
+			t.Fatalf("Expected GetNextLevel to return %d for last=%s when now=%d, got %d", s.x, s.e.String(), s.n, level)
+		}
+	}
+
+}
+
+// cookGetNextLevelTests is used to generate a deterministic
+// set of cases for TestGetNextLevel and thus "freeze" its current behavior
+func CookGetNextLevelTests(t *testing.T) {
+	st := ""
+	var last lookup.Epoch
+	last.Time = 1000000000
+	var now uint64
+	var expected uint8
+	for i := 0; i < 100; i++ {
+		last.Time += uint64(rand.Intn(1<<26)) - (1 << 25)
+		last.Level = uint8(rand.Intn(25))
+		v := last.Level + uint8(rand.Intn(lookup.HighestLevel))
+		if v > lookup.HighestLevel {
+			v = 0
+		}
+		now = last.Time + uint64(rand.Intn(1<<v+1)) - (1 << v)
+		expected = lookup.GetNextLevel(last, now)
+		st = fmt.Sprintf("%s,testG{e:lookup.Epoch{Time:%d, Level:%d}, n:%d, x:%d}", st, last.Time, last.Level, now, expected)
+	}
+	fmt.Println(st)
+}