placement — Rewrite pack

Rewrite pack — placement — branch stable/2026.2

Branch stable/2026.2 @ f4a89d3803cb — repository https://opendev.org/openstack/placement — analysed on 2026-10-28

This file is the entry point of the rewrite pack: what a team needs, on top of files 01 to 06, to re-implement Placement in another language (for example Go) and stay a drop-in replacement for Nova, Neutron and Cyborg. Files 01 to 06 explain the behaviour. This file and _rewrite/ give the machine-readable contracts, the parts that cannot be derived from them without reading the code (the allocation-candidates algorithm), the expectations of the clients, and a conformance strategy.

1. Contents of _rewrite/

All files were extracted from the code of this branch by rewrite_pack.py, run in a virtual environment where openstack-placement and its requirements are installed. The index is [_rewrite/rewrite-pack-index_stable-2026.2.md](_rewrite/rewrite-pack-index_stable-2026.2.md).

The last six files were produced by conformance_capture.py (skill generate-reverse-spec, Placement adapter), which runs the project's own tests with recording; see § 7 for the commands.

Library versions used for the extraction: openstack-placement 16.0.1.dev2, os-traits 3.9.0, os-resource-classes 1.1.0, oslo.policy 6.0.1, keystonemiddleware 13.0.1, microversion-parse 2.1.0, oslo.config 10.7.0, oslo.db 18.1.1, SQLAlchemy 2.1.6 (upper-constraints pins 2.0.52; the DDL does not depend on that difference), gabbi 4.2.3.

2. HTTP behaviour that the contracts do not show

2.1 Middleware pipeline

Order for an incoming request (placement/deploy.py:76-119), outermost first:

1. osprofiler (only if enabled);
2. HTTPProxyToWSGI (X-Forwarded-*);
3. RequestLog (one access-log line per request, placement/requestlog.py);
4. CORS (only if [cors] is configured);
5. authentication: PlacementAuthProtocol, a keystonemiddleware auth_token that **lets GET / through without a token** (placement/auth.py:90-116), or NoAuthMiddleware when [api]/auth_strategy = noauth2 (placement/auth.py:42);
6. PlacementKeystoneContext: builds the request context and returns 401 when there is no user outside / (placement/auth.py:76-88);
7. FaultWrapper: any unexpected exception becomes a JSON 500;
8. MicroversionMiddleware (microversion-parse): parses OpenStack-API-Version: placement X.Y, answers 406 for a version outside 1.0–1.39 and 400 for a malformed one, and adds OpenStack-API-Version and Vary to the response (placement/deploy.py:85-87);
9. PlacementHandler: routing, 404/405, then the handler.

A rewrite must keep this order where it is observable: for example, a request without a token and with an invalid microversion gets 401, not 406, because authentication runs first.

2.2 Error body

Every error, including 404 and 405 from routing, has the same JSON body produced by json_error_formatter (placement/util.py):

{"errors": [{"status": 409, "title": "Conflict", "detail": "…", "code": "placement.concurrent_update", "request_id": "req-…"}]}

code appears from 1.23. It is placement.undefined_code when the handler gave none. The list of codes and of the handlers that emit them is in errors. **The detail text is part of the contract**: Nova parses it (see § 4).

2.3 Other cross-cutting rules

• Content-Type other than application/json on a body → 415. Accept that excludes JSON → 406 (see interactions).
• From 1.15, GET responses carry Last-Modified (the most recent updated_at or created_at of the returned objects, placement/util.py:135-146, or the current time) and Cache-Control: no-cache.
• UUIDs in paths and bodies are accepted with or without dashes when the schema says format: uuid, but are always returned in canonical form [inferred from the jsonschema format checker, not verified for every route].
• Query-string parameters are validated by the query schemas in request-schemas_stable-2026.2.json; unknown parameters are rejected with 400 (additionalProperties: false).

3. Allocation candidates: formal specification

GET /allocation_candidates (placement/handlers/allocation_candidate.py:259) is the only part of Placement with a real algorithm. A rewrite that only follows the API reference will return different candidates, in a different order, with different performance. This section states the algorithm as implemented.

3.1 Input model

The query string is parsed into request groups (placement/lib.py:236):

