[SERVER-56877] insert operations may fail to set index to multikey after aborted multikey catalog update Created: 12/May/21  Updated: 29/Oct/23  Resolved: 20/Jul/21

Status: Closed
Project: Core Server
Component/s: Storage
Affects Version/s: None
Fix Version/s: 5.0.2, 4.4.9, 5.1.0-rc0

Type: Bug Priority: Major - P3
Reporter: Benety Goh Assignee: Benety Goh
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
Related
related to SERVER-56882 unable to complete full validation on... Closed
related to SERVER-57775 collection metadata for multikey not ... Closed
related to SERVER-57178 add regression test for multikey comp... Closed
related to SERVER-57268 add multikey query to validate_multik... Closed
is related to SERVER-41766 Secondary may encounter prepare confl... Closed
is related to SERVER-43757 background validate must skip indexes... Closed
is related to SERVER-47694 fix multikey. again Closed
is related to SERVER-47812 Secondaries persist wildcard multikey... Closed
is related to SERVER-56002 listIndexes can read partial state fr... Closed
is related to SERVER-56023 listCollections can return empty meta... Closed
is related to SERVER-57127 Refactor multikey and other state out... Closed
is related to SERVER-53675 Allow validate to fix up multikey met... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v5.0, v4.4, v4.2, v4.0
Sprint: Execution Team 2021-05-31, Execution Team 2021-06-14
Participants:
Linked BF Score: 127

 Description   

When a storage transaction to update an index to multikey is aborted, it is possible for the in-memory state of an index to appear as multikey but the durable state to remain as non-multikey.

In this scenario, the IndexCatalogEntryImpl (erroneous in-memory state) may contain path-level information which lead to this optimization being erroneously applied to subsequent multikey writes and leaving the index as non-multikey in the catalog.



 Comments   
Comment by Vivian Ge (Inactive) [ 06/Oct/21 ]

Updating the fixversion since branching activities occurred yesterday. This ticket will be in rc0 when it’s been triggered. For more active release information, please keep an eye on #server-release. Thank you!

