Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Specifying a revision for a range request in a transaction may cause data inconsistency #18667

Open
ahrtr opened this issue Oct 2, 2024 · 21 comments
Labels
backport/v3.4 backport/v3.5 priority/important-soon Must be staffed and worked on either currently, or very soon, ideally in time for the next release. type/bug

Comments

@ahrtr
Copy link
Member

ahrtr commented Oct 2, 2024

What happened?

Specifying a revision for a range request in a transaction may cause data inconsistency. The client may get different values against the same key from different endpoints.

How can we reproduce it?

  • Step 1: start a brand new 3 member cluster
  • Step 2: Execute for i in {1..20}; do ./etcdctl put k$i v$i; done
  • Step 3: Execute ./etcdctl compact 21
  • Step 4: Execute ./etcdctl txn --interactive
compares:
value("k1") = "v1"

success requests (get, put, del):
put k2 foo
get k1 --rev=10

failure requests (get, put, del):

The client will get a **etcdserver: mvcc: required revision has been compacted** error.

  • Step 5: Execute ./etcdctl get k2 against different endpoints, you will get different values,
$ ./etcdctl --endpoints=127.0.0.1:2379 get k2
k2
v2
$ ./etcdctl --endpoints=127.0.0.1:22379 get k2
k2
foo
$ ./etcdctl --endpoints=127.0.0.1:32379 get k2
k2
foo

Root cause

The root cause is that etcd server removes range requests from the TXN for endpoints the client isn’t connected to.

needResult := s.w.IsRegistered(id)
if needResult || !noSideEffect(&raftReq) {
if !needResult && raftReq.Txn != nil {
removeNeedlessRangeReqs(raftReq.Txn)
}

For example, if the client connects to member 1, then etcdserver removes the range request (get k1 --rev=10 in above example) from the TXN in member 2 and 3. Accordingly, member 1 applies failed due to checkRange's failures, but member 2 & 3 apply the TXN successfully because the range request was removed. Eventually it leads to the situation that different members have different data.

func checkRange(rv mvcc.ReadView, req *pb.RangeRequest) error {
switch {
case req.Revision == 0:
return nil
case req.Revision > rv.Rev():
return mvcc.ErrFutureRev
case req.Revision < rv.FirstRev():
return mvcc.ErrCompacted
}
return nil
}

Solution

The simplest solution is we don't remove range requests from TXN for any member. The side effect is that other endpoints (the client isn't connected to) will execute the unnecessary range operations.

To resolve the side effect above, we don't execute the range requests on other endpoints that the client isn't connected to; instead etcdservers only verify them to ensure all endpoints always execute consistent validation.

Workaround

If only one member is inconsistent, just replace it. See this guide. After removing the member, delete its data.

If all members are inconsistent, things get trickier. You'll need to pick one member as the source of truth, force creating a single-member cluster, and then re-add other members (don’t forget to clear their data first).

Impact

All versions (including 3.4.x, 3.5.x and main) are affected.

  • Just searched the Kubernetes repo, and confirmed that kubernetes doesn't specify revision for range request in TXN. So Kubernetes isn't affected
  • For non-Kubernetes usage... It’s uncommon for this to be used this way in a real-world product, but I’m not entirely sure it won’t be.
@ahrtr ahrtr added type/bug priority/important-soon Must be staffed and worked on either currently, or very soon, ideally in time for the next release. labels Oct 2, 2024
@ahrtr ahrtr pinned this issue Oct 2, 2024
@ahrtr
Copy link
Member Author

ahrtr commented Oct 3, 2024

The simplest solution is that we never remove range request from TXN, see ahrtr@76ac23f .

  • The good side is simple.
  • The side effect is that the members the client isn't connect to will execute some unnecessary range requests.

@wenjiaswe
Copy link
Contributor

@ArkaSaha30 Thanks for helping out!

@wenjiaswe
Copy link
Contributor

cc @ivanvc as well as you have some context with performance tooling.

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 3, 2024

The simplest solution is that we never remove range request from TXN

Sorry if I missed this part during the call. Is there an option-2 we've already excluded here, which is to treat working-as-intended range responses (like mvcc: required revision has been compacted) in the success/failure ops not as an error that requires Tx to rollback? It will change the semantic for existing clients, but that seems to be broken anyway (in a worse way) as shown by this bug iiuc.

@ahrtr
Copy link
Member Author

ahrtr commented Oct 3, 2024

Rough steps as mentioned in the community meeting,

  • create an e2e or integration test to reproduce the issue.
  • apply the patch (ahrtr@76ac23f) to ensure it fixes the issue.
  • evaluate the performance impact.

cc @ArkaSaha30 @ivanvc

The other solution as mentioned in the meeting is to keep the behaviour unchanged.

  • Ensure all members execute the same validation.
  • But only the member that the client connects to execute the range request in a TXN

