[SERVER-30843] Use std::set::upper_bound when calculating the stable timestamp Created: 25/Aug/17  Updated: 30/Oct/23  Resolved: 12/Sep/17

Status: Closed
Project: Core Server
Component/s: Replication
Affects Version/s: None
Fix Version/s: 3.6.0-rc0

Type: Bug Priority: Major - P3
Reporter: William Schultz (Inactive) Assignee: William Schultz (Inactive)
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Related
is related to SERVER-29891 Roll Back to Checkpoint: Call setStab... Closed
is related to SERVER-30845 Avoid updating the stable timestamp i... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Sprint: Repl 2017-09-11, Repl 2017-10-02
Participants:
Linked BF Score: 0

 Description   

Currently the function ReplicationCoordinatorImpl::_calculateStableTimestamp uses std::find_if to search through the list of stable timestamp candidates. The list of stable timestamp candidates is maintained in sorted order, since it is a std::set, however, std::find_if doesn't take advantage of this. Thus, it's performance is linear in the size of the candidates list, and becomes the slowest part of the set stableTimestampForStorage operation if the candidate list grows to some non-trivial size.

We can optimize this by using the std::set::upper_bound function to calculate the stable timestamp. For a std::set container, upper_bound has logarithmic complexity, and returns the first element in a sorted range that is greater than some given value. If we do something like

candidates.upper_bound(commitPoint)

we can obtain an iterator to the smallest candidate timestamp that is greater than the commit point. By decrementing this iterator by 1, we can then obtain the greatest timestamp candidate that is less than or equal to the commit point. (This is the basic concept; there are a few edge cases to handle).

This should be done to address the performance regressions introduced by SERVER-29891.



 Comments   
Comment by Ramon Fernandez Marina [ 12/Sep/17 ]

Author:

{'username': u'will62794', 'name': u'William Schultz', 'email': u'william.schultz@mongodb.com'}

Message:SERVER-30843 Use std::set::upper_bound to calculate the stable timestamp
Branch:master
https://github.com/mongodb/mongo/commit/bf8ae1b3edbf7470e92b7407f76a042cc2246d48

Generated at Thu Feb 08 04:25:12 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.