Implement get_tree() feature #905

aleksdmladenovic · 2024-05-09T08:09:42Z

Description

I handled get_tree() GRPC request in the CAS Server. Used FIFO(First-In-First-Out) traversal method ( BFS Algorithm ) to loop over directories using VecDeque data structure. Paging is supported and page_token in GetTreeRequest is used to point the directory to start traversing with. And next_page_token in GetTreeResponse refers the page_token parameter which will be used in the next request.

Fixes #355

Type of change

Please delete options that aren't relevant.

New feature (non-breaking change which adds functionality)

How Has This Been Tested?

Still not tested yet.

Checklist

Updated documentation if needed
Tests added/amended
bazel test //... passes locally
PR is contained in a single commit, using git amend see some docs

This change is

aleksdmladenovic · 2024-05-09T08:10:24Z

+@allada, @MarcusSorealheis

adam-singer · 2024-05-09T17:51:40Z

@aleksdmladenovic can we add tests ?

allada

Looks mostly good, but needs some tests.

There's also a few performance improvements that could be made, but it's fine to omit them for now.

Reviewed 1 of 1 files at r1, all commit messages.
Reviewable status: 0 of 1 LGTMs obtained, and 4 discussions need to be resolved

nativelink-service/src/cas_server.rs line 251 at r1 (raw file):

        let mut deque: VecDeque<DigestInfo> = VecDeque::new();
        let mut directories: Vec<Directory> = Vec::new();
        let page_token = inner_request.page_token;

nit: Lets convert this to a DigestInfo and error otherwise. If it's an empty string consider it ok.

You should not use hash_str(), because it also needs to match the size to be in spec.

nativelink-service/src/cas_server.rs line 257 at r1 (raw file):

        // `next_page_token` will return the `hash_str` of the next request round's first directory digest.
        // It will be an empty string when it reached the end of the directory tree.
        let mut next_page_token: String = String::new();

nit: Use digest and convert it last. This saves on allocations too.

nativelink-service/src/cas_server.rs line 261 at r1 (raw file):

        while !deque.is_empty() {
            let digest: DigestInfo = *deque.front().err_tip(|| "In VecDeque::front")?;

nit: use .pop_front() here.

nativelink-service/src/cas_server.rs line 269 at r1 (raw file):

            }
            if page_token_matched {
                if directories.len() as i32 == page_size + 1 {

nit: call directories.push(directory.clone()) first, so you don't need to add + 1 here.

aleksdmladenovic

I've added tests and fixed nits you mentioned.

cc: @allada , @adam-singer

Reviewable status: 0 of 1 LGTMs obtained, and pending CI: Analyze (python), Bazel Dev / ubuntu-22.04, Cargo Dev / macos-13, Cargo Dev / ubuntu-22.04, Local / ubuntu-22.04, Publish image, Publish nativelink-worker-lre-cc, Remote / large-ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), integration-tests (20.04), integration-tests (22.04), macos-13, ubuntu-20.04 / stable, ubuntu-22.04, ubuntu-22.04 / stable, windows-2022 / stable

allada

Reviewed 2 of 2 files at r2, all commit messages.
Reviewable status: 0 of 1 LGTMs obtained, and pending CI: Bazel Dev / ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), macos-13, ubuntu-22.04, and 7 discussions need to be resolved

nativelink-service/src/cas_server.rs line 252 at r2 (raw file):

        let mut directories: Vec<Directory> = Vec::new();
        // `page_token` will return the `{hash_str}:{size_bytes}` of the current request's first directory digest.
        let page_token_parts: Vec<&str> = inner_request.page_token.split(":").collect();

nit: This is really inefficient and causes allocations. Instead you should use .split("-") then .next() on the iterator to get the two parts into the variables (with .err_tip()).

nativelink-service/src/cas_server.rs line 252 at r2 (raw file):

        let mut directories: Vec<Directory> = Vec::new();
        // `page_token` will return the `{hash_str}:{size_bytes}` of the current request's first directory digest.
        let page_token_parts: Vec<&str> = inner_request.page_token.split(":").collect();

