Skip to content

storage/concurrency: implement concurrency Manager#45062

Merged
craig[bot] merged 3 commits intocockroachdb:masterfrom
nvb:nvanbenschoten/concManager
Feb 19, 2020
Merged

storage/concurrency: implement concurrency Manager#45062
craig[bot] merged 3 commits intocockroachdb:masterfrom
nvb:nvanbenschoten/concManager

Conversation

@nvb
Copy link
Copy Markdown
Contributor

@nvb nvb commented Feb 13, 2020

Informs #41720.
Informs #44976.
Initially drawn out in #43775.

This PR implements the concurrency.Manager interface, which is the core structure that ties together the new concurrency package.

The concurrency manager is a structure that sequences incoming requests and provides isolation between requests that intend to perform conflicting operations. During sequencing, conflicts are discovered and any found are resolved through a combination of passive queuing and active pushing. Once a request has been sequenced, it is free to evaluate without concerns of conflicting with other in-flight requests due to the isolation provided by the manager. This isolation is guaranteed for the lifetime of the request but terminates once the request completes.

The manager accomplishes this by piecing together the following components in its request sequencing path:

  • latchManager
  • lockTable
  • lockTableWaiter
  • txnWaitQueue

The largest part of this change is introducing the datadriven testing framework to deterministically test the concurrency manager. This proved difficult for two reasons:

  1. the concurrency manager composes several components to perform it work (latchManager, lockTable, lockTableWaiter, txnWaitQueue). It was difficult to get consistent observability into each of these components in such a way that tests could be run against a set of concurrent requests interacting with them all.
  2. the concurrency manager exposes a primarily blocking interface. Requests call Sequence() and wait for sequencing to complete. This may block in a number of different places - while waiting on latches, while waiting on locks, and while waiting on other transactions. The most important part of these tests is to assert where a given request blocks based on the current state of the concurrency manager and then assert how the request reacts to a state transition by another request.

To address the first problem, the testing harness uses the context-carried tracing infrastructure to track the path of a request. We already had log events scattered throughout these various components, so this did not require digging testing hooks into each of them. Instead, the harness attached a trace recording span to each request and watches as events are added to the span. It then uses these events as the output of the text.

To address the second problem, the testing harness introduces a monitor object which manages a collection of "monitored" goroutines. The monitor watches as these goroutines run and keeps track of their goroutine state as is reported by a goroutine dump. During each step of the datadriven test, the monitor allows all goroutines to proceed until they have either terminated or stalled due to cross-goroutine synchronization dependencies. For instance, it waits for all goroutines to stall while receiving from channels. We can be sure that the goroutine dump provides a consistent snapshot of all goroutine states and statuses because runtime.Stack(all=true) stops the world when called. This means that when all monitored goroutines are simultaneously stalled, we have a deadlock that can only be resolved by proceeding forward with the test and releasing latches, resolving locks, or committing transactions. This structure worked surprisingly well and has held up to long periods of stressrace.

@nvb nvb requested review from sumeerbhola and tbg February 13, 2020 03:41
@cockroach-teamcity
Copy link
Copy Markdown
Member

This change is Reviewable

@nvb nvb force-pushed the nvanbenschoten/concManager branch from 25da103 to 4108a52 Compare February 13, 2020 05:07
Copy link
Copy Markdown
Member

@tbg tbg left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Apologies for the late bikeshedding on the testdata syntax in the first commit. I do think they're reasonable suggestions, but I won't push for them since I wasn't part of the original review.

The goroutine status approach is clever. We have occasionally thought about something like it in roachtest, but since it's opt-in we never even got close to doing it. I just want to caution that this will only keep working as long as the concurrency package's tests don't spin up too many goroutines at once. For example, in pkg/storage, using this in a test that spins up a five node cluster would probably cause real problems (due to dumping a few-mbs worth of stack every time). Don't think it'll ever come to that here, so I like this a lot.

Still have to review the actual datadriven tests, but have to step out now.

Reviewed 3 of 3 files at r1, 11 of 14 files at r2.
Reviewable status: :shipit: complete! 0 of 0 LGTMs obtained (waiting on @nvanbenschoten, @sumeerbhola, and @tbg)


pkg/storage/concurrency/concurrency_manager.go, line 71 at r2 (raw file):

			m: spanlatch.Make(store.Stopper(), store.GetSlowLatchGauge()),
		},
		lt: newLockTable(10000),

Any comment on this number? Even if it's just /* arbitrary */


pkg/storage/concurrency/concurrency_manager.go, line 90 at r2 (raw file):