But the problem is that this solution will reduce the readability and complicate the etcdserver a lot. So If the performance impact of first solution is minimum, then we should NOT go for this solution 2

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 3, 2024

@ahrtr @serathius say even with the fix to execute the range request on all members, wdyt about the same issue happening when (for lack of a better word) non-deterministic failures lead to one node failing the txn.Range() while the other doesn't?

@ahrtr
Copy link
Member Author

ahrtr commented Oct 3, 2024

@ahrtr @serathius say even with the fix to execute the range request on all members, wdyt about the same issue happening when (for lack of a better word) non-deterministic failures lead to one node failing the txn.Range() while the other doesn't?

It's a generic "problem", not specific to this issue.

If a node somehow fails to apply entries due to environment issue (i.e. OOM), then etctserver crashes. When it gets started again, it will re-apply the entries.

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 3, 2024

So far the only vector I found for what I was saying above to happen is if the Tx context was cancelled -

case <-ctx.Done():
return nil, fmt.Errorf("rangeKeys: context cancelled: %w", ctx.Err())

But fortunately (or maybe intentionally) the context that gets piped down to it from Apply is a context.TODO() that should never expire:

return a.applyV3.Apply(context.TODO(), r, a.dispatch)

We probably need to add a big bold note there saying it's risky (wrt data consistency) to change that context to anything finite (I'll send out a PR). But does the overarching risk and #18667 (comment) feel worth discussing to y'all?

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 3, 2024

When it gets started again, it will re-apply the entries.

This part makes sense when the failure happens in transaction validation phase (CI isn't incremented). But cases like what you found would be more dangerous when CI is incremented but applied asymmetrically across nodes. Lemme try digging thru the code to see if there are any potential risks there (hopefully none).

@serathius
Copy link
Member

So far the only vector I found for what I was saying above to happen is if the Tx context was cancelled -

This is a great point about how context can introduce non-determinism into the apply loop, which is highly undesirable. Since the apply loop forms the core of the replicated state machine, any inconsistency caused by context cancellation at different times could lead to significant issues.

I think that using context here seems unnecessary and increases the risk of compromising transactionality. From what I understand, it's primarily used for passing call stack metadata like traces and authorization information. We can definitely find alternative ways to achieve this without relying on context.

To mitigate the risk, I strongly recommend removing context entirely from the apply loop code. Since the asynchronous code within the loop should not involve any non-deterministic asynchronous calls, we can safely eliminate context. We can then re-implement trace logging without relying on it.

@ahrtr
Copy link
Member Author

ahrtr commented Oct 4, 2024

To mitigate the risk, I strongly recommend removing context entirely from the apply loop code.

Agree to this in principle. Clearly, it isn't a minor change. So let's get the low-hanging fix #18674 approved & merged first. Afterwards, we can revisit removing the context without rushing.

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 4, 2024

@serathius @ahrtr the idea of removing context sure seems tempting. Should we discuss few things first:

  • Given context is canonical golang way of passing down other metadata, are we sure we won't need it long-term? There are ways to use context in non-cancellable fashion (see WithoutCancel)
  • Do we foresee any cases where we do want a timeout (for e.g read-only txns, those should be safe to timeout)? Also in case of server shutdown, we may want to cleanly stop an apply (without incrementing CI) when it's safe to do so (for e.g if we're executing the "check" phase of a write txn)
  • Will context be helpful in writing certain class of robustness tests? For e.g say we want to test that entry X+1 isn't applied when entry X fails to apply (we could use context to trigger this)
  • Are there any safe alternatives to solve the overarching problem here i.e. prevent server from moving on when an apply fails? ideally we want the server to halt/crash and not increment the CI at all (making it safe even across restarts)

Also happy to discuss this over our next biweekly call, if you prefer.

@serathius
Copy link
Member

Thanks for the comment, my thoughts:

  • Metadata is passed, but only through the lower levels of mvcc, It's not really used throughout the most of the apply code. Let's not try to predict what we will need in the future, let's focus on the current needs, it's not like we cannot revert the decision in the future.
  • Never, we will never need a timeout. Like I mentioned above, we cannot use timeout as it introduces dependency on local node performance for execution of code that needs to be deterministic. If apply loop is stuck, we should crash, not timeout.
  • No, we have the gofail library to inject failures through on exact code location without context.
  • I don't think this is a problem at all. Server should move on if read fails, because the read fail as the revision it tried to read was no longer available. There is no other place to validate revision used here. Incrementing the CI was correct here, fact we executed TXN in inconsistent way is the issue.

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 5, 2024

Thanks @serathius for laying out that reasoning.

Never, we will never need a timeout

Wdyt about read-only txns (which can go through the apply layer today iiuc)? Those we might want to timeout if taking too long instead of blocking the subsequent applies