nit: Don't use : use -, this is standard in the rest of the code.

nativelink-service/src/cas_server.rs line 292 at r2 (raw file):

        // `next_page_token` will return the `{hash_str}:{size_bytes}` of the next request's first directory digest.
        // It will be an empty string when it reached the end of the directory tree.
        let next_page_token: String = if let Some(value) = deque.front() {

nit: Because we are now grabbing the front-item, we are introducing a fence-post case where deque.front() could be None because the for directory in directory.directories { did not run.

We should move the for-loop above the if page_token_matched { branch to protect us.

nativelink-service/tests/cas_server_test.rs line 346 at r2 (raw file):

        let store_pinned = Pin::new(store_owned.as_ref());

        // Set up 5 sub-directories

nit: Period.

nativelink-service/tests/cas_server_test.rs line 361 at r2 (raw file):

                    mtime: Some(Timestamp {
                        seconds: 0,
                        nanos: i,

nit: put this in seconds. nanos might not get converted properly due to percision issues.

nativelink-service/tests/cas_server_test.rs line 393 at r2 (raw file):

        )
        .await?;
        let root_directory_digest: Digest = Digest::try_from(root_directory_digest_info).unwrap();

nit: use root_directory_digest_info.into() (ditto with others).

nativelink-service/tests/cas_server_test.rs line 431 at r2 (raw file):

        );

        // Must work when paging is enabled ( `page_size` is 2 ).

This should be a different test.

I suggest making a setup function that will get our state all prepared, then we can call it from different tests.

aleksdmladenovic

Resolved comments. cc:@allada, @adam-singer

Reviewable status: 0 of 1 LGTMs obtained, and pending CI: Analyze (javascript-typescript), Analyze (python), Bazel Dev / ubuntu-22.04, Cargo Dev / macos-13, Cargo Dev / ubuntu-22.04, Local / ubuntu-22.04, Publish image, Publish nativelink-worker-lre-cc, Remote / large-ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), integration-tests (20.04), integration-tests (22.04), macos-13, pre-commit-checks, ubuntu-20.04 / stable, ubuntu-22.04, ubuntu-22.04 / stable, windows-2022 / stable, and 1 discussions need to be resolved

nativelink-service/tests/cas_server_test.rs line 431 at r2 (raw file):

Previously, allada (Nathan (Blaise) Bruer) wrote…

This should be a different test.

I suggest making a setup function that will get our state all prepared, then we can call it from different tests.

Done.

allada

Reviewed 2 of 2 files at r3.
Reviewable status: 0 of 1 LGTMs obtained, and pending CI: Bazel Dev / ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), macos-13, pre-commit-checks, ubuntu-22.04, and 6 discussions need to be resolved

nativelink-service/src/cas_server.rs line 260 at r3 (raw file):

                .next()
                .err_tip(|| "Failed to parse `size_bytes` in `page_token`")?
                .parse::<i64>()?,

nit: Please .err_tip() or .map_err().

nativelink-service/src/cas_server.rs line 261 at r3 (raw file):

                .err_tip(|| "Failed to parse `size_bytes` in `page_token`")?
                .parse::<i64>()?,
        )?;

ditto.

nativelink-service/src/cas_server.rs line 275 at r3 (raw file):

                page_token_matched = true;
            }
            for directory in directory.clone().directories {

nit: Clone not needed. You probably want to clone directory.digest() instead.

nativelink-service/src/cas_server.rs line 284 at r3 (raw file):

            }
            if page_token_matched {
                directories.push(directory.clone());

.clone() not needed.

nativelink-service/tests/cas_server_test.rs line 343 at r3 (raw file):

    ) -> Result<
        (
            Digest,

nit: Make a struct that represents these to make it more readable.

nativelink-service/tests/cas_server_test.rs line 349 at r3 (raw file):

            Vec<DigestInfo>,
        ),
        Box<dyn std::error::Error>,

nit: Use nativelink's Error.

aleksdmladenovic

