fix improper use of iteration #1552
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
pongad
commented
Jan 19, 2017
| synchronized (outstandingAckHandlers) { | ||
| addOutstadingAckHandlers(expiration, ackHandlers); | ||
| outstandingAckHandlers.add( | ||
| new ExtensionJob(expiration, INITIAL_ACK_DEADLINE_EXTENSION_SECONDS, ackHandlers)); |
This comment was marked as spam.
This comment was marked as spam.
Sorry, something went wrong.
Member
|
I think @davidtorres should probably do the first pass, since he wrote the original code and understands it better. |
The previous implementation modifies a HashMap while iterating through its key set, causeing unpredictable iteration behavior. This might be the reason our tests intermittently deadlock. The new implementation uses a PriorityQueue. The time complexity is O(M * log N), where M is the number of expirations before the cut over time and N is the total number of expirations. I am not sure how this compares to O(N) intended in the previous implementation. If required, O(N) is also possible using an ArrayList. Unfortunately, a new failure has emerged. Instead of deadlocking, testModifyAckDeadline intermittently fails. Maybe - I have fixed the old bug and created a new one, - I have fixed the old bug that was masking another one, - The deadlock wasn't caused by the iteration. Now the tests just fail before they could deadlock, or some combination thereof. The incorrect iteration should be fixed regardless.
Contributor
Author
|
David's first pass is at 9dc57e8 I'm not sure why the review is not showing up here. @garrettjonesgoogle @davidtorres PTAL. |
|
Changes Unknown when pulling 0aea0fc on pongad:fix-iter into ** on GoogleCloudPlatform:pubsub-hp**. |
Contributor
Author
|
David LGTMed in the linked PR. Still not sure why it's not here... |
pongad
added a commit
that referenced
this pull request
Jan 24, 2017
This is a follow up to #1552 . The linked PR has a race condition: If the ExtensionJobs is added to the queue after the alarm is set up, it is possible that the alarm would fire before the jobs are added. Fixing this is easy, just set up the alarm after. However, doing this consistently deadlocks the tests. Why? The tests uses a fake executor. In tests, time does not flow naturally, but is forced to increment, usually by the executor's `advanceTime` method. There is a race between the test thread advancing the time and the mock server thread inserting more tasks to the fake executor. If the tasks get inserted first, all is well. Otherwise, `advanceTime` doesn't see the tasks, and they do not get executed. The fix is to check the "current time" every time a task is inserted. If the task is inserted "in the past", we run the task immediately. Doing this still deadlocks the tests. Why? The fake executor needs to lock the tas A31D k queue when registering a task. If the task is inserted in the past, it also needs to run the task. Running the task might involve sending a requst to the mock server. A GRPC thread on the mock server might handle the request by adding more tasks to the executor. The executor's queue is locked by the first thread, resulting in a deadlock. The fix is to lock the queue just long enough to retrieve a task, then execute the task without the lock.
meltsufin
pushed a commit
that referenced
this pull request
Dec 22, 2025
meltsufin
pushed a commit
that referenced
this pull request
Dec 22, 2025
🤖 I have created a release *beep* *boop* --- ## [3.16.1](https://togithub.com/googleapis/java-logging/compare/v3.16.0...v3.16.1) (2024-03-07) ### Bug Fixes * **deps:** Update the Java code generator (gapic-generator-java) to 2.37.0 ([#1553](https://togithub.com/googleapis/java-logging/issues/1553)) ([15b05fc](https://togithub.com/googleapis/java-logging/commit/15b05fc4a8e6c4069414110b749525082821e509)) ### Dependencies * Update dependency com.google.cloud:sdk-platform-java-config to v3.27.0 ([#1552](https://togithub.com/googleapis/java-logging/issues/1552)) ([6c5464d](https://togithub.com/googleapis/java-logging/commit/6c5464d1c5a74962fcd459a1e03282747e148a44)) --- This PR was generated with [Release Please](https://togithub.com/googleapis/release-please). See [documentation](https://togithub.com/googleapis/release-please#release-please).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
cc @davidtorres
The previous implementation modifies a HashMap while iterating through
its key set, causeing unpredictable iteration behavior.
This might be the reason our tests intermittently deadlock.
The new implementation uses a PriorityQueue.
The time complexity is O(M * log N),
where M is the number of expirations before the cut over time
and N is the total number of expirations.
I am not sure how this compares to O(N) intended in the previous
implementation.
If required, O(N) is also possible using an ArrayList.
Unfortunately, a new failure has emerged.
Instead of deadlocking, testModifyAckDeadline intermittently fails.
Maybe
before they could deadlock,
or some combination thereof.
The incorrect iteration should be fixed regardless.