it's not like we cannot revert the decision in the future

+1 to this. The part I wasn't fully sure about is how costly/complex will it be to add that back. Seems not too bad from the size of your PRs :)

Incrementing the CI was correct here, fact we executed TXN in inconsistent way is the issue.

Agreed - and the plan laid out above makes full sense to fix this particular issue. Zooming out a bit though, I'm wondering if we need one more invariant besides "txn execution symmetry" - which is "txn side-effect symmetry". FMU the former doesn't necessarily guarantee the latter - potentially because of non-determinism (your context removal change is def going to improve there, but we might have more risks). Since this is a different issue than the original one, I've opened #18679 to discuss more.

@serathius
Copy link
Member

serathius commented Oct 5, 2024

Wdyt about read-only txns (which can go through the apply layer today iiuc)? Those we might want to timeout if taking too long instead of blocking the subsequent applies

If I remember correctly, Read only TXN don't go through apply.

if txn.IsTxnReadonly(r) {
trace := traceutil.New("transaction",
s.Logger(),
traceutil.Field{Key: "read_only", Value: true},
)
ctx = context.WithValue(ctx, traceutil.TraceKey{}, trace)
if !txn.IsTxnSerializable(r) {
err := s.linearizableReadNotify(ctx)
trace.Step("agreement among raft nodes before linearized reading")
if err != nil {
return nil, err
}
}
var resp *pb.TxnResponse
var err error
chk := func(ai *auth.AuthInfo) error {
return txn.CheckTxnAuth(s.authStore, ai, r)
}
defer func(start time.Time) {
txn.WarnOfExpensiveReadOnlyTxnRequest(s.Logger(), s.Cfg.WarningApplyDuration, start, r, resp, err)
trace.LogIfLong(traceThreshold)
}(time.Now())
get := func() {
resp, _, err = txn.Txn(ctx, s.Logger(), r, s.Cfg.ExperimentalTxnModeWriteWithSharedBuffer, s.KV(), s.lessor)
}
if serr := s.doSerialize(ctx, chk, get); serr != nil {
return nil, serr
}
return resp, err
}

+1 to this. The part I wasn't fully sure about is how costly/complex will it be to add that back. Seems not too bad from the size of your PRs :)

Yea, know the code and re-read it before.

your context removal change is def going to improve there, but we might have more risks.

Yes, if I could I would rewrite apply code to ensure clear control of side effects. However, that would require a large investment into testing and don't give a large payout as the apply code is not frequently changed. Now most of the etcd correctness issues come from versions before v3.4. Rewriting it might resurface new bugs, but also introduces a high risk of introducing new issues. That's why I would think robustness testing is better strategically, we need to build a trust into testing that no matter how new is contributor, they can propose improvements to any part of etcd codebase and we can catch up any concurrency bugs.

@shyamjvs
Copy link
Contributor

shyamjvs commented Oct 7, 2024

Read only TXN don't go through apply.

Thanks for the code ref, that makes sense. IIUC there can be a case where txn isn't seen as read-only (say there's a write in the if-branch) but the compare operation renders it as read-only (in else-branch). One good thing here is we should be able to know this before executing the txn itself as we know compare result and traverse the txn tree in the check phase. I can make a change to improve this behavior - but a case to keep in mind for timeouts. Wdyt?

@serathius
Copy link
Member

I think #18749 should resolve the issue, but we are missing an e2e regression test. Anyone interested in implementing one?

@ahrtr
Copy link
Member Author

ahrtr commented Oct 24, 2024

I think #18749 should resolve the issue,

#18749 just fixed a separate but related potential issue caught by @shyamjvs . For this issue, it isn't fixed yet. We still need to apply a patch something like ahrtr@76ac23f

Pls refer to #18667 (comment). Also @ArkaSaha30 is working on the e2e test.

@ahrtr
Copy link
Member Author

ahrtr commented Oct 24, 2024

/assign @ArkaSaha30

@ahrtr
Copy link
Member Author

ahrtr commented Nov 27, 2024

@ArkaSaha30 are you still working on this? I know that you are still working on etcd-operator. If you don't have enough bandwidth, would you mind we assign this to other contributors?

@ArkaSaha30
Copy link
Contributor

@ArkaSaha30 are you still working on this? I know that you are still working on etcd-operator. If you don't have enough bandwidth, would you mind we assign this to other contributors?

Sure @ahrtr , it is taking more time for me than expected to get familiar with writing the E2E tests. If any of the contributors are interested and familiar with the E2E tests this issue can be assigned to them. Sorry for the inconvenience of blocking this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
backport/v3.4 backport/v3.5 priority/important-soon Must be staffed and worked on either currently, or very soon, ideally in time for the next release. type/bug
Development

No branches or pull requests

5 participants