GetSubTree with sort order does not return more than 1000 elements with the same FileName attribute #1642

New issue

Closed

opened 2025-02-11 15:13:08 +00:00 by alexvanin · 2 comments

alexvanin commented

2025-02-11 15:13:08 +00:00

Owner

Expected Behavior

GetSubTree RPC returns all available nodes if they have non-empty FileName attribute

Current Behavior

GetSubTree RPC returns up to 1000 nodes for nodes with the same non-empty FileName attribute.

Steps to Reproduce (for bugs)

Create container
Call AddByPath more than 1000 times with the same FileName attribute
Try to list all these nodes with GetSubTree

import (
        "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool"
        "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool/tree"
)
...
poolInitParams := tree.InitParameters{}
poolInitParams.AddNode(pool.NewNodeParam(1, "127.0.0.1:8080", 1))
poolInitParams.SetKey(key)

ctx := context.Background()

cli, err := tree.NewPool(poolInitParams)
require.NoError(t, err)
err = cli.Dial(ctx)
require.NoError(t, err)

var cnrID cid.ID
err = cnrID.DecodeString("8BNKcqJ1aFmQqUukCtMoUYsxMSXE1jkAK6EZbesvv2cY")
require.NoError(t, err)

const treeID = "versions"
const n = 2000

for i := 0; i < n; i++ {
        path := []string{"dir"}

        _, err = cli.AddNodeByPath(ctx, tree.AddNodeByPathParams{
                CID:    cnrID,  
                TreeID: treeID, 
                Path:   path,   
                Meta: map[string]string{
                        "FileName": "same-version",
                        "id":       fmt.Sprintf("%d", i),
                },      
        })      
        require.NoError(t, err)
}

rdr, err := cli.GetSubTree(ctx, tree.GetSubTreeParams{
        CID:    cnrID,  
        TreeID: treeID, 
        Order:  tree.AscendingOrder,
})
require.NoError(t, err)

elements, err := rdr.ReadAll()
require.NoError(t, err)

require.Len(t, elements, n+2)

Context

S3 gateway may store multiple versions of the same object, so these tree node all have the same FilePath attribute but different object id in the meta. When gate tries to list all available versions, it does not show more than 1000 versions of the same object. In the meantime, it works as expected when FileName attribute is different.

We've already met this issue with 1000 objects while listing multipart data: TrueCloudLab/frostfs-s3-gw#472. Multipart tree nodes does not have FileName attribute so we had to disable sorting to return more than 1000 objects. However this is not the case now.

Regression

Seems like no.

Your Environment

frostfs-node v0.42.18
frostfs-noed v0.44.8

## Expected Behavior GetSubTree RPC returns all available nodes if they have non-empty `FileName` attribute ## Current Behavior GetSubTree RPC returns up to 1000 nodes for nodes with the same non-empty `FileName` attribute. ## Steps to Reproduce (for bugs) 1. Create container 2. Call AddByPath more than 1000 times with the same FileName attribute 3. Try to list all these nodes with GetSubTree ```go import ( "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool" "git.frostfs.info/TrueCloudLab/frostfs-sdk-go/pool/tree" ) ... poolInitParams := tree.InitParameters{} poolInitParams.AddNode(pool.NewNodeParam(1, "127.0.0.1:8080", 1)) poolInitParams.SetKey(key) ctx := context.Background() cli, err := tree.NewPool(poolInitParams) require.NoError(t, err) err = cli.Dial(ctx) require.NoError(t, err) var cnrID cid.ID err = cnrID.DecodeString("8BNKcqJ1aFmQqUukCtMoUYsxMSXE1jkAK6EZbesvv2cY") require.NoError(t, err) const treeID = "versions" const n = 2000 for i := 0; i < n; i++ { path := []string{"dir"} _, err = cli.AddNodeByPath(ctx, tree.AddNodeByPathParams{ CID: cnrID, TreeID: treeID, Path: path, Meta: map[string]string{ "FileName": "same-version", "id": fmt.Sprintf("%d", i), }, }) require.NoError(t, err) } rdr, err := cli.GetSubTree(ctx, tree.GetSubTreeParams{ CID: cnrID, TreeID: treeID, Order: tree.AscendingOrder, }) require.NoError(t, err) elements, err := rdr.ReadAll() require.NoError(t, err) require.Len(t, elements, n+2) ``` ## Context S3 gateway may store multiple versions of the same object, so these tree node all have the same FilePath attribute but different object id in the meta. When gate tries to list all available versions, it does not show more than 1000 versions of the same object. In the meantime, it works as expected when FileName attribute is different. We've already met this issue with 1000 objects while listing multipart data: https://git.frostfs.info/TrueCloudLab/frostfs-s3-gw/pulls/472. Multipart tree nodes does not have `FileName` attribute so we had to disable sorting to return more than 1000 objects. However this is not the case now. ## Regression Seems like no. ## Your Environment frostfs-node v0.42.18 frostfs-noed v0.44.8