func (m *managerImpl) SequenceReq(
	ctx context.Context, prev *Guard, req Request,
) (g *Guard, resp Response, err *Error) {

The naked returns in a larger method like that make me nervous (not in the sense that concretely suspect that something's wrong, but they force me to check more things while I review this). You could s/prev/g/ and then

if g == nil {
  g = newGuard(req)
} else {
  g.assertNoLatches()
}

Hmm, I'm seeing now that you need to access them in the defer below. May I still suggest the following

func (m *managerImpl) SequenceReq(
  ctx context.Context, prev *Guard, req Request
) (g *Guard, resp Response, err *Error) {
	defer func() {
		if g != nil && (resp != nil || err != nil) {
			m.FinishReq(g)
			g = nil
		}
	}()
	return m.sequenceReqInner(ctx, prev, req)
}

and then don't have naked returns in sequenceReqInner.


pkg/storage/concurrency/concurrency_manager.go, line 115 at r2 (raw file):

	// Provide the manager with an opportunity to intercept the request. It
	// may be able to server the request directly, and even if not, it may

serve


pkg/storage/concurrency/concurrency_manager.go, line 219 at r2 (raw file):

		if roachpb.IsTransactional(arg) {
			switch arg.Method() {
			case roachpb.HeartbeatTxn:

How does HeartbeatTxn run into locks? I'm probably missing some conceptual understanding here.


pkg/storage/concurrency/concurrency_manager.go, line 267 at r2 (raw file):

	m.twq.EnqueueTxn(&t.PusheeTxn)

	// Release the Guard's latches but continue to remain in lock wait-queues by

The caller/request here is always a push request, right? Can a push be in any lock-wait queues?


pkg/storage/concurrency/concurrency_manager.go, line 280 at r2 (raw file):

	// field to it.
	if err := m.lt.AcquireLock(&in.Txn, in.Key, lock.Exclusive, lock.Unreplicated); err != nil {
		log.Fatalf(ctx, "assertion failure: %s", err)

do you want log.Fatal(ctx, errors.WithAssertionFailure(err)) for all of these?

@knz the method comment says to not use directly. What do you think is the right thing to use here? Just log.Fatal(ctx, err) or what's here now?


pkg/storage/concurrency/concurrency_manager_test.go, line 48 at r2 (raw file):

)

// TestLockTableBasic verifies that sequences of requests interacting with a

Now that we have new datadriven tests pop up regularly, I wonder if we can come up with a naming scheme signals the "datadrivenness" of a given test (perhaps even connecting it to the test data). Any thoughts? Putting "DataDriven" in the test name would be a start. The goal would be that when confronted with a testdata directory, one would know where to look for the runner.


pkg/storage/concurrency/concurrency_manager_test.go, line 53 at r2 (raw file):

// The input files use the following DSL:
//
// txn             name=<txn-name> ts=<int>[,<int>] epoch=<int>

Similar comment here about new-txn, new-req, new-batch


pkg/storage/concurrency/concurrency_manager_test.go, line 55 at r2 (raw file):

// txn             name=<txn-name> ts=<int>[,<int>] epoch=<int>
// single-request  name=<req-name> type=<proto-name> [fields=<name=value>[,<name2=value2>]...]
// batch-request   name=<batch-name> txn=<txn-name>|none ts=<int>[,<int>] reqs=<req-name>... [priority] [consistency]

Do you ever need requests in isolation? You have here a two-level hierarchy to construct a batch: first you need to create (and name) a number of requests, then you have to list them again in a batch. Couldn't you have a syntax that combines the two, and avoids the need to name individual requests? Something like

new-batch name=...
<proto-name> [fields=....]
<proto-name> [fields=....]
...
----
ok

I understand that datadriven may not make that super convenient since it only parses the first line for you. I wonder if there's something we should do there.
Perhaps this is also fine as is. Just wanted to offer the suggestion.


pkg/storage/concurrency/lock_table.go, line 1696 at r1 (raw file):

func (t *lockTableImpl) Clear() {
	t.clearMostLocks(true /* force */)

Is clearMostLocks still the right name?


pkg/storage/concurrency/lock_table_test.go, line 50 at r1 (raw file):

 Creates a TxnMeta.

request r=<name> txn=<name>|none ts=<int>[,<int>] spans=r|w@<start>[,<end>]+...

It's a bit unfortunate that the "create" family of directives uses verbs as this subtracts from how well tests describe themselves (you have to know if we're requesting something, or creating a request). new-txn, new-req etc would avoid this without being overly verbose.


pkg/storage/concurrency/lock_table_test.go, line 86 at r1 (raw file):

 Adds a discovered lock that is disovered by the named request.

done r=<name>

Why not call this dequeue? "done" is more general than seems useful.


pkg/storage/concurrency/lock_table_test.go, line 100 at r1 (raw file):

  CurState.

guard-start-waiting r=<name>

guard-should-wait? If start-waiting is a better name then it stands to reason that we should rename lockTableGuard.ShouldWait to match.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 77 at r2 (raw file):

----

# Demonstrate that 'reset' clears the lock table.

As written, the lock table could've been cleared via the finish above. Maybe jst move the debug-lock-table invocation down one command.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 106 at r2 (raw file):

[2] sequence req3: pushing txn 00000000-0000-0000-0000-000000000002

on-txn-updated txn=txn2

It's weird that this doesn't specify the update but evidently it got committed.


pkg/storage/concurrency/testdata/lock_table/clear, line 1 at r1 (raw file):

txn txn=txn1 ts=10,1 epoch=0

Could you add light prose to these tests? That way, they will be accessible without reading the testdata format in detail. Right now there is a bit of guesswork on what some of the directives mean. I was thinking something like

Define three transaction we'll use below.


pkg/storage/concurrency/testdata/lock_table/clear, line 12 at r1 (raw file):

request r=req1 txn=txn1 ts=10,1 spans=w@a+w@b
----

txn1 acquires unreplicated exclusive locks at a and b.


pkg/storage/concurrency/testdata/lock_table/clear, line 45 at r1 (raw file):

  holder: txn: 00000000-0000-0000-0000-000000000001, ts: 0.000000010,1
local: num=0

In its next request, txn1 discovers a lock at c held by txn2.


pkg/storage/concurrency/testdata/lock_table/clear, line 68 at r1 (raw file):

local: num=0

request r=req3 txn=none ts=10,1 spans=r@a

A read comes in at a and blocks on the lock.


pkg/storage/concurrency/testdata/lock_table/clear, line 79 at r1 (raw file):

new: state=waitForDistinguished txn=txn1 ts=10,1 key="a" held=true guard-access=read

request r=req4 txn=none ts=10,1 spans=w@a

Similarly, a write at a arrives and blocks.


pkg/storage/concurrency/testdata/lock_table/clear, line 90 at r1 (raw file):

new: state=waitFor txn=txn1 ts=10,1 key="a" held=true guard-access=write

request r=req5 txn=txn3 ts=12,1 spans=w@b

txn3 tries to write to b which also has a lock held, so txn3 has to wait.


pkg/storage/concurrency/testdata/lock_table/clear, line 120 at r1 (raw file):

local: num=0

clear

Clearing removes all locks and allows all waiting requests to proceed.

@tbg tbg self-requested a review February 13, 2020 10:56
Copy link
Copy Markdown
Member

@tbg tbg left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

:lgtm: very nice to see this come together.

Reviewed 3 of 14 files at r2.
Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (waiting on @nvanbenschoten and @sumeerbhola)


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 91 at r2 (raw file):

# -------------------------------------------------------------

on-lock-acquired txn=txn2 key=k

why does this one (and some of the others) launch a monitored goroutine?


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 125 at r2 (raw file):

----
[4] sequence req4: sequencing request
[4] sequence req4: acquiring latches

idea: let the output contain a message describing where the goroutine is blocked if it doesn't run to completion right away. It could be something like blocked: select in someFunction().


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 142 at r2 (raw file):

[6] finish req4: finishing request

reset

Why? (here and elsewhere)


pkg/storage/concurrency/testdata/concurrency_manager/no_latches, line 14 at r2 (raw file):

----
[1] sequence inconsistentReq: sequencing request
[1] sequence inconsistentReq: not acquiring latches

This is convincing, but I would've assumed you would also print the latch manager at this point to prove there in fact aren't any latches. (here and below).

Copy link
Copy Markdown
Contributor Author

@nvb nvb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Apologies for the late bikeshedding on the testdata syntax in the first commit.

It's not late at all - we're just getting started 😃

Don't think it'll ever come to that here, so I like this a lot.

I just checked and the maximum size that the stack dump grows to right now is ~11KB. I'd start to worry if we were pushing multiple MBs, but we seem to have plenty of headroom.

Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (waiting on @nvanbenschoten and @sumeerbhola)

Copy link
Copy Markdown
Collaborator

@sumeerbhola sumeerbhola left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)


pkg/storage/concurrency/lock_table.go, line 1696 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Is clearMostLocks still the right name?

tryClearLocks?

Copy link
Copy Markdown
Collaborator

@sumeerbhola sumeerbhola left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I haven't read the test yet.

Reviewed 3 of 3 files at r1, 9 of 14 files at r2.
Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)


pkg/storage/concurrency/concurrency_manager.go, line 109 at r2 (raw file):

	// Some requests don't need to acquire latches at all.
	if !shouldAcquireLatches(req) {

This seems like a case where we don't even need to create a guard. If that is correct, how about hoisting this to the beginning of the function.


pkg/storage/concurrency/concurrency_manager.go, line 138 at r2 (raw file):

		// Scan for conflicting locks.
		log.Event(ctx, "scanning lock table for conflicting locks")
		g.ltg = m.lt.ScanAndEnqueue(g.req, g.ltg)

I find it a bit peculiar that this code knows about lockTableGuard and lockTable and so does lockTableWaiter, and that this code calls ScanAndEnqueue(). Would it be cleaner to move everything from the ScanAndEnqueue() down to the end of the if-block below into lockTableWaiter?


pkg/storage/concurrency/concurrency_manager.go, line 140 at r2 (raw file):

		g.ltg = m.lt.ScanAndEnqueue(g.req, g.ltg)

		// Wait on each newly conflicting lock, if necessary.

nit: given there is no inner loop here it may be simpler to say
// Wait on conflicting locks, if necessary.
(I am assuming some of this phrasing predates the hiding of all the lock queues inside the lockTable implementation)


pkg/storage/concurrency/concurrency_manager.go, line 172 at r2 (raw file):

	case req.isSingle(roachpb.QueryTxn):
		// If necessary, wait in the txnWaitQueue for a transaction state update
		// or for a dependent transaction to change.

when is QueryTxnRequest used?


pkg/storage/concurrency/concurrency_manager.go, line 177 at r2 (raw file):

	default:
		// TODO(nvanbenschoten): in the future, use this hook to update the lock
		// table to allow contending transactions to proceed.

is this TODO about resolving intents without latches, when the segregated lock table is the source of truth, so there won't be a concern about a race between a reader discovering an intent and the resolution of the intent?


pkg/storage/concurrency/concurrency_manager.go, line 219 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

How does HeartbeatTxn run into locks? I'm probably missing some conceptual understanding here.

does this update the roachpb.Transaction object? Is that the "transaction record" stored in the range where the transaction did its first write?


pkg/storage/concurrency/concurrency_manager.go, line 221 at r2 (raw file):

			case roachpb.HeartbeatTxn:
			case roachpb.Refresh:
			case roachpb.RefreshRange:

I am basing my understanding on reading the comment for RefreshRequest: does this not need to wait on locks because it has a read latch at T to prevent any new concurrent writes <= T, and will update the timestamp cache during evaluation to T so that any subsequent requests will not be able to write <= T?


pkg/storage/concurrency/concurrency_manager.go, line 262 at r2 (raw file):

// HandleTransactionPushError implements the ContentionHandler interface.
func (m *managerImpl) HandleTransactionPushError(

is this the same kind of push error I was asking about in PR #44885 ? And what causes these errors -- RPC failing because the node to which it was sent failed?


pkg/storage/concurrency/concurrency_manager.go, line 318 at r2 (raw file):

// OnSplit implements the RangeStateListener interface.
func (m *managerImpl) OnSplit() {
	m.lt.Clear()

should there be a TODO to do better than a Clear()? Same question about OnMerge().


pkg/storage/concurrency/testdata/lock_table/clear, line 136 at r1 (raw file):

----
new: state=doneWaiting

can you add a scan r=req3 to make it clear that start-waiting will be false (just like you did for req2 above). Same for req4 and req5.

Copy link
Copy Markdown
Collaborator

@sumeerbhola sumeerbhola left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

minor comments about the test -- it made for interesting reading!

Reviewed 2 of 14 files at r2.
Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (waiting on @nvanbenschoten and @tbg)


pkg/storage/concurrency/concurrency_manager_test.go, line 48 at r2 (raw file):

)

// TestLockTableBasic verifies that sequences of requests interacting with a

s/TestLockTableBasic/TestConcurrencyManagerBasic/


pkg/storage/concurrency/concurrency_manager_test.go, line 352 at r2 (raw file):

// cluster implements the Store interface.
func (c *cluster) NodeDescriptor() *roachpb.NodeDescriptor { return c.nodeDesc }
func (c *cluster) DB() *client.DB                          { return nil }

do these nil returns represent things that are needed managerImpl but not by the test, and so represent untested functionality?
Hmm, I don't see in concurrency_manager.go where managerImpl.str is used.


pkg/storage/concurrency/concurrency_manager_test.go, line 369 at r2 (raw file):

		return roachpb.Transaction{}, roachpb.NewError(err)
	}
	// Wait for the transaction to commit.

or abort?


pkg/storage/concurrency/concurrency_manager_test.go, line 548 at r2 (raw file):

						time:     log.Time,
						fieldIdx: i,
						value:    field.Value,

we don't need field.Key? Is the key always "event"?


pkg/storage/concurrency/concurrency_manager_test.go, line 560 at r2 (raw file):

	}

	// Sort logs by (time, fieldIdx).

so fieldIdx is just a tiebreaker? Even within a goroutine, it doesn't reflect the ordering in which the logRecords were encountered in the nested loop above (g.prevLines - prev would be that order, starting from 0).


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 77 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

As written, the lock table could've been cleared via the finish above. Maybe jst move the debug-lock-table invocation down one command.

How about adding another debug-lock-table after the finish to show that lock continues to be held after the request finishes?


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 91 at r2 (raw file):

# -------------------------------------------------------------

on-lock-acquired txn=txn2 key=k

It seems odd that a lock can be acquired without a request from that transaction holding latches. Does it just happen to be how the test is written, or did I miss something?


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 114 at r2 (raw file):

[2] sequence req3: sequencing complete, returned guard

debug-lock-table

can you also add a case with on-lock-updated

Copy link
Copy Markdown
Contributor Author

@nvb nvb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TFTRs!

Reviewable status: :shipit: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @andy-kimball, @knz, @sumeerbhola, and @tbg)


pkg/storage/concurrency/concurrency_manager.go, line 71 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Any comment on this number? Even if it's just /* arbitrary */

Done. And I added a TODO to make this configurable.


pkg/storage/concurrency/concurrency_manager.go, line 90 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

The naked returns in a larger method like that make me nervous (not in the sense that concretely suspect that something's wrong, but they force me to check more things while I review this). You could s/prev/g/ and then

if g == nil {
  g = newGuard(req)
} else {
  g.assertNoLatches()
}

Hmm, I'm seeing now that you need to access them in the defer below. May I still suggest the following

func (m *managerImpl) SequenceReq(
  ctx context.Context, prev *Guard, req Request
) (g *Guard, resp Response, err *Error) {
	defer func() {
		if g != nil && (resp != nil || err != nil) {
			m.FinishReq(g)
			g = nil
		}
	}()
	return m.sequenceReqInner(ctx, prev, req)
}

and then don't have naked returns in sequenceReqInner.

Hm, I'm not seeing any naked returns, just named return arguments. But I get what you're saying. Done.


pkg/storage/concurrency/concurrency_manager.go, line 109 at r2 (raw file):

Previously, sumeerbhola wrote…

This seems like a case where we don't even need to create a guard. If that is correct, how about hoisting this to the beginning of the function.

Yes, that's actually exactly what I had right before I pushed this, but I changed it because this is a rare code-path (so the allocation doesn't matter) and I wanted the "sequencing request" log event. I also changed it because the same argument could be made about the maybeInterceptReq call, but in that case, I don't want to have to ask questions about what would happen if we are re-sequencing a request that previously acquired a guard. Since this is a harder change to make with Tobi's suggestion above anyway, I'm going to leave as is.


pkg/storage/concurrency/concurrency_manager.go, line 115 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

serve

Done.


pkg/storage/concurrency/concurrency_manager.go, line 138 at r2 (raw file):

Previously, sumeerbhola wrote…

I find it a bit peculiar that this code knows about lockTableGuard and lockTable and so does lockTableWaiter, and that this code calls ScanAndEnqueue(). Would it be cleaner to move everything from the ScanAndEnqueue() down to the end of the if-block below into lockTableWaiter?

Yeah, I see what you're saying. The main blocker to that control flow is that we only want to release latches if we're actually waiting on any locks, and I'd find it more strange if the lockTableWaiter had to know about the latchManager and its latchGuard. What do you think?


pkg/storage/concurrency/concurrency_manager.go, line 140 at r2 (raw file):

Previously, sumeerbhola wrote…

nit: given there is no inner loop here it may be simpler to say
// Wait on conflicting locks, if necessary.
(I am assuming some of this phrasing predates the hiding of all the lock queues inside the lockTable implementation)

Good point, done.


pkg/storage/concurrency/concurrency_manager.go, line 172 at r2 (raw file):

Previously, sumeerbhola wrote…

when is QueryTxnRequest used?

QueryTxn is used during deadlock detection for a pusher to query its own record. I added a comment about how this works to the txnWaitQueue interface.


pkg/storage/concurrency/concurrency_manager.go, line 177 at r2 (raw file):

Previously, sumeerbhola wrote…

is this TODO about resolving intents without latches, when the segregated lock table is the source of truth, so there won't be a concern about a race between a reader discovering an intent and the resolution of the intent?

Yes, exactly. And this relies on the lockAwareIterator from https://github.com/nvanbenschoten/cockroach/commits/nvanbenschoten/lockTable capturing the state of the lockTable so it knows which intents have been "virtually resolved", which is part of what inspired the desire for the immutable btree.


pkg/storage/concurrency/concurrency_manager.go, line 219 at r2 (raw file):

How does HeartbeatTxn run into locks?

No, this was mistaken. Removed.

does this update the roachpb.Transaction object? Is that the "transaction record" stored in the range where the transaction did its first write?

Yes, that's correct.


pkg/storage/concurrency/concurrency_manager.go, line 221 at r2 (raw file):

Previously, sumeerbhola wrote…

I am basing my understanding on reading the comment for RefreshRequest: does this not need to wait on locks because it has a read latch at T to prevent any new concurrent writes <= T, and will update the timestamp cache during evaluation to T so that any subsequent requests will not be able to write <= T?

Yes, that's correct. I added a comment about this.


pkg/storage/concurrency/concurrency_manager.go, line 262 at r2 (raw file):
Kind of. This is the reason why transaction push errors don't propagate back up to the node that sent the push request. Instead of returning the error, the push queues in the TxnWaitQueue on the leaseholder of the pushee's record, so these errors are always consumed here.

And what causes these errors -- RPC failing because the node to which it was sent failed?

No, these errors indicate that the push failed because the conditions for it to succeed were not met. For instance, the pushee may not have had a high enough priority or the pusher may not have been expired.


pkg/storage/concurrency/concurrency_manager.go, line 267 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

The caller/request here is always a push request, right? Can a push be in any lock-wait queues?

Good point, no it can't. Done.


pkg/storage/concurrency/concurrency_manager.go, line 280 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

do you want log.Fatal(ctx, errors.WithAssertionFailure(err)) for all of these?

@knz the method comment says to not use directly. What do you think is the right thing to use here? Just log.Fatal(ctx, err) or what's here now?

Done using errors.HandleAsAssertionFailure.


pkg/storage/concurrency/concurrency_manager.go, line 318 at r2 (raw file):

Previously, sumeerbhola wrote…

should there be a TODO to do better than a Clear()? Same question about OnMerge().

The should be for OnSplit, good point. For OnMerge, we need to clear it all, because OnMerge is only called on the RHS of a merge (see the comment on RangeStateListener).


pkg/storage/concurrency/concurrency_manager_test.go, line 48 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Now that we have new datadriven tests pop up regularly, I wonder if we can come up with a naming scheme signals the "datadrivenness" of a given test (perhaps even connecting it to the test data). Any thoughts? Putting "DataDriven" in the test name would be a start. The goal would be that when confronted with a testdata directory, one would know where to look for the runner.

I like the idea, though we already have 32 instances of datadriven tests and there seems to be no pattern in their naming to date. I'd rather not try to unify their naming scheme while making this change.


pkg/storage/concurrency/concurrency_manager_test.go, line 48 at r2 (raw file):

Previously, sumeerbhola wrote…

s/TestLockTableBasic/TestConcurrencyManagerBasic/

Done.


pkg/storage/concurrency/concurrency_manager_test.go, line 53 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Similar comment here about new-txn, new-req, new-batch

Done.


pkg/storage/concurrency/concurrency_manager_test.go, line 55 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Do you ever need requests in isolation? You have here a two-level hierarchy to construct a batch: first you need to create (and name) a number of requests, then you have to list them again in a batch. Couldn't you have a syntax that combines the two, and avoids the need to name individual requests? Something like

new-batch name=...
<proto-name> [fields=....]
<proto-name> [fields=....]
...
----
ok

I understand that datadriven may not make that super convenient since it only parses the first line for you. I wonder if there's something we should do there.
Perhaps this is also fine as is. Just wanted to offer the suggestion.

Ah, I didn't know about datadriven.TestData.Input. Much better! Thanks for the suggestion.


pkg/storage/concurrency/concurrency_manager_test.go, line 352 at r2 (raw file):

Previously, sumeerbhola wrote…

do these nil returns represent things that are needed managerImpl but not by the test, and so represent untested functionality?
Hmm, I don't see in concurrency_manager.go where managerImpl.str is used.

These are all used by the txnWaitQueue, which is completely mocked out in this test, but has plenty of its own tests. I added a comment.


pkg/storage/concurrency/concurrency_manager_test.go, line 369 at r2 (raw file):

Previously, sumeerbhola wrote…

or abort?

Done. Although for the purpose of this test, it doesn't really matter which terminal state pushees enter.


pkg/storage/concurrency/concurrency_manager_test.go, line 548 at r2 (raw file):

Previously, sumeerbhola wrote…

we don't need field.Key? Is the key always "event"?

Yes, the key is always just "event".


pkg/storage/concurrency/concurrency_manager_test.go, line 560 at r2 (raw file):

Previously, sumeerbhola wrote…

so fieldIdx is just a tiebreaker? Even within a goroutine, it doesn't reflect the ordering in which the logRecords were encountered in the nested loop above (g.prevLines - prev would be that order, starting from 0).

Oh no, this was just wrong, though it wasn't actually causing issues. Thanks for catching. Done.


pkg/storage/concurrency/lock_table.go, line 1696 at r1 (raw file):

Previously, sumeerbhola wrote…

tryClearLocks?

Done.


pkg/storage/concurrency/lock_table_test.go, line 50 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

It's a bit unfortunate that the "create" family of directives uses verbs as this subtracts from how well tests describe themselves (you have to know if we're requesting something, or creating a request). new-txn, new-req etc would avoid this without being overly verbose.