• the unsuffixed group resources, required, member_of, in_tree. It has use_same_provider = False: its resources may come from several providers of one tree, plus sharing providers (placement/lib.py:126);
• granular groups resources<S>, required<S>, member_of<S>, in_tree<S>, with a suffix S (1.25+: any string of 1–64 [A-Za-z0-9_-]; 1.22–1.24: digits). They have use_same_provider = True: all the resources of one granular group come from a single provider;
• request-wide parameters (placement/lib.py:405-445): limit, group_policy (none or isolate, required when there is more than one granular group: 400 otherwise, placement/handlers/allocation_candidate.py:275-281), root_required (1.35+), same_subtree (1.36+).

Validation rules, all answering 400 (placement/lib.py:153-232):

• every group with required or member_of must have resources; every group must have resources; at least one group must exist. From 1.36 a group listed in same_subtree may have no resources (placement/lib.py:153-170);
• a trait cannot be both required and forbidden in the same group;
• the suffixes in same_subtree must exist.

required syntax: T (required), !T (forbidden, 1.22+), in:A,B (any of, 1.39+). Several required parameters in the same group are ANDed. member_of: in:A,B (any of), several parameters ANDed, ! forbidden (1.32+).

3.2 Capacity of a provider for a class

For an inventory record (provider P, class C):

capacity(P, C) = floor((total - reserved) * allocation_ratio)
used(P, C)     = sum(allocations.used where provider = P and class = C)

(placement/objects/allocation_candidate.py:571-578). An amount a of class C fits on P when

used + a <= capacity  AND  min_unit <= a <= max_unit  AND  a mod step_size == 0

(SQL form in placement/objects/research_context.py:421-501, reproduced in interactions).

3.3 Algorithm

function allocation_candidates(groups, params, microversion):
    nested_aware := microversion >= 1.29
    sharing := providers having trait MISC_SHARES_VIA_AGGREGATE        # placement/objects/research_context.py:1194
    candidates := {}
    for each group g (in query order):
        record per class the total amount over all groups, and the classes requested by more than one group (multi_group_rcs)
        areqs := search_one_group(g)
        if areqs is empty: return ([], [])                            # short-circuit, placement/objects/allocation_candidate.py:162-165
        mark each areq with g.use_same_provider
        candidates[g.suffix] := areqs
    (areqs, summaries) := merge(candidates)
    if not nested_aware: drop areqs that use two providers of the same tree   # placement/objects/research_context.py:262-292
    return limit(areqs, summaries)

(placement/objects/allocation_candidate.py:135-182)

search_one_group (placement/objects/allocation_candidate.py:84-131):

• if the group is unsuffixed and sharing providers or trees exist: find trees that can satisfy all the group's resources together, taking each class from any provider of the tree or from a sharing provider associated with it by an aggregate (get_trees_matching_all, placement/objects/research_context.py:617). Short-cut first: if the group requires traits and no provider at all has any of them, return nothing. Build every combination of (one provider per class) inside each tree (_alloc_candidates_multiple_providers, placement/objects/allocation_candidate.py:300-396). Required and forbidden traits of the unsuffixed group apply to the union of the providers used by an allocation request (_check_traits_for_alloc_request, placement/objects/allocation_candidate.py:590);
• otherwise (granular group, or flat world): find the providers that alone have all the group's resources with free capacity, the required traits, no forbidden trait, and the required aggregates (get_provider_ids_matching, placement/objects/research_context.py:530). One allocation request per provider (_alloc_candidates_single_provider, placement/objects/allocation_candidate.py:397-462).
• Each allocation request carries an anchor: the root of the tree it belongs to. For a sharing provider used alone, the anchors are the roots of the trees that share its aggregates (anchors_for_sharing_providers, placement/objects/research_context.py:1257). in_tree and root_required filter anchors (placement/objects/research_context.py:223-260).

merge (placement/objects/allocation_candidate.py:867-976):

1. Group the per-suffix allocation requests by anchor.
2. For each anchor, keep it only if it has a candidate for every suffix, and if the overall-capacity pre-check passes: for each class requested by several groups, the sum of the capacities of all the providers appearing in that anchor's candidates must be at least the total requested amount. This is the bug 2160721 fix (_pre_check_overall_capacity, placement/objects/allocation_candidate.py:794-844). It only removes trees that could never fit; it never changes the result set.
3. For each kept anchor, generate the Cartesian product of its per-suffix lists, in suffix order (_get_areq_list_generators, placement/objects/allocation_candidate.py:747-791).
   • [placement]/allocation_candidates_generation_strategy (placement/conf/placement.py:93): depth-first (default) exhausts one anchor after the other; breadth-first takes one product element from each anchor in turn (round robin) (placement/objects/allocation_candidate.py:847-864).
   • [workarounds]/optimize_for_wide_provider_trees (default False, placement/conf/workarounds.py:30) prunes the product as it is built, dropping partial combinations that already exceed a capacity (util.filtered_product). The results are the same, only faster on wide trees.
