Multiplatform lock-free LRU memory cache

apollographql / apollo-kotlin

:rocket: A strongly-typed, caching GraphQL client for the JVM, Android, and Kotlin multiplatform.

https://www.apollographql.com/docs/kotlin

MIT License

3.75k stars 651 forks source link

Multiplatform lock-free LRU memory cache #2844

Closed martinbonnin closed 3 years ago

ychescale9 commented 3 years ago

This sounds exciting! Is it going to be a KMP replacement for com.nytimes.android.external.cache.Cache?

If this is implemented as a generic in-memory KMP caching library, it'll help Store's KMP effort a lot.

I have a very basic implementation based on stately-isolate which supports what Store needs (time and size based evictions), but I know performance is not going to be great right now 😃 .

So I'm really curious to know the scope of your implementation and learn about how lock-free synchronization looks like in K/N.

martinbonnin commented 3 years ago

This sounds exciting! Is it going to be a KMP replacement for com.nytimes.android.external.cache.Cache?

Yes, that the ticket for exactly that ! Sorry I did not include more in the description. I have a very limited idea of what actually needs to be done there, I added the ticket mainly to keep track of what still needs to be need done in dev-3.x and make sure we do not duplicate work.

I have a very basic implementation based on stately-isolate which supports what Store needs

Nice :). Is that available somewhere?

learn about how lock-free synchronization looks like in K/N.

Yup, the threading part is still an open question. Discussing with @sav007 we were wondering if threads would actually be required for an in-memory cache. If it's fast enough, we might end up designing the runtime so that accesses are single-threaded. Although now that I'm thinking more about it, that will certainly introduce thread switching latency.

ychescale9 commented 3 years ago

I'll clean it up a bit and make it public.

It's ported from my original kotlin/JVM cache contribution for store but was reverted before 1.0 as KMP wasn't a priority.

ychescale9 commented 3 years ago

https://github.com/ReactiveCircus/cache4k

A few notes:

currently supports jvm, ios, macos, js, but I haven't tested in a real app other than running the tests on those platforms
implementation is powered by Stately's IsolateState and AtomicReference
this is probably not 100% thread-safe as there's no synchronization of those 3 collections (will need to learn how to do it without using a Lock in all operations)
haven't done any benchmarking
from memory Apollo needs a weigher API? this is not yet implemented

martinbonnin commented 3 years ago

https://github.com/ReactiveCircus/cache4k

Awesome, will look into it!

this is probably not 100% thread-safe as there's no synchronization of those 3 collections (will need to learn how to do it without using a Lock in all operations)

Something we discussed with @sav007 was optimizing for the JVM case first. Multi-threading might change on K/N and there are less synchronization primitives so it would certainly be ok if K/N is a bit less performant for the time being. That's not an option on the JVM

from memory Apollo needs a weigher API? this is not yet implemented

We do use the weigher API in 2.x. I think it's useful to keep the MemoryCache constrained in size and avoid OOMs.

ychescale9 commented 3 years ago

Thanks! Let me know if you have any feedback. If it's easier, I'm on ASG and kotlinlang slack (Yang) so feel free to ping me there:)

martinbonnin commented 3 years ago

3.0.0-alpha01 has its own LruCache. It's not thread safe but that shouldn't matter because DefaultApolloStore locks the cache accesses (the same was true in Apollo Android 2). Closing for now. Will reopen if we really really need to shave some nanoseconds.