sync: use ephemeral multiverse trees for sparse sync

[guggero]

Fixes #621.

This PR first optimizes the FetchLeaves call of the multiverse database by adding database-level indexes and caches.
In the second part we then start using ephemeral multiverse roots to find out what universes need to be synced.

TODO:

• Actually implement a bi-section algorithm instead of just doing a single comparison
• Add integration tests for sparse sync

[guggero]

Here are some of the benchmark runs and improvements from this PR.

Legend

Everything is in nanoseconds.

• ns/op: The duration for a full benchmark loop (sum of all other metrics)
• fetch_10_specific_leaves_ns/op: Time to query 10 specific multiverse leaves
• fetch_50_specific_leaves_ns/op: Time to query 50 specific multiverse leaves
• fetch_all_leaves_ns/op: Time to fetch all (200) leaves in a single query
• fetch_specific_leaves_all_ns/op: Time to fetch all (200) leaves by specifying the IDs (causing individual queries to be made for each ID)
• fetch_issuance_root_ns/op: Fetch issuance multiverse root node (not cached yet)
• fetch_transfer_root_ns/op: Fetch transfer multiverse root node (not cached yet)

SQLite

go test -bench=BenchmarkMultiverse -test.run=BenchmarkMultiverse -tags="dev" -test.v ./tapdb/

No optimizations

1,970,220,957		ns/op
7,393,715		fetch_10_specific_leaves_ns/op
37,135,598		fetch_50_specific_leaves_ns/op
3,671,098		fetch_all_leaves_ns/op
148,661,496		fetch_specific_leaves_all_ns/op
69,814			fetch_issuance_root_ns/op
5,1623			fetch_transfer_root_ns/op

Database indexes

45,869,662	ns/op
1,703,161	fetch_10_specific_leaves_ns/op
7,736,871	fetch_50_specific_leaves_ns/op
3,643,695	fetch_all_leaves_ns/op
32,599,530	fetch_specific_leaves_all_ns/op
78,760		fetch_issuance_root_ns/op
64,341		fetch_transfer_root_ns/op

Database indexes + cache

4,527,723	ns/op
17,707		fetch_10_specific_leaves_ns/op
57,416		fetch_50_specific_leaves_ns/op
3,943,808	fetch_all_leaves_ns/op
326,858		fetch_specific_leaves_all_ns/op
85,376		fetch_issuance_root_ns/op
64,676		fetch_transfer_root_ns/op

Postgres

go test -bench=BenchmarkMultiverse -test.run=BenchmarkMultiverse -tags="dev test_db_postgres" -test.v ./tapdb/                                            

No optimizations

120,578,925	ns/op
4,589,554	fetch_10_specific_leaves_ns/op
21,259,377	fetch_50_specific_leaves_ns/op
9,324,566	fetch_all_leaves_ns/op
84,591,172	fetch_specific_leaves_all_ns/op
416,736		fetch_issuance_root_ns/op
33,1435		fetch_transfer_root_ns/op

Database indexes

54,382,023	ns/op
2,072,208	fetch_10_specific_leaves_ns/op
9,351,045	fetch_50_specific_leaves_ns/op
4,953,068	fetch_all_leaves_ns/op
37,288,501	fetch_specific_leaves_all_ns/op
347,129		fetch_issuance_root_ns/op
313,650		fetch_transfer_root_ns/op

Database indexes + cache

7,445,830	ns/op
199,799		fetch_10_specific_leaves_ns/op
264,958		fetch_50_specific_leaves_ns/op
5,493,731	fetch_all_leaves_ns/op
781,388		fetch_specific_leaves_all_ns/op
335,530		fetch_issuance_root_ns/op
320,593		fetch_transfer_root_ns/op

[jtobin]

Closing as stale.