4. For each combination, in generation order:
   • group_policy=isolate: the granular groups must use as many distinct providers as there are granular groups (_satisfies_group_policy, placement/objects/allocation_candidate.py:978-1020). The unsuffixed group is not concerned;
   • same_subtree: for each listed set of suffixes, the providers used must all descend from one of them (placement/objects/allocation_candidate.py:1023-1064);
   • consolidate: merge the resource requests of all groups into one allocation request, adding amounts for the same (provider, class) (placement/objects/allocation_candidate.py:658-694);
   • capacity: reject it if, for any (provider, class), used + amount > capacity or amount > max_unit (placement/objects/research_context.py:348-372). This catches two groups taking the same class from the same provider;
   • add it to a set (duplicates collapse); stop when [placement]/max_allocation_candidates (default −1, no limit) is reached.
5. Provider summaries: every provider of every tree used by at least one result, with capacity, used and traits.

limit (placement/objects/research_context.py:294-326):

• with limit=N and more than N results: random.sample(N) if [placement]/randomize_allocation_candidates is True, otherwise the first N; summaries are trimmed to the trees still used;
• without a limit: random.shuffle if randomisation is on.

3.4 Ordering and determinism

The results come out of a Python set, so their order is not part of the contract. Clients must not depend on it, and Nova does not. A rewrite does not have to reproduce the order, but it must reproduce:

• which candidates exist when there is no limit and no max_allocation_candidates;
• the fact that max_allocation_candidates cuts during generation, so with depth-first the first anchors are favoured. This is why operators switch to breadth-first with a cap;
• the fact that limit is applied after generation.

The gabbi tests for candidates compare sets or counts, not order (see conformance_stable-2026.2.md), which confirms this reading [inferred from the test files read, not checked one by one].

Replaying the recorded cases showed one more point: **with a limit that truncates the result and no randomisation, "the first N" is not reproducible either**. The set's iteration order depends on Python's per-process hash seed, so two runs of the Python service on the same data can return different candidates (on the first replay, case 0009 of cases-allocation-candidates_stable-2026.2.json, limit=1 with two possible candidates, returned the other candidate than the recording). A rewrite only has to return N valid candidates.

3.5 Response shape by microversion

The observed schemas are in response-schemas_stable-2026.2.json (operation GET /allocation_candidates, status 200); the rules below come from the code.

placement/handlers/allocation_candidate.py:38-243:

• < 1.12: allocation_requests as a list of {resource_provider: {uuid}, resources: {...}}; ≥ 1.12: a dict keyed by provider UUID;
• ≥ 1.17: traits in summaries; ≥ 1.27: all classes of each provider in summaries, not only the requested ones; ≥ 1.29: parent_provider_uuid and root_provider_uuid in summaries, and nested results; ≥ 1.34: mappings (suffix → provider UUIDs) in each allocation request;
• ≥ 1.15: Last-Modified and Cache-Control.

3.6 Test cases of the algorithm

cases-allocation-candidates_stable-2026.2.json holds 83 cases, recorded from the 48 tests (of 60) of placement/tests/functional/db/test_allocation_candidates.py and placement/tests/functional/test_allocation_candidates.py that call the algorithm; the other tests check internal functions. Each case gives:

• rows: the database state at call time, table by table (standard traits and classes only when a row references them);
• request: the equivalent HTTP request, as a list of query parameters and as a query string, with OpenStack-API-Version (1.39, or 1.28 when the test asked for the pre-nested behaviour) and X-Auth-Token: admin for noauth2;
• config: the four algorithm options of § 3.3;
• expected: the allocation requests (allocations per provider and class, mappings) and provider summaries, normalised and sorted; or the error for the one failing case (unknown trait → 400). Above 200 candidates (13 cases, up to 8192), the allocation requests are given as a SHA-256 digest of their canonical JSON (sorted keys, no spaces) and the summaries as the list of providers;
• deterministic: false for the 14 cases where only the number of candidates can be compared (randomisation, or truncation by limit);
• replay: the result of the replay against the Python service.

