)]}'
{"id":"openstack%2Fswift~983508","triplet_id":"openstack%2Fswift~master~I26a80354e9a6db3add5f0e6f88312cb6e44f64e5","project":"openstack/swift","branch":"master","topic":"ringv2_history_chain","attention_set":{"7233":{"account":{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},"last_update":"2026-06-01 10:29:51.000000000","reason":"A robot voted negatively on a label"},"6968":{"account":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"last_update":"2026-06-01 10:29:51.000000000","reason":"A robot voted negatively on a label"}},"removed_from_attention_set":{},"hashtags":[],"change_id":"I26a80354e9a6db3add5f0e6f88312cb6e44f64e5","subject":"Add PartHistory class that is a sparse/dense array hybrid","status":"NEW","created":"2026-04-07 05:01:51.000000000","updated":"2026-06-01 10:29:51.000000000","submit_type":"MERGE_IF_NECESSARY","mergeable":false,"submittable":false,"total_comment_count":1,"unresolved_comment_count":1,"has_review_started":true,"meta_rev_id":"699a7abecaf593fc3fb99dace0fea62f5c3ad7b4","_number":983508,"virtual_id_number":983508,"owner":{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},"actions":{},"labels":{"Verified":{"disliked":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"all":[{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},{"tag":"autogenerated:zuul:check","value":-1,"date":"2026-06-01 10:29:51.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":"","value":-1,"default_value":0,"optional":true},"Code-Review":{"disliked":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"all":[{"value":0,"permitted_voting_range":{"min":-2,"max":2},"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},{"value":-1,"date":"2026-06-01 08:21:52.000000000","permitted_voting_range":{"min":-2,"max":2},"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},{"value":0,"permitted_voting_range":{"min":-1,"max":1},"_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":"","value":-1,"default_value":0,"optional":true},"Workflow":{"all":[{"value":0,"permitted_voting_range":{"min":-1,"max":1},"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},{"value":0,"permitted_voting_range":{"min":-1,"max":1},"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},{"_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}},"removable_reviewers":[],"reviewers":{"REVIEWER":[{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]}]},"pending_reviewers":{},"reviewer_updates":[{"updated":"2026-04-07 05:30:59.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":"CC"},{"updated":"2026-04-07 07:05:36.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":"2026-05-18 09:08:43.000000000","updated_by":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"reviewer":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"state":"REVIEWER"}],"messages":[{"id":"753560e6dcf1951d473fc2e1bd92128832bffe33","tag":"autogenerated:gerrit:newPatchSet","author":{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},"date":"2026-04-07 05:01:51.000000000","message":"Uploaded patch set 1.","accounts_in_message":[],"_revision_number":1},{"id":"3cb40042d9a0bb66a920dfdd9843408a97b1a81f","author":{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},"date":"2026-04-07 05:14:09.000000000","message":"Patch Set 1: Workflow-1","accounts_in_message":[],"_revision_number":1},{"id":"504c9d29a6e7f84324e2cb9c7e926a5b399f0d2e","tag":"autogenerated:zuul:check-arm64","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2026-04-07 05:30:59.000000000","message":"Patch Set 1:\n\nBuild succeeded (ARM64 pipeline).\nhttps://zuul.opendev.org/t/openstack/buildset/498c56b4a16c486ebe465dae66da37a8\n\n- swift-tox-py312-arm64 https://zuul.opendev.org/t/openstack/build/8c4754487c3d4948b0eadbc045cdca4c : SUCCESS in 27m 03s","accounts_in_message":[],"_revision_number":1},{"id":"092bf2536d47f690f494c9a308b04f828c897d72","tag":"autogenerated:zuul:check","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2026-04-07 07:05:36.000000000","message":"Patch Set 1: Verified-1\n\nBuild failed (check pipeline).  For information on how to proceed, see\nhttps://docs.opendev.org/opendev/infra-manual/latest/developers.html#automated-testing\nand https://docs.openstack.org/project-team-guide/testing.html#how-to-handle-test-failures\n\nhttps://zuul.opendev.org/t/openstack/buildset/cf04776c069d4b1f9cb5fc12700bc4d4\n\n- openstack-tox-docs https://zuul.opendev.org/t/openstack/build/9c04dbf6bbde49c891f081c15346e383 : FAILURE in 6m 23s\n- grenade https://zuul.opendev.org/t/openstack/build/4982b1a2e71649da92abac8f5c7928af : SUCCESS in 1h 13m 28s\n- grenade-skip-level-always https://zuul.opendev.org/t/openstack/build/f52687499d52482e8536c19d91d02e0c : SUCCESS in 50m 57s\n- tempest-integrated-object-storage https://zuul.opendev.org/t/openstack/build/7cb0f77caed04f489c92b77bd465703a : SUCCESS in 51m 27s\n- openstacksdk-functional-devstack https://zuul.opendev.org/t/openstack/build/28957c4244654f7db03854c6382565ca : SUCCESS in 36m 59s\n- swift-tox-func-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/9dc1cfbef4224ade99507c65bd434ad8 : SUCCESS in 10m 47s (non-voting)\n- swift-tox-func-encryption-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/78d32cb8f3f148c5bf32053ed9420ab8 : SUCCESS in 11m 56s (non-voting)\n- swift-tox-func-ec-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/3872c750e17a43698232050ddf6c7f04 : SUCCESS in 17m 51s (non-voting)\n- swift-build-image https://zuul.opendev.org/t/openstack/build/97d817dd9c174086924ade9776e6bd41 : SUCCESS in 6m 08s (non-voting)\n- swift-tox-py37 https://zuul.opendev.org/t/openstack/build/a81fdab6963742c0a428090fc2ac839d : SUCCESS in 18m 08s\n- swift-tox-py310 https://zuul.opendev.org/t/openstack/build/c09ae482397a4455b98c5dbecd657af3 : SUCCESS in 21m 05s\n- swift-tox-py313 https://zuul.opendev.org/t/openstack/build/89b29f6a9d7e4cb5a0c7db7cd48c0089 : SUCCESS in 28m 54s\n- swift-tox-py314 https://zuul.opendev.org/t/openstack/build/a90a2f77ffe941ea88caf562cf28c263 : SUCCESS in 20m 53s\n- swift-tox-func-py312 https://zuul.opendev.org/t/openstack/build/29545a208dc140baad9761886e4239c0 : SUCCESS in 15m 48s\n- swift-tox-func-encryption-py312 https://zuul.opendev.org/t/openstack/build/c39aaf30ca7a4dd78707fe39ab4d93ea : SUCCESS in 9m 06s\n- swift-tox-func-ec-py312 https://zuul.opendev.org/t/openstack/build/6a71337bef8a4062a7a9d4de4e2620ff : SUCCESS in 19m 32s\n- swift-func-cors https://zuul.opendev.org/t/openstack/build/9114e2fb741149ef8cbe54b24e237e9f : SUCCESS in 6m 34s\n- swift-tox-func-ceph-s3tests-tempauth https://zuul.opendev.org/t/openstack/build/77d323d5768c4c1d8bf72e24f7886683 : SUCCESS in 18m 21s (non-voting)\n- swift-tox-func-s3api-compat-tests-tempauth https://zuul.opendev.org/t/openstack/build/141838bc80f3400f8bdfd458f30269f9 : SUCCESS in 8m 15s\n- swift-probetests-centos-9-stream https://zuul.opendev.org/t/openstack/build/b0272aec8dc742119198e286dae8dd9b : TIMED_OUT in 2h 01m 19s\n- swift-dsvm-functional https://zuul.opendev.org/t/openstack/build/952f68d6a43f40adbaf980158c19c08c : SUCCESS in 31m 42s\n- swift-dsvm-functional-ipv6 https://zuul.opendev.org/t/openstack/build/fa48eef93bd74ae6b8faa844da44b030 : SUCCESS in 53m 17s\n- swift-tox-lower-constraints https://zuul.opendev.org/t/openstack/build/f7ed1b4b77bf4727b972ebe0531bd609 : SUCCESS in 25m 13s\n- openstack-tox-pep8 https://zuul.opendev.org/t/openstack/build/40eaa4b6b9b8486b91706be0e336363f : SUCCESS in 4m 15s\n- swift-multinode-rolling-upgrade https://zuul.opendev.org/t/openstack/build/7f064f02f04242ce9571f3e8ff5d624b : SUCCESS in 18m 34s\n- tempest-ipv6-only https://zuul.opendev.org/t/openstack/build/124863e81ae7496aa5d72349e9430847 : SUCCESS in 46m 34s","accounts_in_message":[],"_revision_number":1},{"id":"6651e5ec2178deddf0d57e228817b2ecb098f0d5","author":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"date":"2026-05-18 09:08:43.000000000","message":"Patch Set 1: Code-Review-1\n\n(1 comment)","accounts_in_message":[],"_revision_number":1},{"id":"bb1e2549eb997103d492e069d253bb1af5062d18","tag":"autogenerated:gerrit:newPatchSet","author":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"date":"2026-06-01 08:21:52.000000000","message":"Uploaded patch set 2: Patch Set 1 was rebased.\n\nCopied Votes:\n* Code-Review-1 (copy condition: \"**changekind:TRIVIAL_REBASE** OR is:MIN\")\n\nOutdated Votes:\n* Verified-1 (copy condition: \"NEVER\")\n* Workflow-1 (copy condition: \"NEVER\")\n","accounts_in_message":[],"_revision_number":2},{"id":"4d4341ae145001fdbd620c8f23055968cc6ae630","tag":"autogenerated:zuul:check-arm64","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2026-06-01 10:17:09.000000000","message":"Patch Set 2:\n\nBuild succeeded (ARM64 pipeline).\nhttps://zuul.opendev.org/t/openstack/buildset/42ee05a4627f46f281bd34db9f057b95\n\n- swift-tox-py312-arm64 https://zuul.opendev.org/t/openstack/build/c3799b30d25a45e1a8779d733acab255 : SUCCESS in 1h 03m 26s","accounts_in_message":[],"_revision_number":2},{"id":"699a7abecaf593fc3fb99dace0fea62f5c3ad7b4","tag":"autogenerated:zuul:check","author":{"_account_id":22348,"name":"Zuul","username":"zuul","tags":["SERVICE_USER"]},"date":"2026-06-01 10:29:51.000000000","message":"Patch Set 2: Verified-1\n\nBuild failed (check pipeline).  For information on how to proceed, see\nhttps://docs.opendev.org/opendev/infra-manual/latest/developers.html#automated-testing\nand https://docs.openstack.org/project-team-guide/testing.html#how-to-handle-test-failures\n\nhttps://zuul.opendev.org/t/openstack/buildset/20f0c44cc7e74f60bbddd18b355128d8\n\n- openstack-tox-docs https://zuul.opendev.org/t/openstack/build/418ff94e4f7745ea98da63b18de67448 : FAILURE in 7m 39s\n- build-openstack-releasenotes https://zuul.opendev.org/t/openstack/build/766cc81021f543de9bd986f6565ce1e4 : SUCCESS in 8m 58s\n- grenade https://zuul.opendev.org/t/openstack/build/9da671aa30d74ed595f6f6170b968ead : SUCCESS in 1h 03m 39s\n- grenade-skip-level-always https://zuul.opendev.org/t/openstack/build/e7082ffc19a7421e98ed12d6f06d49c0 : SUCCESS in 1h 02m 16s\n- tempest-integrated-object-storage https://zuul.opendev.org/t/openstack/build/329ad31cab2a48a0a2cbe8b345a45b56 : SUCCESS in 57m 00s\n- openstacksdk-functional-devstack https://zuul.opendev.org/t/openstack/build/926a410e8b1b43e4bdcc8f5e3f898776 : SUCCESS in 1h 02m 08s\n- swift-tox-func-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/27cd4ca944dc484db4b12f0bc09760d6 : SUCCESS in 18m 05s (non-voting)\n- swift-tox-func-encryption-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/cff5f308df984456b4a45e8d719fc47d : SUCCESS in 19m 59s (non-voting)\n- swift-tox-func-ec-py39-centos-9-stream-fips https://zuul.opendev.org/t/openstack/build/3e7b47692f3043ed9b537cc9958b2510 : SUCCESS in 20m 37s (non-voting)\n- swift-build-image https://zuul.opendev.org/t/openstack/build/f1f5ee8bba364f8baf3ec5743814598b : SUCCESS in 6m 12s (non-voting)\n- swift-tox-py37 https://zuul.opendev.org/t/openstack/build/389238424d30499784daf4a89eda9327 : SUCCESS in 25m 10s\n- swift-tox-py310 https://zuul.opendev.org/t/openstack/build/cd305351280b453d9e89ab84e284ca5a : SUCCESS in 17m 24s\n- swift-tox-py313 https://zuul.opendev.org/t/openstack/build/534408b317d34079b8ea73c5e0fb79e9 : SUCCESS in 37m 14s\n- swift-tox-py314 https://zuul.opendev.org/t/openstack/build/90c386f04be341f9afcaa9edd14382fc : SUCCESS in 19m 21s\n- swift-tox-func-py312 https://zuul.opendev.org/t/openstack/build/9bbaf5bb30ee4d079f8a4b9f8258e40d : SUCCESS in 15m 25s\n- swift-tox-func-encryption-py312 https://zuul.opendev.org/t/openstack/build/66dd02ef9f7f422789f391d98530acea : SUCCESS in 13m 32s\n- swift-tox-func-ec-py312 https://zuul.opendev.org/t/openstack/build/e7fcfb58e0444f93aefdc45b6976183f : SUCCESS in 16m 34s\n- swift-func-cors https://zuul.opendev.org/t/openstack/build/4771c243a10e4fdc9fc0af10c67fa857 : SUCCESS in 4m 07s\n- swift-tox-func-ceph-s3tests-tempauth https://zuul.opendev.org/t/openstack/build/8c42d4b5d05a4515b6c2484e51352ab5 : SUCCESS in 18m 18s (non-voting)\n- swift-tox-func-s3api-compat-tests-tempauth https://zuul.opendev.org/t/openstack/build/ca6657139be248dc80b376411d904cdc : SUCCESS in 10m 04s\n- swift-probetests-centos-9-stream https://zuul.opendev.org/t/openstack/build/865785a5269a46a29df5fafb9ef1156a : TIMED_OUT in 2h 01m 12s\n- swift-dsvm-functional https://zuul.opendev.org/t/openstack/build/8999f3daaf1a4bc397ef9dffa1d5977e : SUCCESS in 27m 28s\n- swift-dsvm-functional-ipv6 https://zuul.opendev.org/t/openstack/build/90af796eeb3142c190c96d268ec7233c : SUCCESS in 38m 16s\n- swift-tox-lower-constraints https://zuul.opendev.org/t/openstack/build/b6c9b74619384d619d3dc7cfe1b963ec : SUCCESS in 24m 03s\n- openstack-tox-pep8 https://zuul.opendev.org/t/openstack/build/08b341e44b514b7489197f0ebd5d9e95 : SUCCESS in 5m 38s\n- swift-multinode-rolling-upgrade https://zuul.opendev.org/t/openstack/build/ae628ed9cc854c798f1e4ae7c545ad02 : SUCCESS in 13m 36s\n- tempest-ipv6-only https://zuul.opendev.org/t/openstack/build/f4bb7ac8d2a94e22a0703b94698aa00d : SUCCESS in 44m 34s","accounts_in_message":[],"_revision_number":2}],"current_revision_number":2,"current_revision":"387de8e7865909259113b7b50856b9b6b22d6be7","revisions":{"7a731ea72f362e0cf095f6f87c35b933565e2002":{"kind":"REWORK","_number":1,"created":"2026-04-07 05:01:51.000000000","uploader":{"_account_id":7233,"name":"Matthew Oliver","email":"matt@oliver.net.au","username":"mattoliverau"},"ref":"refs/changes/08/983508/1","fetch":{"anonymous http":{"url":"https://review.opendev.org/openstack/swift","ref":"refs/changes/08/983508/1","commands":{"Checkout":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/1 \u0026\u0026 git checkout FETCH_HEAD","Cherry Pick":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/1 \u0026\u0026 git cherry-pick FETCH_HEAD","Format Patch":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/1 \u0026\u0026 git format-patch -1 --stdout FETCH_HEAD","Pull":"git pull https://review.opendev.org/openstack/swift refs/changes/08/983508/1"}}},"commit":{"parents":[{"commit":"2555abd104b902c3274f804778a4c170598421a3","subject":"ring: Add a rebalance history in the ring","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/2555abd104b902c3274f804778a4c170598421a3"}]}],"author":{"name":"Matthew Oliver","email":"matt@oliver.net.au","date":"2026-04-07 04:45:38.000000000","tz":600},"committer":{"name":"Matthew Oliver","email":"matt@oliver.net.au","date":"2026-04-07 04:58:52.000000000","tz":600},"subject":"Add PartHistory class that is a sparse/dense array hybrid","message":"Add PartHistory class that is a sparse/dense array hybrid\n\nUsing an array.array when storing last primaries would be fine if every\nrebalance moved every or most partitions. But many rebalances are just\ntaking a broken drive out of the ring.\nIn the small rebalance case, almost all elements in the array will be\nthe none_dev_id. This is alot of wasted space.\nIt would be much better to have a sparse style array which only stores\nwhat\u0027s changed and the default (the none_dev_id) only needs to be a\nsingle value.\n\nThat is what this is calling a sparse array, and this is much more\nefficient when we can smaller rebalaces, but the data structure can\nquickly become far more inefficient when too many partitions move.\n\nEnter the PartHistory class, which will store in sparse mode until the\nSPARSE_THRESHOLD (currently 0.5 or 50%) has passed then will be promoted\nto a dense array, i.e. single array.array like a ring replica.\n\nThis does cause some serialisation issues in ringv2, we need to store\nwhether a snapshot in rebalance history is sparse or dense. So.\n\n    [total length]\n    [num_histories: uint32]\n    for each history table:\n      [format: uint8]   # 0 \u003d sparse, 1 \u003d dense\n      if sparse:\n        [count: uint32]\n        [part_ids: uint32 * count]\n        [values: dev_id_bytes * count]\n      if dense:\n        [values: dev_id_bytes * num_parts]\n\nChange-Id: I26a80354e9a6db3add5f0e6f88312cb6e44f64e5\nSigned-off-by: Matthew Oliver \u003cmatt@oliver.net.au\u003e\n","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/7a731ea72f362e0cf095f6f87c35b933565e2002"}],"resolve_conflicts_web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/7a731ea72f362e0cf095f6f87c35b933565e2002"}]},"branch":"refs/heads/master"},"387de8e7865909259113b7b50856b9b6b22d6be7":{"kind":"TRIVIAL_REBASE","_number":2,"created":"2026-06-01 08:21:52.000000000","uploader":{"_account_id":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"},"ref":"refs/changes/08/983508/2","fetch":{"anonymous http":{"url":"https://review.opendev.org/openstack/swift","ref":"refs/changes/08/983508/2","commands":{"Checkout":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/2 \u0026\u0026 git checkout FETCH_HEAD","Cherry Pick":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/2 \u0026\u0026 git cherry-pick FETCH_HEAD","Format Patch":"git fetch https://review.opendev.org/openstack/swift refs/changes/08/983508/2 \u0026\u0026 git format-patch -1 --stdout FETCH_HEAD","Pull":"git pull https://review.opendev.org/openstack/swift refs/changes/08/983508/2"}}},"commit":{"parents":[{"commit":"5764d9c65648fb2ae380d1d9df70c6553b9b8186","subject":"ring: Add a rebalance history in the ring","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/5764d9c65648fb2ae380d1d9df70c6553b9b8186"}]}],"author":{"name":"Matthew Oliver","email":"matt@oliver.net.au","date":"2026-04-07 04:45:38.000000000","tz":600},"committer":{"name":"Christian Schwede","email":"cschwede@mailbox.org","date":"2026-05-31 14:23:39.000000000","tz":120},"subject":"Add PartHistory class that is a sparse/dense array hybrid","message":"Add PartHistory class that is a sparse/dense array hybrid\n\nUsing an array.array when storing last primaries would be fine if every\nrebalance moved every or most partitions. But many rebalances are just\ntaking a broken drive out of the ring.\nIn the small rebalance case, almost all elements in the array will be\nthe none_dev_id. This is alot of wasted space.\nIt would be much better to have a sparse style array which only stores\nwhat\u0027s changed and the default (the none_dev_id) only needs to be a\nsingle value.\n\nThat is what this is calling a sparse array, and this is much more\nefficient when we can smaller rebalaces, but the data structure can\nquickly become far more inefficient when too many partitions move.\n\nEnter the PartHistory class, which will store in sparse mode until the\nSPARSE_THRESHOLD (currently 0.5 or 50%) has passed then will be promoted\nto a dense array, i.e. single array.array like a ring replica.\n\nThis does cause some serialisation issues in ringv2, we need to store\nwhether a snapshot in rebalance history is sparse or dense. So.\n\n    [total length]\n    [num_histories: uint32]\n    for each history table:\n      [format: uint8]   # 0 \u003d sparse, 1 \u003d dense\n      if sparse:\n        [count: uint32]\n        [part_ids: uint32 * count]\n        [values: dev_id_bytes * count]\n      if dense:\n        [values: dev_id_bytes * num_parts]\n\nChange-Id: I26a80354e9a6db3add5f0e6f88312cb6e44f64e5\nSigned-off-by: Matthew Oliver \u003cmatt@oliver.net.au\u003e\n","web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/387de8e7865909259113b7b50856b9b6b22d6be7"}],"resolve_conflicts_web_links":[{"name":"gitea","tooltip":"Open in GitWeb","url":"https://opendev.org/openstack/swift/commit/387de8e7865909259113b7b50856b9b6b22d6be7"}]},"branch":"refs/heads/master"}},"requirements":[],"submit_records":[{"rule_name":"gerrit~DefaultSubmitRule","status":"OK","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":6968,"name":"Christian Schwede","email":"cschwede@nvidia.com","username":"cschwede"}},{"label":"Workflow","status":"MAY"}]}],"submit_requirements":[{"name":"Verified","description":"Verified in gate by CI","status":"UNSATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Verified\u003dMAX AND -label:Verified\u003dMIN","fulfilled":false,"status":"FAIL","passing_atoms":[],"failing_atoms":["label:Verified\u003dMAX","label:Verified\u003dMIN"],"atom_explanations":{"label:Verified\u003dMAX":"","label:Verified\u003dMIN":""}}},{"name":"Code-Review","description":"Code reviewed by core reviewer","status":"UNSATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Code-Review\u003dMAX AND -label:Code-Review\u003dMIN","fulfilled":false,"status":"FAIL","passing_atoms":[],"failing_atoms":["label:Code-Review\u003dMAX","label:Code-Review\u003dMIN"],"atom_explanations":{"label:Code-Review\u003dMAX":"","label:Code-Review\u003dMIN":""}}},{"name":"Workflow","description":"Approved for gate by core reviewer","status":"UNSATISFIED","is_legacy":false,"submittability_expression_result":{"expression":"label:Workflow\u003dMAX AND -label:Workflow\u003dMIN","fulfilled":false,"status":"FAIL","passing_atoms":[],"failing_atoms":["label:Workflow\u003dMAX","label:Workflow\u003dMIN"],"atom_explanations":{"label:Workflow\u003dMAX":"","label:Workflow\u003dMIN":""}}}]}