Reviewable status: 0 of 1 LGTMs obtained, and pending CI: Bazel Dev / ubuntu-22.04, Cargo Dev / macos-13, Cargo Dev / ubuntu-22.04, Publish image, Publish nativelink-worker-lre-cc, Remote / large-ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), integration-tests (20.04), integration-tests (22.04), macos-13, ubuntu-20.04 / stable, ubuntu-22.04, ubuntu-22.04 / stable, windows-2022 / stable, and 2 discussions need to be resolved

nativelink-service/src/cas_server.rs line 261 at r3 (raw file):

Previously, allada (Nathan (Blaise) Bruer) wrote…

ditto.

Done.

nativelink-service/src/cas_server.rs line 284 at r3 (raw file):

Previously, allada (Nathan (Blaise) Bruer) wrote…

.clone() not needed.

Done.

allada

Reviewed 1 of 2 files at r4, all commit messages.
Reviewable status: 1 of 1 LGTMs obtained, and pending CI: Cargo Dev / macos-13, and 1 discussions need to be resolved

nativelink-service/tests/cas_server_test.rs line 341 at r4 (raw file):

    struct SetupDirectoryResult {
        root_directory_digest: Digest,

nit: just use DigestInfo, it's always safe to convert directly to Digest.

aleksdmladenovic

Resolved. cc: @allada

Reviewable status: 1 of 1 LGTMs obtained, and pending CI: Analyze (javascript-typescript), Analyze (python), Bazel Dev / ubuntu-22.04, Cargo Dev / macos-13, Cargo Dev / ubuntu-22.04, Local / ubuntu-22.04, Publish image, Publish nativelink-worker-lre-cc, Remote / large-ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), integration-tests (20.04), integration-tests (22.04), macos-13, pre-commit-checks, ubuntu-20.04 / stable, ubuntu-22.04, ubuntu-22.04 / stable, windows-2022 / stable

allada

Reviewed 1 of 1 files at r5, all commit messages.
Reviewable status: 1 of 1 LGTMs obtained, and pending CI: Bazel Dev / ubuntu-22.04, Cargo Dev / macos-13, Cargo Dev / ubuntu-22.04, Publish image, Publish nativelink-worker-lre-cc, Remote / large-ubuntu-22.04, asan / ubuntu-22.04, docker-compose-compiles-nativelink (20.04), docker-compose-compiles-nativelink (22.04), macos-13, ubuntu-20.04 / stable, ubuntu-22.04 / stable, windows-2022 / stable

MarcusSorealheis · 2024-05-15T11:36:22Z

This looks good. thank you for the PR aleksdmladenovic!

MarcusSorealheis

Reviewable status: 2 of 1 LGTMs obtained, and pending CI: pre-commit-checks

MarcusSorealheis · 2024-05-15T12:00:49Z

@allada If this looks good still, please merge it.Even though we don't use it, a lot of tools do use it so maybe it will be helpful to NativeLink users.

adam-singer

Reviewed 1 of 2 files at r4, 1 of 1 files at r5, all commit messages.
Reviewable status: 3 of 1 LGTMs obtained, and pending CI: Cargo Dev / macos-13, macos-13

Handled get_tree() GRPC request in the CAS Server. Used FIFO(First-In-First-Out) traversal method ( BFS Algorithm ) to loop over directories using `VecDeque` data structure. Paging is supported and `page_token` in `GetTreeRequest` is used to point the directory to start traversing with. And `next_page_token` in `GetTreeResponse` refers the `page_token` parameter which will be used in the next request.

MarcusSorealheis · 2024-05-15T23:50:27Z

@aleksdmladenovic what was the reason for the most recent push?

MarcusSorealheis · 2024-05-15T23:50:58Z

Looks like it may have been a rebase but correct me if I am wrong.

aleksdmladenovic · 2024-05-15T23:57:32Z

Just rebase. cc: @MarcusSorealheis

MarcusSorealheis

again due to rebase

Reviewed all commit messages.
Reviewable status: complete! 3 of 1 LGTMs obtained