Replay result, identical on two runs: 68 exact matches (digests included), 14 matches on size, 1 matching error, so all 83 pass. The cases cover local, shared, nested and granular providers, traits, aggregates, group_policy, limit, and the four options: 19 cases use breadth-first, 11 optimize_for_wide_provider_trees, 20 a max_allocation_candidates cap, 2 randomisation. **Truncation by max_allocation_candidates is reproducible** (for example test_global_limit_hit: 8000 candidates under a cap of 8000, same digest on both replays), because it cuts during generation, in a deterministic order; truncation by limit is not (§ 3.4).

Limitation: some of these tests also assert how the kept candidates are spread over the trees (breadth-first "balanced" results). For the size-only cases, the case files do not encode that property; reproduce it from the test (placement/tests/functional/test_allocation_candidates.py) if the rewrite must keep it.

3.7 Performance targets

The Python implementation is CPU-bound in the product and capacity checks (exceeds_capacity is commented as "potentially called a million times", placement/objects/research_context.py:348-372). A compiled rewrite should do at least as well; the useful benchmarks are the wide-tree cases of bugs 2126751 and 2160721 (see change history).

4. What the clients expect

Nova is the main client. Its report client (nova/scheduler/client/report.py, Nova branch stable/2026.2 @ 8df1922926dd; references are written nova:<path>) depends on these details, which must be kept exactly:

Neutron and Cyborg use a smaller subset (providers, inventories, traits, in_tree, allocations for bandwidth and accelerators) [inferred, not read in their code]. Their contract is covered by the same API tests.

5. Database strategy

Recommendation: keep the existing schema and share it during migration. A rewrite that uses the same tables can run side by side with the Python service (blue/green or canary per controller) and be rolled back without data conversion.

• Schema: use schema-mysql_stable-2026.2.sql (or the PostgreSQL one). Keep the Alembic alembic_version table at the head revision of this branch, so that placement-manage db sync from Python stays usable and the two implementations agree on the schema version.
• No foreign key on allocations and inventories towards resource_providers (see schema-sqlite-migrated_stable-2026.2.sql): referential integrity is maintained by the code. Deleting a provider must refuse when allocations or children exist (409, see scenario 5), then delete its inventories, aggregate and trait links itself.
• Standard classes: IDs 0–20 are the positions in standard-resource-classes_stable-2026.2.json; custom classes start at 10000 (MIN_CUSTOM_RESOURCE_CLASS_ID, placement/objects/resource_class.py:35). Both rules must be kept, because the IDs are stored in inventories and allocations.
• Concurrency: keep optimistic locking by generation (UPDATE … WHERE generation = :g, 0 rows → 409 placement.concurrent_update), and **no SELECT … FOR UPDATE** (see interactions). Allocation writes must keep the server-side retry on a provider generation conflict, up to [placement]/allocation_conflict_retry_count (default 10), and the retry on deadlock. Consumer generation conflicts are not retried.
• Isolation: the Python service relies on MySQL's default REPEATABLE READ and on oslo.db enginefacade. The provider re-read during allocation retries uses an independent transaction (placement/objects/allocation.py:579-582). A rewrite must re-read outside the failed transaction too, or the retry will see the same stale snapshot.
• Startup: copy the standard traits and classes into the database (insert-only, duplicates ignored), as in async processing. sync_on_startup is an option, False by default.
• Online data migrations: set_root_provider_ids and create_incomplete_consumers are only needed for databases older than this branch. A rewrite can refuse to start when placement-status upgrade check would fail, instead of re-implementing them.

6. Authentication, policies, configuration and CLI

• Authentication: Keystone tokens validated against Keystone v3 (GET /v3/auth/tokens), with the service user of [keystone_authtoken], and a token cache. In Go, there is no keystonemiddleware: the rewrite must implement token validation, the cache, and the X-Service-Token handling itself, or sit behind a proxy that does it. noauth2 mode (the X-Auth-Token value is read as user:project, and user admin gets the admin role, placement/auth.py:42-66) is needed to run the gabbi tests.
• Policies: the 38 rules of policies_stable-2026.2.json, with scope checks always enforced (oslo.policy ≥ 6.0.0, see change history). Operators may override them in policy.yaml, written in the oslo.policy language (role:admin and system_scope:all, rule:…, project_id:%(project_id)s, @, !). A rewrite must parse that language, or the overrides of existing deployments will be lost. A policy failure returns 403 with placement.undefined_code.
• Configuration: keep the oslo.config INI format and option names of config_stable-2026.2.conf ([placement], [placement_database], [api], [keystone_authtoken], [cors], [oslo_policy], [workarounds]) so that deployment tools (devstack, kolla, OpenStack-Ansible, charms) keep working.
• CLI: placement-manage db sync|version|stamp|online_data_migrations and placement-status upgrade check, with their exit codes (async processing). They can stay in Python during a transition.