This makes sense. Done here and in __ (to sequence better with Sumeer's changes).


pkg/storage/concurrency/lock_table_test.go, line 86 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Why not call this dequeue? "done" is more general than seems useful.

I had a TODO in lock_table_test.go to make that change. Done in #45147 (to sequence better with Sumeer's changes).


pkg/storage/concurrency/lock_table_test.go, line 100 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

guard-should-wait? If start-waiting is a better name then it stands to reason that we should rename lockTableGuard.ShouldWait to match.

Yep, I also had a TODO in lock_table_test.go to make this change. Done in #45147 (to sequence better with Sumeer's changes).


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 77 at r2 (raw file):

Previously, sumeerbhola wrote…

How about adding another debug-lock-table after the finish to show that lock continues to be held after the request finishes?

Done.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 91 at r2 (raw file):

Previously, sumeerbhola wrote…

It seems odd that a lock can be acquired without a request from that transaction holding latches. Does it just happen to be how the test is written, or did I miss something?

This shouldn't actually be possible, but the test allows it because it would be cumbersome to have to create and sequence a request every time the test wants to add a lock to the lockTable. I'm willing to change it if you feel strongly.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 91 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

why does this one (and some of the others) launch a monitored goroutine?

Yeah, that's a good question. I'm using this right now just to get access to a context with trace recording enabled that's hooked into the monitor tracing infrastructure. I added a runSync method instead.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 106 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

It's weird that this doesn't specify the update but evidently it got committed.

Done.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 114 at r2 (raw file):

Previously, sumeerbhola wrote…

can you also add a case with on-lock-updated

Done. on-lock-updated doesn't really make sense as a directive in this setup because the distinguished waiters always end up waiting directly on the txn record and calls into OnLockUpdated in cluster.ResolveIntent, so I structured this as two waiters. Only one is distinguished so only one will wait while pushing and the other will wait in lockTable.

Also, this led me to find a bug in lockState.increasedLockTs where we had a timestamp comparison backwards. I've added a new commit to fix this. PTAL.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 125 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

idea: let the output contain a message describing where the goroutine is blocked if it doesn't run to completion right away. It could be something like blocked: select in someFunction().

Cool idea! Done.

I also started using https://godoc.org/github.com/maruel/panicparse/stack, which means that I no longer need to parse any of this myself. It looks like you were already vendoring that library.


pkg/storage/concurrency/testdata/concurrency_manager/basic, line 142 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Why? (here and elsewhere)

This was @andy-kimball's idea and I think it's a good one. reset clears the lockTable and asserts that we're not leaking any test state into the next sequence of events. It's meant to give some separation between test setups so that a reader doesn't need to read the entire file from the start to be able to reason locally about the state of the system.


pkg/storage/concurrency/testdata/concurrency_manager/no_latches, line 14 at r2 (raw file):

Previously, tbg (Tobias Grieger) wrote…

This is convincing, but I would've assumed you would also print the latch manager at this point to prove there in fact aren't any latches. (here and below).

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 1 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Could you add light prose to these tests? That way, they will be accessible without reading the testdata format in detail. Right now there is a bit of guesswork on what some of the directives mean. I was thinking something like

Define three transaction we'll use below.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 12 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

txn1 acquires unreplicated exclusive locks at a and b.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 45 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

In its next request, txn1 discovers a lock at c held by txn2.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 68 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

A read comes in at a and blocks on the lock.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 79 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Similarly, a write at a arrives and blocks.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 90 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

txn3 tries to write to b which also has a lock held, so txn3 has to wait.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 120 at r1 (raw file):

Previously, tbg (Tobias Grieger) wrote…

Clearing removes all locks and allows all waiting requests to proceed.

Done.


pkg/storage/concurrency/testdata/lock_table/clear, line 136 at r1 (raw file):

Previously, sumeerbhola wrote…

can you add a scan r=req3 to make it clear that start-waiting will be false (just like you did for req2 above). Same for req4 and req5.

Done.

@nvb nvb force-pushed the nvanbenschoten/concManager branch 3 times, most recently from 5ad4fe2 to 1bc3d4b Compare February 18, 2020 20:14
nvb added a commit to nvb/cockroach that referenced this pull request Feb 18, 2020
nvb added a commit to nvb/cockroach that referenced this pull request Feb 18, 2020
…art-waiting/should-wait/

Suggested in cockroachdb#45062. Addresses TODOs.
@nvb nvb force-pushed the nvanbenschoten/concManager branch from 1bc3d4b to 74b90f7 Compare February 18, 2020 21:15
Copy link
Copy Markdown
Collaborator

@sumeerbhola sumeerbhola left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

:lgtm:

Reviewed 1 of 16 files at r3, 2 of 2 files at r4, 3 of 14 files at r5, 1 of 2 files at r7, 9 of 14 files at r8.
Reviewable status: :shipit: complete! 1 of 0 LGTMs obtained (and 1 stale) (waiting on @andy-kimball, @knz, @nvanbenschoten, @sumeerbhola, and @tbg)


pkg/storage/concurrency/concurrency_manager.go, line 138 at r2 (raw file):

Previously, nvanbenschoten (Nathan VanBenschoten) wrote…

Yeah, I see what you're saying. The main blocker to that control flow is that we only want to release latches if we're actually waiting on any locks, and I'd find it more strange if the lockTableWaiter had to know about the latchManager and its latchGuard. What do you think?

I had overlooked the issue with releasing latches, and it is questionable which is better if we start passing a preWaitFunc to lockTableWaiter to release the latches. The current code is fine.


pkg/storage/concurrency/concurrency_manager_test.go, line 632 at r5 (raw file):

	}

	// Sort logs by g.osSeq. This will sort synchronous goroutines before