Comment by Githook User [ 12/Aug/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 track uncommitted changes to multikey paths with a counter

This change applies the technique in commit 3566db153ea61fb10d3ef11ea917fc7bc93eac4d
for the isMultikey boolean flags to the reader and writer multikey paths.

This commit is designed to support pre-5.0 backports and will be superseded by a
new patch that uses the Collection metadata introduced in 5.0.

(cherry picked from commit 5d8ac7127e207e0ef1aeaa90dcc62cda6896b71e)
Branch: v4.4
https://github.com/mongodb/mongo/commit/399cec41f3e950a044b0a7bad2d34aabdeeeb03c

Comment by Githook User [ 10/Aug/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 rename IndexCatalogEntryImpl::_indexMultikeyPaths to _indexMultikeyPathsForRead

(cherry picked from commit 262036ae4b0219c229ff38c644a1e10487e7a586)
Branch: v4.4
https://github.com/mongodb/mongo/commit/8a9094b569292ec593f977eb623bf1ff7a48094a

Comment by Githook User [ 10/Aug/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey compound index after restarting

This test checks that the multikey paths for a compound index remain consistent
despite some failed writes. The test uses a compound index with two indexed fields
that are updated separately by different write operations. A hashed index provides
an easy way to fail a write operation due to a constraint on field values in a hashed
index.

This initial version of the test characterizes a defect in multikey tracking that shows
up as validation errors after the server restarts.

(cherry picked from commit 54f015ab1bc386b61c8011d5d8e3267bb4e181bf)
Branch: v4.4
https://github.com/mongodb/mongo/commit/b8ec200c830d8a79217195af175b023f40a60943

Comment by Githook User [ 10/Aug/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting a re-elected node

This test checks that a full validation runs successfully on a collection with a multikey
index (for a geo 2dsphere index) after some interrupted writes (due to a stepdown). On
restarting, we validate the collection to ensure that the multikey information loaded from
the durable catalog is consistent with the geo documents in the collection.

This initial version of the test characterizes a defect in multikey state tracking that
shows up as validation errors upon server restart.

(cherry picked from commit 393465e9fe428e693c259223c85299f8e7aac1fc)
Branch: v4.4
https://github.com/mongodb/mongo/commit/59183f9335c9deede96f016951e8ef0fb3aa6052

Comment by Githook User [ 10/Aug/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting

This test checks that the multikey state of an index is updated correctly in the durable
catalog despite some earlier writes failing due to a hashed index constraint. Upon restarting,
we perform a full validation to ensure that the multikey information in the catalog is
consistent with the contents of the collection.

This initial version of the test characterizes an defect in tracking the multikey information
that leads to validation errors after the server restarts.

(cherry picked from commit aefb1ac44425c13e8803ff72a3c7fcb194ee599c)
Branch: v4.4
https://github.com/mongodb/mongo/commit/6c41e4c55bb460f087f378e03e6839a0848b9066

Comment by Githook User [ 21/Jul/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 IndexCatalogEntryImpl::setIndexIsMultikey() uses multikey paths in Collection metadata

This change depends on improvements made in commit 11de948b0c50df7d12de09ae0f01e791fc5d70d7 and
cannot be backported to pre-5.0 branches.

(cherry picked from commit bdb1299412486fab396214f5745d1768a56a449f)
Branch: v5.0
https://github.com/mongodb/mongo/commit/fb40f3c16d9ea6ca5f1c35580f8cc8983252cf1c

Comment by Githook User [ 20/Jul/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 track uncommitted changes to multikey paths with a counter

This change applies the technique in commit 3566db153ea61fb10d3ef11ea917fc7bc93eac4d
for the isMultikey boolean flags to the reader and writer multikey paths.

This commit is designed to support pre-5.0 backports and will be superseded by a
new patch that uses the Collection metadata introduced in 5.0.

(cherry picked from commit 5d8ac7127e207e0ef1aeaa90dcc62cda6896b71e)
Branch: v5.0
https://github.com/mongodb/mongo/commit/1928c8d20941bdaf094507d0b1616ca58d530330

Comment by Githook User [ 20/Jul/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js tests and rename multikey paths member name

This reverts commit fcddb1393fa511f68706b1ff8e74c65f40c086bc.

(cherry picked from commit aefb1ac44425c13e8803ff72a3c7fcb194ee599c)
(cherry picked from commit 393465e9fe428e693c259223c85299f8e7aac1fc)
(cherry picked from commit 54f015ab1bc386b61c8011d5d8e3267bb4e181bf)
(cherry picked from commit 262036ae4b0219c229ff38c644a1e10487e7a586)
Branch: v5.0
https://github.com/mongodb/mongo/commit/7203d2537140239706d0a18a1c05d3155b21d07a

Comment by Githook User [ 02/Jun/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 IndexCatalogEntryImpl::setIndexIsMultikey() uses multikey paths in Collection metadata

This change depends on improvements made in commit 11de948b0c50df7d12de09ae0f01e791fc5d70d7 and
cannot be backported to pre-5.0 branches.
Branch: master
https://github.com/mongodb/mongo/commit/bdb1299412486fab396214f5745d1768a56a449f

Comment by Githook User [ 02/Jun/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 track uncommitted changes to multikey paths with a counter

This change applies the technique in commit 3566db153ea61fb10d3ef11ea917fc7bc93eac4d
for the isMultikey boolean flags to the reader and writer multikey paths.

This commit is designed to support pre-5.0 backports and will be superseded by a
new patch that uses the Collection metadata introduced in 5.0.
Branch: master
https://github.com/mongodb/mongo/commit/5d8ac7127e207e0ef1aeaa90dcc62cda6896b71e

Comment by Githook User [ 25/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: Revert "SERVER-56877 add js tests and rename multikey paths member name"

This reverts commit f73a9e99f3f1b9def1087904ddc6891952e62efc.
This reverts commit 8e87947b7780fea3d1cf50f4bfb4d8bc4c00ef64.
This reverts commit 42085147889412fca894a4c247b82ea11af031e4.
This reverts commit 6014b48240fdffbb1d1b0151b8a1bf426d45a534.
Branch: v5.0
https://github.com/mongodb/mongo/commit/fcddb1393fa511f68706b1ff8e74c65f40c086bc

Comment by Benety Goh [ 24/May/21 ]

SERVER-57127 describes how we should be doing things in 5.0 by leveraging the work in SERVER-56002 and SERVER-56023.

Comment by Benety Goh [ 24/May/21 ]

Backports to 4.2 and 4.0 may have to take into account minor edits to IndexCatalogEntryImpl made in SERVER-41766 and SERVER-43757.

Comment by Benety Goh [ 21/May/21 ]

The main issue with the reverted commit bc095d5c is in this line where we unconditionally replace the read paths with the last successfully persisted write paths.

We are not taking into account the compound index case where we may be updating separate paths, from different documents, in a single storage transaction.

Comment by Githook User [ 21/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: Revert "SERVER-56877 IndexCatalogEntryImpl maintains separate copies of multikey paths for readers and writers"

This reverts commit c1c9bafde288414adf94b3f8372189e38b2f8e0f.
Branch: v5.0
https://github.com/mongodb/mongo/commit/bf2d51542967e89cc0e620e167af9562de1d9298

Comment by Githook User [ 21/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: Revert "SERVER-56877 IndexCatalogEntryImpl maintains separate copies of multikey paths for readers and writers"

This reverts commit bc095d5cef314bab9fd583c3908eb1cfecb49dd9.
Branch: master
https://github.com/mongodb/mongo/commit/7e01c960ee3a2ecf32aa3745db93e1bef84d1030

Comment by Githook User [ 20/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 IndexCatalogEntryImpl maintains separate copies of multikey paths for readers and writers

(cherry picked from commit bc095d5cef314bab9fd583c3908eb1cfecb49dd9)
Branch: v5.0
https://github.com/mongodb/mongo/commit/c1c9bafde288414adf94b3f8372189e38b2f8e0f

Comment by Githook User [ 20/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 rename IndexCatalogEntryImpl::_indexMultikeyPaths to _indexMultikeyPathsForRead

(cherry picked from commit 262036ae4b0219c229ff38c644a1e10487e7a586)
Branch: v5.0
https://github.com/mongodb/mongo/commit/f73a9e99f3f1b9def1087904ddc6891952e62efc

Comment by Githook User [ 20/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey compound index after restarting

This test checks that the multikey paths for a compound index remain consistent
despite some failed writes. The test uses a compound index with two indexed fields
that are updated separately by different write operations. A hashed index provides
an easy way to fail a write operation due to a constraint on field values in a hashed
index.

This initial version of the test characterizes a defect in multikey tracking that shows
up as validation errors after the server restarts.

(cherry picked from commit 54f015ab1bc386b61c8011d5d8e3267bb4e181bf)
Branch: v5.0
https://github.com/mongodb/mongo/commit/8e87947b7780fea3d1cf50f4bfb4d8bc4c00ef64

Comment by Githook User [ 20/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting a re-elected node

This test checks that a full validation runs successfully on a collection with a multikey
index (for a geo 2dsphere index) after some interrupted writes (due to a stepdown). On
restarting, we validate the collection to ensure that the multikey information loaded from
the durable catalog is consistent with the geo documents in the collection.

This initial version of the test characterizes a defect in multikey state tracking that
shows up as validation errors upon server restart.

(cherry picked from commit 393465e9fe428e693c259223c85299f8e7aac1fc)
Branch: v5.0
https://github.com/mongodb/mongo/commit/42085147889412fca894a4c247b82ea11af031e4

Comment by Githook User [ 20/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting

This test checks that the multikey state of an index is updated correctly in the durable
catalog despite some earlier writes failing due to a hashed index constraint. Upon restarting,
we perform a full validation to ensure that the multikey information in the catalog is
consistent with the contents of the collection.

This initial version of the test characterizes an defect in tracking the multikey information
that leads to validation errors after the server restarts.

(cherry picked from commit aefb1ac44425c13e8803ff72a3c7fcb194ee599c)
Branch: v5.0
https://github.com/mongodb/mongo/commit/6014b48240fdffbb1d1b0151b8a1bf426d45a534

Comment by Benety Goh [ 20/May/21 ]

SERVER-56002 and SERVER-56023 will clean multikey up further for 5.0. The tests added here will still be used for regression testing.

Comment by Githook User [ 19/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 IndexCatalogEntryImpl maintains separate copies of multikey paths for readers and writers
Branch: master
https://github.com/mongodb/mongo/commit/bc095d5cef314bab9fd583c3908eb1cfecb49dd9

Comment by Githook User [ 19/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey compound index after restarting

This test checks that the multikey paths for a compound index remain consistent
despite some failed writes. The test uses a compound index with two indexed fields
that are updated separately by different write operations. A hashed index provides
an easy way to fail a write operation due to a constraint on field values in a hashed
index.

This initial version of the test characterizes a defect in multikey tracking that shows
up as validation errors after the server restarts.
Branch: master
https://github.com/mongodb/mongo/commit/54f015ab1bc386b61c8011d5d8e3267bb4e181bf

Comment by Githook User [ 19/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting a re-elected node

This test checks that a full validation runs successfully on a collection with a multikey
index (for a geo 2dsphere index) after some interrupted writes (due to a stepdown). On
restarting, we validate the collection to ensure that the multikey information loaded from
the durable catalog is consistent with the geo documents in the collection.

This initial version of the test characterizes a defect in multikey state tracking that
shows up as validation errors upon server restart.
Branch: master
https://github.com/mongodb/mongo/commit/393465e9fe428e693c259223c85299f8e7aac1fc

Comment by Githook User [ 19/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 add js test for validating multikey index after restarting

This test checks that the multikey state of an index is updated correctly in the durable
catalog despite some earlier writes failing due to a hashed index constraint. Upon restarting,
we perform a full validation to ensure that the multikey information in the catalog is
consistent with the contents of the collection.

This initial version of the test characterizes an defect in tracking the multikey information
that leads to validation errors after the server restarts.
Branch: master
https://github.com/mongodb/mongo/commit/aefb1ac44425c13e8803ff72a3c7fcb194ee599c

Comment by Githook User [ 18/May/21 ]

Author:

{'name': 'Benety Goh', 'email': 'benety@mongodb.com', 'username': 'benety'}

Message: SERVER-56877 rename IndexCatalogEntryImpl::_indexMultikeyPaths to _indexMultikeyPathsForRead
Branch: master
https://github.com/mongodb/mongo/commit/262036ae4b0219c229ff38c644a1e10487e7a586

Comment by Daniel Gottlieb (Inactive) [ 18/May/21 ]

It might make sense to split this variable into two versions (one for readers and one for writers) the way we split the isMultikey state in SERVER-47694, but we would have to work through all the possible scenarios where this may make things better/cause more problems.

This to me is the natural progression of the solution. Each multikey path gets a read variable and a write variable (which probably means some sort of set/map of paths).

The corresponding read variable is pessimistically set before the accompanying write is committed. Even if the write is rolled back, the variable stays set. This variable determines whether the index/path is multikey for query's purpose.

The corresponding write variable is set in an onCommit hook. Every write that has multikey paths must perform a write to the catalog to set its corresponding multikey path until this variable is observed to be set.

Comment by Louis Williams [ 13/May/21 ]

Since this "versioned catalog" project might be coming soon, I think we should consider deferring this bug fix until we understand how much longer we have to wait for a solution that makes all of this in-memory multikey maintenance code go away. That is, unless this bug fix is simple. Based on the discussion here, that does not seem to be the case.

Comment by Daniel Gottlieb (Inactive) [ 13/May/21 ]

If I understand your example with paths 'a' and 'b', that scenario is still an issue today.

Yep. I'd still consider that the same bug, but it's certainly true that checking "is multikey for write" will eliminate a case that can hit the bug.

I wonder what the effect of guarding the optimization with _isMultikeyKeyForWrite and installing a rollback handler to restore the state of _indexMultikeyPaths here would be on the scenario you described.

I understand that, even with the ability to restore the previous version of _indexMultikeyPaths, we will still not be able to resolve all the possible interleaving cases.

Correct. The interleaving that's problematic:

| Writer 1                         | Writer 2                                |
|----------------------------------+-----------------------------------------|
| BeginTxn                         |                                         |
| Insert A                         |                                         |
| Flip inmemory multikey paths "a" |                                         |
| Flip durable path "a"            |                                         |
| WTRollback                       |                                         |
|                                  | BeginTxn                                |
|                                  | Insert B                                |
|                                  | Sees inmemory multikey path "a" is true |
|                                  | Does not set durable multikey path "a"  |
|                                  | Commit                                  |
| onRollback                       |                                         |
| Unflip multikey path "a"         |                                         |

Most of the logic for the in-memory path maintenance appears to be some approximation of the logic we use to update the durable state in DurableCatalogImpl::setIndexIsMultiKey()

That's exactly what it is. If we could atomically change in-memory state with the storage engine, we wouldn't need all these tricks.

The lock free reads project has given us a lot of the code changes necessary to move to a "versioned catalog". To me, that means that whenever we get a collection object, we actually use the snapshot on the recovery unit to read the collection metadata from the _mdb_catalog table and hydrate a (relatively) immutable collection object from that data.

Comment by Benety Goh [ 12/May/21 ]

If I understand your example with paths 'a' and 'b', that scenario is still an issue today.

I wonder what the effect of guarding the optimization with _isMultikeyKeyForWrite and installing a rollback handler to restore the state of _indexMultikeyPaths here would be on the scenario you described.

I understand that, even with the ability to restore the previous version of _indexMultikeyPaths, we will still not be able to resolve all the possible interleaving cases.

Most of the logic for the in-memory path maintenance appears to be some approximation of the logic we use to update the durable state in DurableCatalogImpl::setIndexIsMultiKey()

Comment by Daniel Gottlieb (Inactive) [ 12/May/21 ]

Talking about solutions to these are tricky, so I've diagramed a few interleavings:

My understanding of how (the bug) happens today:

| Writer 1                     | Writer 2                            |
|------------------------------+-------------------------------------|
| BeginTxn                     |                                     |
| Insert A                     |                                     |
| Flip multikeyForRead         |                                     |
| Flip inmemory multikey paths |                                     |
| Flip Path A                  |                                     |
| WTRollback                   |                                     |
| onRollback                   |                                     |
|                              | BeginTxn                            |
|                              | Insert B                            |
|                              | See inmemory multikey paths flipped |
|                              | Does not set durable multikey paths |
|                              | Commit                              |

My understanding of how checking for _isMultikeyForWrite addresses the prior example (correctly):

Reading from multikeyForWrite (working example)
| Writer 1                        | Writer 2                       |
|---------------------------------+--------------------------------|
| BeginTxn                        |                                |
| Insert A                        |                                |
| Flip multikeyForRead            |                                |
| Flip inmemory multikey path "a" |                                |
| Flip durable path "a"           |                                |
| WTRollback                      |                                |
| onRollback                      |                                |
|                                 | BeginTxn                       |
|                                 | Insert B                       |
|                                 | Sees multikeyForWrite is false |
|                                 | Flip durable path "a"          |
|                                 | Commit                         |

I claim that checking _isMultikeyForWrite isn't sufficient because it's not granular enough. Flipping _isMultikeykeyForWrite when we flip multikey path "a" to to true is not sufficient for protecting the above rollback scenario when wanting to flip multikey path "b".

This is my understanding of what would still be a bug:

| Writer 1                         | Writer 2                                |
|----------------------------------+-----------------------------------------|
| BeginTxn                         |                                         |
| Insert A                         |                                         |
| Flip multikeyForRead             |                                         |
| Flip inmemory multikey path "a"  |                                         |
| Commit                           |                                         |
| Flip multikeyForWrite            |                                         |
|                                  |                                         |
| BeginTxn                         |                                         |
| Insert B                         |                                         |
| multikeyForRead already flipped  |                                         |
| Flip inmemory multikey paths "b" |                                         |
| Flip durable path "b"            |                                         |
| WTRollback                       |                                         |
| onRollback                       |                                         |
|                                  | BeginTxn                                |
|                                  | Insert C                                |
|                                  | Sees multikeyForWrite is true           |
|                                  | Sees inmemory multikey path "b" is true |
|                                  | Does not set durable multikey path "b"  |
|                                  | Commit                                  |

Comment by Benety Goh [ 12/May/21 ]

The atomic flags _isMultikeyForRead and _isMultikeyForWrite were added in SERVER-47694.

SERVER-47812 describes the most recent modifications to how we manage multikey path level information in IndexCatalogEntryImpl.

Generated at Thu Feb 08 05:40:26 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.