alexvanin added the

bug

triage

labels 2025-02-11 15:13:08 +00:00

aarifullin self-assigned this 2025-02-18 06:54:27 +00:00

aarifullin commented

2025-02-19 15:19:27 +00:00

Member

The problem can't be solved so easily. We create "same-version" nodes outgoing from the same parent ID:

              ○ - parentID

○ ○ ○ ○ ○ ○ . . . ○ ○ ○ ○ ○ ○ - children (2000, 3000, 4000)

Let's have a look at getSortedSubTree. The invocation performs depth-traversal.
When parentID is processed here, we go into boltForest.

We pick nodes to the heap
We get 2000 nodes after push
We're cutting result to 1000 nodes. 1000 comes from batchSize
We keep the last tracked filename ("same-version")
If I correctly understand, we're emptying these children here and then we process this parentID again
I suppose at this point the call expects different filename: see but they are the same with 4.
The heap won't push these items, we're losing them

The problem is that fillSortedChildren is aiming to not duplicate results, but can't seek to correct childID to start repicking nodes with the same filename

Temporary solution: increase batch size

The problem can't be solved so easily. We create "same-version" nodes outgoing from the same parent ID: ``` ○ - parentID ○ ○ ○ ○ ○ ○ . . . ○ ○ ○ ○ ○ ○ - children (2000, 3000, 4000) ``` Let's have a look at [getSortedSubTree](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/services/tree/service.go#L415). The invocation performs depth-traversal. When `parentID` is processed [here](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/services/tree/service.go#L482), we go into [boltForest](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1080-L1161). 1. We [pick](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1130) nodes to the [heap](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1130) 2. We get 2000 nodes after [push](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1245) 3. We're [cutting result](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1154) to `1000` nodes. `1000` comes from [batchSize](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/services/tree/service.go#L416) 4. We keep the last tracked filename (`"same-version"`) 5. If I correctly understand, we're emptying these children [here](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/services/tree/service.go#L416) and then we process this parentID [again](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/services/tree/service.go#L463) 6. I suppose at this point the call expects different filename: [see](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/boltdb.go#L1219-L1240) but they are the same with 4. 7. The heap [won't push these items](https://git.frostfs.info/TrueCloudLab/frostfs-node/src/branch/master/pkg/local_object_storage/pilorama/heap.go#L53), we're losing them The problem is that `fillSortedChildren` is aiming to not duplicate results, but can't seek to correct childID to start repicking nodes with the same filename Temporary solution: increase batch size

alexvanin commented

2025-02-20 06:22:23 +00:00

Author

Owner

Temporary solution: increase batch size

I think we can keep it as it is for now, 1000 limit is no worse than 2000 or 3000 limit, in my opinion.

Can we say that this batch limit can be reworked with next version on tree service?

> Temporary solution: increase batch size I think we can keep it as it is for now, 1000 limit is no worse than 2000 or 3000 limit, in my opinion. Can we say that this batch limit can be reworked with next version on tree service?

aarifullin referenced this issue from a pull request that will close it,

2025-02-20 09:42:49 +00:00

Fix sorted getSubtree for multiversion filenames #1650