Implement AddSequencedLeaves in MySQL storage by pav-kv · Pull Request #1036 · google/trillian

pav-kv · 2018-03-01T16:26:05Z

This is a stub which does not yet fully implement the API contract, in particular it doesn't return duplicates if any.

Martin2112 · 2018-03-01T16:29:35Z

storage/mysql/log_storage.go

 }

-func (m *mySQLLogStorage) beginInternal(ctx context.Context, tree *trillian.Tree) (storage.LogTreeTX, error) {
+func (m *mySQLLogStorage) beginInternal(ctx context.Context, tree *trillian.Tree) (*logTreeTX, error) {


Not sure why this changed.

AddSequencedLeaves below needs to access logTreeTX internals, in particular tx. This is because I could not use LogTreeTX.UpdateSequencedLeaves as it does not update LeafData.
I think what I could do is shifting this implementation a bit deeper to a dedicated storage.LogTreeTX.AddSequencedLeaves method. WDYT?

Martin2112 · 2018-03-01T16:30:43Z

storage/mysql/log_storage.go

+		return nil, err
+	}
+
+	ok := status.New(codes.OK, "OK").Proto()


Not sure these really help that much?

Indeed, the 2 vars below are better looking if inlined. Not sure about ok, seems like a good optimization for the quick-path case when most/all returned statuses are OK: instead of allocating new proto for the status each time we reuse this one everywhere.

Martin2112 · 2018-03-01T16:32:35Z

storage/mysql/log_storage.go

 	if err != nil && err != storage.ErrTreeNeedsInit {
 		return nil, err
 	}
-	return tx.(storage.ReadOnlyLogTreeTX), err


Does removing this cast change any behaviour such as losing the readonly?

This line did not compile as it was because tx had become a *logTreeTX. The returned value of this function is still the readonly interface, so I suppose nothing changes on the caller's side?

Now tx is again storage.LogTreeTX, but I think casting is unnecessary.

codecov-io · 2018-03-01T16:51:36Z

Codecov Report

Merging #1036 into master will decrease coverage by 0.27%.
The diff coverage is 31.14%.

@@            Coverage Diff             @@
##           master    #1036      +/-   ##
==========================================
- Coverage    62.6%   62.32%   -0.28%     
==========================================
  Files         103      103              
  Lines        8455     8513      +58     
==========================================
+ Hits         5293     5306      +13     
- Misses       2632     2667      +35     
- Partials      530      540      +10

Impacted Files	Coverage Δ
storage/mock_storage.go	`0% <0%> (ø)`	⬆️
storage/mysql/queue.go	`42% <0%> (ø)`	⬆️
server/log_rpc_server.go	`77.46% <100%> (ø)`	⬆️
storage/mysql/log_storage.go	`65.71% <37.5%> (-2.68%)`	⬇️
storage/mysql/map_storage.go	`66.66% <0%> (-1.93%)`	⬇️
server/map_rpc_server.go	`30.58% <0%> (-1.13%)`	⬇️
crypto/verifier.go	`48.14% <0%> (-0.95%)`	⬇️
integration/maptest/map.go	`72.05% <0%> (-0.75%)`	⬇️
examples/ct/ctmapper/mapper/mapper.go	`11.81% <0%> (-0.19%)`	⬇️
client/map_verifier.go	`0% <0%> (ø)`	⬆️
... and 2 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 6282acf...2bf0a96. Read the comment docs.

+ refactor + dummy implementations in other storages + go generate

pav-kv · 2018-03-01T19:40:49Z

storage/mysql/log_storage.go

+	res := make([]*trillian.QueuedLogLeaf, len(leaves))
+	ok := status.New(codes.OK, "OK").Proto()
+
+	// Note: Leaves are sorted by LeafIndex, so no reordering is necessary.


selfnit: ... no deterministic reordering is necessary.

pav-kv · 2018-03-02T10:59:40Z

@AlCutter @daviddrysdale Martin is OOO, could you please take a look?

AlCutter · 2018-03-05T18:24:33Z

storage/mysql/log_storage.go

@@ -259,15 +261,26 @@ func (m *mySQLLogStorage) ReadWriteTransaction(ctx context.Context, tree *trilli
 }

 func (m *mySQLLogStorage) AddSequencedLeaves(ctx context.Context, tree *trillian.Tree, leaves []*trillian.LogLeaf) ([]*trillian.QueuedLogLeaf, error) {


Is this func (on LogStorage impl) needed, or is this a LogTreeTX thing?

It is both, similarly to QueueLeaves. Currently both are transactional, but we discussed earlier that we wanted to allow the LogStorage ones treat entries independently. WDYT?

AlCutter · 2018-03-15T11:39:44Z

storage/mysql/log_storage.go

+		// TODO(pavelkalinnikov): Measure latencies.
+		_, err := t.tx.ExecContext(ctx, insertLeafDataSQL,
+			t.treeID, leaf.LeafIdentityHash, leaf.LeafValue, leaf.ExtraData, 0)
+		// Note: QueueTimestamp == 0 because the entry bypasses the queue.


Will that mess with the integration latency metrics? (The signer sets integration_timestamp and computes the difference for each leaf, which it then add to a histogram - might be useful for seeing how the mirroring etc. is going on fetching leaves vs. integrating them?)

Good catch. Are you suggesting to overload QueueTimestamp so that for PREORDERED_LOG it really means AddTimestamp?
We could add another field like SequencingTimestamp (which would make sense for regular LOG mode as well), or just rename this one to a more generic AddTimestamp. WDYT?

Also, I think we should split the metric in two: one for the LOG's merge delay, another for PREORDERED_LOG's integration delay.

@AlCutter ping

Sorry, I think splitting the metrics is a good idea.
I guess I was suggesting overloading the QueueTimestamp, it's still kinda true in that it's queued to be properly integrated into the tree right?

Done timestamp saving, TODOed the new metric bit.
Yeah, kinda, but not queued in the sense we are used to, rather added/stored. Leaving it as is for now though.

pav-kv

@AlCutter Addressed some of your comments, PTAL.

pav-kv · 2018-03-08T12:00:50Z

storage/mysql/log_storage.go

+			return nil, err
+		}
+
+		// Note: If LeafIdentityHash collides, we still store the indexed entry.


@AlCutter Since we decided to postpone fixing the duplicates issue, I think it's safer to not silently store the erroneous data here, but rather return an error. See the updated code.

pav-kv · 2018-03-16T12:27:54Z

storage/mysql/log_storage.go

+	res := make([]*trillian.QueuedLogLeaf, len(leaves))
+	ok := status.New(codes.OK, "OK").Proto()
+
+	// Note: Leaves are sorted by LeafIndex, so no reordering is necessary.


pav-kv · 2018-03-16T12:49:44Z

storage/mysql/log_storage.go

+		// TODO(pavelkalinnikov): Measure latencies.
+		_, err := t.tx.ExecContext(ctx, insertLeafDataSQL,
+			t.treeID, leaf.LeafIdentityHash, leaf.LeafValue, leaf.ExtraData, 0)
+		// Note: QueueTimestamp == 0 because the entry bypasses the queue.


Good catch. Are you suggesting to overload QueueTimestamp so that for PREORDERED_LOG it really means AddTimestamp?
We could add another field like SequencingTimestamp (which would make sense for regular LOG mode as well), or just rename this one to a more generic AddTimestamp. WDYT?

pav-kv · 2018-03-16T16:41:10Z

storage/mysql/log_storage.go

+			t.treeID, leaf.LeafIdentityHash, leaf.MerkleLeafHash, leaf.LeafIndex, 0)
+		// TODO(pavelkalinnikov): Update IntegrateTimestamp on integrating the leaf.
+
+		if isDuplicateErr(err) {


Started manually testing, found a bug. Suppose we are trying to erroneously insert a new unique identity to an occupied leaf index. The INSERT above stores the identity, but the second INSERT fails because the index is occupied. Still, the tx gets committed, and the side-effect remains. Now this identity can't be inserted anymore.

I think I should add a test for this, and couple of simpler scenarios.

Wow, this actually complicates things more than I thought it would. Essentially, we need to do 2 INSERTs, each can fail independently of the other (it can be conflicting identity and/or conflicting leaf index). Thus, if one fails, we should cancel the effect of the other to leave the db in the old state. We can do it by either making separate transactions, which is slow, or by manually deleting inserted keys which doesn't look nice.

@AlCutter @Martin2112 Any thoughts?

The third option is reading before doing the inserts.

Let's look at this again next week. Might be able to use savepoints for this at least in MySQL.

Yes, this works. Will update the PR shortly (after #1061 is done as this one now depends on it).

pav-kv · 2018-03-21T11:02:09Z

@Martin2112 PTAL.

Martin2112 · 2018-03-21T11:05:27Z

Maybe alcutter@ knows but how will we implement this on CloudSpanner? I don't think it has an equivalent of savepoints.

pav-kv · 2018-03-21T11:19:46Z

I think we can at least do a ReadWrite transaction that first tries to read the identity/entry and does the two inserts only if there is no conflict. Anyway, this would be in a separate PR.

Martin2112 · 2018-03-21T11:25:37Z

Yes I'm not suggesting we write the code now. Just checking we have a plan.

Martin2112 · 2018-03-21T11:34:01Z

storage/mysql/log_storage.go

+
+	// Leaves in this transaction are inserted in two tables. For each leaf, if
+	// one of the two inserts fails, we remove the side effect by rolling back to
+	// a savepoint installed before the first insert.


I thought the savepoint would be updated each pass through the loop so only the ones that fail are rolled back? Is that not how it's meant to work?

OK I now realize we're still in an all or nothing situation. Ignore that comment.

Oh, actually we are not in all-or-nothing. Your initial interpretation was right: only the failed-to-insert entries are rolled back. This is why I update the savepoint on each loop iteration below.

OK. It's hard to read GitHub diffs. I'll have another look.

The reason why I create this savepoint upfront is making sure the "RELEASE SAVEPOINT ..." after the loop has something to delete and doesn't return an error.

Martin2112 · 2018-03-21T11:37:05Z

storage/mysql/log_storage.go

+		glog.Errorf("Error adding savepoint: %s", err)
+		return nil, err
+	}
+	// TODO(pavelkalinnikov): Consider performance implication of executing this


I think the overhead of creating a savepoint is low but we should test this theory.

Yes, will get to it later.

Martin2112 · 2018-03-21T12:12:11Z

Yep. It's probably better to clean it up like this rather than wait for commit or rollback.

…

On 21 March 2018 at 12:11, Pavel Kalinnikov ***@***.***> wrote: ***@***.**** commented on this pull request. ------------------------------ In storage/mysql/log_storage.go <#1036 (comment)>: > @@ -501,6 +513,78 @@ func (t *logTreeTX) QueueLeaves(ctx context.Context, leaves []*trillian.LogLeaf, return existingLeaves, nil } +func (t *logTreeTX) AddSequencedLeaves(ctx context.Context, leaves []*trillian.LogLeaf) ([]*trillian.QueuedLogLeaf, error) { + res := make([]*trillian.QueuedLogLeaf, len(leaves)) + ok := status.New(codes.OK, "OK").Proto() + + // Leaves in this transaction are inserted in two tables. For each leaf, if + // one of the two inserts fails, we remove the side effect by rolling back to + // a savepoint installed before the first insert. The reason why I create this savepoint upfront is making sure the "RELEASE SAVEPOINT ..." after the loop has something to delete and doesn't return an error. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1036 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AMv2T9P8PC0qMIVv09fdk5IjDdBXbysJks5tgkNZgaJpZM4SYluF> .

pav-kv · 2018-03-21T12:15:47Z

I wonder why the 4th builder in Travis consistently complains about SQL syntax, while others don't.

Martin2112 · 2018-03-21T12:16:56Z

That's a different queue implementation for Lets Encrypt with a build flag to enable it. It's probably a real error.

…

On 21 March 2018 at 12:15, Pavel Kalinnikov ***@***.***> wrote: I wonder why the 4th builder in Travis consistently complains about SQL syntax, while others don't. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1036 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AMv2T2UVstc1uuyijrIBvXhx0yD0rI70ks5tgkR4gaJpZM4SYluF> .

Martin2112 · 2018-03-21T12:17:43Z

I've looked at it again and I think it's doing the right thing. Let's investigate the batched_queue error travis error now.

pav-kv · 2018-03-21T12:34:30Z

I think the reason is that insertSequencedLeafSQL variable gets overridden in batched_queue mode by the one in queue_batching.go file. Will see how I can fix this.

pav-kv · 2018-03-21T15:11:35Z

@Martin2112 I fixed the errors, PTAL. For the performance (with or without savepoints), I will probably add a Benchmark test in a follow-up PR, and play with it locally to see the difference.

* master: storage/testdb: drop now-unused entrypoints (google#1067) Drop use of SQLite (google#1064) Implement AddSequencedLeaves in MySQL storage (google#1036)

Implement AddSequencedLeaves in MySQL storage

b30d0d9

pav-kv requested review from AlCutter and Martin2112 March 1, 2018 16:26

googlebot added the cla: yes label Mar 1, 2018

Martin2112 reviewed Mar 1, 2018

View reviewed changes

Introduce LogTreeTX.AddSequencedLeaves method

6c31b2a

+ refactor + dummy implementations in other storages + go generate

pav-kv commented Mar 1, 2018

View reviewed changes

pav-kv requested a review from daviddrysdale March 2, 2018 10:59

AlCutter reviewed Mar 5, 2018

View reviewed changes

AlCutter reviewed Mar 15, 2018

View reviewed changes

pav-kv added 2 commits March 16, 2018 12:23

Merge branch 'master' into mysql_add_sequenced_leaves

ebf6fa8

Address some comments

68a5b5e

pav-kv commented Mar 16, 2018

View reviewed changes

pav-kv added 3 commits March 20, 2018 16:02

Use savepoints to correctly rollback inserting duplicates

7169b38

Add tests

38b3e41

Merge branch 'master' into mysql_add_sequenced_leaves

4beb88f

Martin2112 reviewed Mar 21, 2018

View reviewed changes

Save timestamp; fix batched_queue build; go generate

8807358

Fix SQL error

2bf0a96

Martin2112 approved these changes Mar 21, 2018

View reviewed changes

pav-kv merged commit 812857a into google:master Mar 22, 2018

pav-kv deleted the mysql_add_sequenced_leaves branch March 22, 2018 10:12

		@@ -259,15 +261,26 @@ func (m mySQLLogStorage) ReadWriteTransaction(ctx context.Context, tree trilli
		}

		func (m mySQLLogStorage) AddSequencedLeaves(ctx context.Context, tree trillian.Tree, leaves []trillian.LogLeaf) ([]trillian.QueuedLogLeaf, error) {

Conversation

pav-kv commented Mar 1, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

codecov-io commented Mar 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pav-kv commented Mar 2, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pav-kv left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pav-kv Mar 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pav-kv commented Mar 21, 2018

Uh oh!

Martin2112 commented Mar 21, 2018

Uh oh!

pav-kv commented Mar 21, 2018

Uh oh!

Martin2112 commented Mar 21, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

codecov-io commented Mar 1, 2018 •

edited

Loading

pav-kv Mar 19, 2018 •

edited

Loading

pav-kv commented Mar 21, 2018 •

edited

Loading