Use hashicorp/go-memdb instead of truncindex

memdb already knows how to search by prefix so there is no need to keep
a separate list of container ids in the truncindex

Benchmarks:

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkDBGetByPrefix100$ github.com/docker/docker/container
goos: linux
goarch: amd64
pkg: github.com/docker/docker/container
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkDBGetByPrefix100-6        16018             73935 ns/op           33888 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16502             73150 ns/op           33888 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16218             74014 ns/op           33856 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        15733             73370 ns/op           33792 B/op       1100 allocs/op
BenchmarkDBGetByPrefix100-6        16432             72546 ns/op           33744 B/op       1100 allocs/op
PASS
ok      github.com/docker/docker/container      9.752s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkTruncIndexGet100$ github.com/docker/docker/pkg/truncindex
goos: linux
goarch: amd64
pkg: github.com/docker/docker/pkg/truncindex
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkTruncIndexGet100-6        16862             73732 ns/op           44776 B/op       1173 allocs/op
BenchmarkTruncIndexGet100-6        16832             73629 ns/op           45184 B/op       1179 allocs/op
BenchmarkTruncIndexGet100-6        17214             73571 ns/op           45160 B/op       1178 allocs/op
BenchmarkTruncIndexGet100-6        16113             71680 ns/op           45360 B/op       1182 allocs/op
BenchmarkTruncIndexGet100-6        16676             71246 ns/op           45056 B/op       1184 allocs/op
PASS
ok      github.com/docker/docker/pkg/truncindex 9.759s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkDBGetByPrefix500$ github.com/docker/docker/container
goos: linux
goarch: amd64
pkg: github.com/docker/docker/container
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkDBGetByPrefix500-6         1539            753541 ns/op          169381 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1624            749975 ns/op          169458 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1635            761222 ns/op          169298 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1693            727856 ns/op          169297 B/op       5500 allocs/op
BenchmarkDBGetByPrefix500-6         1874            710813 ns/op          169570 B/op       5500 allocs/op
PASS
ok      github.com/docker/docker/container      6.711s

$ go test -benchmem -run=^$ -count 5 -tags linux -bench ^BenchmarkTruncIndexGet500$ github.com/docker/docker/pkg/truncindex
goos: linux
goarch: amd64
pkg: github.com/docker/docker/pkg/truncindex
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkTruncIndexGet500-6         1934            780328 ns/op          224073 B/op       5929 allocs/op
BenchmarkTruncIndexGet500-6         1713            713935 ns/op          225011 B/op       5937 allocs/op
BenchmarkTruncIndexGet500-6         1780            702847 ns/op          224090 B/op       5943 allocs/op
BenchmarkTruncIndexGet500-6         1736            711086 ns/op          224027 B/op       5929 allocs/op
BenchmarkTruncIndexGet500-6         2448            508694 ns/op          222322 B/op       5914 allocs/op
PASS
ok      github.com/docker/docker/pkg/truncindex 6.877s

Signed-off-by: Djordje Lukic <djordje.lukic@docker.com>

2 files changed, 366 insertions, 0 deletions

diff --git a/container/view.go b/container/view.go
index 962a20b9e1..e061cf4007 100644
--- a/container/view.go
+++ b/container/view.go
@@ -17,6 +17,7 @@ const (
 	memdbContainersTable  = "containers"
 	memdbNamesTable       = "names"
 	memdbIDIndex          = "id"
+	memdbIDIndexPrefix    = "id_prefix"
 	memdbContainerIDIndex = "containerid"
 )
 
@@ -27,6 +28,24 @@ var (
 	ErrNameNotReserved = errors.New("name is not reserved")
 )
 
