search

cockroachdb / pebble

RocksDB/LevelDB inspired key-value database in Go
BSD 3-Clause "New" or "Revised" License
4.91k stars 456 forks source link

sstable: virtual sstable seeking violates iterator contract [TestMeta failed] #3128

Closed cockroach-teamcity closed 11 months ago

cockroach-teamcity commented 11 months ago

github.com/cockroachdb/pebble/internal/metamorphic.TestMeta failed with artifacts on refs/heads/master @ 348b3a068f94:

=== RUN   TestMeta/execution/standard-005
=== PAUSE TestMeta/execution/standard-005
=== CONT  TestMeta/execution/standard-005
=== RUN   TestMeta/compare/standard-001
=== RUN   TestMeta/compare/standard-014
=== RUN   TestMeta/compare/standard-025
=== RUN   TestMeta/execution/random-002
=== PAUSE TestMeta/execution/random-002
=== CONT  TestMeta/execution/random-002
=== RUN   TestMeta/execution/random-007
=== PAUSE TestMeta/execution/random-007
=== CONT  TestMeta/execution/random-007
=== RUN   TestMeta/execution/random-015
=== PAUSE TestMeta/execution/random-015
=== CONT  TestMeta/execution/random-015
=== RUN   TestMeta/execution/standard-002
=== PAUSE TestMeta/execution/standard-002
=== CONT  TestMeta/execution/standard-002
=== RUN   TestMeta/execution/standard-023
=== PAUSE TestMeta/execution/standard-023
=== CONT  TestMeta/execution/standard-023
=== RUN   TestMeta/execution/random-018
=== PAUSE TestMeta/execution/random-018
=== CONT  TestMeta/execution/random-018
=== RUN   TestMeta/compare/standard-005
=== RUN   TestMeta/compare/standard-017
=== RUN   TestMeta/compare/standard-027
=== RUN   TestMeta/execution/random-013
=== PAUSE TestMeta/execution/random-013
=== CONT  TestMeta/execution/random-013
=== RUN   TestMeta/execution/random-025
=== PAUSE TestMeta/execution/random-025
=== CONT  TestMeta/execution/random-025
=== RUN   TestMeta/execution/standard-011
=== PAUSE TestMeta/execution/standard-011
=== CONT  TestMeta/execution/standard-011
=== RUN   TestMeta/compare/standard-008
=== RUN   TestMeta/compare/standard-015
=== RUN   TestMeta/execution/random-023
=== PAUSE TestMeta/execution/random-023
=== CONT  TestMeta/execution/random-023
=== RUN   TestMeta/execution/standard-004
=== PAUSE TestMeta/execution/standard-004
=== CONT  TestMeta/execution/standard-004
=== RUN   TestMeta/execution/standard-013
=== PAUSE TestMeta/execution/standard-013
=== CONT  TestMeta/execution/standard-013
=== RUN   TestMeta/execution/standard-018
=== PAUSE TestMeta/execution/standard-018
=== CONT  TestMeta/execution/standard-018
Help

To reproduce, try: ```bash go test -tags 'invariants' -exec 'stress -p 1' -timeout 0 -test.v -run TestMeta$ ./internal/metamorphic -seed 1701853586999955896 -ops "uniform:5000-10000" ```

This test on roachdash | Improve this report!