7. Conformance strategy

The gabbi tests are the conformance suite: 1316 declarative HTTP tests in 79 YAML files (placement/tests/functional/gabbits/), language-independent. conformance_stable-2026.2.md maps them to routes; GET /allocation_candidates alone has 217 tests in 18 files.

To replay them against a rewrite:

1. Run gabbi (Python) with gabbi-run against the URL of the rewritten service, in noauth2 mode, one YAML file at a time.
2. Before each file, reset the database and load that file's entry of fixture-seeds_stable-2026.2.json, which replaces the Python fixtures:
   • start from an empty schema and let the service insert the standard traits and classes, as at startup;
   • insert rows table by table, parents first, by natural key: when a row's unique key (traits.name, resource_classes.name, consumer_types.name…) already exists, use the existing row and re-point the foreign keys that referenced the old ID. Auto-increment IDs of standard traits are not stable across databases, names are;
   • export environ for gabbi ($ENVIRON[...] substitutions);
   • apply config (for example [cors] for placement/tests/functional/gabbits/cors.yaml) and policy (rules that differ from the defaults: OpenPolicyFixture opens every rule; with [oslo_policy]/enforce_new_defaults = false, oslo.policy ORs the deprecated check strings into four base rules). Files whose seed has no enforce_new_defaults override run with the new defaults (SecureRBACPolicyFixture). A test-only endpoint or a SQL loader in the rewrite's test harness can do this. Proof of sufficiency: the 79 files were re-run against the Python service with every fixture replaced by a loader of its seed: 1316 of 1316 tests pass, as in the reference run (replay-report_stable-2026.2.json). The fixtures being replaced are in placement/tests/functional/fixtures/gabbits.py, for reference:

1. Run the 83 algorithm cases of § 3.6: load rows (same loader), set config, send request, normalise the response as in expected and compare (as sets; by size when deterministic is false).
2. Differential testing: exchanges_stable-2026.2.json gives the Python responses of the whole gabbi run. Compare the rewrite's responses to them, ignoring generated values (UUIDs, request_id, dates, Location). Validate response bodies against response-schemas_stable-2026.2.json, and error texts against observed-errors_stable-2026.2.md.
3. At the end, run Tempest and the Nova functional tests that use a real Placement (nova/tests/functional, with the PlacementFixture replaced by the rewrite's URL) [inferred: requires adapting Nova's fixture].

8. Gaps found while building the pack

9. Non-functional requirements

• Stateless processes: no shared cache between requests (see interactions); any number of instances behind a load balancer.
• Latency: GET /allocation_candidates must stay within Nova's scheduler budget on large fleets; the other calls are a few SQL queries each.
• Observability: one access-log line per request with method, path, status, size, duration and microversion; propagate X-Openstack-Request-Id and return it in errors.
• Compatibility window: microversions 1.0 to 1.39 all supported at once; default 1.0 without a header.

10. Rewrite checklist

• [ ] Routing from routes_stable-2026.2.json, 404/405 with Allow, JSON error body
• [ ] Middleware order of § 2.1, microversion negotiation 1.0–1.39
• [ ] All request schemas applied per schema-selection_stable-2026.2.json
• [ ] Per-handler error conversion and placement.* codes from errors, including Nova-parsed detail texts
• [ ] Generations: providers, consumers, aggregates and traits; server-side retry for allocations only
• [ ] Allocation-candidates algorithm of § 3, with the four configuration options
• [ ] Keystone token validation and noauth2; oslo.policy rules, language and scope checks
• [ ] oslo.config option names and defaults; startup copy of standard traits and classes
• [ ] Shared schema at the same Alembic head; no new foreign keys
• [ ] Seed loader by natural key; 1316 gabbi tests green with fixture-seeds_stable-2026.2.json
• [ ] 83 algorithm cases green; responses valid against response-schemas_stable-2026.2.json; differential run against exchanges_stable-2026.2.json
• [ ] Change history of 06 applied (scope checks, bug 2160721, wide-tree workaround)

Source: reverse-spec-placement/07-rewrite-pack_stable-2026.2.md. The _rewrite/ and _inventory/ files are not published on the site.