Introduce a BoundedTrie metric which is used to efficiently store and… #33385

rohitsinha54 · 2024-12-16T10:26:18Z

… aggregate a collection of string sequences (FQNs) with a limited size.

It is recommended to review this PR by commits.

BoundedTrie is a space-saving way to store many string sequences (like FQN/file paths). It acts like a tree with branches, holding sequences within a size limit. It can efficiently add, combine, and search and perform trimming of children when the size increases beyond defined max.

Let's say we want to store these sequences, with a size limit of 3:

"folder1/file1.txt"
"folder1/file2.txt"
"folder2/file3.txt"
Here's how the BoundedTrie might look:

root
  - folder1
     - file1.txt
     - file2.txt
  - folder2
     - file3.txt

If we try to add "folder1/file4.txt", the trie might trim to "folder1", dropping all children to stay within the size limit.

This will be used to replace the StringSet metric for lineage tracking for very large lineage graphs to overcome the size limits.

Thank you for your contribution! Follow this checklist to help us incorporate your contribution quickly and easily:

Mention the appropriate issue in your description (for example: addresses #123), if applicable. This will automatically add a link to the pull request in the issue. If you would like the issue to automatically close on merging the pull request, comment fixes #<ISSUE NUMBER> instead.
Update CHANGES.md with noteworthy changes.
If this contribution is large, please file an Apache Individual Contributor License Agreement.

See the Contributor Guide for more tips on how to make review process smoother.

To check the build health, please visit https://github.com/apache/beam/blob/master/.test-infra/BUILD_STATUS.md

GitHub Actions Tests Status (on master branch)

See CI.md for more information about GitHub Actions CI or the workflows README to see a list of phrases to trigger workflows.

rohitsinha54 · 2024-12-16T10:27:03Z

R: @robertwb

github-actions · 2024-12-16T10:28:13Z

Stopping reviewer notifications for this pull request: review requested by someone other than the bot, ceding control. If you'd like to restart, comment assign set of reviewers

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieCell.java

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

robertwb · 2024-12-16T21:46:54Z

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

+    } else if (other.root().isPresent() && other.singleton().isPresent()) {
+      return this;
+    } else {
+      BoundedTrieNode combined = new BoundedTrieNode(asTrie());


Same as above.

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

sdks/java/core/src/main/java/org/apache/beam/sdk/metrics/BoundedTrieResult.java

rohitsinha54 · 2024-12-19T23:52:38Z

@robertwb : Please have another look. Thank you very much.

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

sdks/java/core/src/main/java/org/apache/beam/sdk/metrics/BoundedTrieResult.java

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

rohitsinha54 · 2024-12-20T19:42:56Z

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

+  }
+
+  /** Returns a new {@link BoundedTrieData} instance that is a deep copy of this instance. */
+  public synchronized BoundedTrieData getCumulative() {


This returns a BoundedTrieData over a Set to be consistent with other MetricData in java SDK

rohitsinha54 · 2024-12-20T19:44:55Z

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

+   *
+   * @param other The other {@link BoundedTrieData} to combine with.
+   */
+  public synchronized void combine(@Nonnull BoundedTrieData other) {


This return a void rather than a reference to updated object because the object is mutable and returning a reference from here will then require unnecessary overhead of using AtomicReference in BoundedTrieCell to safely be able to handle combine call from mutli-threads.

rohitsinha54 · 2024-12-25T22:04:21Z

The 2 failing checks
:runners:google-cloud-dataflow-java:worker:test and :sdks:java:io:mqtt:test both passed locally so they seem to be transient failure in the workflow.

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

...ogle-cloud-dataflow-java/src/main/java/org/apache/beam/runners/dataflow/DataflowMetrics.java

...r/src/main/java/org/apache/beam/runners/dataflow/worker/MetricsToCounterUpdateConverter.java

runners/portability/java/src/main/java/org/apache/beam/runners/portability/PortableMetrics.java

robertwb · 2024-12-27T21:53:55Z

sdks/java/core/src/test/java/org/apache/beam/sdk/metrics/MetricsTest.java

@@ -277,7 +286,8 @@ public static class CommittedMetricTests extends SharedTestBase {
      UsesCounterMetrics.class,
      UsesDistributionMetrics.class,
      UsesGaugeMetrics.class,
-      UsesStringSetMetrics.class
+      UsesStringSetMetrics.class,
+      UsesBoundedTrieMetrics.class


Does this mean we lose (ordinary) counter coverage for runners not yet supporting bounded trie metrics?

I don't believe so.
This (all inclusive) annotation is on testAllAttemptedMetrics so only runner which supports all of them will run it. But the runner who do not support will not run testAllAttemptedMetrics but they will run others like for example for counters (ordinary) there is a test method below testAttemptedCounterMetrics which is annotated only with @Category({ValidatesRunner.class, UsesAttemptedMetrics.class, UsesCounterMetrics.class}).

rohitsinha54 · 2024-12-27T18:47:05Z

runners/google-cloud-dataflow-java/build.gradle

@@ -94,6 +94,7 @@ dependencies {
  // io-kafka is only used in PTransform override so it is optional
  provided project(":sdks:java:io:kafka")
  implementation project(":sdks:java:io:google-cloud-platform")
+  implementation project(":runners:core-java")


@robertwb I believe adding this dependency here is acceptable i.e. specialized runners can depend on core. Can you please confirm?

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java

...ogle-cloud-dataflow-java/src/main/java/org/apache/beam/runners/dataflow/DataflowMetrics.java

...r/src/main/java/org/apache/beam/runners/dataflow/worker/MetricsToCounterUpdateConverter.java

rohitsinha54 · 2025-01-02T18:45:48Z

sdks/java/core/src/test/java/org/apache/beam/sdk/metrics/MetricsTest.java

@@ -277,7 +286,8 @@ public static class CommittedMetricTests extends SharedTestBase {
      UsesCounterMetrics.class,
      UsesDistributionMetrics.class,
      UsesGaugeMetrics.class,
-      UsesStringSetMetrics.class
+      UsesStringSetMetrics.class,
+      UsesBoundedTrieMetrics.class


I don't believe so.
This (all inclusive) annotation is on testAllAttemptedMetrics so only runner which supports all of them will run it. But the runner who do not support will not run testAllAttemptedMetrics but they will run others like for example for counters (ordinary) there is a test method below testAttemptedCounterMetrics which is annotated only with @Category({ValidatesRunner.class, UsesAttemptedMetrics.class, UsesCounterMetrics.class}).

rohitsinha54 · 2025-01-06T17:17:29Z

@robertwb: Gentle nudge.

rohitsinha54 · 2025-01-31T08:36:25Z

@robertwb I verified that all changes are intended after rebasing.
Can you please help merge this PR?

Also please squash them to retain just the first commit

Introduce a BoundedTrie metric which is used to efficiently store and aggregate a collection of string sequences (FQNs) with a limited size.

Thanks.

rohitsinha54 · 2025-01-31T17:33:54Z

Failing test is on master fixed here: #33823

… aggregate a collection of string sequences (FQNs) with a limited size.

… mutable BoundedTrieData

…in fuzzy run tests

…reference

…l Dataflow java client support is ready

codecov · 2025-01-31T18:41:40Z

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 59.08%. Comparing base (1742b2e) to head (31b41b0).
Report is 6 commits behind head on master.

Additional details and impacted files

@@             Coverage Diff              @@
##             master   #33385      +/-   ##
============================================
+ Coverage     57.48%   59.08%   +1.60%     
- Complexity     1474     3239    +1765     
============================================
  Files           985     1156     +171     
  Lines        155918   176834   +20916     
  Branches       1076     3391    +2315     
============================================
+ Hits          89630   104488   +14858     
- Misses        64073    68979    +4906     
- Partials       2215     3367    +1152

Flag	Coverage Δ
java	`70.34% <ø> (+1.77%)`	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

rohitsinha54 · 2025-01-31T19:26:36Z

spotbugs fails on multi-threading for some cases where they are on purpose not synchronized. cc: @robertwb

robertwb

Thanks. I'll merge as soon as I verify all tests are passing.

github-actions bot added java runners core labels Dec 16, 2024

rohitsinha54 commented Dec 16, 2024

View reviewed changes

runners/core-java/src/main/java/org/apache/beam/runners/core/metrics/BoundedTrieData.java Outdated Show resolved Hide resolved

robertwb reviewed Dec 16, 2024

View reviewed changes

github-actions bot added the dataflow label Dec 19, 2024

rohitsinha54 force-pushed the user-bounded-trie branch from c9f106b to 01ffe0f Compare December 19, 2024 21:22

github-actions bot added the jet label Dec 19, 2024

rohitsinha54 force-pushed the user-bounded-trie branch 3 times, most recently from 5a5ddae to ebbe4f9 Compare December 19, 2024 21:49

github-actions bot removed dataflow jet labels Dec 19, 2024

rohitsinha54 force-pushed the user-bounded-trie branch from ebbe4f9 to 35e0a8c Compare December 19, 2024 23:52

rohitsinha54 commented Dec 20, 2024

View reviewed changes

github-actions bot added dataflow jet direct extensions portability labels Dec 23, 2024

rohitsinha54 mentioned this pull request Dec 27, 2024

Btrie disable flag #33457

Open

3 tasks

robertwb reviewed Dec 27, 2024

View reviewed changes

rohitsinha54 force-pushed the user-bounded-trie branch from db4e944 to 9298dfa Compare December 30, 2024 21:08

rohitsinha54 commented Jan 2, 2025

View reviewed changes

robertwb approved these changes Jan 21, 2025

View reviewed changes

rohitsinha54 force-pushed the user-bounded-trie branch from df8849c to f2969ef Compare January 31, 2025 08:34

rohitsinha54 added 21 commits January 31, 2025 17:54

Introduce a BoundedTrie metric which is used to efficiently store and…

0ba6c8a

… aggregate a collection of string sequences (FQNs) with a limited size.

Address comments, perform deep copies and support synchronization for…

b476466

… mutable BoundedTrieData

Add more unit tests for trienode and fix merge on empty node

7849f5f

Add more unit test for BoundedTrieData which are not already covered …

aaf3bd8

…in fuzzy run tests

Add unit tests for Cell

2b41b17

Plumb BoundedTrie to MetricsContainerImpl

631a34b

Plumb BoundedTrie to StreamingStepMetricsContainer

ba85636

Plumb BoundedTrie to StreamingStepMetricsContainer

a60330f

Plumb BoundedTrie to MetricQueryResults

5e2ec9e

Plumb BoundedTrie to MetricsContainerStepMap and make combine return …

b7b74e6

…reference

Add test in MetricsContainerStepMapTest

6cef4c5

Plumb BoundedTrie to DirectMetrics

6cd8fdc

Add BoundedTrieResult class

a7e237e

Plumb BoundedTrieResult and BoundedTrie in DataflowMetrics

4825bf2

Plumb BoundedTrie JetMetric and PortableMetric

5908879

Add test for BoundedTrieResult and some more plumbing

78508bf

Fixes for github checks

c959101

Multi-threaded test in MetricsContainerImplTest and some clean up

3761e59

Address comments part 2

35ea66b

Drop support DataflowMetrics and MetricsToCounterUpdateConverter unti…

b9d3986

…l Dataflow java client support is ready

rebase fixes

31b41b0

rohitsinha54 force-pushed the user-bounded-trie branch from f2969ef to 31b41b0 Compare January 31, 2025 17:55

Suppress IS2_INCONSISTENT_SYNC warning

f68fe75

robertwb approved these changes Feb 1, 2025

View reviewed changes

robertwb merged commit 5e031ab into apache:master Feb 1, 2025
28 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Introduce a BoundedTrie metric which is used to efficiently store and… #33385

Introduce a BoundedTrie metric which is used to efficiently store and… #33385

rohitsinha54 commented Dec 16, 2024 •

edited

Loading

rohitsinha54 commented Dec 16, 2024

github-actions bot commented Dec 16, 2024

robertwb Dec 16, 2024

rohitsinha54 commented Dec 19, 2024

rohitsinha54 Dec 20, 2024

rohitsinha54 Dec 20, 2024

rohitsinha54 commented Dec 25, 2024

robertwb Dec 27, 2024

rohitsinha54 Jan 2, 2025

rohitsinha54 Dec 27, 2024

robertwb Jan 21, 2025

rohitsinha54 Jan 2, 2025

rohitsinha54 commented Jan 6, 2025

rohitsinha54 commented Jan 31, 2025

rohitsinha54 commented Jan 31, 2025

codecov bot commented Jan 31, 2025

rohitsinha54 commented Jan 31, 2025

robertwb left a comment

Introduce a BoundedTrie metric which is used to efficiently store and… #33385

Introduce a BoundedTrie metric which is used to efficiently store and… #33385

Conversation

rohitsinha54 commented Dec 16, 2024 • edited Loading

GitHub Actions Tests Status (on master branch)

rohitsinha54 commented Dec 16, 2024

github-actions bot commented Dec 16, 2024

Choose a reason for hiding this comment

rohitsinha54 commented Dec 19, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rohitsinha54 commented Dec 25, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

rohitsinha54 commented Jan 6, 2025

rohitsinha54 commented Jan 31, 2025

rohitsinha54 commented Jan 31, 2025

codecov bot commented Jan 31, 2025

Codecov Report

rohitsinha54 commented Jan 31, 2025

robertwb left a comment

Choose a reason for hiding this comment

rohitsinha54 commented Dec 16, 2024 •

edited

Loading