nicktrav commented 11 months ago 
[09:06:38] :     [Step 1/1]         ===== SEED =====
[09:06:38] :     [Step 1/1]         1701853586999955896
[09:06:38] :     [Step 1/1]         ===== DIFF =====
[09:06:38] :     [Step 1/1]         /artifacts/meta/231206-090626.9991318084806/{standard-000,random-004}
[09:06:38] :     [Step 1/1]         @@ -7133,11 +7133,11 @@
[09:06:38] :     [Step 1/1]  db1.Set("imqcacjxlz@14", "usnfjekjmqp") // <nil> #7132
[09:06:38] :     [Step 1/1]  iter70.SeekPrefixGE("bmjkdhh@12") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #7133
[09:06:38] :     [Step 1/1]  iter69.SetBounds("bbjlyu@14", "giqmriehujk@7") // <nil> #7134
[09:06:38] :     [Step 1/1]  iter69.SeekLT("giqmriehujk@7", "") // [true,"fxwq@16","jny",["frfsrhki","giqmriehujk@7")=>{"@15"="ryfbuku","@5"="no","@1"="jogpscccy"}*] <nil> #7135
[09:06:38] :     [Step 1/1]  iter69.Prev("") // [true,"frfsrhki",<no point>,["frfsrhki","giqmriehujk@7")=>{"@15"="ryfbuku","@5"="no","@1"="jogpscccy"}] <nil> #7136
[09:06:38] :     [Step 1/1] -iter69.Prev("") // [true,"bvuxhqu@13","pjujkp",<no range>*] <nil> #7137
[09:06:38] :     [Step 1/1] +iter69.Prev("") // [true,"bldfn@17","qykbhrdrtbghmunyj",<no range>*] <nil> #7137
[09:06:38] :     [Step 1/1]  iter71.NextPrefix() // [false] NextPrefix not permitted with upper bound ldxixt@6 #7138
[09:06:38] :     [Step 1/1]  iter70.Prev("") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #7139
[09:06:38] :     [Step 1/1]  snap50.Get("alkdkdl@2") // [""] pebble: not found #7140
[09:06:38] :     [Step 1/1]  db1.Get("alkdkdl@14") // ["wepkgowfegnftjyh"] <nil> #7141
[09:06:38] :     [Step 1/1]  db1.DeleteRange("hoxaydvsba@20", "ldwgyt@6") // <nil> #7142
itsbilal commented 11 months ago

bvuxhqu@13#0,MERGE [706a756a6b70] is getting skipped when Prev()ing.

Note that at iterator creation time, that key was a virtual sstable end bound:

  added:         L6 000348:278<#0-#1999>[aduujknz#1580,RANGEKEYSET-bvuxhqu@13#0,MERGE]

I wonder if something's going wrong around virtual sstable bounds, MERGE, and endKeyInclusive handling.

itsbilal commented 11 months ago

Figured it out. Basically, this case:

https://github.com/cockroachdb/pebble/blob/348b3a068f94b20f708271c928c4491376578f85/sstable/reader_iter_single_lvl.go#L856

Is tricky with range key masking. virtualLast can get called as part of SeekLT, and the rest of the iterator stack could be at a range key that's fully right of us. Our mask has been updated by the interleaving iter to be that range key. Then, when we call SeekGE internally here to try to land at the highest key the virtual sstable, we will only check against the upper bound of the range key here:

https://github.com/cockroachdb/pebble/blob/348b3a068f94b20f708271c928c4491376578f85/sstable/reader_iter_single_lvl.go#L466

In the failing example from above, the range key masking filter basically concludes bvuxhqu@13#0,MERGE is within ["frfsrhki","giqmriehujk@7")=>{"@15"="ryfbuku","@5"="no","@1"="jogpscccy"} as the index separator of the block containing the MERGE, c, is strictly less than the upper bound of the range key, and so it excludes the MERGE and forces us to load the key before it as the last key in the virtual sstable instead.

It might not be fun fixing this. I think the underlying challenge is going to be that assuming dir = +1 for any sub-calls of virtualLast is not an accurate assumption.

jbowens commented 11 months ago

I think during virtual sstable implementation, we discussed unconditionally using exclusive upper bounds. That would resolve this by allowing us to always use SeekLT? Are there any obstacles to only using exclusive bounds here?

cockroach-teamcity commented 11 months ago

github.com/cockroachdb/pebble/internal/metamorphic.TestMeta failed with artifacts on refs/heads/master @ b3f359e3a503:

iter66.SeekPrefixGE("pcpojik@151")
iter66.SeekPrefixGE("pcpojik@159")
iter67.Next("")
iter66.SetBounds("pcpojik@143", "qoqricoxl@215")
iter66.SeekGE("pcpojik@143", "")
iter66.Prev("")
iter67.SeekLT("pcpojik@206", "")
iter67.SeekGE("ygbqxpsqx@188", "ygbqxpsqx@84")
db1.Set("cpmd@194", "vuezl")
db1.Get("uvibovqouw@96")
iter67.Last()
iter68 = db1.NewIter("", "", 2 /* key types */, 0, 0, false /* use L6 filters */, "" /* masking suffix */)
db1.Get("famrwhjzp@171")
iter67.SeekGE("cpmd@92", "")
db1.Set("bccbditg@136", "zqauflkrgxqituwn")
iter67.SeekGE("uvibovqouw@57", "")
iter66.SeekLT("ufkzquurcoz@190", "")
iter67.Last()
db1.Set("vqxewhpmqe@4", "zbzrzlqzla")
iter68.SeekGE("pcpojik@107", "")
db1.Set("uqkpaecjf@42", "svso")
iter68.SeekLT("lhbmf@232", "")
snap47 = db1.NewSnapshot("arhfetjrks", "cpmd", "lhbmf", "qoqricoxl", "uvibovqouw", "ygbqxpsqx")
iter68.First()
iter67.Prev("")
iter68.Prev("")
db1.Set("famrwhjzp@210", "ikwgjtd")
iter66.First()
iter66.Last()
iter68.Close()
iter67.Close()
iter66.Close()
snap46.Close()
snap47.Close()
db1.Close()

        === RUN   TestMeta/compare/standard-012
