)]}'
{"id":"openstack%2Fplacement~964220","triplet_id":"openstack%2Fplacement~stable%2F2025.2~I13ab83a165c229ae57876df4570e8af25221a45e","project":"openstack/placement","branch":"stable/2025.2","topic":"bug/2126751","attention_set":{},"removed_from_attention_set":{"9708":{"account":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"last_update":"2025-11-24 14:09:53.000000000","reason":"Change was submitted"}},"hashtags":[],"change_id":"I13ab83a165c229ae57876df4570e8af25221a45e","subject":"Prune a_c search space by invalid prefixes","status":"MERGED","created":"2025-10-16 14:19:44.000000000","updated":"2025-11-24 14:11:33.000000000","submitted":"2025-11-24 14:09:53.000000000","submitter":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"total_comment_count":2,"unresolved_comment_count":0,"has_review_started":true,"submission_id":"964220-bug/2126751","meta_rev_id":"5d558e5c13c0df5733521fb908738b499a8ae67c","_number":964220,"virtual_id_number":964220,"owner":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"actions":{},"labels":{"Verified":{"approved":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"all":[{"value":0,"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},{"value":0,"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},{"tag":"autogenerated:zuul:gate","value":2,"date":"2025-11-24 14:09:53.000000000","permitted_voting_range":{"min":2,"max":2},"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}],"values":{"-2":"Fails","-1":"Doesn\u0027t seem to work"," 0":"No score","+1":"Works for me","+2":"Verified"},"description":"","default_value":0,"optional":true},"Code-Review":{"approved":{"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},"all":[{"value":2,"date":"2025-10-17 20:35:00.000000000","permitted_voting_range":{"min":2,"max":2},"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},{"value":2,"date":"2025-11-24 12:14:02.000000000","permitted_voting_range":{"min":2,"max":2},"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},{"value":0,"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}],"values":{"-2":"Do not merge","-1":"This patch needs further work before it can be merged"," 0":"No score","+1":"Looks good to me, but someone else must approve","+2":"Looks good to me (core reviewer)"},"description":"","default_value":0,"optional":true},"Workflow":{"approved":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},"all":[{"value":0,"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},{"value":1,"date":"2025-11-24 12:14:02.000000000","permitted_voting_range":{"min":1,"max":1},"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},{"value":0,"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}],"values":{"-1":"Work in progress"," 0":"Ready for reviews","+1":"Approved"},"description":"","default_value":0,"optional":true},"Review-Priority":{"all":[{"value":0,"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},{"value":0,"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},{"value":0,"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}],"values":{" 0":"Default Priority","+1":"Contributor Review Promise","+2":"Core Review Promise"},"description":"","default_value":0,"optional":true}},"removable_reviewers":[],"reviewers":{"REVIEWER":[{"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}]},"pending_reviewers":{},"reviewer_updates":[{"updated":"2025-10-16 15:28:37.000000000","updated_by":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"reviewer":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"state":"REVIEWER"},{"updated":"2025-10-17 20:35:00.000000000","updated_by":{"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},"reviewer":{"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},"state":"REVIEWER"},{"updated":"2025-11-24 12:14:02.000000000","updated_by":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},"reviewer":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},"state":"REVIEWER"}],"messages":[{"id":"73db8b34fd666fc5495f76fd694ad855f4ad0ce1","tag":"autogenerated:gerrit:newPatchSet","author":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"date":"2025-10-16 14:19:44.000000000","message":"Uploaded patch set 1.","accounts_in_message":[],"_revision_number":1},{"id":"f81fe61822fdba91a002ee5665f0b5041a13ce44","tag":"autogenerated:zuul:check","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2025-10-16 15:28:37.000000000","message":"Patch Set 1: Verified+1\n\nBuild succeeded (check pipeline).\nhttps://zuul.opendev.org/t/openstack/buildset/d81915350c3c4bf2ae160d426689e88a\n\n- grenade https://zuul.opendev.org/t/openstack/build/c66b60068d3c43bc89e58cdba3f5ce0e : SUCCESS in 55m 39s\n- tempest-integrated-placement https://zuul.opendev.org/t/openstack/build/ef5bfa6995ec4a68bd02efc42106af59 : SUCCESS in 58m 42s\n- openstacksdk-functional-devstack https://zuul.opendev.org/t/openstack/build/8e4577c61a354aec8026563b8a7b775e : SUCCESS in 35m 24s\n- openstack-tox-cover https://zuul.opendev.org/t/openstack/build/3004c16e34274c7da6c76ff225db82bb : SUCCESS in 14m 45s\n- openstack-tox-pep8 https://zuul.opendev.org/t/openstack/build/98446989706f408d8430ac818cfecd2a : SUCCESS in 5m 24s\n- openstack-tox-py310 https://zuul.opendev.org/t/openstack/build/e65807cae73140c4b3dda6b825a274ec : SUCCESS in 5m 28s\n- openstack-tox-py312 https://zuul.opendev.org/t/openstack/build/88b2fb23f2264dc29b73ed2b14e5b4f2 : SUCCESS in 6m 57s\n- openstack-tox-py313 https://zuul.opendev.org/t/openstack/build/c3a98b821d4b46f2b037264ba7c0a9d0 : SUCCESS in 7m 52s (non-voting)\n- openstack-tox-docs https://zuul.opendev.org/t/openstack/build/bf6f68f15a1c49a9ae75aabeb44f6dce : SUCCESS in 10m 10s\n- build-openstack-releasenotes https://zuul.opendev.org/t/openstack/build/0ce1d19ffb4f477ab5eae945830eada7 : SUCCESS in 4m 36s\n- openstack-tox-functional-py310 https://zuul.opendev.org/t/openstack/build/c0720d64f8614be1a1ce0e3a38f81763 : SUCCESS in 6m 33s\n- openstack-tox-functional-py312 https://zuul.opendev.org/t/openstack/build/3058e168fac04c7e863bd06979060a90 : SUCCESS in 9m 18s\n- placement-nova-tox-functional-py312 https://zuul.opendev.org/t/openstack/build/1e74e18e64f847b3808e6eebe16adae0 : SUCCESS in 18m 50s\n- placement-nested-perfload https://zuul.opendev.org/t/openstack/build/fb57461ad3f94bafa2a8b4b2b136ade9 : SUCCESS in 14m 14s (non-voting)\n- placement-perfload https://zuul.opendev.org/t/openstack/build/542c2e29cfb64f90997dfa2acb6358b2 : FAILURE in 2m 14s (non-voting)\n- tempest-ipv6-only https://zuul.opendev.org/t/openstack/build/8f59f4895a474e4d8c93a275846e6057 : SUCCESS in 28m 27s","accounts_in_message":[],"_revision_number":1},{"id":"4ae7a56755f22209cf4c1239c9d11ff0068ae175","author":{"_account_id":4690,"name":"melanie witt","display_name":"melwitt","email":"melwittt@gmail.com","username":"melwitt"},"date":"2025-10-17 20:35:00.000000000","message":"Patch Set 1: Code-Review+2\n\n(1 comment)","accounts_in_message":[],"_revision_number":1},{"id":"dc3e2270594c826cca0994419a7106a80da4bd2c","author":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"},"date":"2025-11-24 12:14:02.000000000","message":"Patch Set 1: Code-Review+2 Workflow+1\n\n(1 comment)","accounts_in_message":[],"_revision_number":1},{"id":"c4bf46b920a09192d4dc3daa0e5adeb736787e84","tag":"autogenerated:zuul:gate","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2025-11-24 12:17:22.000000000","message":"Patch Set 1: -Verified\n\nStarting gate jobs.","accounts_in_message":[],"_revision_number":1},{"id":"7b0dbea8111e4be12b679fbbeb5e6d721139d8ac","tag":"autogenerated:zuul:gate","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2025-11-24 14:09:53.000000000","message":"Patch Set 1: Verified+2\n\nBuild succeeded (gate pipeline).\nhttps://zuul.opendev.org/t/openstack/buildset/52fb09cbdca3478ab2811bfa05e7d6dd\n\n- grenade https://zuul.opendev.org/t/openstack/build/7b18f56a31ef49fbadc139cc6a308003 : SUCCESS in 45m 31s\n- tempest-integrated-placement https://zuul.opendev.org/t/openstack/build/d7d3d239d44d43cc9629fb718d62bfcd : SUCCESS in 1h 44m 47s\n- grenade-skip-level-always https://zuul.opendev.org/t/openstack/build/b991e81f88fa41d3aff120ce2ea94d16 : SUCCESS in 37m 39s\n- openstacksdk-functional-devstack https://zuul.opendev.org/t/openstack/build/cf62a5dd0158497abe62b83e2c01b55a : SUCCESS in 36m 17s\n- openstack-tox-pep8 https://zuul.opendev.org/t/openstack/build/6dddec477a1a44d68b6aaa8064fa2632 : SUCCESS in 4m 43s\n- openstack-tox-py310 https://zuul.opendev.org/t/openstack/build/49e7cb3f60c649d3bfa1643cf155a16e : SUCCESS in 5m 06s\n- openstack-tox-py312 https://zuul.opendev.org/t/openstack/build/4e95909fdd034ae68093570a284c45f6 : SUCCESS in 5m 39s\n- openstack-tox-docs https://zuul.opendev.org/t/openstack/build/3a716b92497c4044b509e85db01f3fe2 : SUCCESS in 4m 50s\n- build-openstack-releasenotes https://zuul.opendev.org/t/openstack/build/15dcf9bf6c0e49b5abc18613b2a83caf : SUCCESS in 4m 47s\n- openstack-tox-functional-py310 https://zuul.opendev.org/t/openstack/build/1c36de216fe14aeaaf5f491834ce9f9b : SUCCESS in 6m 04s\n- openstack-tox-functional-py312 https://zuul.opendev.org/t/openstack/build/ffadcecadbd540b987ea41eb81a2266f : SUCCESS in 9m 32s\n- placement-nova-tox-functional-py312 https://zuul.opendev.org/t/openstack/build/9e7d48d7fa7f4928a63354202124c3e0 : SUCCESS in 25m 58s\n- tempest-ipv6-only https://zuul.opendev.org/t/openstack/build/225d4ea95df94d9daeca9705d877796f : SUCCESS in 55m 04s","accounts_in_message":[],"_revision_number":1},{"id":"786981534e54e3615b42215e2083b8c68fea6ca5","tag":"autogenerated:gerrit:merged","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2025-11-24 14:09:53.000000000","message":"Change has been successfully merged","accounts_in_message":[],"_revision_number":1},{"id":"5d558e5c13c0df5733521fb908738b499a8ae67c","tag":"autogenerated:zuul:promote","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2025-11-24 14:11:33.000000000","message":"Patch Set 1:\n\nBuild succeeded (promote pipeline).\nhttps://zuul.opendev.org/t/openstack/buildset/048c23603a4d439788bb32beb3b8374a\n\n- promote-openstack-tox-docs https://zuul.opendev.org/t/openstack/build/be1564b7452041269d343ba46bab6ad4 : SUCCESS in 39s\n- promote-openstack-releasenotes https://zuul.opendev.org/t/openstack/build/dddb1e821a5b4fef8be1bccc7c5ab782 : SUCCESS in 36s","accounts_in_message":[],"_revision_number":1}],"current_revision_number":1,"current_revision":"192f62baada531b8ae96a2e6eac07506034dbdc3","revisions":{"192f62baada531b8ae96a2e6eac07506034dbdc3":{"kind":"REWORK","_number":1,"created":"2025-10-16 14:19:44.000000000","uploader":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"ref":"refs/changes/20/964220/1","fetch":{"anonymous http":{"url":"https://review.opendev.org/openstack/placement","ref":"refs/changes/20/964220/1","commands":{"Checkout":"git fetch https://review.opendev.org/openstack/placement refs/changes/20/964220/1 \u0026\u0026 git checkout FETCH_HEAD","Cherry Pick":"git fetch https://review.opendev.org/openstack/placement refs/changes/20/964220/1 \u0026\u0026 git cherry-pick FETCH_HEAD","Format Patch":"git fetch https://review.opendev.org/openstack/placement refs/changes/20/964220/1 \u0026\u0026 git format-patch -1 --stdout FETCH_HEAD","Pull":"git pull https://review.opendev.org/openstack/placement refs/changes/20/964220/1"}}},"commit":{"parents":[{"commit":"0ec7b16caf44c84d5e8b97400a3dda0771a5b94f","subject":"Reproduce GET a_c slowness bug/2126751","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/placement/commit/0ec7b16caf44c84d5e8b97400a3dda0771a5b94f"}]}],"author":{"name":"Balazs Gibizer","email":"gibi@redhat.com","date":"2025-10-02 09:40:31.000000000","tz":120},"committer":{"name":"Balazs Gibizer","email":"gibi@redhat.com","date":"2025-10-16 14:19:09.000000000","tz":120},"subject":"Prune a_c search space by invalid prefixes","message":"Prune a_c search space by invalid prefixes\n\nAssume we have 8 RPs with 1 resource, and we request 8 groups\nwith 1 resource each.\nThe full candidate matrix for a single provider tree (compute node)\nby satisfying each group independently (G is request group, R is RP):\n\n  G0: [R0, R1,..., R7] # G0 can be fulfilled from R0, R1, ..., R7\n  G1: [R0, R1,..., R7]\n  ...\n  G7: [R0, R1,..., R7]\n\nPlacement needs to satisfy every group in the request so it\ncreates all the possible combinations (a Cartesian product) of the\nindividual group fulfilments and checks if they are valid, i.e if\nthere are no two or more groups trying to use the same single piece\nof resource.\nThe product looks like\n(C is candidate, G0-R0 means G0 group satisfied from R0 RP):\n\n  C0: [G0-R0, G1-R0, ..., G7-R0] # invalid, R0 has 1 res but C0 needs 8\n  C1: [G0-R0, G2-R0, ..., G7-R1] # invalid, R0 has 1 res but C1 needs 7\n  ...\n  Cx: [G0-R0, G1-R1, ..., G7-R7] # valid, each Rx has 1 res and\n                                 # Cx ask form 1 res each\n\nFrom this picture it is clear that:\n\n* There are a lot more invalid candidates than valid ones. Actually\n  in this specific scenario the total number of candidates are\n  8^8 ~ 16M. The valid candidates are 8! ~ 40K. Finding the valid ones\n  by blindly searching all possible ones are scaling very badly as\n  exponential grows faster than factorial. I.e. valid candidates will be\n  farther apart from each other in the search space.\n\n* There is a structure within and across the candidates. E.g. If we\n  know that C0 is invalid already because of G0-R0 and G1-R0 tries\n  to consume the same singe resource from R0 then:\n\n  * We don\u0027t need to check how G2 is mapped in C0 as that mapping cannot\n    change the fact the whole candidate is invalid.\n\n  * We know that every candidate that starts with G0-R0, G1-R0 are\n    invalid for the same reason and we don\u0027t need to generate and\n    test them\n\nThe latter means that C1...Cy (y \u003c x - 1) can be pruned out from the\nsearch space after C0 is tested. This is a lot of candidates. In the\nabove natural ordering of the product generation algorithm it is\nactually more than 40K candidates that we can skip after just testing\nC0 alone. When we reach Cx, the first valid candidate, the algo already\npruned out more than 300k candidates.\n\nAfter this patch the above pruning logic is not turned on automatically\nbut can be enabled via the config option:\n\n  [workarounds]\n  optimize_for_wide_provider_trees \u003d true\n\nThe implementation consists of the following pieces:\n\nA recursive product generator algorithm that calls a function on each\npartial candidate and if that function signals that the partial\ncandidate is invalid then the algorithm does skips any candidate that\nhas the same partial candidate prefix.\n\nThe recursion does a tree traversal to find all partial prefixes.\nWith the above G0-G8, RP0, RP8 example the start of the traversal\nlooks like:\n1. partial product G0-RP0, this does not exceed capacity so recurse\n2. partial product G0-RP0, G1-RP0, this exceeds capacity so do not\n   recurse but try another RP on this level.\n3. partial product G0-RP0, G1-RP1, this does not exceeds capacity so\n   recurse.\n4. partial product G0-RP0, G1-RP1, G2-RP0, this exceeds capacity so\n   do not recurse but try another RP on this level\n...\n\nWithout the optimization Placement uses the logic\n\n        areq \u003d _consolidate_allocation_requests(areq_list, rw_ctx)\n        if rw_ctx.exceeds_capacity(areq)\n            continue\n\non all products after it was generated. The\n_consolidate_allocation_requests folds the individual\nAllocationRequestResource object in the product into a single\nallocation. This has a side effect on some of the ARRs so the logic does\ncopy the affected ARRs. This is expensive especially if we want to call\nit on every partial product as well. However if we only want to check\nthe capacity we don\u0027t need to fold the ARRs we just need to sum the\namount each ARR hold and the check that against the capacity. So\n_exceeds_capacity() was added to do this optimized, side effect and copy\nfree, capacity check when the optimization is enabled.\n\nWhen a valid product is generated _consolidate_allocation_requests still\nneeds to be called to get the folded AllocationRequest in any case as\nthe caller of _merge_candidates expects such structure. But the final\nrw_ctx.exceeds_capacity can we skipped if the optimization is enabled.\n\nThe depth of the recursion is equal to the number of iterables passed to\nthe product call. It can be seen by the fact that each level of\nrecursion appends a new item to the partial product and when the length\nof the partial product equals to the number of iterables then we have a\nfull product and the algo yields. The default python recursion limit is\n1000 so we are not really limited by that as that means we could handle\n~ 990 iterables, meaning an allocation candidate query with 990 request\ngroups. The limiting factor of this algorithm is not recursion depth but\nexecution time.\n\nGemini 2.5 pro was used to put together the generic Cartesian product\nalgorithm.\n\nCo-Authored-by: Sean Mooney \u003cwork@seanmooney.info\u003e\nAssisted-By: gemini-2.5-pro\nCloses-Bug: #2126751\nChange-Id: I13ab83a165c229ae57876df4570e8af25221a45e\nSigned-off-by: Balazs Gibizer \u003cgibi@redhat.com\u003e\n(cherry picked from commit 5b73b980d0f022de2855480f57c9d5f04a7a4712)\n","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/placement/commit/192f62baada531b8ae96a2e6eac07506034dbdc3"}],"resolve_conflicts_web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/placement/commit/192f62baada531b8ae96a2e6eac07506034dbdc3"}]},"branch":"refs/heads/stable/2025.2"}},"requirements":[],"submit_records":[{"rule_name":"gerrit~DefaultSubmitRule","status":"CLOSED","labels":[{"label":"Verified","status":"MAY","applied_by":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}},{"label":"Code-Review","status":"MAY","applied_by":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"}},{"label":"Workflow","status":"MAY","applied_by":{"_account_id":17685,"name":"Elod Illes","email":"elod.illes@est.tech","username":"elod.illes"}},{"label":"Review-Priority","status":"MAY"}]}],"submit_requirements":[{"name":"Verified","description":"Verified in gate by CI","status":"SATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Verified\u003dMAX AND -label:Verified\u003dMIN","fulfilled":true,"status":"PASS","passing_atoms":["label:Verified\u003dMAX"],"failing_atoms":["label:Verified\u003dMIN"],"atom_explanations":{}}},{"name":"Code-Review","description":"Code reviewed by core reviewer","status":"SATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Code-Review\u003dMAX AND -label:Code-Review\u003dMIN","fulfilled":true,"status":"PASS","passing_atoms":["label:Code-Review\u003dMAX"],"failing_atoms":["label:Code-Review\u003dMIN"],"atom_explanations":{}}},{"name":"Review-Priority","description":"Review Priority","status":"NOT_APPLICABLE","is_legacy":false,"applicability_expression_result":{"fulfilled":false,"status":"FAIL"},"submittability_expression_result":{"expression":"is:true","fulfilled":true,"status":"NOT_EVALUATED","passing_atoms":[],"failing_atoms":[],"atom_explanations":{}}},{"name":"Workflow","description":"Approved for gate by core reviewer","status":"SATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Workflow\u003dMAX AND -label:Workflow\u003dMIN","fulfilled":true,"status":"PASS","passing_atoms":["label:Workflow\u003dMAX"],"failing_atoms":["label:Workflow\u003dMIN"],"atom_explanations":{}}}]}