+var (
+	// ErrEmptyPrefix is an error returned if the prefix was empty.
+	ErrEmptyPrefix = errors.New("Prefix can't be empty")
+
+	// ErrNotExist is returned when ID or its prefix not found in index.
+	ErrNotExist = errors.New("ID does not exist")
+)
+
+// ErrAmbiguousPrefix is returned if the prefix was ambiguous
+// (multiple ids for the prefix).
+type ErrAmbiguousPrefix struct {
+	prefix string
+}
+
+func (e ErrAmbiguousPrefix) Error() string {
+	return fmt.Sprintf("Multiple IDs found with provided prefix: %s", e.prefix)
+}
+
 // Snapshot is a read only view for Containers. It holds all information necessary to serve container queries in a
 // versioned ACID in-memory store.
 type Snapshot struct {
@@ -64,6 +83,8 @@ type ViewDB interface {
 	Save(*Container) error
 	Delete(*Container) error
 
+	GetByPrefix(string) (string, error)
+
 	ReserveName(name, containerID string) error
 	ReleaseName(name string) error
 }
@@ -131,6 +152,38 @@ func NewViewDB() (ViewDB, error) {
 	return &memDB{store: store}, nil
 }
 
+func (db *memDB) GetByPrefix(s string) (string, error) {
+	if s == "" {
+		return "", ErrEmptyPrefix
+	}
+	txn := db.store.Txn(false)
+	iter, err := txn.Get(memdbContainersTable, memdbIDIndexPrefix, s)
+	if err != nil {
+		return "", err
+	}
+
+	var (
+		id string
+	)
+
+	for {
+		item := iter.Next()
+		if item == nil {
+			break
+		}
+		if id != "" {
+			return "", ErrAmbiguousPrefix{prefix: s}
+		}
+		id = item.(*Container).ID
+	}
+
+	if id != "" {
+		return id, nil
+	}
+
+	return "", ErrNotExist
+}
+
 // Snapshot provides a consistent read-only View of the database
 func (db *memDB) Snapshot() View {
 	return &memdbView{
@@ -441,6 +494,20 @@ func (e *containerByIDIndexer) FromArgs(args ...interface{}) ([]byte, error) {
 	return []byte(arg), nil
 }
 
+func (e *containerByIDIndexer) PrefixFromArgs(args ...interface{}) ([]byte, error) {
+	val, err := e.FromArgs(args...)
+	if err != nil {
+		return nil, err
+	}
+
+	// Strip the null terminator, the rest is a prefix
+	n := len(val)
+	if n > 0 {
+		return val[:n-1], nil
+	}
+	return val, nil
+}
+
 // namesByNameIndexer is used to index container name associations by name.
 type namesByNameIndexer struct{}
 
diff --git a/container/view_test.go b/container/view_test.go
index 290282c907..099da49df9 100644
--- a/container/view_test.go
+++ b/container/view_test.go
@@ -1,12 +1,14 @@
 package container // import "github.com/docker/docker/container"
 
 import (
+	"math/rand"
 	"os"
 	"path/filepath"
 	"testing"
 
 	"github.com/docker/docker/api/types"
 	containertypes "github.com/docker/docker/api/types/container"
+	"github.com/docker/docker/pkg/stringid"
 	"github.com/google/uuid"
 	"gotest.tools/v3/assert"
 	is "gotest.tools/v3/assert/cmp"
@@ -183,3 +185,300 @@ func TestViewWithHealthCheck(t *testing.T) {
 		t.Fatalf("expected Health=starting. Got: %+v", s)
 	}
 }
+
+func TestTruncIndex(t *testing.T) {
+	db, err := NewViewDB()
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// Get on an empty index
+	if _, err := db.GetByPrefix("foobar"); err == nil {
+		t.Fatal("Get on an empty index should return an error")
+	}
+
+	id := "99b36c2c326ccc11e726eee6ee78a0baf166ef96"
+	// Add an id
+	if err := db.Save(&Container{ID: id}); err != nil {
+		t.Fatal(err)
+	}
+
+	type testacase struct {
+		name           string
+		input          string
+		expectedResult string
+		expectError    bool
+	}
+
+	for _, tc := range []testacase{
+		{
+			name:        "Get a non-existing id",
+			input:       "abracadabra",
+			expectError: true,
+		},
+		{
+			name:           "Get an empty id",
+			input:          "",
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "Get the exact id",
+			input:          id,
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "The first letter should match",
+			input:          id[:1],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "The first half should match",
+			input:          id[:len(id)/2],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:        "The second half should NOT match",
+			input:       id[len(id)/2:],
+			expectError: true,
+		},
+	} {
+		t.Run(tc.name, func(t *testing.T) {
+			assertIndexGet(t, db, tc.input, tc.expectedResult, tc.expectError)
+		})
+	}
+
+	id2 := id[:6] + "blabla"
+	// Add an id
+	if err := db.Save(&Container{ID: id2}); err != nil {
+		t.Fatal(err)
+	}
+
+	for _, tc := range []testacase{
+		{
+			name:           "id should work",
+			input:          id,
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "id2 should work",
+			input:          id2,
+			expectedResult: id2,
+			expectError:    false,
+		},
+		{
+			name:           "6 characters should conflict",
+			input:          id[:6],
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "4 characters should conflict",
+			input:          id[:4],
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "1 character should conflict",
+			input:          id[:6],
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "7 characters of id should not conflict",
+			input:          id[:7],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "7 characters of id2 should not conflict",
+			input:          id2[:7],
+			expectedResult: id2,
+			expectError:    false,
+		},
+	} {
+		t.Run(tc.name, func(t *testing.T) {
+			assertIndexGet(t, db, tc.input, tc.expectedResult, tc.expectError)
+		})
+	}
+
+	// Deleting id2 should remove conflicts
+	if err := db.Delete(&Container{ID: id2}); err != nil {
+		t.Fatal(err)
+	}
+
+	for _, tc := range []testacase{
+		{
+			name:           "id2 should no longer work",
+			input:          id2,
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "7 characters id2 should no longer work",
+			input:          id2[:7],
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "11 characters id2 should no longer work",
+			input:          id2[:11],
+			expectedResult: "",
+			expectError:    true,
+		},
+		{
+			name:           "conflicts between id[:6] and id2 should be gone",
+			input:          id[:6],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "conflicts between id[:4] and id2 should be gone",
+			input:          id[:4],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "conflicts between id[:1] and id2 should be gone",
+			input:          id[:1],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "non-conflicting 7 character substrings should still not conflict",
+			input:          id[:7],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "non-conflicting 15 character substrings should still not conflict",
+			input:          id[:15],
+			expectedResult: id,
+			expectError:    false,
+		},
+		{
+			name:           "non-conflicting substrings should still not conflict",
+			input:          id,
+			expectedResult: id,
+			expectError:    false,
+		},
+	} {
+		t.Run(tc.name, func(t *testing.T) {
+			assertIndexGet(t, db, tc.input, tc.expectedResult, tc.expectError)
+		})
+	}
+}
+
+func assertIndexGet(t *testing.T, snapshot ViewDB, input, expectedResult string, expectError bool) {
+	if result, err := snapshot.GetByPrefix(input); err != nil && !expectError {
+		t.Fatalf("Unexpected error getting '%s': %s", input, err)
+	} else if err == nil && expectError {
+		t.Fatalf("Getting '%s' should return an error, not '%s'", input, result)
+	} else if result != expectedResult {
+		t.Fatalf("Getting '%s' returned '%s' instead of '%s'", input, result, expectedResult)
+	}
+}
+
+func BenchmarkDBAdd100(b *testing.B) {
+	var testSet []string
+	for i := 0; i < 100; i++ {
+		testSet = append(testSet, stringid.GenerateRandomID())
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		db, err := NewViewDB()
+		if err != nil {
+			b.Fatal(err)
+		}
+		for _, id := range testSet {
+			if err := db.Save(&Container{ID: id}); err != nil {
+				b.Fatal(err)
+			}
+		}
+	}
+}
+
+func BenchmarkDBGetByPrefix100(b *testing.B) {
+	var testSet []string
+	var testKeys []string
+	for i := 0; i < 100; i++ {
+		testSet = append(testSet, stringid.GenerateRandomID())
+	}
+	db, err := NewViewDB()
+	if err != nil {
+		b.Fatal(err)
+	}
+	for _, id := range testSet {
+		if err := db.Save(&Container{ID: id}); err != nil {
+			b.Fatal(err)
+		}
+		l := rand.Intn(12) + 12
+		testKeys = append(testKeys, id[:l])
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		for _, id := range testKeys {
+			if res, err := db.GetByPrefix(id); err != nil {
+				b.Fatal(res, err)
+			}
+		}
+	}
+}
+
+func BenchmarkDBGetByPrefix250(b *testing.B) {
+	var testSet []string
+	var testKeys []string
+	for i := 0; i < 250; i++ {
+		testSet = append(testSet, stringid.GenerateRandomID())
+	}
+	db, err := NewViewDB()
+	if err != nil {
+		b.Fatal(err)
+	}
+	for _, id := range testSet {
+		if err := db.Save(&Container{ID: id}); err != nil {
+			b.Fatal(err)
+		}
+		l := rand.Intn(12) + 12
+		testKeys = append(testKeys, id[:l])
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		for _, id := range testKeys {
+			if res, err := db.GetByPrefix(id); err != nil {
+				b.Fatal(res, err)
+			}
+		}
+	}
+}
+
+func BenchmarkDBGetByPrefix500(b *testing.B) {
+	var testSet []string
+	var testKeys []string
+	for i := 0; i < 500; i++ {
+		testSet = append(testSet, stringid.GenerateRandomID())
+	}
+	db, err := NewViewDB()
+	if err != nil {
+		b.Fatal(err)
+	}
+	for _, id := range testSet {
+		if err := db.Save(&Container{ID: id}); err != nil {
+			b.Fatal(err)
+		}
+		l := rand.Intn(12) + 12
+		testKeys = append(testKeys, id[:l])
+	}
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		for _, id := range testKeys {
+			if res, err := db.GetByPrefix(id); err != nil {
+				b.Fatal(res, err)
+			}
+		}
+	}
+}