Improve startup time by caching lists

[ThinkChaos]

As mentioned in this thread, I'm creating a discussion about caching for individual lists (this will also apply to host files since my refactor is unifying how we load both of those).

Here's the relevant parts of that thread:

@ThinkChaos:

Didn't check how it's implemented in your branch, but based on the screen shot, it looks like list cache is done at the group level.
I think we should split everything up by URL instead so different groups can reuse the same cache. And if you change the lists for a given group, most of it can be reused easily.
This would probably cause conflicts with the changes I'm working on as part of supporting multiple hosts files, so it would probably be best for you to continue with per group caches, but just keep in mind that I'd like to change it after.
Of course my assumption could be wrong, or if you think per group is better, please tell me :)

On the subject of caching, I'm also working on speeding up lists downloads by deduplicating requests to the same URL. I was planning on adding a local cache, but if we integrate ruedis, that's probably not needed, so I'll just start with the dedup'ing and see after all of that is merged with your ruedis changes.

@0xERR0R:

It looks like we'll still support both installation types:

• with redis: only regex entries are in the internal in-memory cache. Lists and responses in redis
• without redis: all caches are in-memory

Application only uses the interfaces, so it should not matter whether Redis or In-memory

Regarding the cache structure:
Currently cache is devided into groups (like partitions). Each partition (group) is independent and contains data from multiple urls. This was done for the following reasons:

• Entries in each group are deduplicated (typically, a group contains links for lists with the same content type)
• As a user, I want to know how many requests were blocked, grouped by group
• Lookup speed is typically dependent on a group size: as a user I can define small group for all user and a big group for some user and I'll don't have performance impact (for example: small ads group for all and big p0rn blacklist for children).
• List refresh performs group-wise: A group will be updated only if all links are downloaded and processed without error. That means, if a download link is temporary not reachable, only one group will not be refreshed and contains "old" data. That means also, we do temporarily keep data for a group twice in memory.

This approach has some disadvantages: we have some data duplication if multiple group contain the same entries and we can't determine from which list was a particular entry.

We can think about the change of the structure and collecting caches per URL, but we should check the reasons above and consider them.

@ThinkChaos:

Yeah I agree we want the fastest cache to stay per group since that's what blocky actually uses.
I'm thinking of another cache layer for URLs. Without Redis it would be on disk.
With Redis configured, I think Redis would be more appropriate since it's shared across blocky instances. And if we cache URLs in Redis, then maybe we can cache groups directly in memory so that code matches more between Redis and no Redis.
What do you think of that?

[kwitsch]

I think we should split everything up by URL instead so different groups can reuse the same cache.

At least for my current Redis implementation this would add more complexity without a real benefit. The blocklists are stored as string lists in Redis and can therefore be queried with SISMEMBER which results in a boolean result. The cached response on the client side is really small and key access can be optimized through the server since there is a repetitive access to a few keys.

If we switch to url level we generate a lot more keys with lesser access and these have to contain information where they are included. I think this would decrease performance. 🤔

[kwitsch]

I'm currently investigating going in the opposite direction.

Client group cache:

• cache blocklists (like the current implementation)
• squash blocklists per client group (Redis command: SUNIONSTORE)
• ability to check if a url is blocked per group with one call (SISMEMBER client group cache key url1-n)

[kwitsch]

My current main priority is speed. This will most likely result in data duplication in Redis to optimize queries.
I'll include a bunch of big lists in my next test to see how big the impact is. 👍

[ThinkChaos]

How do you intend to handle inline lists since they don't have a source as identification?
Squash them per blocking group and use the name as key?

Good question. Probably just use a hash as key.
I've already refactored the code to have a BytesSource type that is either Text/File/HTTP. So having a cache key method there will be easy enough.

[kwitsch]

Good question. Probably just use a hash as key.
I've already refactored the code to have a BytesSource type that is either Text/File/HTTP. So having a cache key method there will be easy enough.

At least for Redis we need an identification to invalidate old keys. Since the hash would change at each modification we would need to track these references independently. Prefixing them with the group name or creating a linking entry(group name to currently valid keys) would be an option.

[ThinkChaos]

Yeah I haven't thought that far ahead and I'm not familiar with Redis enough. Was hoping we could set a TTL on the whole group and have blocky reset it on each refresh that confirms the list didn't change.

[kwitsch]

This would be possible but I try to avoid TTLs for the lists since they would be gone if a instance is offline for some time.
Even if the instance stays online but the list download fails the TTL need to be reset.