allada approved these changes May 12, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch from f4772cf to 313b369 Compare May 13, 2024 17:55

aleksdmladenovic requested a review from allada May 13, 2024 17:57

aleksdmladenovic commented May 13, 2024

View reviewed changes

allada requested changes May 14, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch from 313b369 to 1b9bc02 Compare May 14, 2024 04:04

aleksdmladenovic commented May 14, 2024

View reviewed changes

steedmicro requested a review from allada May 14, 2024 14:32

allada requested changes May 14, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch from 1b9bc02 to 4503f91 Compare May 14, 2024 16:40

aleksdmladenovic requested a review from allada May 14, 2024 16:41

aleksdmladenovic commented May 14, 2024

View reviewed changes

allada approved these changes May 14, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch 2 times, most recently from 421103e to 0be5aeb Compare May 14, 2024 18:28

aleksdmladenovic commented May 14, 2024

View reviewed changes

allada approved these changes May 14, 2024

View reviewed changes

aleksdmladenovic closed this May 15, 2024

aleksdmladenovic force-pushed the implement-get-tree branch from 0be5aeb to 0ff1f45 Compare May 15, 2024 07:35

aleksdmladenovic reopened this May 15, 2024

MarcusSorealheis approved these changes May 15, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch from 9807160 to 49c284b Compare May 15, 2024 15:22

adam-singer approved these changes May 15, 2024

View reviewed changes

aleksdmladenovic force-pushed the implement-get-tree branch from 49c284b to d63016b Compare May 15, 2024 23:49

MarcusSorealheis approved these changes May 16, 2024

View reviewed changes

MarcusSorealheis merged commit ae44878 into TraceMachina:main May 16, 2024
25 checks passed

This was referenced Sep 9, 2024

The get_tree operation should not require a page_token #1339

Closed

Allow empty page_token for get_tree #1340

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement get_tree() feature #905

Implement get_tree() feature #905

aleksdmladenovic commented May 9, 2024 •

edited

Loading

aleksdmladenovic commented May 9, 2024

adam-singer commented May 9, 2024

allada left a comment

aleksdmladenovic left a comment

allada left a comment

aleksdmladenovic left a comment

allada left a comment

aleksdmladenovic left a comment

allada left a comment

aleksdmladenovic left a comment

allada left a comment

MarcusSorealheis commented May 15, 2024

MarcusSorealheis left a comment

MarcusSorealheis commented May 15, 2024

adam-singer left a comment

MarcusSorealheis commented May 15, 2024

MarcusSorealheis commented May 15, 2024

aleksdmladenovic commented May 15, 2024

MarcusSorealheis left a comment

Implement get_tree() feature #905

Implement get_tree() feature #905

Conversation

aleksdmladenovic commented May 9, 2024 • edited Loading

Description

Type of change

How Has This Been Tested?

Checklist

aleksdmladenovic commented May 9, 2024

adam-singer commented May 9, 2024

allada left a comment

Choose a reason for hiding this comment

aleksdmladenovic left a comment

Choose a reason for hiding this comment

allada left a comment

Choose a reason for hiding this comment

aleksdmladenovic left a comment

Choose a reason for hiding this comment

allada left a comment

Choose a reason for hiding this comment

aleksdmladenovic left a comment

Choose a reason for hiding this comment

allada left a comment

Choose a reason for hiding this comment

aleksdmladenovic left a comment

Choose a reason for hiding this comment

allada left a comment

Choose a reason for hiding this comment

MarcusSorealheis commented May 15, 2024

MarcusSorealheis left a comment

Choose a reason for hiding this comment

MarcusSorealheis commented May 15, 2024

adam-singer left a comment

Choose a reason for hiding this comment

MarcusSorealheis commented May 15, 2024

MarcusSorealheis commented May 15, 2024

aleksdmladenovic commented May 15, 2024

MarcusSorealheis left a comment

Choose a reason for hiding this comment

aleksdmladenovic commented May 9, 2024 •

edited

Loading