sql: add Bloom filters for ATXs and malicious identities

[ivan4th]

Motivation

atxs.Has and identities.IsMalicious require database access and a lot of such queries are made when fetching ATXs, resulting in false in majority of cases. Bloom filter can be used to avoid database access in most cases.

Description

This adds Bloom filters that are initialized on startup and are updated as new ATXs and malicious identities are being added. ~114 MiB Bloom filter has 1% false positive rate for 100M ATXs, and 234 KiB Bloom filter has 0.01% false positive rate for 10K malicious identities. False positives don't mean that the check will yield incorrect result, they just incur a database query which is always done when the Bloom filter gives positive result.

About 2 min on an old Xeon (E5-2696) machine is needed to load the filters during startup. This appears to be a worthy tradeoff; the filter false positive rate and expected size values aren't expected to change often, thus I didn't add config values for them just yet. UPD: will update the PR so that bloom filters are loaded in background and only used when they're ready, falling back to the old "always query DB" behavior while the filters are not ready yet.

The rqlite/sql SQLite parser/stringifier dependency introduced in the code would of course not be justified if it was only intended for the Bloom filters, as the necessary SQL could be hardcoded instead, but there are several places where SQL is processed or dynamically generated in go-spacemesh and the intent is to use the new sql/expr package in several other places to, extending it as needed:

• normalizing SQL schema for drift detection
• removing comments from migration scripts (not done correctly right now)
• replacing sql/builder package
• syncv2 database-backed sync data structure

In case of things like Bloom filters writing out all the queries explicitly may sound as a good "less magic" approach, and that may be subject for discussion, but repeated SQL queries for "mostly same" thing do cause issues, e.g. here we have a bug in equivocation set handling for malicious identities which resulted from not all related SQL queries being updated correctly: #6331 (to be fixed soon in a separate PR, w/o dynamic SQL)

The intent for sql/expr package is to hide most of the rqlite/sql functionality we don't need, and provide a simple and minimalistic interface for dynamic SQL needs of the codebase instead. The idea is not to use rqlite/sql directly in other go-spacemesh packages. sql/expr has been extracted from the syncv2 code and thus has slightly more functionality than Bloom filters use.

Test Plan

Verify on a mainnet node

TODO

• [ ] Test changes and document test plan
• [ ] Update changelog as needed

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 88.81119% with 32 lines in your changes missing coverage. Please review.

Project coverage is 81.8%. Comparing base (5091028) to head (18f5acb). Report is 12 commits behind head on develop.

Files with missing lines	Patch %	Lines
sql/bloom.go	91.3%	6 Missing and 4 partials :warning:
sql/expr/expr.go	90.0%	6 Missing and 2 partials :warning:
sql/identities/identities.go	74.1%	4 Missing and 4 partials :warning:
sql/atxs/atxs.go	75.0%	2 Missing and 2 partials :warning:
sql/database.go	95.1%	1 Missing and 1 partial :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## develop #6332 +/- ## ======================================== Coverage 81.8% 81.8% ======================================== Files 312 314 +2 Lines 34606 34890 +284 ======================================== + Hits 28318 28563 +245 - Misses 4452 4484 +32 - Partials 1836 1843 +7 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[dshulyak]

i also was looking into leveraging bloom filters after realizing that most of the identities are not malicious therefore this index scan always has to complete fully but return nothing https://github.com/spacemeshos/go-spacemesh/pull/6326. apparently sqlite itself has support for bloom filters, but i am not sure when query optimizer picks them

one thing to note is that this query was added wrongly, the way it is written will make situation with atx handling worse if it wasn't yet released.

there should be more optimal approach, that doesn't pay the cost all the time but only when it is actually needed. for example when equivocation happens update all atxs in equivocation set.

    SELECT 1 FROM identities
    WHERE (marriage_atx = (
        SELECT marriage_atx FROM identities WHERE pubkey = ?1 AND marriage_atx IS NOT NULL) AND proof IS NOT NULL
    )
    OR (pubkey = ?1 AND marriage_atx IS NULL AND proof IS NOT NULL);

[dshulyak]

one other thing is that i will likely get rid of atx warmup and long tortoise loading, adding more time to startup seems like poor choice. maybe consider loading this bloom filter in the background and use it only once loaded (if sqlite bloom filter is hard to use)

[ivan4th]

maybe consider loading this bloom filter in the background and use it only once loaded

That's a good idea, thanks, will do so

[ivan4th]

Updating all the identities in the equivocation set when one of them becomes malicious also makes sense to me, I had similar thoughts too, but this should probably be done in a separate PR

[ivan4th]

Switched to background loading of the Bloom filters

[dshulyak]

btw are ATX optimization speed up things noticeably for you? i mean, not just measuing how long atxs.Has was before/now, but in terms of syncv2 rate or resource usage. the reason why am asking is that it doesn't appear to be largest hotspot in atxs processing, this is distribution of vfs read syscalls by sqlite on v1.6.8, they don't hit disc because of large memory on my computer but this is the largest slow down after verification

it is far from optimal, i would rework that to use smarter access, just changing how/when sqlite is used:

• cache poet proofs, they are mostly reused, but have to be loaded all the time
• load only necessary data for validation, not whole atx blobs, and preferably in one scan
• run fetchReferences only for data that can't be loaded, e.g don't do work of checking deps twice
• sql.Commit is likely will be optimized with batching, it won't have to write same pages to WAL multiple times
• atxs.Add will be optimized by reducing number of indexes on atxs table
• sql.WithTx has a lot of reads in it, this makes atx processing significantly slower as this is all them synhronized
• IsMalicious has to scan whole table now, it is good luck that it is small, but it will be more optimal if read has to check only small index . if after such change checking index is still too slow then bloom filter is the right solution
• atxs.Has can use epoch || atxid (added epoch prefix) to query for existence as it will improve scan

that list just addresses "mistakes" and doesn't introduce any additional complexity, and once addressed maybe adding more complexity will not be necessary. but if adding bloom filter help significantly in short term i won't object adding them

[dshulyak]

i prototyped several optimizations from the list above, the result is that unless atx verifier hits the disk the latency is dominated by the post verification (even if it is just a few labels for vrf nonce).

disk reads for my branch vs v1.6.8

latency distribution, note that all reads are from memory, otherwise the difference would be more substantial

the rate might be somewhat better but still dominated by verification, sorry timestamp are not adjusted

so i think the goal is just not too reduce disk/vfs usage as much as possible, but otherwise small optimizations won't matter

[poszu]

@dshulyak

i prototyped several optimizations from the list above, the result is that unless atx verifier hits the disk the latency is dominated by the post verification (even if it is just a few labels for vrf nonce). so i think the goal is just not too reduce disk/vfs usage as much as possible, but otherwise small optimizations won't matter

You have a very fast disk, don't you? The results could be very different on a slow one, where the disk would quickly become the limiting factor. Wdyt?

[dshulyak]

one other thing if you are focusing on this part that runs the atxs.Has check, it makes more sense to refactor it such that caller always checks locally if atx exists and don't redo the work in the fetcher.

more concretely, atx handler always needs to load previous atx for validation, if it tries to load it and sql.ErrNotFound is raised, you call that handler with previous atx id, otherwise you don't. in my opinion it is better to fix "logic" rather than adding more workarounds

[ivan4th]

Converted to draft for now b/c more testing may be needed to justify the use of the bloom filters, with more pressing issues being there right now.