=== RUN   TestMeta/compare/standard-022
=== RUN   TestMeta/execution/standard-002
=== PAUSE TestMeta/execution/standard-002
=== CONT  TestMeta/execution/standard-002
=== RUN   TestMeta/execution/standard-006
=== PAUSE TestMeta/execution/standard-006
=== CONT  TestMeta/execution/standard-006
=== RUN   TestMeta/execution/standard-013
=== PAUSE TestMeta/execution/standard-013
=== CONT  TestMeta/execution/standard-013
=== RUN   TestMeta/execution/standard-025
=== PAUSE TestMeta/execution/standard-025
=== CONT  TestMeta/execution/standard-025
Help

To reproduce, try: ```bash go test -tags 'invariants' -exec 'stress -p 1' -timeout 0 -test.v -run TestMeta$ ./internal/metamorphic -seed 1701930270447718512 -ops "uniform:5000-10000" ```

This test on roachdash | Improve this report!

itsbilal commented 11 months ago

I think during virtual sstable implementation, we discussed unconditionally using exclusive upper bounds. That would resolve this by allowing us to always use SeekLT? Are there any obstacles to only using exclusive bounds here?

@jbowens Yes that's right, that would solve this. It'd come at the cost of always necessitating looser virtual sstable bounds than we would otherwise see if we keep doing the current thing of generating tight bounds whenever we can (eg. with ingest splits), but I can't think of any other obstacles in the way of doing that.

jbowens commented 11 months ago

@itsbilal I think that's a worthwhile simplification. I doubt we'll save much iteration cost by narrowing the bounds between points.

cockroach-teamcity commented 11 months ago

