belliottsmith commented on code in PR #113: URL: https://github.com/apache/cassandra-accord/pull/113#discussion_r1750209782
########## accord-core/src/main/java/accord/impl/DefaultRemoteListeners.java: ########## @@ -0,0 +1,525 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package accord.impl; + +import java.util.Arrays; +import java.util.concurrent.ConcurrentHashMap; + +import com.google.common.annotations.VisibleForTesting; + +import accord.api.RemoteListeners; +import accord.local.Command; +import accord.local.Node; +import accord.local.SafeCommand; +import accord.local.SafeCommandStore; +import accord.local.SaveStatus; +import accord.local.Status.Durability; +import accord.messages.Await.AsyncAwaitComplete; +import accord.primitives.Route; +import accord.primitives.TxnId; +import accord.utils.Invariants; +import accord.utils.SortedArrays; +import accord.utils.btree.BTree; + +// TODO (required): evict to disk +public class DefaultRemoteListeners implements RemoteListeners +{ + public interface NotifySink + { + void notify(TxnId txnId, SaveStatus saveStatus, Route<?> participants, long[] listeners, int listenerCount); + } + + public static class DefaultNotifySink implements NotifySink + { + final Node node; + public DefaultNotifySink(Node node) + { + this.node = node; + } + + @Override + public void notify(TxnId txnId, SaveStatus saveStatus, Route<?> route, long[] listeners, int listenerCount) + { + for (int i = 0 ; i < listenerCount ; ++i) + { + long listener = listeners[i]; + // we could in theory reply to the same node multiple times here, but should not be common enough to optimise + Node.Id replyTo = new Node.Id(listenerNodeId(listener)); + int callbackId = listenerCallbackId(listener); + node.send(replyTo, new AsyncAwaitComplete(txnId, route, saveStatus, callbackId)); + } + } + } + + static class StatusListeners + { + final int await; + + // waitingOn is sorted, but to save time on deletions we only set the top bit to mark deleted + // until we have halved the number of entries, at which point we remove the tombstones + // waitingOnSize tracks the top entry, waitingOnCount the number of live entries + int[] waitingOn; + long[] listeners; + int waitingOnSize, waitingOnCount, listenerCount; + + StatusListeners(SaveStatus awaitSaveStatus, Durability awaitDurability, int[] waitingOn, int waitingOnCount, int listenerNodeId, int listenerCallbackId) + { + this.await = encodeAwait(awaitSaveStatus, awaitDurability); + this.waitingOn = waitingOn; + this.waitingOnCount = this.waitingOnSize = waitingOnCount; + this.listeners = new long[] { encodeListener(listenerNodeId, listenerCallbackId) }; + this.listenerCount = 1; + } + + StatusListeners merge(StatusListeners that) + { + mergeInts(this.waitingOn, this.waitingOnSize, that.waitingOn, that.waitingOnSize, StatusListeners::updateWaitingOn); + mergeLongs(this.listeners, this.listenerCount, that.listeners, that.listenerCount, StatusListeners::updateListeners); + return this; + } + + interface IntMergeConsumer + { + void accept(StatusListeners listeners, int[] out, int count); + } + + interface LongMergeConsumer + { + void accept(StatusListeners listeners, long[] out, int count); + } + + private void updateWaitingOn(int[] newWaitingOn, int newWaitingOnCount) + { + this.waitingOn = newWaitingOn; + this.waitingOnCount = this.waitingOnSize = newWaitingOnCount; + Invariants.checkArgument(SortedArrays.isSorted(newWaitingOn, 0, newWaitingOnCount)); + } + + private void updateListeners(long[] newListeners, int newListenerCount) + { + this.listeners = newListeners; + this.listenerCount = newListenerCount; + Invariants.checkArgument(SortedArrays.isSorted(newListeners, 0, newListenerCount)); + } + + void mergeInts(int[] vis, int viSize, int[] vjs, int vjSize, IntMergeConsumer consumer) + { + int count = 0; + int i = 0, j = 0; + while (i < viSize && j < vjSize) + { + int vi = vis[i], vj = vjs[j]; + if (Math.min(vi, vj) < 0) + { + i += vi >>> 31; + j += vj >>> 31; + continue; + } + + int c = vis[i] - vjs[j]; + if (c <= 0) + { + vis[count++] = vis[i++]; + j += c == 0 ? 1 : 0; + } + else if (count < i) + { + vis[count++] = vjs[j++]; + } + else + { + int[] newvis = new int[count + (viSize - i) + (vjSize - j)]; + System.arraycopy(vis, 0, newvis, 0, count); + int remaining = (viSize - i); + System.arraycopy(vis, i, newvis, newvis.length - remaining, remaining); + vis = newvis; + i = vis.length - remaining; + viSize = newvis.length; + } + } + + while (i < viSize) + { + if (vis[i] >= 0) + vis[count++] = vis[i]; + i++; + } + + if (vis.length < count + vjSize - j) + vis = Arrays.copyOf(vis, Math.max(viSize + viSize/2, count + vjSize - j)); + + while (j < vjSize) + { + if (vjs[j] >= 0) + vis[count++] = vjs[j]; + ++j; + } + + consumer.accept(this, vis, count); + } + + void mergeLongs(long[] vis, int viSize, long[] vjs, int vjSize, LongMergeConsumer consumer) + { + int count = 0; + int i = 0, j = 0; + while (i < viSize && j < vjSize) + { + long vi = vis[i], vj = vjs[j]; + if (Math.min(vi, vj) < 0) + { + i += vi >>> 31; + j += vj >>> 31; + continue; + } + + long c = vis[i] - vjs[j]; + if (c <= 0) + { + vis[count++] = vis[i++]; + j += c == 0 ? 1 : 0; + } + else if (count < i) + { + vis[count++] = vjs[j++]; + } + else + { + long[] newvis = new long[count + (viSize - i) + (vjSize - j)]; + System.arraycopy(vis, 0, newvis, 0, count); + int remaining = (viSize - i); + System.arraycopy(vis, i, newvis, newvis.length - remaining, remaining); + vis = newvis; + i = vis.length - remaining; + viSize = newvis.length; + } + } + + while (i < viSize) + { + if (vis[i] >= 0) + vis[count++] = vis[i]; + i++; + } + + if (vis.length < count + vjSize - j) + vis = Arrays.copyOf(vis, Math.max(viSize + viSize/2, count + vjSize - j)); + + while (j < vjSize) + { + if (vjs[j] >= 0) + vis[count++] = vjs[j]; + ++j; + } + + consumer.accept(this, vis, count); + } + + void removeWaitingOn(int storeId) + { + int index = find(waitingOn, 0, waitingOnSize, storeId); + if (index >= 0 && waitingOn[index] >= 0) + { + waitingOn[index] |= Integer.MIN_VALUE; + --waitingOnCount; + if (waitingOnCount <= waitingOnSize / 2) + { + int count = 0; + for (int i = 0 ; i < waitingOnSize ; ++i) + { + if (waitingOn[i] >= 0) + waitingOn[count++] = waitingOn[i]; + } + Invariants.checkState(count == waitingOnCount); + waitingOnSize = waitingOnCount; + } + } + } + + // copied and simplified from SortedArrays + private static int find(int[] waitingOn, int from, int to, int find) + { + while (from < to) + { + int i = (from + to) >>> 1; + int c = Integer.compare(find, waitingOn[i] & Integer.MAX_VALUE); + if (c < 0) to = i; + else if (c > 0) from = i + 1; + else return i; + } + return -1 - from; + } + + @Override + public String toString() + { + return awaitSaveStatus(await) + "+" + awaitDurability(await); + } + } + + static class Listeners + { + // btree + StatusListeners[] statusListeners; + int start, end; + + Listeners(StatusListeners statusListeners) + { + this.statusListeners = new StatusListeners[] { statusListeners }; + this.end = 1; + } + + Listeners merge(Listeners that) + { + int count = 0; + int i = this.start, j = that.start; + while (i < this.end && j < that.end) + { + int c = Integer.compare(this.statusListeners[i].await, that.statusListeners[j].await); + if (c == 0) + { + this.statusListeners[count++] = this.statusListeners[i++].merge(that.statusListeners[j++]); + } + else if (c < 0) + { + this.statusListeners[count++] = this.statusListeners[i++]; + } + else if (count < i) + { + this.statusListeners[count++] = that.statusListeners[j++]; + } + else + { + StatusListeners[] newStatusListeners = new StatusListeners[count + (this.end - i) + (that.end - j)]; + System.arraycopy(statusListeners, 0, newStatusListeners, 0, count); + int remaining = (this.end - i); + System.arraycopy(statusListeners, i, newStatusListeners, newStatusListeners.length - remaining, remaining); + statusListeners = newStatusListeners; + i = statusListeners.length - remaining; + end = statusListeners.length; + } + } + + while (i < this.end) + statusListeners[count++] = this.statusListeners[i++]; + + if (statusListeners.length < count + that.end - j) + statusListeners = Arrays.copyOf(statusListeners, Math.max(statusListeners.length + statusListeners.length/2, count + that.end - j)); + + while (j < that.end) + statusListeners[count++] = that.statusListeners[j++]; + + if (count < end) + Arrays.fill(statusListeners, count, end, null); + + start = 0; + end = count; + return this; + } + } + + class Register implements Registration + { + final TxnId txnId; + final SaveStatus awaitSaveStatus; + final Durability awaitDurability; + final Node.Id listeningNodeId; + final int callbackId; + + int[] waitingOn = new int[4]; + int count = 0; + + Register(TxnId txnId, SaveStatus awaitSaveStatus, Durability awaitDurability, Node.Id listeningNodeId, int callbackId) + { + this.txnId = txnId; + this.awaitSaveStatus = awaitSaveStatus; + this.awaitDurability = awaitDurability; + this.listeningNodeId = listeningNodeId; + this.callbackId = callbackId; + } + + @Override + public synchronized void add(SafeCommandStore safeStore, SafeCommand safeCommand) + { + Invariants.checkState(safeCommand.current().saveStatus().compareTo(awaitSaveStatus) < 0); + if (count == waitingOn.length) + { + trim(); + if (count >= waitingOn.length/2) + { + int[] newWaitingOn = new int[count * 2]; + System.arraycopy(waitingOn, 0, newWaitingOn, 0, count); + waitingOn = newWaitingOn; + } + } + waitingOn[count++] = safeStore.commandStore().id(); + } + + private void trim() + { + Arrays.sort(waitingOn, 0, count); + int removedCount = 0; + for (int i = 1 ; i < count ; ++i) + { + if (waitingOn[i - 1] == waitingOn[i]) ++removedCount; + else if (removedCount > 0) waitingOn[i - removedCount] = waitingOn[i]; + } + count -= removedCount; + } + + @Override + public synchronized void cancel(SafeCommandStore safeStore) + { + int storeId = safeStore.commandStore().id(); + int i = 0; + while (i < count) + { + if (waitingOn[i] != storeId) ++i; + else waitingOn[i] = waitingOn[--count]; + } + } + + @Override + public void cancel() + { + } + + @Override + public int done() + { + if (count == 0) + return 0; + + trim(); + if (waitingOn.length > 4 && count < waitingOn.length / 2) + waitingOn = Arrays.copyOf(waitingOn, count); + + StatusListeners listener = new StatusListeners(awaitSaveStatus, awaitDurability, waitingOn, count, listeningNodeId.id, callbackId); + listeners.merge(txnId, new Listeners(listener), Listeners::merge); + return count; + } + } + + final NotifySink notifySink; + final ConcurrentHashMap<TxnId, Listeners> listeners = new ConcurrentHashMap<>(); Review Comment: the call to `merge` deletes when appropriate (by returning `null`) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
