[SERVER-52568] implement libdeps graph command line tool advanced queries Created: 02/Nov/20  Updated: 29/Oct/23  Resolved: 16/Apr/21

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 4.9.0

Type: New Feature Priority: Major - P3
Reporter: Daniel Moody Assignee: Daniel Moody
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PNG File whiteboardappdotorg20210319115206.png    
Issue Links:
Depends
depends on SERVER-52567 Create python command line tool for l... Closed
Backwards Compatibility: Fully Compatible
Sprint: Dev Platform 2021-01-11, Dev Platform 2021-01-25, Dev Platform 2021-02-08, Dev Platform 2021-02-22, Dev Platform 2021-03-08, Dev Platform 2021-03-22, Dev Platform 2021-04-05, Dev Platform 2021-04-19
Participants:

 Description   

implement options to allow the tool to perform and return the values for these queries:

  • What are all paths by which node X depends on node Y?
  • Is there a single edge which if removed disconnects node X from node Y?
  • What are the weightiest public edges (e.g. add the most transitive edges)


 Comments   
Comment by Githook User [ 15/Apr/21 ]

Author:

{'name': 'Daniel Moody', 'email': 'daniel.moody@mongodb.com', 'username': 'dmoody256'}

Message: SERVER-52568 Added GraphPaths, CriticalEdges, and PublicWieghts quieries to libdeps graph analyzer.
Branch: master
https://github.com/mongodb/mongo/commit/0782c59e71146e316e7d61ac61d76e2330f29eb4

Comment by Daniel Moody [ 17/Mar/21 ]

I went back and tested my heaviest libdeps algorithm it was taking much longer then when I originally tested it several months ago (not sure what changed that caused the increase in time). I stopped it at 20 mins in and decided to just improve it. The main issue I was running into was computing the redundancy of a given transitive edge, the number of other direct public edges that would create the same transitive edge. Originally my algorithm was recomputing this for every edge in the graph, so precomputing it all once speeds things up. Now it's about 8 seconds to precompute the redundancy and 30 seconds to count the weight of every direct public edge in the graph.

Question: So I can precompute the redundancy during the SCons build and store it in the graph data, but this means bumping the schema version, so the algorithm can only run more recent commits, or I can precompute every time the analyzer is run. This leads me to several options:

  1. make the algorithm require a new schema version and precompute in the SCons build
  2. always re-precompute when the analyzer is run
  3. re-compute in the analyzer and if the graph is wrong schema version and write back to the graph and update the graph files schema version (maintenance concerns, I would prefer analyzer remain read only)
  4. precompute during the SCons build and also during the analyzer, always precompute if the graph is an older schema version
Generated at Thu Feb 08 05:28:24 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.