Signature duplicate check with checkpointing is slow

[aeyakovenko]

Problem

Even with bloom filters, #2289, the signature filtering needs to traverse a bunch of checkpoints per signature to check if its present or not. It looks like a single bloom filter check is going to be on the order of 1us, so 32 checks is going to be to slow for our target tps (although they can be run in parallel).

Proposed Solution

type ForkId = u64;
//probably a small amount of entries in this map, so a vec might be better
type ForkStatusMap = HashMap<ForkId, Result<()>>;
type SignatureMap = HashMap<Signature, ForkStatusMap>;
//the LastId is also from a specific fork.  But any descendants could have signatures for it.
type StatusCache = HashMap<LastId, (ForkId, SignatureMap)>;

• Use a single LastId delimited map that keeps track of which fork the signature had been executed in. This data structure doesn't checkpoint, or merge, and is a single data structure for all the forks in the system.

• When checking for dup signatures in the current fork, find the results in the above data structure for all the forks a signature has been processed. Check if the forks are an ancestor of the current fork.

• Garbage collect as LastIds expire, since they expire globally for all the forks.

• At a specific tick count, multiple LastIds would expire, because the values are different in each fork.

• Some interesting optimizations,

//bitfield if the signature is present
//offset in the field is number of forks above the LastIds ForkId
type ForkStatusMap = u32;

and using 80 bits of the Signature instead of the full 256.
tag: @garious @rob-solana @sakridge

[rob-solana]

so lastids will expire with forks instead of with ticks?

[aeyakovenko]

They still expire with ticks. Ticks overlap fork lifetimes because the counter moves forward in every fork.

So at a specific tick count, multiple LastIds would expire, because the values are different in each fork.

[aeyakovenko]

https://github.com/solana-labs/solana/projects/11

[rob-solana]

I'm having trouble with how keeping track of which fork a sig was observed in helps. Is that a memory optimization?

Once a status_cache has been parented, it becomes read-only and can be shared across all forks that include the parent bank.

Garbage collection is part of squash() currently.

[aeyakovenko]

@rob-solana, it helps with lookups. Since there is just hashmap lookup, vs a bunch

[rob-solana]

are SignatureMaps shared across Forks? Arc<RwLock> ?

if so, how do they come to be shared?

if not, how can a ForkStatusMap have more than one entry?

[aeyakovenko]

@rob-solana it is just a global data structure for all the banks.