1454 lines
42 KiB
Go
1454 lines
42 KiB
Go
package pilorama
|
|
|
|
import (
|
|
"context"
|
|
"crypto/rand"
|
|
"fmt"
|
|
mrand "math/rand"
|
|
"path/filepath"
|
|
"strconv"
|
|
"strings"
|
|
"sync"
|
|
"testing"
|
|
"time"
|
|
|
|
"git.frostfs.info/TrueCloudLab/frostfs-node/pkg/local_object_storage/shard/mode"
|
|
cidSDK "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/container/id"
|
|
cidtest "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/container/id/test"
|
|
objectSDK "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/object"
|
|
"github.com/google/uuid"
|
|
"github.com/stretchr/testify/require"
|
|
"golang.org/x/sync/errgroup"
|
|
)
|
|
|
|
var providers = []struct {
|
|
name string
|
|
construct func(t testing.TB, opts ...Option) ForestStorage
|
|
}{
|
|
{"inmemory", func(t testing.TB, _ ...Option) ForestStorage {
|
|
f := NewMemoryForest()
|
|
require.NoError(t, f.Open(context.Background(), mode.ReadWrite))
|
|
require.NoError(t, f.Init())
|
|
return f
|
|
}},
|
|
{"bbolt", func(t testing.TB, opts ...Option) ForestStorage {
|
|
f := NewBoltForest(
|
|
append([]Option{
|
|
WithPath(filepath.Join(t.TempDir(), "test.db")),
|
|
WithMaxBatchSize(1),
|
|
}, opts...)...)
|
|
require.NoError(t, f.Open(context.Background(), mode.ReadWrite))
|
|
require.NoError(t, f.Init())
|
|
return f
|
|
}},
|
|
}
|
|
|
|
func testMeta(t *testing.T, f Forest, cid cidSDK.ID, treeID string, nodeID, parentID Node, expected Meta) {
|
|
actualMeta, actualParent, err := f.TreeGetMeta(context.Background(), cid, treeID, nodeID)
|
|
require.NoError(t, err)
|
|
require.Equal(t, parentID, actualParent)
|
|
require.Equal(t, expected, actualMeta)
|
|
}
|
|
|
|
func TestForest_TreeMove(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeMove(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeMove(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
|
|
meta := []KeyValue{
|
|
{Key: AttributeVersion, Value: []byte("XXX")},
|
|
{Key: AttributeFilename, Value: []byte("file.txt")},
|
|
}
|
|
lm, err := s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "to"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 3, len(lm))
|
|
|
|
nodeID := lm[2].Child
|
|
t.Run("invalid descriptor", func(t *testing.T) {
|
|
_, err = s.TreeMove(context.Background(), CIDDescriptor{cid, 0, 0}, treeID, &Move{
|
|
Parent: lm[1].Child,
|
|
Meta: Meta{Items: append(meta, KeyValue{Key: "NewKey", Value: []byte("NewValue")})},
|
|
Child: nodeID,
|
|
})
|
|
require.ErrorIs(t, err, ErrInvalidCIDDescriptor)
|
|
})
|
|
t.Run("same parent, update meta", func(t *testing.T) {
|
|
res, err := s.TreeMove(context.Background(), d, treeID, &Move{
|
|
Parent: lm[1].Child,
|
|
Meta: Meta{Items: append(meta, KeyValue{Key: "NewKey", Value: []byte("NewValue")})},
|
|
Child: nodeID,
|
|
})
|
|
require.NoError(t, err)
|
|
require.Equal(t, res.Child, nodeID)
|
|
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "to", "file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.ElementsMatch(t, []Node{nodeID}, nodes)
|
|
})
|
|
t.Run("different parent", func(t *testing.T) {
|
|
res, err := s.TreeMove(context.Background(), d, treeID, &Move{
|
|
Parent: RootID,
|
|
Meta: Meta{Items: append(meta, KeyValue{Key: "NewKey", Value: []byte("NewValue")})},
|
|
Child: nodeID,
|
|
})
|
|
require.NoError(t, err)
|
|
require.Equal(t, res.Child, nodeID)
|
|
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "to", "file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.True(t, len(nodes) == 0)
|
|
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.ElementsMatch(t, []Node{nodeID}, nodes)
|
|
})
|
|
}
|
|
|
|
func TestMemoryForest_TreeGetChildren(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeGetChildren(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeGetChildren(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
|
|
treeAdd := func(t *testing.T, child, parent Node) {
|
|
_, err := s.TreeMove(context.Background(), d, treeID, &Move{
|
|
Parent: parent,
|
|
Child: child,
|
|
})
|
|
require.NoError(t, err)
|
|
}
|
|
|
|
// 0
|
|
// |- 10
|
|
// | |- 3
|
|
// | |- 6
|
|
// | |- 11
|
|
// |- 2
|
|
// |- 7
|
|
treeAdd(t, 10, 0)
|
|
treeAdd(t, 3, 10)
|
|
treeAdd(t, 6, 10)
|
|
treeAdd(t, 11, 6)
|
|
treeAdd(t, 2, 0)
|
|
treeAdd(t, 7, 0)
|
|
|
|
testGetChildren := func(t *testing.T, nodeID Node, expected []NodeInfo) {
|
|
actual, err := s.TreeGetChildren(context.Background(), cid, treeID, nodeID)
|
|
require.NoError(t, err)
|
|
require.ElementsMatch(t, expected, actual)
|
|
}
|
|
|
|
testGetChildren(t, 0, []NodeInfo{
|
|
{ID: 10, Meta: Meta{Time: 1, Items: []KeyValue{}}},
|
|
{ID: 2, Meta: Meta{Time: 5, Items: []KeyValue{}}},
|
|
{ID: 7, Meta: Meta{Time: 6, Items: []KeyValue{}}},
|
|
})
|
|
testGetChildren(t, 10, []NodeInfo{
|
|
{ID: 3, ParentID: 10, Meta: Meta{Time: 2, Items: []KeyValue{}}},
|
|
{ID: 6, ParentID: 10, Meta: Meta{Time: 3, Items: []KeyValue{}}},
|
|
})
|
|
testGetChildren(t, 3, nil)
|
|
testGetChildren(t, 6, []NodeInfo{{ID: 11, ParentID: 6, Meta: Meta{Time: 4, Items: []KeyValue{}}}})
|
|
testGetChildren(t, 11, nil)
|
|
testGetChildren(t, 2, nil)
|
|
testGetChildren(t, 7, nil)
|
|
t.Run("missing node", func(t *testing.T) {
|
|
testGetChildren(t, 42, nil)
|
|
})
|
|
t.Run("missing tree", func(t *testing.T) {
|
|
_, err := s.TreeGetChildren(context.Background(), cid, treeID+"123", 0)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
}
|
|
|
|
func BenchmarkForestSortedIteration(b *testing.B) {
|
|
for i := range providers {
|
|
if providers[i].name == "inmemory" {
|
|
continue
|
|
}
|
|
|
|
cnr := cidtest.ID()
|
|
treeID := "version"
|
|
f := providers[i].construct(b)
|
|
|
|
const total = 100_000
|
|
d := CIDDescriptor{cnr, 0, 1}
|
|
for i := 0; i < total; i++ {
|
|
u, err := uuid.NewRandom()
|
|
if err != nil {
|
|
b.FailNow()
|
|
}
|
|
|
|
_, err = f.TreeMove(context.Background(), d, treeID, &Move{
|
|
Parent: RootID,
|
|
Child: RootID + Node(i+1),
|
|
Meta: Meta{
|
|
Time: Timestamp(i + 1),
|
|
Items: []KeyValue{{
|
|
Key: AttributeFilename, Value: []byte(u.String()),
|
|
}},
|
|
},
|
|
})
|
|
if err != nil {
|
|
b.FailNow()
|
|
}
|
|
}
|
|
|
|
b.Run(providers[i].name+",root", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
res, _, err := f.TreeSortedByFilename(context.Background(), cnr, treeID, RootID, nil, 100)
|
|
if err != nil || len(res) != 100 {
|
|
b.Fatalf("err %v, count %d", err, len(res))
|
|
}
|
|
}
|
|
})
|
|
b.Run(providers[i].name+",leaf", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
res, _, err := f.TreeSortedByFilename(context.Background(), cnr, treeID, 1, nil, 100)
|
|
if err != nil || len(res) != 0 {
|
|
b.FailNow()
|
|
}
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestForest_TreeSortedIteration(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeSortedIteration(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeSortedIteration(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
treeAdd := func(t *testing.T, ts int, filename string) {
|
|
_, err := s.TreeMove(context.Background(), d, treeID, &Move{
|
|
Child: RootID + uint64(ts),
|
|
Parent: RootID,
|
|
Meta: Meta{
|
|
Time: Timestamp(ts),
|
|
Items: []KeyValue{
|
|
{Key: AttributeFilename, Value: []byte(filename)},
|
|
},
|
|
},
|
|
})
|
|
require.NoError(t, err)
|
|
}
|
|
|
|
const count = 9
|
|
treeAdd(t, 1, "")
|
|
for i := 1; i < count; i++ {
|
|
treeAdd(t, i+1, strconv.Itoa(i+1))
|
|
}
|
|
|
|
var result []NodeInfo
|
|
treeAppend := func(t *testing.T, last *string, count int) *string {
|
|
res, cursor, err := s.TreeSortedByFilename(context.Background(), d.CID, treeID, RootID, last, count)
|
|
require.NoError(t, err)
|
|
result = append(result, res...)
|
|
return cursor
|
|
}
|
|
|
|
last := treeAppend(t, nil, 2)
|
|
last = treeAppend(t, last, 3)
|
|
last = treeAppend(t, last, 0)
|
|
last = treeAppend(t, last, 1)
|
|
_ = treeAppend(t, last, 10)
|
|
|
|
require.Len(t, result, count)
|
|
for i := range result {
|
|
require.Equal(t, RootID+uint64(i+1), result[i].ID)
|
|
if i == 0 {
|
|
require.Equal(t, "", string(result[i].Meta.GetAttr(AttributeFilename)))
|
|
} else {
|
|
require.Equal(t, strconv.Itoa(RootID+i+1), string(result[i].Meta.GetAttr(AttributeFilename)))
|
|
}
|
|
}
|
|
}
|
|
|
|
func TestForest_TreeSortedFilename(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeSortedByFilename(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeSortedByFilename(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
const controlAttr = "control_attr"
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
|
|
treeAddByPath := func(t *testing.T, filename string) {
|
|
path := strings.Split(filename, "/")
|
|
_, err := s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, path[:len(path)-1],
|
|
[]KeyValue{
|
|
{Key: AttributeFilename, Value: []byte(path[len(path)-1])},
|
|
{Key: controlAttr, Value: []byte(filename)},
|
|
},
|
|
)
|
|
require.NoError(t, err)
|
|
}
|
|
|
|
expectAttributes := func(t *testing.T, attr string, expected []string, res []NodeInfo) {
|
|
require.Equal(t, len(expected), len(res))
|
|
|
|
actual := make([]string, len(res))
|
|
for i := range actual {
|
|
actual[i] = string(res[i].Meta.GetAttr(attr))
|
|
}
|
|
require.Equal(t, expected, actual)
|
|
}
|
|
|
|
items := []string{
|
|
"a/bbb/ccc",
|
|
"a/bbb/xxx",
|
|
"a/bbb/z",
|
|
"b/bbb/ccc",
|
|
"b/xxx/z",
|
|
"c",
|
|
}
|
|
|
|
// Ensure we do not depend on insertion order in any way.
|
|
mrand.Shuffle(len(items), func(i, j int) {
|
|
items[i], items[j] = items[j], items[i]
|
|
})
|
|
for i := range items {
|
|
treeAddByPath(t, items[i])
|
|
}
|
|
|
|
getChildren := func(t *testing.T, id Node) []NodeInfo {
|
|
res, _, err := s.TreeSortedByFilename(context.Background(), d.CID, treeID, id, nil, len(items))
|
|
require.NoError(t, err)
|
|
return res
|
|
}
|
|
|
|
res := getChildren(t, RootID)
|
|
expectAttributes(t, AttributeFilename, []string{"a", "b", "c"}, res)
|
|
expectAttributes(t, controlAttr, []string{"", "", "c"}, res)
|
|
|
|
{
|
|
ra := getChildren(t, res[0].ID)
|
|
expectAttributes(t, AttributeFilename, []string{"bbb"}, ra)
|
|
expectAttributes(t, controlAttr, []string{""}, ra)
|
|
|
|
rabbb := getChildren(t, ra[0].ID)
|
|
expectAttributes(t, AttributeFilename, []string{"ccc", "xxx", "z"}, rabbb)
|
|
expectAttributes(t, controlAttr, []string{"a/bbb/ccc", "a/bbb/xxx", "a/bbb/z"}, rabbb)
|
|
}
|
|
{
|
|
rb := getChildren(t, res[1].ID)
|
|
expectAttributes(t, AttributeFilename, []string{"bbb", "xxx"}, rb)
|
|
expectAttributes(t, controlAttr, []string{"", ""}, rb)
|
|
|
|
rbbbb := getChildren(t, rb[0].ID)
|
|
expectAttributes(t, AttributeFilename, []string{"ccc"}, rbbbb)
|
|
expectAttributes(t, controlAttr, []string{"b/bbb/ccc"}, rbbbb)
|
|
|
|
rbxxx := getChildren(t, rb[1].ID)
|
|
expectAttributes(t, AttributeFilename, []string{"z"}, rbxxx)
|
|
expectAttributes(t, controlAttr, []string{"b/xxx/z"}, rbxxx)
|
|
}
|
|
{
|
|
rc := getChildren(t, res[2].ID)
|
|
require.Len(t, rc, 0)
|
|
}
|
|
}
|
|
|
|
func TestForest_TreeDrop(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeDrop(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeDrop(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
const cidsSize = 3
|
|
var cids [cidsSize]cidSDK.ID
|
|
|
|
for i := range cids {
|
|
cids[i] = cidtest.ID()
|
|
}
|
|
cid := cids[0]
|
|
|
|
t.Run("return nil if not found", func(t *testing.T) {
|
|
require.ErrorIs(t, s.TreeDrop(context.Background(), cid, "123"), ErrTreeNotFound)
|
|
})
|
|
|
|
require.NoError(t, s.TreeDrop(context.Background(), cid, ""))
|
|
|
|
trees := []string{"tree1", "tree2"}
|
|
var descs [cidsSize]CIDDescriptor
|
|
for i := range descs {
|
|
descs[i] = CIDDescriptor{cids[i], 0, 1}
|
|
}
|
|
d := descs[0]
|
|
for i := range trees {
|
|
_, err := s.TreeAddByPath(context.Background(), d, trees[i], AttributeFilename, []string{"path"},
|
|
[]KeyValue{{Key: "TreeName", Value: []byte(trees[i])}})
|
|
require.NoError(t, err)
|
|
}
|
|
|
|
err := s.TreeDrop(context.Background(), cid, trees[0])
|
|
require.NoError(t, err)
|
|
|
|
_, err = s.TreeGetByPath(context.Background(), cid, trees[0], AttributeFilename, []string{"path"}, true)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
|
|
_, err = s.TreeGetByPath(context.Background(), cid, trees[1], AttributeFilename, []string{"path"}, true)
|
|
require.NoError(t, err)
|
|
|
|
for j := range descs {
|
|
for i := range trees {
|
|
_, err := s.TreeAddByPath(context.Background(), descs[j], trees[i], AttributeFilename, []string{"path"},
|
|
[]KeyValue{{Key: "TreeName", Value: []byte(trees[i])}})
|
|
require.NoError(t, err)
|
|
}
|
|
}
|
|
list, err := s.TreeList(context.Background(), cid)
|
|
require.NoError(t, err)
|
|
require.NotEmpty(t, list)
|
|
|
|
require.NoError(t, s.TreeDrop(context.Background(), cid, ""))
|
|
|
|
list, err = s.TreeList(context.Background(), cid)
|
|
require.NoError(t, err)
|
|
require.Empty(t, list)
|
|
|
|
for j := 1; j < len(cids); j++ {
|
|
list, err = s.TreeList(context.Background(), cids[j])
|
|
require.NoError(t, err)
|
|
require.Equal(t, len(list), len(trees))
|
|
}
|
|
}
|
|
|
|
func TestForest_TreeAdd(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeAdd(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeAdd(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
|
|
meta := []KeyValue{
|
|
{Key: AttributeVersion, Value: []byte("XXX")},
|
|
{Key: AttributeFilename, Value: []byte("file.txt")},
|
|
}
|
|
m := &Move{
|
|
Parent: RootID,
|
|
Child: RootID,
|
|
Meta: Meta{Items: meta},
|
|
}
|
|
|
|
t.Run("invalid descriptor", func(t *testing.T) {
|
|
_, err := s.TreeMove(context.Background(), CIDDescriptor{cid, 0, 0}, treeID, m)
|
|
require.ErrorIs(t, err, ErrInvalidCIDDescriptor)
|
|
})
|
|
|
|
lm, err := s.TreeMove(context.Background(), d, treeID, m)
|
|
require.NoError(t, err)
|
|
|
|
testMeta(t, s, cid, treeID, lm.Child, lm.Parent, Meta{Time: lm.Time, Items: meta})
|
|
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.ElementsMatch(t, []Node{lm.Child}, nodes)
|
|
|
|
t.Run("other trees are unaffected", func(t *testing.T) {
|
|
_, err := s.TreeGetByPath(context.Background(), cid, treeID+"123", AttributeFilename, []string{"file.txt"}, false)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
|
|
_, _, err = s.TreeGetMeta(context.Background(), cid, treeID+"123", 0)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
}
|
|
|
|
func TestForest_TreeAddByPath(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeAddByPath(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeAddByPath(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cid := cidtest.ID()
|
|
d := CIDDescriptor{cid, 0, 1}
|
|
treeID := "version"
|
|
|
|
meta := []KeyValue{
|
|
{Key: AttributeVersion, Value: []byte("XXX")},
|
|
{Key: AttributeFilename, Value: []byte("file.txt")},
|
|
}
|
|
|
|
t.Run("invalid descriptor", func(t *testing.T) {
|
|
_, err := s.TreeAddByPath(context.Background(), CIDDescriptor{cid, 0, 0}, treeID, AttributeFilename, []string{"yyy"}, meta)
|
|
require.ErrorIs(t, err, ErrInvalidCIDDescriptor)
|
|
})
|
|
t.Run("invalid attribute", func(t *testing.T) {
|
|
_, err := s.TreeAddByPath(context.Background(), d, treeID, AttributeVersion, []string{"yyy"}, meta)
|
|
require.ErrorIs(t, err, ErrNotPathAttribute)
|
|
})
|
|
|
|
lm, err := s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "to"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 3, len(lm))
|
|
testMeta(t, s, cid, treeID, lm[0].Child, lm[0].Parent, Meta{Time: lm[0].Time, Items: []KeyValue{{AttributeFilename, []byte("path")}}})
|
|
testMeta(t, s, cid, treeID, lm[1].Child, lm[1].Parent, Meta{Time: lm[1].Time, Items: []KeyValue{{AttributeFilename, []byte("to")}}})
|
|
|
|
firstID := lm[2].Child
|
|
testMeta(t, s, cid, treeID, firstID, lm[2].Parent, Meta{Time: lm[2].Time, Items: meta})
|
|
|
|
// TreeAddByPath must return operations in increasing time order.
|
|
require.True(t, lm[0].Time < lm[1].Time)
|
|
require.True(t, lm[1].Time < lm[2].Time)
|
|
|
|
meta[0].Value = []byte("YYY")
|
|
lm, err = s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "to"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 1, len(lm))
|
|
|
|
secondID := lm[0].Child
|
|
testMeta(t, s, cid, treeID, secondID, lm[0].Parent, Meta{Time: lm[0].Time, Items: meta})
|
|
|
|
t.Run("get versions", func(t *testing.T) {
|
|
// All versions.
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "to", "file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.ElementsMatch(t, []Node{firstID, secondID}, nodes)
|
|
|
|
// Latest version.
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "to", "file.txt"}, true)
|
|
require.NoError(t, err)
|
|
require.Equal(t, []Node{secondID}, nodes)
|
|
})
|
|
|
|
meta[0].Value = []byte("ZZZ")
|
|
meta[1].Value = []byte("cat.jpg")
|
|
lm, err = s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "dir"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 2, len(lm))
|
|
testMeta(t, s, cid, treeID, lm[0].Child, lm[0].Parent, Meta{Time: lm[0].Time, Items: []KeyValue{{AttributeFilename, []byte("dir")}}})
|
|
testMeta(t, s, cid, treeID, lm[1].Child, lm[1].Parent, Meta{Time: lm[1].Time, Items: meta})
|
|
|
|
t.Run("create internal nodes", func(t *testing.T) {
|
|
meta[0].Value = []byte("SomeValue")
|
|
meta[1].Value = []byte("another")
|
|
lm, err = s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 1, len(lm))
|
|
|
|
oldMove := lm[0]
|
|
|
|
meta[0].Value = []byte("Leaf")
|
|
meta[1].Value = []byte("file.txt")
|
|
lm, err = s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "another"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 2, len(lm))
|
|
|
|
testMeta(t, s, cid, treeID, lm[0].Child, lm[0].Parent,
|
|
Meta{Time: lm[0].Time, Items: []KeyValue{{AttributeFilename, []byte("another")}}})
|
|
testMeta(t, s, cid, treeID, lm[1].Child, lm[1].Parent, Meta{Time: lm[1].Time, Items: meta})
|
|
|
|
require.NotEqual(t, lm[0].Child, oldMove.Child)
|
|
testMeta(t, s, cid, treeID, oldMove.Child, oldMove.Parent,
|
|
Meta{Time: oldMove.Time, Items: []KeyValue{
|
|
{AttributeVersion, []byte("SomeValue")},
|
|
{AttributeFilename, []byte("another")},
|
|
}})
|
|
|
|
t.Run("get by path", func(t *testing.T) {
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "another"}, false)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 2, len(nodes))
|
|
require.ElementsMatch(t, []Node{lm[0].Child, oldMove.Child}, nodes)
|
|
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"path", "another", "file.txt"}, false)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 1, len(nodes))
|
|
require.Equal(t, lm[1].Child, nodes[0])
|
|
})
|
|
})
|
|
|
|
t.Run("empty component", func(t *testing.T) {
|
|
meta := []KeyValue{
|
|
{Key: AttributeVersion, Value: []byte("XXX")},
|
|
{Key: AttributeFilename, Value: []byte{}},
|
|
}
|
|
lm, err := s.TreeAddByPath(context.Background(), d, treeID, AttributeFilename, []string{"path", "to"}, meta)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 1, len(lm))
|
|
|
|
nodes, err := s.TreeGetByPath(context.Background(), d.CID, treeID, AttributeFilename, []string{"path", "to", ""}, false)
|
|
require.NoError(t, err)
|
|
require.Equal(t, 1, len(nodes))
|
|
require.Equal(t, lm[0].Child, nodes[0])
|
|
})
|
|
}
|
|
|
|
func TestForest_Apply(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeApply(t, providers[i].construct)
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeApply(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage) {
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
testApply := func(t *testing.T, s Forest, child, parent Node, meta Meta) {
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &Move{
|
|
Child: child,
|
|
Parent: parent,
|
|
Meta: meta,
|
|
}, false))
|
|
}
|
|
|
|
t.Run("add a child, then insert a parent removal", func(t *testing.T) {
|
|
s := constructor(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
testApply(t, s, 10, 0, Meta{Time: 1, Items: []KeyValue{{"grand", []byte{1}}}})
|
|
|
|
meta := Meta{Time: 3, Items: []KeyValue{{"child", []byte{3}}}}
|
|
testApply(t, s, 11, 10, meta)
|
|
testMeta(t, s, cid, treeID, 11, 10, meta)
|
|
|
|
testApply(t, s, 10, TrashID, Meta{Time: 2, Items: []KeyValue{{"parent", []byte{2}}}})
|
|
testMeta(t, s, cid, treeID, 11, 10, meta)
|
|
})
|
|
t.Run("add a child to non-existent parent, then add a parent", func(t *testing.T) {
|
|
s := constructor(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
meta := Meta{Time: 1, Items: []KeyValue{{"child", []byte{3}}}}
|
|
testApply(t, s, 11, 10, meta)
|
|
testMeta(t, s, cid, treeID, 11, 10, meta)
|
|
|
|
testApply(t, s, 10, 0, Meta{Time: 2, Items: []KeyValue{{"grand", []byte{1}}}})
|
|
testMeta(t, s, cid, treeID, 11, 10, meta)
|
|
})
|
|
}
|
|
|
|
func TestForest_ApplySameOperation(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
parallel := providers[i].name != "inmemory"
|
|
testForestApplySameOperation(t, providers[i].construct, parallel)
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestApplySameOperation(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage, parallel bool) {
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
batchSize := 3
|
|
ctx := context.Background()
|
|
errG, _ := errgroup.WithContext(ctx)
|
|
if !parallel {
|
|
batchSize = 1
|
|
errG.SetLimit(1)
|
|
}
|
|
|
|
meta := []Meta{
|
|
{Time: 1, Items: []KeyValue{{AttributeFilename, []byte("1")}, {"attr", []byte{1}}}},
|
|
{Time: 2, Items: []KeyValue{{AttributeFilename, []byte("2")}, {"attr", []byte{1}}}},
|
|
{Time: 3, Items: []KeyValue{{AttributeFilename, []byte("3")}, {"attr", []byte{1}}}},
|
|
}
|
|
logs := []Move{
|
|
{
|
|
Child: 1,
|
|
Parent: RootID,
|
|
Meta: meta[0],
|
|
},
|
|
{
|
|
Child: 2,
|
|
Parent: 1,
|
|
Meta: meta[1],
|
|
},
|
|
{
|
|
Child: 1,
|
|
Parent: 2,
|
|
Meta: meta[2],
|
|
},
|
|
}
|
|
|
|
check := func(t *testing.T, s Forest) {
|
|
testMeta(t, s, cid, treeID, 1, RootID, meta[0])
|
|
testMeta(t, s, cid, treeID, 2, 1, meta[1])
|
|
|
|
nodes, err := s.TreeGetChildren(ctx, cid, treeID, RootID)
|
|
require.NoError(t, err)
|
|
require.Equal(t, []NodeInfo{{ID: 1, ParentID: RootID, Meta: meta[0]}}, nodes)
|
|
|
|
nodes, err = s.TreeGetChildren(ctx, cid, treeID, 1)
|
|
require.NoError(t, err)
|
|
require.Equal(t, []NodeInfo{{ID: 2, ParentID: 1, Meta: meta[1]}}, nodes)
|
|
}
|
|
|
|
t.Run("expected", func(t *testing.T) {
|
|
s := constructor(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
for i := range logs {
|
|
require.NoError(t, s.TreeApply(ctx, cid, treeID, &logs[i], false))
|
|
}
|
|
check(t, s)
|
|
})
|
|
|
|
s := constructor(t, WithMaxBatchSize(batchSize))
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
require.NoError(t, s.TreeApply(ctx, cid, treeID, &logs[0], false))
|
|
for i := 0; i < batchSize; i++ {
|
|
errG.Go(func() error {
|
|
return s.TreeApply(ctx, cid, treeID, &logs[2], false)
|
|
})
|
|
}
|
|
require.NoError(t, errG.Wait())
|
|
require.NoError(t, s.TreeApply(ctx, cid, treeID, &logs[1], false))
|
|
check(t, s)
|
|
}
|
|
|
|
func TestForest_GetOpLog(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeGetOpLog(t, providers[i].construct)
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeGetOpLog(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage) {
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
logs := []Move{
|
|
{
|
|
Meta: Meta{Time: 4, Items: []KeyValue{{"grand", []byte{1}}}},
|
|
Child: 1,
|
|
},
|
|
{
|
|
Meta: Meta{Time: 5, Items: []KeyValue{{"second", []byte{1, 2, 3}}}},
|
|
Child: 4,
|
|
},
|
|
{
|
|
Parent: 10,
|
|
Meta: Meta{Time: 256 + 4, Items: []KeyValue{}}, // make sure keys are big-endian
|
|
Child: 11,
|
|
},
|
|
}
|
|
|
|
s := constructor(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
t.Run("empty log, no panic", func(t *testing.T) {
|
|
_, err := s.TreeGetOpLog(context.Background(), cid, treeID, 0)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
|
|
for i := range logs {
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &logs[i], false))
|
|
}
|
|
|
|
testGetOpLog := func(t *testing.T, height uint64, m Move) {
|
|
lm, err := s.TreeGetOpLog(context.Background(), cid, treeID, height)
|
|
require.NoError(t, err)
|
|
require.Equal(t, m, lm)
|
|
}
|
|
|
|
testGetOpLog(t, 0, logs[0])
|
|
testGetOpLog(t, 4, logs[0])
|
|
testGetOpLog(t, 5, logs[1])
|
|
testGetOpLog(t, 6, logs[2])
|
|
testGetOpLog(t, 260, logs[2])
|
|
t.Run("missing entry", func(t *testing.T) {
|
|
testGetOpLog(t, 261, Move{})
|
|
})
|
|
t.Run("missing tree", func(t *testing.T) {
|
|
_, err := s.TreeGetOpLog(context.Background(), cid, treeID+"123", 4)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
}
|
|
|
|
func TestForest_TreeExists(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeExists(t, providers[i].construct)
|
|
})
|
|
}
|
|
}
|
|
|
|
func testForestTreeExists(t *testing.T, constructor func(t testing.TB, opts ...Option) ForestStorage) {
|
|
s := constructor(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
checkExists := func(t *testing.T, expected bool, cid cidSDK.ID, treeID string) {
|
|
actual, err := s.TreeExists(context.Background(), cid, treeID)
|
|
require.NoError(t, err)
|
|
require.Equal(t, expected, actual)
|
|
}
|
|
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
t.Run("empty state, no panic", func(t *testing.T) {
|
|
checkExists(t, false, cid, treeID)
|
|
})
|
|
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &Move{Meta: Meta{Time: 11}, Parent: 0, Child: 1}, false))
|
|
checkExists(t, true, cid, treeID)
|
|
|
|
height, err := s.TreeHeight(context.Background(), cid, treeID)
|
|
require.NoError(t, err)
|
|
require.EqualValues(t, 11, height)
|
|
|
|
checkExists(t, false, cidtest.ID(), treeID) // different CID, same tree
|
|
|
|
_, err = s.TreeHeight(context.Background(), cidtest.ID(), treeID)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
|
|
checkExists(t, false, cid, "another tree") // same CID, different tree
|
|
|
|
t.Run("can be removed", func(t *testing.T) {
|
|
require.NoError(t, s.TreeDrop(context.Background(), cid, treeID))
|
|
checkExists(t, false, cid, treeID)
|
|
})
|
|
}
|
|
|
|
func TestApplyTricky1(t *testing.T) {
|
|
ops := []Move{
|
|
{
|
|
Parent: 1,
|
|
Meta: Meta{Time: 100},
|
|
Child: 2,
|
|
},
|
|
{
|
|
Parent: 0,
|
|
Meta: Meta{Time: 80},
|
|
Child: 1,
|
|
},
|
|
}
|
|
|
|
expected := []struct{ child, parent Node }{
|
|
{1, 0},
|
|
{2, 1},
|
|
}
|
|
|
|
treeID := "version"
|
|
cid := cidtest.ID()
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
s := providers[i].construct(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
for i := range ops {
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &ops[i], false))
|
|
}
|
|
|
|
for i := range expected {
|
|
_, parent, err := s.TreeGetMeta(context.Background(), cid, treeID, expected[i].child)
|
|
require.NoError(t, err)
|
|
require.Equal(t, expected[i].parent, parent)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestApplyTricky2(t *testing.T) {
|
|
// Apply operations in the reverse order and then insert an operation in the middle
|
|
// so that previous "old" parent becomes invalid.
|
|
ops := []Move{
|
|
{
|
|
Parent: 10000,
|
|
Meta: Meta{Time: 100},
|
|
Child: 5,
|
|
},
|
|
{
|
|
Parent: 3,
|
|
Meta: Meta{Time: 80},
|
|
Child: 5,
|
|
},
|
|
{
|
|
Parent: 5,
|
|
Meta: Meta{Time: 40},
|
|
Child: 3,
|
|
},
|
|
{
|
|
Parent: 5,
|
|
Meta: Meta{Time: 60},
|
|
Child: 1,
|
|
},
|
|
{
|
|
Parent: 1,
|
|
Meta: Meta{Time: 90},
|
|
Child: 2,
|
|
},
|
|
{
|
|
Parent: 0,
|
|
Meta: Meta{Time: 10},
|
|
Child: 5,
|
|
},
|
|
}
|
|
|
|
expected := []struct{ child, parent Node }{
|
|
{5, 10_000},
|
|
{3, 5},
|
|
{2, 1},
|
|
{1, 5},
|
|
}
|
|
|
|
treeID := "version"
|
|
cid := cidtest.ID()
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
s := providers[i].construct(t)
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
for i := range ops {
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &ops[i], false))
|
|
}
|
|
|
|
for i := range expected {
|
|
_, parent, err := s.TreeGetMeta(context.Background(), cid, treeID, expected[i].child)
|
|
require.NoError(t, err)
|
|
require.Equal(t, expected[i].parent, parent)
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestForest_ApplyRandom(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeApplyRandom(t, providers[i].construct)
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestForest_ParallelApply(t *testing.T) {
|
|
for i := range providers {
|
|
if providers[i].name == "inmemory" {
|
|
continue
|
|
}
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testForestTreeParallelApply(t, providers[i].construct, 8, 128, 10)
|
|
})
|
|
}
|
|
}
|
|
|
|
// prepareRandomTree creates a random sequence of operation and applies them to tree.
|
|
// The operations are guaranteed to be applied and returned sorted by `Time`.
|
|
func prepareRandomTree(nodeCount, opCount int) []Move {
|
|
ops := make([]Move, nodeCount+opCount)
|
|
for i := 0; i < nodeCount; i++ {
|
|
ops[i] = Move{
|
|
Parent: 0,
|
|
Meta: Meta{
|
|
Time: Timestamp(i),
|
|
Items: []KeyValue{
|
|
{Key: AttributeFilename, Value: []byte(strconv.Itoa(i))},
|
|
{Value: make([]byte, 10)},
|
|
},
|
|
},
|
|
Child: uint64(i) + 1,
|
|
}
|
|
rand.Read(ops[i].Meta.Items[1].Value)
|
|
}
|
|
|
|
r := mrand.New(mrand.NewSource(time.Now().Unix()))
|
|
for i := nodeCount; i < len(ops); i++ {
|
|
ops[i] = Move{
|
|
Parent: r.Uint64() % uint64(nodeCount+12),
|
|
Meta: Meta{
|
|
Time: Timestamp(i + nodeCount),
|
|
Items: []KeyValue{
|
|
{Key: AttributeFilename, Value: []byte(strconv.Itoa(i))},
|
|
{Value: make([]byte, 10)},
|
|
},
|
|
},
|
|
Child: r.Uint64() % uint64(nodeCount+10),
|
|
}
|
|
if r.Uint32()%5 == 0 {
|
|
ops[i].Parent = TrashID
|
|
}
|
|
rand.Read(ops[i].Meta.Items[1].Value)
|
|
}
|
|
|
|
return ops
|
|
}
|
|
|
|
func compareForests(t *testing.T, expected, actual Forest, cid cidSDK.ID, treeID string, nodeCount int) {
|
|
for i := uint64(0); i < uint64(nodeCount); i++ {
|
|
expectedMeta, expectedParent, err := expected.TreeGetMeta(context.Background(), cid, treeID, i)
|
|
require.NoError(t, err)
|
|
actualMeta, actualParent, err := actual.TreeGetMeta(context.Background(), cid, treeID, i)
|
|
require.NoError(t, err)
|
|
require.Equal(t, expectedParent, actualParent, "node id: %d", i)
|
|
require.Equal(t, expectedMeta, actualMeta, "node id: %d", i)
|
|
|
|
if ma, ok := actual.(*memoryForest); ok {
|
|
me := expected.(*memoryForest)
|
|
require.Equal(t, len(me.treeMap), len(ma.treeMap))
|
|
|
|
for k, sa := range ma.treeMap {
|
|
se, ok := me.treeMap[k]
|
|
require.True(t, ok)
|
|
require.Equal(t, se.operations, sa.operations)
|
|
require.Equal(t, se.infoMap, sa.infoMap)
|
|
}
|
|
require.Equal(t, expected, actual, i)
|
|
}
|
|
}
|
|
}
|
|
|
|
func testForestTreeParallelApply(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage, batchSize, opCount, iterCount int) {
|
|
r := mrand.New(mrand.NewSource(42))
|
|
|
|
const nodeCount = 5
|
|
|
|
ops := prepareRandomTree(nodeCount, opCount)
|
|
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
expected := constructor(t, WithNoSync(true))
|
|
defer func() { require.NoError(t, expected.Close()) }()
|
|
|
|
for i := range ops {
|
|
require.NoError(t, expected.TreeApply(context.Background(), cid, treeID, &ops[i], false))
|
|
}
|
|
|
|
for i := 0; i < iterCount; i++ {
|
|
// Shuffle random operations, leave initialization in place.
|
|
r.Shuffle(len(ops), func(i, j int) { ops[i], ops[j] = ops[j], ops[i] })
|
|
|
|
actual := constructor(t, WithMaxBatchSize(batchSize), WithNoSync(true))
|
|
wg := new(sync.WaitGroup)
|
|
ch := make(chan *Move)
|
|
for i := 0; i < batchSize; i++ {
|
|
wg.Add(1)
|
|
go func() {
|
|
defer wg.Done()
|
|
for op := range ch {
|
|
require.NoError(t, actual.TreeApply(context.Background(), cid, treeID, op, false))
|
|
}
|
|
}()
|
|
}
|
|
|
|
for i := range ops {
|
|
ch <- &ops[i]
|
|
}
|
|
close(ch)
|
|
wg.Wait()
|
|
|
|
compareForests(t, expected, actual, cid, treeID, nodeCount)
|
|
require.NoError(t, actual.Close())
|
|
}
|
|
}
|
|
|
|
func testForestTreeApplyRandom(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage) {
|
|
r := mrand.New(mrand.NewSource(42))
|
|
|
|
const (
|
|
nodeCount = 5
|
|
opCount = 20
|
|
)
|
|
|
|
ops := prepareRandomTree(nodeCount, opCount)
|
|
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
expected := constructor(t, WithNoSync(true))
|
|
defer func() { require.NoError(t, expected.Close()) }()
|
|
|
|
for i := range ops {
|
|
require.NoError(t, expected.TreeApply(context.Background(), cid, treeID, &ops[i], false))
|
|
}
|
|
|
|
const iterCount = 200
|
|
for i := 0; i < iterCount; i++ {
|
|
// Shuffle random operations, leave initialization in place.
|
|
r.Shuffle(len(ops), func(i, j int) { ops[i], ops[j] = ops[j], ops[i] })
|
|
|
|
actual := constructor(t, WithNoSync(true))
|
|
for i := range ops {
|
|
require.NoError(t, actual.TreeApply(context.Background(), cid, treeID, &ops[i], false))
|
|
}
|
|
compareForests(t, expected, actual, cid, treeID, nodeCount)
|
|
require.NoError(t, actual.Close())
|
|
}
|
|
}
|
|
|
|
const benchNodeCount = 1000
|
|
|
|
var batchSizes = []int{1, 2, 4, 8, 16, 32}
|
|
|
|
func BenchmarkApplySequential(b *testing.B) {
|
|
for i := range providers {
|
|
if providers[i].name == "inmemory" { // memory backend is not thread-safe
|
|
continue
|
|
}
|
|
b.Run(providers[i].name, func(b *testing.B) {
|
|
for _, bs := range batchSizes {
|
|
b.Run("batchsize="+strconv.Itoa(bs), func(b *testing.B) {
|
|
r := mrand.New(mrand.NewSource(time.Now().Unix()))
|
|
s := providers[i].construct(b, WithMaxBatchSize(bs))
|
|
defer func() { require.NoError(b, s.Close()) }()
|
|
|
|
benchmarkApply(b, s, func(opCount int) []Move {
|
|
ops := make([]Move, opCount)
|
|
for i := range ops {
|
|
ops[i] = Move{
|
|
Parent: uint64(r.Intn(benchNodeCount)),
|
|
Meta: Meta{
|
|
Time: Timestamp(i),
|
|
Items: []KeyValue{{Value: []byte{0, 1, 2, 3, 4}}},
|
|
},
|
|
Child: uint64(r.Intn(benchNodeCount)),
|
|
}
|
|
}
|
|
return ops
|
|
})
|
|
})
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func BenchmarkApplyReorderLast(b *testing.B) {
|
|
// Group operations in a blocks of 10, order blocks in increasing timestamp order,
|
|
// and operations in a single block in reverse.
|
|
const blockSize = 10
|
|
|
|
for i := range providers {
|
|
if providers[i].name == "inmemory" { // memory backend is not thread-safe
|
|
continue
|
|
}
|
|
b.Run(providers[i].name, func(b *testing.B) {
|
|
for _, bs := range batchSizes {
|
|
b.Run("batchsize="+strconv.Itoa(bs), func(b *testing.B) {
|
|
r := mrand.New(mrand.NewSource(time.Now().Unix()))
|
|
s := providers[i].construct(b, WithMaxBatchSize(bs))
|
|
defer func() { require.NoError(b, s.Close()) }()
|
|
|
|
benchmarkApply(b, s, func(opCount int) []Move {
|
|
ops := make([]Move, opCount)
|
|
for i := range ops {
|
|
ops[i] = Move{
|
|
Parent: uint64(r.Intn(benchNodeCount)),
|
|
Meta: Meta{
|
|
Time: Timestamp(i),
|
|
Items: []KeyValue{{Value: []byte{0, 1, 2, 3, 4}}},
|
|
},
|
|
Child: uint64(r.Intn(benchNodeCount)),
|
|
}
|
|
if i != 0 && i%blockSize == 0 {
|
|
for j := 0; j < blockSize/2; j++ {
|
|
ops[i-j], ops[i+j-blockSize] = ops[i+j-blockSize], ops[i-j]
|
|
}
|
|
}
|
|
}
|
|
return ops
|
|
})
|
|
})
|
|
}
|
|
})
|
|
}
|
|
}
|
|
|
|
func benchmarkApply(b *testing.B, s Forest, genFunc func(int) []Move) {
|
|
ops := genFunc(b.N)
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
ch := make(chan int, b.N)
|
|
for i := 0; i < b.N; i++ {
|
|
ch <- i
|
|
}
|
|
|
|
b.ResetTimer()
|
|
b.ReportAllocs()
|
|
b.SetParallelism(10)
|
|
b.RunParallel(func(pb *testing.PB) {
|
|
for pb.Next() {
|
|
if err := s.TreeApply(context.Background(), cid, treeID, &ops[<-ch], false); err != nil {
|
|
b.Fatalf("error in `Apply`: %v", err)
|
|
}
|
|
}
|
|
})
|
|
}
|
|
|
|
func TestTreeGetByPath(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testTreeGetByPath(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testTreeGetByPath(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
cid := cidtest.ID()
|
|
treeID := "version"
|
|
|
|
// /
|
|
// |- a (1)
|
|
// |- cat1.jpg, Version=TTT (3)
|
|
// |- b (2)
|
|
// |- cat1.jpg, Version=XXX (4)
|
|
// |- cat1.jpg, Version=YYY (5)
|
|
// |- cat2.jpg, Version=ZZZ (6)
|
|
testMove(t, s, 0, 1, 0, cid, treeID, "a", "")
|
|
testMove(t, s, 1, 2, 0, cid, treeID, "b", "")
|
|
testMove(t, s, 2, 3, 1, cid, treeID, "cat1.jpg", "TTT")
|
|
testMove(t, s, 3, 4, 2, cid, treeID, "cat1.jpg", "XXX")
|
|
testMove(t, s, 4, 5, 2, cid, treeID, "cat1.jpg", "YYY")
|
|
testMove(t, s, 5, 6, 2, cid, treeID, "cat2.jpg", "ZZZ")
|
|
|
|
if mf, ok := s.(*memoryForest); ok {
|
|
single := mf.treeMap[cid.String()+"/"+treeID]
|
|
t.Run("test meta", func(t *testing.T) {
|
|
for i := 0; i < 6; i++ {
|
|
require.Equal(t, uint64(i), single.infoMap[Node(i+1)].Meta.Time)
|
|
}
|
|
})
|
|
}
|
|
|
|
t.Run("invalid attribute", func(t *testing.T) {
|
|
_, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeVersion, []string{"", "TTT"}, false)
|
|
require.ErrorIs(t, err, ErrNotPathAttribute)
|
|
})
|
|
|
|
nodes, err := s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"b", "cat1.jpg"}, false)
|
|
require.NoError(t, err)
|
|
require.Equal(t, []Node{4, 5}, nodes)
|
|
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"a", "cat1.jpg"}, false)
|
|
require.Equal(t, []Node{3}, nodes)
|
|
|
|
t.Run("missing child", func(t *testing.T) {
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"a", "cat3.jpg"}, false)
|
|
require.True(t, len(nodes) == 0)
|
|
})
|
|
t.Run("missing parent", func(t *testing.T) {
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, []string{"xyz", "cat1.jpg"}, false)
|
|
require.True(t, len(nodes) == 0)
|
|
})
|
|
t.Run("empty path", func(t *testing.T) {
|
|
nodes, err = s.TreeGetByPath(context.Background(), cid, treeID, AttributeFilename, nil, false)
|
|
require.True(t, len(nodes) == 0)
|
|
})
|
|
}
|
|
|
|
func testMove(t *testing.T, s Forest, ts int, node, parent Node, cid cidSDK.ID, treeID, filename, version string) {
|
|
items := make([]KeyValue, 1, 2)
|
|
items[0] = KeyValue{AttributeFilename, []byte(filename)}
|
|
if version != "" {
|
|
items = append(items, KeyValue{AttributeVersion, []byte(version)})
|
|
}
|
|
|
|
require.NoError(t, s.TreeApply(context.Background(), cid, treeID, &Move{
|
|
Parent: parent,
|
|
Child: node,
|
|
Meta: Meta{
|
|
Time: uint64(ts),
|
|
Items: items,
|
|
},
|
|
}, false))
|
|
}
|
|
|
|
func TestGetTrees(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testTreeGetTrees(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testTreeGetTrees(t *testing.T, s ForestStorage) {
|
|
defer func() { require.NoError(t, s.Close()) }()
|
|
|
|
cids := []cidSDK.ID{cidtest.ID(), cidtest.ID()}
|
|
d := CIDDescriptor{Position: 0, Size: 1}
|
|
|
|
treeIDs := make(map[cidSDK.ID][]string, len(cids))
|
|
for i, cid := range cids {
|
|
treeIDs[cid] = []string{
|
|
fmt.Sprintf("test1_%d", i),
|
|
fmt.Sprintf("test2_%d", i),
|
|
fmt.Sprintf("test3_%d", i),
|
|
fmt.Sprintf("1test_%d", i),
|
|
fmt.Sprintf("2test_%d", i),
|
|
fmt.Sprintf("3test_%d", i),
|
|
"",
|
|
}
|
|
}
|
|
|
|
for _, cid := range cids {
|
|
d.CID = cid
|
|
|
|
for _, treeID := range treeIDs[cid] {
|
|
_, err := s.TreeAddByPath(context.Background(), d, treeID, objectSDK.AttributeFileName, []string{"path"}, nil)
|
|
require.NoError(t, err)
|
|
}
|
|
}
|
|
|
|
for _, cid := range cids {
|
|
d.CID = cid
|
|
|
|
trees, err := s.TreeList(context.Background(), cid)
|
|
require.NoError(t, err)
|
|
|
|
require.ElementsMatch(t, treeIDs[cid], trees)
|
|
}
|
|
}
|
|
|
|
func TestTreeLastSyncHeight(t *testing.T) {
|
|
for i := range providers {
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testTreeLastSyncHeight(t, providers[i].construct(t))
|
|
})
|
|
}
|
|
}
|
|
|
|
func testTreeLastSyncHeight(t *testing.T, f ForestStorage) {
|
|
defer func() { require.NoError(t, f.Close()) }()
|
|
|
|
cnr := cidtest.ID()
|
|
treeID := "someTree"
|
|
|
|
t.Run("ErrNotFound if no log operations are stored for a tree", func(t *testing.T) {
|
|
_, err := f.TreeLastSyncHeight(context.Background(), cnr, treeID)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
|
|
err = f.TreeUpdateLastSyncHeight(context.Background(), cnr, treeID, 1)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
|
|
_, err := f.TreeMove(context.Background(), CIDDescriptor{CID: cnr, Size: 1}, treeID, &Move{
|
|
Parent: RootID,
|
|
Child: 1,
|
|
})
|
|
require.NoError(t, err)
|
|
|
|
h, err := f.TreeLastSyncHeight(context.Background(), cnr, treeID)
|
|
require.NoError(t, err)
|
|
require.EqualValues(t, 0, h)
|
|
|
|
t.Run("separate storages for separate containers", func(t *testing.T) {
|
|
_, err := f.TreeLastSyncHeight(context.Background(), cidtest.ID(), treeID)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
|
|
require.NoError(t, f.TreeUpdateLastSyncHeight(context.Background(), cnr, treeID, 10))
|
|
|
|
h, err = f.TreeLastSyncHeight(context.Background(), cnr, treeID)
|
|
require.NoError(t, err)
|
|
require.EqualValues(t, 10, h)
|
|
|
|
t.Run("removed correctly", func(t *testing.T) {
|
|
require.NoError(t, f.TreeDrop(context.Background(), cnr, treeID))
|
|
|
|
_, err := f.TreeLastSyncHeight(context.Background(), cnr, treeID)
|
|
require.ErrorIs(t, err, ErrTreeNotFound)
|
|
})
|
|
}
|
|
|
|
func TestForest_ListTrees(t *testing.T) {
|
|
for i := range providers {
|
|
i := i
|
|
t.Run(providers[i].name, func(t *testing.T) {
|
|
testTreeListTrees(t, providers[i].construct)
|
|
})
|
|
}
|
|
}
|
|
|
|
func testTreeListTrees(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage) {
|
|
batchSize := 10
|
|
t.Run("empty", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, 0)
|
|
})
|
|
t.Run("count lower than batch size", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, batchSize-1)
|
|
})
|
|
t.Run("count equals batch size", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, batchSize)
|
|
})
|
|
t.Run("count greater than batch size", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, batchSize+1)
|
|
})
|
|
t.Run("count equals multiplied batch size", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, 3*batchSize)
|
|
})
|
|
t.Run("count equals multiplied batch size with addition", func(t *testing.T) {
|
|
testTreeListTreesCount(t, constructor, batchSize, 3*batchSize+batchSize/2)
|
|
})
|
|
}
|
|
|
|
func testTreeListTreesCount(t *testing.T, constructor func(t testing.TB, _ ...Option) ForestStorage, batchSize, count int) {
|
|
f := constructor(t)
|
|
var expected []ContainerIDTreeID
|
|
|
|
treeIDs := []string{"version", "system", "s", "avada kedavra"}
|
|
for i := 0; i < count; i++ {
|
|
cid := cidtest.ID()
|
|
treeID := treeIDs[i%len(treeIDs)]
|
|
expected = append(expected, ContainerIDTreeID{
|
|
CID: cid,
|
|
TreeID: treeID,
|
|
})
|
|
|
|
ops := prepareRandomTree(5, 5)
|
|
for _, op := range ops {
|
|
require.NoError(t, f.TreeApply(context.Background(), cid, treeID, &op, false))
|
|
}
|
|
}
|
|
|
|
actual, err := treeListAll(context.Background(), f, batchSize)
|
|
require.NoError(t, err)
|
|
|
|
require.ElementsMatch(t, expected, actual)
|
|
}
|