github.com/cockroachdb/pebble/internal/metamorphic.TestMeta failed with artifacts on refs/heads/master @ dbeb05897e38:

        iter59.InternalNext() // <nil> #6021
        iter59.SeekLT("mocijt@9", "") // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}*] <nil> #6034
        iter59.SeekGE("abupilcha@9", "") // [true,"abyfbeuk",<no point>,["abyfbeuk","aoub")=>{"@10"="w"}*] <nil> #6040
        iter51.SeekLT("xwkmjmxyma@15", "") // [true,"xqmw",<no point>,["xqmw","xqmw@9")=>{"@13"="qgrgiwh","@11"="bawpnlcbcuiscbahe","@7"="squzszq","@6"="vczcutunns"}*] <nil> #6043
        iter51.Prev("") // [true,"xpfbkchko",<no point>,["xpfbkchko","xqmw")=>{"@13"="qgrgiwh","@11"="bawpnlcbcuiscbahe","@6"="vczcutunns"}*] <nil> #6047
        iter59.SeekLT("picqufwyg", "") // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}*] <nil> #6053
        iter51.SeekPrefixGE("fasbvnzx") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #6060
        iter59.SeekGE("bhkzxoisjm@5", "") // [false] <nil> #6077
        iter59.SeekGE("kkgueu@1", "") // [false] <nil> #6080
        iter59.InternalNext() // <nil> #6086
        iter51.SeekGE("aobiz", "") // [true,"uzouqdyfj@13",<no point>,["uzouqdyfj@13","vvly")=>{"@13"="zyqgfavhnyez"}*] <nil> #6095
        iter59.Prev("") // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}*] <nil> #6108
        iter59.SeekLT("ectyyuk@4", "") // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}] <nil> #6116
        iter59.Next("") // [false] <nil> #6129
        iter59.Last() // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}*] <nil> #6164
        iter51.Prev("dtohkwomgra@12") // [invalid] <nil> #6169
        iter59.NextPrefix() // [false] NextPrefix not permitted with upper bound ardpoz@7 #6176
        iter51.SetBounds("hpmvjiw@13", "mndd@1") // <nil> #6187
        iter51.SeekLT("mndd@1", "") // [false] <nil> #6188
        iter51.Next("") // [false] <nil> #6189
        iter51.Prev("") // [false] <nil> #6190
        iter59.First() // [true,"abyfbeuk",<no point>,["abyfbeuk","aoub")=>{"@10"="w"}*] <nil> #6194
        iter59.SeekLT("scrbo@2", "") // [true,"ardpoz@10","khkcdtjiflgixdmitdo",["aoub","ardpoz@7")=>{""="kouktxv","@10"="w"}*] <nil> #6195
        iter58.SeekGE("klzbjnpqn@14", "") // [false] <nil> #5955
        iter58.Next("") // [false] <nil> #5969
        iter50.Prev("") // [false] <nil> #5970
        iter50.Next("") // [false] <nil> #5981
        iter50.SeekPrefixGE("abyfbeuk@4") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #6016
        iter50.SeekPrefixGE("ectyyuk@4") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #6027
        iter50.SeekLT("bvtx@11", "") // [false] <nil> #6028
        iter50.SetOptions("jrylk@15", "scvzhm@12", 2 /* key types */, 0, 0, false /* use L6 filters */, "@13" /* masking suffix */) // <nil> #6036
        iter50.Last() // [true,"qlszktjod",<no point>,["qlszktjod","scvzhm@12")=>{"@13"="zyqgfavhnyez","@11"="bawpnlcbcuiscbahe","@10"="w"}*] <nil> #6037
        iter50.SeekLT("nkdwpqpzm@6", "") // [true,"lyudy@1","",<no range>*] <nil> #6046
        iter50.SeekLT("wnlwgma@7", "") // [true,"qlszktjod",<no point>,["qlszktjod","scvzhm@12")=>{"@13"="zyqgfavhnyez","@11"="bawpnlcbcuiscbahe","@10"="w"}*] <nil> #6059
        iter58.Next("") // [false] <nil> #6068
        iter58.SeekPrefixGE("zrgbt@11") // [false] pebble: SeekPrefixGE supplied with key outside of upper bound #6073
        iter58.SeekPrefixGE("uubkbvxvftx@4") // [false] pebble: SeekPrefixGE supplied with key outside of upper bound #6104
        iter50.Prev("") // [true,"pwzzmlaxfbr",<no point>,["pwzzmlaxfbr","qlszktjod")=>{"@13"="zyqgfavhnyez","@11"="bawpnlcbcuiscbahe","@10"="w","@5"="alilmvsudkathcew"}*] <nil> #6107
        iter50.SeekPrefixGE("fasbvnzx") // [false] pebble: SeekPrefixGE supplied with key outside of lower bound #6115
        iter50.First() // [true,"kabe","jjieihnocg",<no range>] <nil> #6126
        iter58.Last() // [false] <nil> #6133
        iter50.SeekLT("xolocmkksyy@8", "") // [true,"qlszktjod",<no point>,["qlszktjod","scvzhm@12")=>{"@13"="zyqgfavhnyez","@11"="bawpnlcbcuiscbahe","@10"="w"}*] <nil> #6139
        iter58.Next("") // [false] <nil> #6141
        iter58.SetBounds("kdwssecb", "kyphrszn") // <nil> #6145
        iter58.SeekLT("kyphrszn", "") // [true,"krtwcggpen@11","nsuphzrbumcmwav",<no range>] <nil> #6146
        iter58.Next("") // [false] <nil> #6147
        iter58.Prev("") // [true,"krtwcggpen@11","nsuphzrbumcmwav",<no range>] <nil> #6148
        iter58.Prev("") // [false] <nil> #6149
        iter58.InternalNext() // <nil> #6153
        --- FAIL: TestMeta/execution/random-001 (0.82s)
Help

To reproduce, try: ```bash go test -tags 'invariants' -exec 'stress -p 1' -timeout 0 -test.v -run TestMeta$ ./internal/metamorphic -seed 1702018894164012460 -ops "uniform:5000-10000" ```

This test on roachdash | Improve this report!