blob: f595e6ac53b63e1760977443ec10945705ca5eb1 [file] [log] [blame]
Jonathan Hartdb3af892015-01-26 13:19:07 -08001/*
2 * Copyright 2015 Open Networking Laboratory
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
Madan Jampanif4c88502016-01-21 12:35:36 -080016package org.onosproject.store.primitives.impl;
Jonathan Hartdb3af892015-01-26 13:19:07 -080017
Madan Jampanif4c88502016-01-21 12:35:36 -080018import static com.google.common.base.Preconditions.checkNotNull;
19import static com.google.common.base.Preconditions.checkState;
20import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
21import static org.onlab.util.BoundedThreadPool.newFixedThreadPool;
22import static org.onlab.util.Tools.groupedThreads;
23import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.PUT;
24import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.REMOVE;
Jonathan Hartdb3af892015-01-26 13:19:07 -080025
Jonathan Hartdb3af892015-01-26 13:19:07 -080026import java.util.Collection;
Madan Jampani3d76c942015-06-29 23:37:10 -070027import java.util.Collections;
Jonathan Hartdb3af892015-01-26 13:19:07 -080028import java.util.List;
29import java.util.Map;
Madan Jampanid13f3b82015-07-01 17:37:50 -070030import java.util.Objects;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070031import java.util.Optional;
Jonathan Hartdb3af892015-01-26 13:19:07 -080032import java.util.Set;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080033import java.util.Timer;
Jonathan Hartdb3af892015-01-26 13:19:07 -080034import java.util.concurrent.ExecutorService;
35import java.util.concurrent.Executors;
36import java.util.concurrent.ScheduledExecutorService;
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -080037import java.util.concurrent.TimeUnit;
Madan Jampani3d76c942015-06-29 23:37:10 -070038import java.util.concurrent.atomic.AtomicBoolean;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070039import java.util.concurrent.atomic.AtomicReference;
Brian O'Connor5eb77c82015-03-02 18:09:39 -080040import java.util.function.BiFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -080041import java.util.stream.Collectors;
42
Madan Jampanif4c88502016-01-21 12:35:36 -080043import org.apache.commons.lang3.tuple.Pair;
44import org.onlab.util.AbstractAccumulator;
45import org.onlab.util.KryoNamespace;
46import org.onlab.util.SlidingWindowCounter;
47import org.onosproject.cluster.ClusterService;
48import org.onosproject.cluster.ControllerNode;
49import org.onosproject.cluster.NodeId;
50import org.onosproject.persistence.PersistenceService;
51import org.onosproject.store.LogicalTimestamp;
52import org.onosproject.store.Timestamp;
53import org.onosproject.store.cluster.messaging.ClusterCommunicationService;
54import org.onosproject.store.cluster.messaging.MessageSubject;
55import org.onosproject.store.serializers.KryoNamespaces;
56import org.onosproject.store.serializers.KryoSerializer;
57import org.onosproject.store.service.EventuallyConsistentMap;
58import org.onosproject.store.service.EventuallyConsistentMapEvent;
59import org.onosproject.store.service.EventuallyConsistentMapListener;
60import org.onosproject.store.service.Serializer;
61import org.onosproject.store.service.WallClockTimestamp;
62import org.slf4j.Logger;
63import org.slf4j.LoggerFactory;
64
65import com.google.common.collect.Collections2;
66import com.google.common.collect.ImmutableList;
67import com.google.common.collect.ImmutableMap;
68import com.google.common.collect.Lists;
69import com.google.common.collect.Maps;
70import com.google.common.collect.Sets;
Jonathan Hartdb3af892015-01-26 13:19:07 -080071
72/**
73 * Distributed Map implementation which uses optimistic replication and gossip
74 * based techniques to provide an eventually consistent data store.
75 */
76public class EventuallyConsistentMapImpl<K, V>
77 implements EventuallyConsistentMap<K, V> {
78
79 private static final Logger log = LoggerFactory.getLogger(EventuallyConsistentMapImpl.class);
80
Madan Jampani3d76c942015-06-29 23:37:10 -070081 private final Map<K, MapValue<V>> items;
Jonathan Hartdb3af892015-01-26 13:19:07 -080082
Jonathan Hartdb3af892015-01-26 13:19:07 -080083 private final ClusterService clusterService;
84 private final ClusterCommunicationService clusterCommunicator;
85 private final KryoSerializer serializer;
Madan Jampani3d76c942015-06-29 23:37:10 -070086 private final NodeId localNodeId;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -070087 private final PersistenceService persistenceService;
Jonathan Hartdb3af892015-01-26 13:19:07 -080088
Madan Jampanibcf1a482015-06-24 19:05:56 -070089 private final BiFunction<K, V, Timestamp> timestampProvider;
Jonathan Hartdb3af892015-01-26 13:19:07 -080090
91 private final MessageSubject updateMessageSubject;
Jonathan Hartaaa56572015-01-28 21:56:35 -080092 private final MessageSubject antiEntropyAdvertisementSubject;
Jonathan Hartdb3af892015-01-26 13:19:07 -080093
Jonathan Hartaaa56572015-01-28 21:56:35 -080094 private final Set<EventuallyConsistentMapListener<K, V>> listeners
Madan Jampani3d76c942015-06-29 23:37:10 -070095 = Sets.newCopyOnWriteArraySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -080096
97 private final ExecutorService executor;
Jonathan Hartdb3af892015-01-26 13:19:07 -080098 private final ScheduledExecutorService backgroundExecutor;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080099 private final BiFunction<K, V, Collection<NodeId>> peerUpdateFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800100
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700101 private final ExecutorService communicationExecutor;
102 private final Map<NodeId, EventAccumulator> senderPending;
Madan Jampani28726282015-02-19 11:40:23 -0800103
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700104 private final String mapName;
105
Jonathan Hartdb3af892015-01-26 13:19:07 -0800106 private volatile boolean destroyed = false;
Jonathan Hart539a6462015-01-27 17:05:43 -0800107 private static final String ERROR_DESTROYED = " map is already destroyed";
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800108 private final String destroyedMessage;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800109
Jonathan Hart4f397e82015-02-04 09:10:41 -0800110 private static final String ERROR_NULL_KEY = "Key cannot be null";
111 private static final String ERROR_NULL_VALUE = "Null values are not allowed";
112
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700113 private final long initialDelaySec = 5;
114 private final boolean lightweightAntiEntropy;
115 private final boolean tombstonesDisabled;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800116
Jonathan Hart233a18a2015-03-02 17:24:58 -0800117 private static final int WINDOW_SIZE = 5;
118 private static final int HIGH_LOAD_THRESHOLD = 0;
119 private static final int LOAD_WINDOW = 2;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700120 private SlidingWindowCounter counter = new SlidingWindowCounter(WINDOW_SIZE);
Jonathan Hart233a18a2015-03-02 17:24:58 -0800121
Jonathan Hartca335e92015-03-05 10:34:32 -0800122 private final boolean persistent;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700123
124 private static final String PERSISTENT_LOCAL_MAP_NAME = "itemsMap";
125
Jonathan Hartca335e92015-03-05 10:34:32 -0800126
Jonathan Hartdb3af892015-01-26 13:19:07 -0800127 /**
128 * Creates a new eventually consistent map shared amongst multiple instances.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800129 * <p>
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700130 * See {@link org.onosproject.store.service.EventuallyConsistentMapBuilder}
131 * for more description of the parameters expected by the map.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800132 * </p>
Jonathan Hartdb3af892015-01-26 13:19:07 -0800133 *
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700134 * @param mapName a String identifier for the map.
135 * @param clusterService the cluster service
136 * @param clusterCommunicator the cluster communications service
137 * @param serializerBuilder a Kryo namespace builder that can serialize
138 * both K and V
Madan Jampanibcf1a482015-06-24 19:05:56 -0700139 * @param timestampProvider provider of timestamps for K and V
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700140 * @param peerUpdateFunction function that provides a set of nodes to immediately
141 * update to when there writes to the map
142 * @param eventExecutor executor to use for processing incoming
143 * events from peers
144 * @param communicationExecutor executor to use for sending events to peers
145 * @param backgroundExecutor executor to use for background anti-entropy
146 * tasks
147 * @param tombstonesDisabled true if this map should not maintain
148 * tombstones
149 * @param antiEntropyPeriod period that the anti-entropy task should run
Jonathan Hartca335e92015-03-05 10:34:32 -0800150 * @param antiEntropyTimeUnit time unit for anti-entropy period
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700151 * @param convergeFaster make anti-entropy try to converge faster
Jonathan Hartca335e92015-03-05 10:34:32 -0800152 * @param persistent persist data to disk
Jonathan Hartdb3af892015-01-26 13:19:07 -0800153 */
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700154 EventuallyConsistentMapImpl(String mapName,
155 ClusterService clusterService,
156 ClusterCommunicationService clusterCommunicator,
157 KryoNamespace.Builder serializerBuilder,
Madan Jampanibcf1a482015-06-24 19:05:56 -0700158 BiFunction<K, V, Timestamp> timestampProvider,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700159 BiFunction<K, V, Collection<NodeId>> peerUpdateFunction,
160 ExecutorService eventExecutor,
161 ExecutorService communicationExecutor,
162 ScheduledExecutorService backgroundExecutor,
163 boolean tombstonesDisabled,
164 long antiEntropyPeriod,
165 TimeUnit antiEntropyTimeUnit,
Jonathan Hartca335e92015-03-05 10:34:32 -0800166 boolean convergeFaster,
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700167 boolean persistent,
168 PersistenceService persistenceService) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700169 this.mapName = mapName;
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700170 this.serializer = createSerializer(serializerBuilder);
171 this.persistenceService = persistenceService;
172 this.persistent =
173 persistent;
174 if (persistent) {
175 items = this.persistenceService.<K, MapValue<V>>persistentMapBuilder()
176 .withName(PERSISTENT_LOCAL_MAP_NAME)
177 .withSerializer(new Serializer() {
178
179 @Override
180 public <T> byte[] encode(T object) {
181 return EventuallyConsistentMapImpl.this.serializer.encode(object);
182 }
183
184 @Override
185 public <T> T decode(byte[] bytes) {
186 return EventuallyConsistentMapImpl.this.serializer.decode(bytes);
187 }
188 })
189 .build();
190 } else {
191 items = Maps.newConcurrentMap();
192 }
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800193 senderPending = Maps.newConcurrentMap();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700194 destroyedMessage = mapName + ERROR_DESTROYED;
Madan Jampani28726282015-02-19 11:40:23 -0800195
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700196 this.clusterService = clusterService;
197 this.clusterCommunicator = clusterCommunicator;
Madan Jampani3d76c942015-06-29 23:37:10 -0700198 this.localNodeId = clusterService.getLocalNode().id();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700199
Madan Jampanibcf1a482015-06-24 19:05:56 -0700200 this.timestampProvider = timestampProvider;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700201
202 if (peerUpdateFunction != null) {
203 this.peerUpdateFunction = peerUpdateFunction;
204 } else {
205 this.peerUpdateFunction = (key, value) -> clusterService.getNodes().stream()
206 .map(ControllerNode::id)
Madan Jampani3d76c942015-06-29 23:37:10 -0700207 .filter(nodeId -> !nodeId.equals(localNodeId))
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700208 .collect(Collectors.toList());
209 }
210
211 if (eventExecutor != null) {
212 this.executor = eventExecutor;
213 } else {
214 // should be a normal executor; it's used for receiving messages
215 this.executor =
216 Executors.newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-fg-%d"));
217 }
218
219 if (communicationExecutor != null) {
220 this.communicationExecutor = communicationExecutor;
221 } else {
222 // sending executor; should be capped
223 //TODO this probably doesn't need to be bounded anymore
224 this.communicationExecutor =
225 newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-publish-%d"));
226 }
227
Jonathan Hartca335e92015-03-05 10:34:32 -0800228
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700229 if (backgroundExecutor != null) {
230 this.backgroundExecutor = backgroundExecutor;
231 } else {
232 this.backgroundExecutor =
233 newSingleThreadScheduledExecutor(groupedThreads("onos/ecm", mapName + "-bg-%d"));
234 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800235
Jonathan Hartaaa56572015-01-28 21:56:35 -0800236 // start anti-entropy thread
Madan Jampani3d76c942015-06-29 23:37:10 -0700237 this.backgroundExecutor.scheduleAtFixedRate(this::sendAdvertisement,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700238 initialDelaySec, antiEntropyPeriod,
239 antiEntropyTimeUnit);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800240
Jonathan Hartdb3af892015-01-26 13:19:07 -0800241 updateMessageSubject = new MessageSubject("ecm-" + mapName + "-update");
242 clusterCommunicator.addSubscriber(updateMessageSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700243 serializer::decode,
244 this::processUpdates,
245 this.executor);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800246
Jonathan Hartaaa56572015-01-28 21:56:35 -0800247 antiEntropyAdvertisementSubject = new MessageSubject("ecm-" + mapName + "-anti-entropy");
248 clusterCommunicator.addSubscriber(antiEntropyAdvertisementSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700249 serializer::decode,
250 this::handleAntiEntropyAdvertisement,
251 this.backgroundExecutor);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800252
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700253 this.tombstonesDisabled = tombstonesDisabled;
254 this.lightweightAntiEntropy = !convergeFaster;
Madan Jampanie1356282015-03-10 19:05:36 -0700255 }
256
Jonathan Hartdb3af892015-01-26 13:19:07 -0800257 private KryoSerializer createSerializer(KryoNamespace.Builder builder) {
258 return new KryoSerializer() {
259 @Override
260 protected void setupKryoPool() {
261 // Add the map's internal helper classes to the user-supplied serializer
262 serializerPool = builder
Madan Jampani3d76c942015-06-29 23:37:10 -0700263 .register(KryoNamespaces.BASIC)
Madan Jampanidb5d06a2015-06-30 11:16:48 -0700264 .nextId(KryoNamespaces.BEGIN_USER_CUSTOM_ID)
Madan Jampani3e033bd2015-04-08 13:03:49 -0700265 .register(LogicalTimestamp.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800266 .register(WallClockTimestamp.class)
Jonathan Hartaaa56572015-01-28 21:56:35 -0800267 .register(AntiEntropyAdvertisement.class)
Madan Jampani3d76c942015-06-29 23:37:10 -0700268 .register(UpdateEntry.class)
269 .register(MapValue.class)
270 .register(MapValue.Digest.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800271 .build();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800272 }
273 };
274 }
275
276 @Override
Madan Jampania090a112016-01-18 16:38:17 -0800277 public String name() {
278 return mapName;
279 }
280
281 @Override
Jonathan Hartdb3af892015-01-26 13:19:07 -0800282 public int size() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800283 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700284 // TODO: Maintain a separate counter for tracking live elements in map.
285 return Maps.filterValues(items, MapValue::isAlive).size();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800286 }
287
288 @Override
289 public boolean isEmpty() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800290 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700291 return size() == 0;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800292 }
293
294 @Override
295 public boolean containsKey(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800296 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800297 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani3d76c942015-06-29 23:37:10 -0700298 return get(key) != null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800299 }
300
301 @Override
302 public boolean containsValue(V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800303 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800304 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani3d76c942015-06-29 23:37:10 -0700305 return items.values()
306 .stream()
307 .filter(MapValue::isAlive)
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700308 .anyMatch(v -> value.equals(v.get()));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800309 }
310
311 @Override
312 public V get(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800313 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800314 checkNotNull(key, ERROR_NULL_KEY);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800315
Madan Jampani3d76c942015-06-29 23:37:10 -0700316 MapValue<V> value = items.get(key);
317 return (value == null || value.isTombstone()) ? null : value.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800318 }
319
320 @Override
321 public void put(K key, V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800322 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800323 checkNotNull(key, ERROR_NULL_KEY);
324 checkNotNull(value, ERROR_NULL_VALUE);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800325
Madan Jampani3d76c942015-06-29 23:37:10 -0700326 MapValue<V> newValue = new MapValue<>(value, timestampProvider.apply(key, value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700327 if (putInternal(key, newValue)) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700328 notifyPeers(new UpdateEntry<>(key, newValue), peerUpdateFunction.apply(key, value));
Madan Jampanicab114c2015-07-23 00:14:19 -0700329 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800330 }
331 }
332
Jonathan Hartdb3af892015-01-26 13:19:07 -0800333 @Override
Madan Jampani43e9c9c2015-06-26 14:16:46 -0700334 public V remove(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800335 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800336 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700337 return removeAndNotify(key, null);
338 }
339
340 @Override
341 public void remove(K key, V value) {
342 checkState(!destroyed, destroyedMessage);
343 checkNotNull(key, ERROR_NULL_KEY);
344 checkNotNull(value, ERROR_NULL_VALUE);
345 removeAndNotify(key, value);
346 }
347
348 private V removeAndNotify(K key, V value) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700349 Timestamp timestamp = timestampProvider.apply(key, value);
350 Optional<MapValue<V>> tombstone = tombstonesDisabled || timestamp == null
351 ? Optional.empty() : Optional.of(MapValue.tombstone(timestamp));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700352 MapValue<V> previousValue = removeInternal(key, Optional.ofNullable(value), tombstone);
Madan Jampania0ac4872015-07-02 11:23:49 -0700353 if (previousValue != null) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700354 notifyPeers(new UpdateEntry<>(key, tombstone.orElse(null)),
355 peerUpdateFunction.apply(key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700356 if (previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700357 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700358 }
359 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700360 return previousValue != null ? previousValue.get() : null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800361 }
362
Madan Jampani483d0a22015-08-19 17:33:00 -0700363 private MapValue<V> removeInternal(K key, Optional<V> value, Optional<MapValue<V>> tombstone) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700364 checkState(!destroyed, destroyedMessage);
365 checkNotNull(key, ERROR_NULL_KEY);
366 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani483d0a22015-08-19 17:33:00 -0700367 tombstone.ifPresent(v -> checkState(v.isTombstone()));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700368
369 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700370 AtomicBoolean updated = new AtomicBoolean(false);
Madan Jampanid13f3b82015-07-01 17:37:50 -0700371 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
Madan Jampani3d76c942015-06-29 23:37:10 -0700372 items.compute(key, (k, existing) -> {
Madan Jampanid13f3b82015-07-01 17:37:50 -0700373 boolean valueMatches = true;
374 if (value.isPresent() && existing != null && existing.isAlive()) {
375 valueMatches = Objects.equals(value.get(), existing.get());
Madan Jampani3d76c942015-06-29 23:37:10 -0700376 }
Brian O'Connor6325dad2015-07-07 15:36:29 -0700377 if (existing == null) {
Jonathan Hart4a29c592015-09-23 17:55:07 -0700378 log.trace("ECMap Remove: Existing value for key {} is already null", k);
Brian O'Connor6325dad2015-07-07 15:36:29 -0700379 }
Madan Jampani483d0a22015-08-19 17:33:00 -0700380 if (valueMatches) {
381 if (existing == null) {
382 updated.set(tombstone.isPresent());
383 } else {
384 updated.set(!tombstone.isPresent() || tombstone.get().isNewerThan(existing));
385 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700386 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700387 if (updated.get()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700388 previousValue.set(existing);
389 return tombstone.orElse(null);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700390 } else {
391 return existing;
392 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700393 });
Madan Jampanid13f3b82015-07-01 17:37:50 -0700394 return previousValue.get();
Jonathan Hart5ec32ba2015-02-05 13:33:58 -0800395 }
396
397 @Override
Madan Jampani4727a112015-07-16 12:12:58 -0700398 public V compute(K key, BiFunction<K, V, V> recomputeFunction) {
399 checkState(!destroyed, destroyedMessage);
400 checkNotNull(key, ERROR_NULL_KEY);
401 checkNotNull(recomputeFunction, "Recompute function cannot be null");
402
403 AtomicBoolean updated = new AtomicBoolean(false);
404 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
405 MapValue<V> computedValue = items.compute(key, (k, mv) -> {
406 previousValue.set(mv);
407 V newRawValue = recomputeFunction.apply(key, mv == null ? null : mv.get());
408 MapValue<V> newValue = new MapValue<>(newRawValue, timestampProvider.apply(key, newRawValue));
409 if (mv == null || newValue.isNewerThan(mv)) {
410 updated.set(true);
411 return newValue;
412 } else {
413 return mv;
414 }
415 });
416 if (updated.get()) {
417 notifyPeers(new UpdateEntry<>(key, computedValue), peerUpdateFunction.apply(key, computedValue.get()));
418 EventuallyConsistentMapEvent.Type updateType = computedValue.isTombstone() ? REMOVE : PUT;
419 V value = computedValue.isTombstone()
420 ? previousValue.get() == null ? null : previousValue.get().get()
421 : computedValue.get();
422 if (value != null) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700423 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, updateType, key, value));
Madan Jampani4727a112015-07-16 12:12:58 -0700424 }
425 }
426 return computedValue.get();
427 }
428
429 @Override
Jonathan Hartdb3af892015-01-26 13:19:07 -0800430 public void putAll(Map<? extends K, ? extends V> m) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800431 checkState(!destroyed, destroyedMessage);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800432 m.forEach(this::put);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800433 }
434
435 @Override
436 public void clear() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800437 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700438 Maps.filterValues(items, MapValue::isAlive)
439 .forEach((k, v) -> remove(k));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800440 }
441
442 @Override
443 public Set<K> keySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800444 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700445 return Maps.filterValues(items, MapValue::isAlive)
446 .keySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800447 }
448
449 @Override
450 public Collection<V> values() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800451 checkState(!destroyed, destroyedMessage);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700452 return Collections2.transform(Maps.filterValues(items, MapValue::isAlive).values(), MapValue::get);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800453 }
454
455 @Override
456 public Set<Map.Entry<K, V>> entrySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800457 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700458 return Maps.filterValues(items, MapValue::isAlive)
459 .entrySet()
460 .stream()
461 .map(e -> Pair.of(e.getKey(), e.getValue().get()))
462 .collect(Collectors.toSet());
463 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800464
Madan Jampani3d76c942015-06-29 23:37:10 -0700465 /**
466 * Returns true if newValue was accepted i.e. map is updated.
Aaron Kruglikov66cf0b92015-10-26 15:46:54 -0700467 *
Madan Jampani3d76c942015-06-29 23:37:10 -0700468 * @param key key
469 * @param newValue proposed new value
470 * @return true if update happened; false if map already contains a more recent value for the key
471 */
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700472 private boolean putInternal(K key, MapValue<V> newValue) {
473 checkState(!destroyed, destroyedMessage);
474 checkNotNull(key, ERROR_NULL_KEY);
475 checkNotNull(newValue, ERROR_NULL_VALUE);
476 checkState(newValue.isAlive());
477 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700478 AtomicBoolean updated = new AtomicBoolean(false);
479 items.compute(key, (k, existing) -> {
480 if (existing == null || newValue.isNewerThan(existing)) {
481 updated.set(true);
Madan Jampani3d76c942015-06-29 23:37:10 -0700482 return newValue;
483 }
484 return existing;
485 });
Madan Jampani3d76c942015-06-29 23:37:10 -0700486 return updated.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800487 }
488
489 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800490 public void addListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800491 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800492
493 listeners.add(checkNotNull(listener));
494 }
495
496 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800497 public void removeListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800498 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800499
500 listeners.remove(checkNotNull(listener));
501 }
502
503 @Override
504 public void destroy() {
505 destroyed = true;
506
507 executor.shutdown();
508 backgroundExecutor.shutdown();
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800509 communicationExecutor.shutdown();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800510
Jonathan Hart584d2f32015-01-27 19:46:14 -0800511 listeners.clear();
512
Jonathan Hartdb3af892015-01-26 13:19:07 -0800513 clusterCommunicator.removeSubscriber(updateMessageSubject);
Jonathan Hart584d2f32015-01-27 19:46:14 -0800514 clusterCommunicator.removeSubscriber(antiEntropyAdvertisementSubject);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800515 }
516
Jonathan Hartaaa56572015-01-28 21:56:35 -0800517 private void notifyListeners(EventuallyConsistentMapEvent<K, V> event) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700518 listeners.forEach(listener -> listener.event(event));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800519 }
520
Madan Jampani3d76c942015-06-29 23:37:10 -0700521 private void notifyPeers(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800522 queueUpdate(event, peers);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800523 }
524
Madan Jampani3d76c942015-06-29 23:37:10 -0700525 private void queueUpdate(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800526 if (peers == null) {
527 // we have no friends :(
528 return;
529 }
530 peers.forEach(node ->
Jonathan Hart9a426f82015-09-03 15:43:13 +0200531 senderPending.computeIfAbsent(node, unusedKey -> new EventAccumulator(node)).add(event)
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800532 );
533 }
534
Jonathan Hart233a18a2015-03-02 17:24:58 -0800535 private boolean underHighLoad() {
536 return counter.get(LOAD_WINDOW) > HIGH_LOAD_THRESHOLD;
537 }
538
Madan Jampani3d76c942015-06-29 23:37:10 -0700539 private void sendAdvertisement() {
540 try {
Thomas Vachuska152f9fd2015-04-02 16:28:13 -0700541 if (underHighLoad() || destroyed) {
Jonathan Hart233a18a2015-03-02 17:24:58 -0800542 return;
543 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700544 pickRandomActivePeer().ifPresent(this::sendAdvertisementToPeer);
545 } catch (Exception e) {
546 // Catch all exceptions to avoid scheduled task being suppressed.
547 log.error("Exception thrown while sending advertisement", e);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800548 }
549 }
550
Madan Jampani3d76c942015-06-29 23:37:10 -0700551 private Optional<NodeId> pickRandomActivePeer() {
552 List<NodeId> activePeers = clusterService.getNodes()
553 .stream()
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700554 .map(ControllerNode::id)
555 .filter(id -> !localNodeId.equals(id))
Madan Jampani3d76c942015-06-29 23:37:10 -0700556 .filter(id -> clusterService.getState(id) == ControllerNode.State.ACTIVE)
557 .collect(Collectors.toList());
558 Collections.shuffle(activePeers);
559 return activePeers.isEmpty() ? Optional.empty() : Optional.of(activePeers.get(0));
560 }
561
562 private void sendAdvertisementToPeer(NodeId peer) {
563 clusterCommunicator.unicast(createAdvertisement(),
564 antiEntropyAdvertisementSubject,
565 serializer::encode,
566 peer)
567 .whenComplete((result, error) -> {
568 if (error != null) {
Madan Jampania0ac4872015-07-02 11:23:49 -0700569 log.debug("Failed to send anti-entropy advertisement to {}", peer, error);
Madan Jampani3d76c942015-06-29 23:37:10 -0700570 }
571 });
572 }
573
Jonathan Hartaaa56572015-01-28 21:56:35 -0800574 private AntiEntropyAdvertisement<K> createAdvertisement() {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700575 return new AntiEntropyAdvertisement<K>(localNodeId,
576 ImmutableMap.copyOf(Maps.transformValues(items, MapValue::digest)));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800577 }
578
579 private void handleAntiEntropyAdvertisement(AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700580 if (destroyed || underHighLoad()) {
581 return;
582 }
583 try {
Jonathan Hart9a426f82015-09-03 15:43:13 +0200584 if (log.isTraceEnabled()) {
585 log.trace("Received anti-entropy advertisement from {} for {} with {} entries in it",
586 mapName, ad.sender(), ad.digest().size());
587 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700588 antiEntropyCheckLocalItems(ad).forEach(this::notifyListeners);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800589
Madan Jampani3d76c942015-06-29 23:37:10 -0700590 if (!lightweightAntiEntropy) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700591 // if remote ad has any entries that the local copy is missing, actively sync
592 // TODO: Missing keys is not the way local copy can be behind.
593 if (Sets.difference(ad.digest().keySet(), items.keySet()).size() > 0) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700594 // TODO: Send ad for missing keys and for entries that are stale
595 sendAdvertisementToPeer(ad.sender());
Jonathan Hartf893be82015-02-24 17:35:51 -0800596 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800597 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700598 } catch (Exception e) {
599 log.warn("Error handling anti-entropy advertisement", e);
HIGUCHI Yuta00c3f572015-02-25 07:33:50 -0800600 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800601 }
602
603 /**
Madan Jampani3d76c942015-06-29 23:37:10 -0700604 * Processes anti-entropy ad from peer by taking following actions:
605 * 1. If peer has an old entry, updates peer.
606 * 2. If peer indicates an entry is removed and has a more recent
607 * timestamp than the local entry, update local state.
Jonathan Hartaaa56572015-01-28 21:56:35 -0800608 */
Jonathan Hartaaa56572015-01-28 21:56:35 -0800609 private List<EventuallyConsistentMapEvent<K, V>> antiEntropyCheckLocalItems(
610 AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700611 final List<EventuallyConsistentMapEvent<K, V>> externalEvents = Lists.newLinkedList();
Jonathan Hartaaa56572015-01-28 21:56:35 -0800612 final NodeId sender = ad.sender();
Madan Jampani3d76c942015-06-29 23:37:10 -0700613 items.forEach((key, localValue) -> {
614 MapValue.Digest remoteValueDigest = ad.digest().get(key);
615 if (remoteValueDigest == null || localValue.isNewerThan(remoteValueDigest.timestamp())) {
Jonathan Hartaaa56572015-01-28 21:56:35 -0800616 // local value is more recent, push to sender
Madan Jampani3d76c942015-06-29 23:37:10 -0700617 queueUpdate(new UpdateEntry<>(key, localValue), ImmutableList.of(sender));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700618 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700619 if (remoteValueDigest != null
620 && remoteValueDigest.isNewerThan(localValue.digest())
621 && remoteValueDigest.isTombstone()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700622 MapValue<V> tombstone = MapValue.tombstone(remoteValueDigest.timestamp());
Madan Jampanid13f3b82015-07-01 17:37:50 -0700623 MapValue<V> previousValue = removeInternal(key,
624 Optional.empty(),
Madan Jampani483d0a22015-08-19 17:33:00 -0700625 Optional.of(tombstone));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700626 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700627 externalEvents.add(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800628 }
629 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700630 });
Jonathan Hartaaa56572015-01-28 21:56:35 -0800631 return externalEvents;
632 }
633
Madan Jampani3d76c942015-06-29 23:37:10 -0700634 private void processUpdates(Collection<UpdateEntry<K, V>> updates) {
635 if (destroyed) {
636 return;
Jonathan Hartaaa56572015-01-28 21:56:35 -0800637 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700638 updates.forEach(update -> {
639 final K key = update.key();
640 final MapValue<V> value = update.value();
Madan Jampani483d0a22015-08-19 17:33:00 -0700641 if (value == null || value.isTombstone()) {
642 MapValue<V> previousValue = removeInternal(key, Optional.empty(), Optional.ofNullable(value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700643 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700644 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700645 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700646 } else if (putInternal(key, value)) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700647 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800648 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700649 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800650 }
651
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800652 // TODO pull this into the class if this gets pulled out...
653 private static final int DEFAULT_MAX_EVENTS = 1000;
654 private static final int DEFAULT_MAX_IDLE_MS = 10;
655 private static final int DEFAULT_MAX_BATCH_MS = 50;
656 private static final Timer TIMER = new Timer("onos-ecm-sender-events");
Jonathan Hartdb3af892015-01-26 13:19:07 -0800657
Madan Jampani3d76c942015-06-29 23:37:10 -0700658 private final class EventAccumulator extends AbstractAccumulator<UpdateEntry<K, V>> {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800659
660 private final NodeId peer;
661
662 private EventAccumulator(NodeId peer) {
663 super(TIMER, DEFAULT_MAX_EVENTS, DEFAULT_MAX_BATCH_MS, DEFAULT_MAX_IDLE_MS);
664 this.peer = peer;
665 }
666
667 @Override
Madan Jampani3d76c942015-06-29 23:37:10 -0700668 public void processItems(List<UpdateEntry<K, V>> items) {
669 Map<K, UpdateEntry<K, V>> map = Maps.newHashMap();
670 items.forEach(item -> map.compute(item.key(), (key, existing) ->
Madan Jampani92c64eb2015-07-23 15:37:07 -0700671 item.isNewerThan(existing) ? item : existing));
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800672 communicationExecutor.submit(() -> {
Madan Jampani3d76c942015-06-29 23:37:10 -0700673 clusterCommunicator.unicast(ImmutableList.copyOf(map.values()),
Madan Jampani175e8fd2015-05-20 14:10:45 -0700674 updateMessageSubject,
675 serializer::encode,
676 peer)
677 .whenComplete((result, error) -> {
678 if (error != null) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700679 log.debug("Failed to send to {}", peer, error);
Madan Jampani175e8fd2015-05-20 14:10:45 -0700680 }
681 });
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800682 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800683 }
684 }
Jonathan Hart4a29c592015-09-23 17:55:07 -0700685}