Async Remove

[sunmisc]

Hello, I want to discuss a fully asynchronous cache with you. I apologize immediately,
I do not have a good knowledge of English (because I am not a native speaker of this language)
I also want to apologize, because my language will not be like an academic one,
but will be comparable to the language of an ordinary schoolboy (which it is)

I want to implement an asynchronous delete method from the map(yes by Completablefuture)
What I propose and what I have implemented,
let's take a ConcurrentHashMap and store the-Node values. Each node will have at least 2 fields-a boolean flag and CompletableFuture next
the flag is required for emergency braking load or unload, and then a stack of action
as soon as I want to delete, I add to the stack CompletableFuture that will decide whether a value is removed from the card or not
(Boolean value helps you determine whether to add/delete the following action or not.
For example, true-deleted,
false - added
you can use this result to determine if I need to add or remove, or if the last action has already done it for me.
here is an example of the pseudocode of the append method:

//remove method

CompletableFuture<Boolean> left next;
synchronized (node) {
   left = node.stack
   if (!removing) {
       removing = true
       next = node.stack = newCompletableFuture
   }
}

if (next == null) {
   return left;
else {
   left thenAccept(rem -> {
     if (removing && !rem) {
         map.remove(node)
         next.complete(true)
     } else
         next.complete(rem)
   });
}

as you can see, this requires minimal blocking costs(you can even CAS probably)

It should look like a pipe with gateways

      +-+    +-+    +-+    +-+    +-+    +-+    +-+    +-+
      |R|--->|A|--->|R|--->|A|--->|R|--->|A|--->|R|--->|A|-->result
      +-+    +-+    +-+    +-+    +-+    +-+    +-+    +-+
       X             X             X             X      V
       |_____________|_____________|_____________|______|

If you need my full implementation let me know
I hope I didn't show that I'm a complete idiot, thank you

[ben-manes]

Hi @JolyJDIA,

Unfortunately, I am not sure what your question is to respond to. Generally map remove operations are very fast and an asynchronous delete is unnecessary. This won't hold if you perform long running map computations as it must synchronize, but in an AsyncCache that computation is performed by the future rather than within the map. I don't think the map writes need to be handled asynchronously due to performance, so you could simplify the code by dropping that. If you are unsure, then a JMH benchmark might be informative.

[ben-manes]

I see, thanks for the clarification. I am sure your sketch is probably quite good, but I may not be familiar enough with your requirements to offer much insight. From your email,

I have a game server when a player arrives, it is loaded from the database, of course, in a separate thread. When a player leaves the server, their data is uploaded to the database, also in a separate thread. And the thing is, it's not safe: the player can log in again when the data has not been saved yet, I will get the stale data (and then delete it from the cache completely). I want to implement an asynchronous delete method from the map(yes by Completablefuture)

It sounds like you want a write-back cache, where the data is strongly consistent and only eligible for eviction once it has been flushed. This way you can avoid ABA style of problems that you describe with a login observing stale state. In that case you could disallow the cached entry from being evicted from memory until the last write has been flushed, and reads will always observe the latest copy.

If you write through the cache, you can tune the expiration / size eviction to not discard those entries. For example if you have a dirty flag then the entry could be evaluated to a size of zero and an infinite expiration time, making it be pinned. When the last write finishes then it could unpin the entry as a callback write to the cache.

Another approach is to delay login until the server has caught up. If you view the queue of writes as a transaction log, you could wait until all tasks have been processed up until the login timestamp. This would add a small delay to login, but ensure consistency by the time you read the database record. Assuming that this write queue flushes quickly, it might be fast.

If you have a distributed set of servers, then your synchronization point should be coordinated externally (e.g. through Redis).

Hope that helps.

[sunmisc]

Yes, thank you for clarifying, you were right that it could be made easier
My idea of a cache would rather be good in unrealistic events, where CompletableFuture runs for a very long time and the remove/put queue has accumulated, I can only throw all my efforts at the last put and load once, but as practice has shown, the DATABASE sends a response MUCH faster, and roughly speaking, all this optimization has the opposite effect

    class Node { volatile boolean removing; CompletableFuture value; }

    public CompletableFuture<V> put(K key, CompletableFuture<V> v) {
        return map.compute(key, (k, vNode) -> {
            if (vNode != null) {
                vNode.removing= false;
            } else {
                vNode = new Node<>(v);
            }
            return vNode;
        }).value;
    }
    public CompletableFuture<Boolean> remove(K key,
                                             BiFunction<K, V, CompletableFuture<Boolean>> remappingFunction) {
        Node<V> f = map.get(key);
        if (f == null) {
            return CompletableFuture.completedFuture(false);
        }
        f.removing= true;
        return f.value.thenComposeAsync(v -> {
            if (f.removing) {
                return remappingFunction.apply(key, v).thenApply(x -> map.computeIfPresent(key, (k, vNode) -> {
                    if (x && vNode.removing) {
                         return null;//delete
                    }
                    return vNode;
                }) == null);
            } else {
                return CompletableFuture.completedFuture(false);
            }
        });
    }

it will be 99.999% more efficient

[sunmisc]

I apologize for my mutability, but unfortunately this doesn't work, according to the specification of my cache, the remove method should return the future removing of the node by key. The first implementation turned out to be not only working, but also more productive there are a couple of reasons

1. when calling the delete method, I have to initialize either the remove or return the removing process (if there is one)

2. when calling the put, I should cancel the removing(if possible)

3. in the chronology where long computation and action similar to put/remove/put/remove (remove - the last action at the moment) my last cache with a large share of probability will only remove once(or the last and the rest just accept his decision) the same situation and with the addition of
   if the line of action the last step is to add (put/remove/put/remove/put for example) my cache will probably complete the put method once

P. S by put and remove I mean not just adding to the map but binding actions the CompletableFuture interface

CompletableFuture<Boolean> remove(K key, BiFunction<K, V, CompletableFuture<Boolean>> remappingFunction);

where return true - successfully removed
return false - someone managed to add it to the cache again

in the Completablefuture<Boolean> remappingFunction I can decide whether I need to delete the moment data at all(there I can also asynchronously bind the event)

[ben-manes]

If your first implementation works, then that's great. If it solves your problems then go with that.