s/osSeq/opSeq/


pkg/storage/concurrency/lock_table.go, line 1248 at r8 (raw file):

		curr := e
		e = e.Next()
		if !g.ts.LessEq(newTs) {

thanks for finding this

craig bot pushed a commit that referenced this pull request Feb 18, 2020
45147: storage/concurrency: clean up lockTable datadriven tests r=nvanbenschoten a=nvanbenschoten

This PR contains three small improvements that were suggested in #45062 by @tbg:
- prefix creation directives with "new-"
- rename `done` directive to `dequeue`
- rename `guard-start-waiting` directive to `should-wait`

@sumeerbhola I'll let you decide how you'd like to sequence this with #45124.

Co-authored-by: Nathan VanBenschoten <nvanbenschoten@gmail.com>
nvb added 3 commits February 18, 2020 18:26
This commit implements the Clear method on lockTableImpl.

While doing so, it fixes a bug in lockTableImpl.clearMostLocks where we
were mutating the btree while iterating over it. This is not supported
by the btree library we use, and was causing the clear to miss locks.
…sedLockTs

This comparison was allowing readers through if their timestamp was
equal to or greater than that of the new lock timestamp. It should have
been the other way around.
Informs cockroachdb#41720.
Informs cockroachdb#44976.

This PR implements the concurrency.Manager interface, which is the
core structure that ties together the new concurrency package.

The concurrency manager is a structure that sequences incoming requests
and provides isolation between requests that intend to perform
conflicting operations. During sequencing, conflicts are discovered and
any found are resolved through a combination of passive queuing and
active pushing. Once a request has been sequenced, it is free to
evaluate without concerns of conflicting with other in-flight requests
due to the isolation provided by the manager. This isolation is
guaranteed for the lifetime of the request but terminates once the
request completes.

The manager accomplishes this by piecing together the following components
in its request sequencing path:
- `latchManager`
- `lockTable`
- `lockTableWaiter`
- `txnWaitQueue`

The largest part of this change is introducing the datadriven testing
framework to deterministically test the concurrency manager. This proved
difficult for two reasons:
1. the concurrency manager composes several components to perform it
   work (latchManager, lockTable, lockTableWaiter, txnWaitQueue). It was
   difficult to get consistent observability into each of these components
   in such a way that tests could be run against a set of concurrent requests
   interacting with them all.
2. the concurrency manager exposes a primarily blocking interface. Requests
   call `Sequence()` and wait for sequencing to complete. This may block in
   a number of different places - while waiting on latches, while waiting on
   locks, and while waiting on other transactions. The most important part
   of these tests is to assert _where_ a given request blocks based on the
   current state of the concurrency manager and then assert _how_ the request
   reacts to a state transition by another request.

To address the first problem, the testing harness uses the context-carried
tracing infrastructure to track the path of a request. We already had log
events scattered throughout these various components, so this did not require
digging testing hooks into each of them. Instead, the harness attached a
trace recording span to each request and watches as events are added to the
span. It then uses these events as the output of the text.

To address the second problem, the testing harness introduces a monitor
object which manages a collection of "monitored" goroutines. The monitor
watches as these goroutines run and keeps track of their goroutine state as
is reported by a goroutine dump. During each step of the datadriven test, the
monitor allows all goroutines to proceed until they have either terminated or
stalled due to cross-goroutine synchronization dependencies. For instance, it
waits for all goroutines to stall while receiving from channels. We can be
sure that the goroutine dump provides a consistent snapshot of all goroutine
states and statuses because `runtime.Stack(all=true)` stops the world when
called. This means that when all monitored goroutines are simultaneously
stalled, we have a deadlock that can only be resolved by proceeding forward
with the test and releasing latches, resolving locks, or committing
transactions. This structure worked surprisingly well and has held up to
long periods of stressrace.
@nvb nvb force-pushed the nvanbenschoten/concManager branch from 74b90f7 to cad0b0f Compare February 18, 2020 23:26
Copy link
Copy Markdown
Contributor Author

@nvb nvb left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TFTRs!

bors r+

Reviewable status: :shipit: complete! 0 of 0 LGTMs obtained (and 2 stale) (waiting on @andy-kimball, @knz, @sumeerbhola, and @tbg)


pkg/storage/concurrency/concurrency_manager_test.go, line 632 at r5 (raw file):

Previously, sumeerbhola wrote…

s/osSeq/opSeq/

Done.

@nvb
Copy link
Copy Markdown
Contributor Author

nvb commented Feb 19, 2020

"message\":\"Required status check"

bors r+

craig bot pushed a commit that referenced this pull request Feb 19, 2020
45062: storage/concurrency: implement concurrency Manager r=nvanbenschoten a=nvanbenschoten

Informs #41720.
Informs #44976.
Initially drawn out in #43775.

This PR implements the concurrency.Manager interface, which is the core structure that ties together the new concurrency package. 

The concurrency manager is a structure that sequences incoming requests and provides isolation between requests that intend to perform conflicting operations. During sequencing, conflicts are discovered and any found are resolved through a combination of passive queuing and active pushing. Once a request has been sequenced, it is free to evaluate without concerns of conflicting with other in-flight requests due to the isolation provided by the manager. This isolation is guaranteed for the lifetime of the request but terminates once the request completes.

The manager accomplishes this by piecing together the following components in its request sequencing path:
- `latchManager`
- `lockTable`
- `lockTableWaiter`
- `txnWaitQueue`

The largest part of this change is introducing the datadriven testing framework to deterministically test the concurrency manager. This proved difficult for two reasons:
1. the concurrency manager composes several components to perform it work (latchManager, lockTable, lockTableWaiter, txnWaitQueue). It was difficult to get consistent observability into each of these components in such a way that tests could be run against a set of concurrent requests interacting with them all.
2. the concurrency manager exposes a primarily blocking interface. Requests call `Sequence()` and wait for sequencing to complete. This may block in a number of different places - while waiting on latches, while waiting on locks, and while waiting on other transactions. The most important part of these tests is to assert _where_ a given request blocks based on the current state of the concurrency manager and then assert _how_ the request reacts to a state transition by another request.

To address the first problem, the testing harness uses the context-carried tracing infrastructure to track the path of a request. We already had log events scattered throughout these various components, so this did not require digging testing hooks into each of them. Instead, the harness attached a trace recording span to each request and watches as events are added to the span. It then uses these events as the output of the text.

To address the second problem, the testing harness introduces a monitor object which manages a collection of "monitored" goroutines. The monitor watches as these goroutines run and keeps track of their goroutine state as is reported by a goroutine dump. During each step of the datadriven test, the monitor allows all goroutines to proceed until they have either terminated or stalled due to cross-goroutine synchronization dependencies. For instance, it waits for all goroutines to stall while receiving from channels. We can be sure that the goroutine dump provides a consistent snapshot of all goroutine states and statuses because `runtime.Stack(all=true)` stops the world when called. This means that when all monitored goroutines are simultaneously stalled, we have a deadlock that can only be resolved by proceeding forward with the test and releasing latches, resolving locks, or committing transactions. This structure worked surprisingly well and has held up to long periods of stressrace.

Co-authored-by: Nathan VanBenschoten <nvanbenschoten@gmail.com>
@craig
Copy link
Copy Markdown
Contributor

craig bot commented Feb 19, 2020

Build succeeded

@craig craig bot merged commit cad0b0f into cockroachdb:master Feb 19, 2020
@nvb nvb deleted the nvanbenschoten/concManager branch February 19, 2020 01:46
@nvb nvb restored the nvanbenschoten/concManager branch February 20, 2020 01:09
@nvb nvb deleted the nvanbenschoten/concManager branch February 20, 2020 01:09
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants