blob: 2859b62f1cf5c53d494c4d9548cdd22143f575a7 [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 */
Jonathan Hart77bdd262015-02-03 09:07:48 -080016package org.onosproject.store.ecmap;
Jonathan Hartdb3af892015-01-26 13:19:07 -080017
Madan Jampani4f1f4cd2015-07-08 23:05:35 -070018import com.google.common.collect.Collections2;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080019import com.google.common.collect.ImmutableList;
Madan Jampani4f1f4cd2015-07-08 23:05:35 -070020import com.google.common.collect.ImmutableMap;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080021import com.google.common.collect.Lists;
22import com.google.common.collect.Maps;
Madan Jampani3d76c942015-06-29 23:37:10 -070023import com.google.common.collect.Sets;
Madan Jampani3e033bd2015-04-08 13:03:49 -070024
Jonathan Hartf9108232015-02-02 16:37:35 -080025import org.apache.commons.lang3.tuple.Pair;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080026import org.onlab.util.AbstractAccumulator;
Jonathan Hartdb3af892015-01-26 13:19:07 -080027import org.onlab.util.KryoNamespace;
Jonathan Hart233a18a2015-03-02 17:24:58 -080028import org.onlab.util.SlidingWindowCounter;
Jonathan Hartdb3af892015-01-26 13:19:07 -080029import org.onosproject.cluster.ClusterService;
Jonathan Hartaaa56572015-01-28 21:56:35 -080030import org.onosproject.cluster.ControllerNode;
Jonathan Hartdb3af892015-01-26 13:19:07 -080031import org.onosproject.cluster.NodeId;
32import org.onosproject.store.Timestamp;
33import org.onosproject.store.cluster.messaging.ClusterCommunicationService;
Jonathan Hartdb3af892015-01-26 13:19:07 -080034import org.onosproject.store.cluster.messaging.MessageSubject;
Madan Jampani3e033bd2015-04-08 13:03:49 -070035import org.onosproject.store.impl.LogicalTimestamp;
Jonathan Hart63939a32015-05-08 11:57:03 -070036import org.onosproject.store.service.WallClockTimestamp;
Madan Jampani3d76c942015-06-29 23:37:10 -070037import org.onosproject.store.serializers.KryoNamespaces;
Jonathan Hartdb3af892015-01-26 13:19:07 -080038import org.onosproject.store.serializers.KryoSerializer;
Jonathan Hart6ec029a2015-03-24 17:12:35 -070039import org.onosproject.store.service.EventuallyConsistentMap;
40import org.onosproject.store.service.EventuallyConsistentMapEvent;
41import org.onosproject.store.service.EventuallyConsistentMapListener;
Jonathan Hartdb3af892015-01-26 13:19:07 -080042import org.slf4j.Logger;
43import org.slf4j.LoggerFactory;
44
Madan Jampani3d76c942015-06-29 23:37:10 -070045import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.PUT;
46import static org.onosproject.store.service.EventuallyConsistentMapEvent.Type.REMOVE;
47
Jonathan Hartdb3af892015-01-26 13:19:07 -080048import java.util.Collection;
Madan Jampani3d76c942015-06-29 23:37:10 -070049import java.util.Collections;
Jonathan Hartdb3af892015-01-26 13:19:07 -080050import java.util.List;
51import java.util.Map;
Madan Jampanid13f3b82015-07-01 17:37:50 -070052import java.util.Objects;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070053import java.util.Optional;
Jonathan Hartdb3af892015-01-26 13:19:07 -080054import java.util.Set;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080055import java.util.Timer;
Jonathan Hartdb3af892015-01-26 13:19:07 -080056import java.util.concurrent.ExecutorService;
57import java.util.concurrent.Executors;
58import java.util.concurrent.ScheduledExecutorService;
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -080059import java.util.concurrent.TimeUnit;
Madan Jampani3d76c942015-06-29 23:37:10 -070060import java.util.concurrent.atomic.AtomicBoolean;
Madan Jampani43e9c9c2015-06-26 14:16:46 -070061import java.util.concurrent.atomic.AtomicReference;
Brian O'Connor5eb77c82015-03-02 18:09:39 -080062import java.util.function.BiFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -080063import java.util.stream.Collectors;
64
65import static com.google.common.base.Preconditions.checkNotNull;
66import static com.google.common.base.Preconditions.checkState;
67import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
Brian O'Connorc6713a82015-02-24 11:55:48 -080068import static org.onlab.util.BoundedThreadPool.newFixedThreadPool;
Brian O'Connor4b2ba5f2015-02-18 20:54:00 -080069import static org.onlab.util.Tools.groupedThreads;
Jonathan Hartdb3af892015-01-26 13:19:07 -080070
71/**
72 * Distributed Map implementation which uses optimistic replication and gossip
73 * based techniques to provide an eventually consistent data store.
74 */
75public class EventuallyConsistentMapImpl<K, V>
76 implements EventuallyConsistentMap<K, V> {
77
78 private static final Logger log = LoggerFactory.getLogger(EventuallyConsistentMapImpl.class);
79
Madan Jampani3d76c942015-06-29 23:37:10 -070080 private final Map<K, MapValue<V>> items;
Jonathan Hartdb3af892015-01-26 13:19:07 -080081
Jonathan Hartdb3af892015-01-26 13:19:07 -080082 private final ClusterService clusterService;
83 private final ClusterCommunicationService clusterCommunicator;
84 private final KryoSerializer serializer;
Madan Jampani3d76c942015-06-29 23:37:10 -070085 private final NodeId localNodeId;
Jonathan Hartdb3af892015-01-26 13:19:07 -080086
Madan Jampanibcf1a482015-06-24 19:05:56 -070087 private final BiFunction<K, V, Timestamp> timestampProvider;
Jonathan Hartdb3af892015-01-26 13:19:07 -080088
89 private final MessageSubject updateMessageSubject;
Jonathan Hartaaa56572015-01-28 21:56:35 -080090 private final MessageSubject antiEntropyAdvertisementSubject;
Jonathan Hartdb3af892015-01-26 13:19:07 -080091
Jonathan Hartaaa56572015-01-28 21:56:35 -080092 private final Set<EventuallyConsistentMapListener<K, V>> listeners
Madan Jampani3d76c942015-06-29 23:37:10 -070093 = Sets.newCopyOnWriteArraySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -080094
95 private final ExecutorService executor;
Jonathan Hartdb3af892015-01-26 13:19:07 -080096 private final ScheduledExecutorService backgroundExecutor;
Brian O'Connoreeaea2c2015-03-05 16:24:34 -080097 private final BiFunction<K, V, Collection<NodeId>> peerUpdateFunction;
Jonathan Hartdb3af892015-01-26 13:19:07 -080098
Jonathan Hart6ec029a2015-03-24 17:12:35 -070099 private final ExecutorService communicationExecutor;
100 private final Map<NodeId, EventAccumulator> senderPending;
Madan Jampani28726282015-02-19 11:40:23 -0800101
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700102 private final String mapName;
103
Jonathan Hartdb3af892015-01-26 13:19:07 -0800104 private volatile boolean destroyed = false;
Jonathan Hart539a6462015-01-27 17:05:43 -0800105 private static final String ERROR_DESTROYED = " map is already destroyed";
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800106 private final String destroyedMessage;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800107
Jonathan Hart4f397e82015-02-04 09:10:41 -0800108 private static final String ERROR_NULL_KEY = "Key cannot be null";
109 private static final String ERROR_NULL_VALUE = "Null values are not allowed";
110
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700111 private final long initialDelaySec = 5;
112 private final boolean lightweightAntiEntropy;
113 private final boolean tombstonesDisabled;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800114
Jonathan Hart233a18a2015-03-02 17:24:58 -0800115 private static final int WINDOW_SIZE = 5;
116 private static final int HIGH_LOAD_THRESHOLD = 0;
117 private static final int LOAD_WINDOW = 2;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700118 private SlidingWindowCounter counter = new SlidingWindowCounter(WINDOW_SIZE);
Jonathan Hart233a18a2015-03-02 17:24:58 -0800119
Jonathan Hartca335e92015-03-05 10:34:32 -0800120 private final boolean persistent;
121 private final PersistentStore<K, V> persistentStore;
122
Jonathan Hartdb3af892015-01-26 13:19:07 -0800123 /**
124 * Creates a new eventually consistent map shared amongst multiple instances.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800125 * <p>
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700126 * See {@link org.onosproject.store.service.EventuallyConsistentMapBuilder}
127 * for more description of the parameters expected by the map.
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800128 * </p>
Jonathan Hartdb3af892015-01-26 13:19:07 -0800129 *
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700130 * @param mapName a String identifier for the map.
131 * @param clusterService the cluster service
132 * @param clusterCommunicator the cluster communications service
133 * @param serializerBuilder a Kryo namespace builder that can serialize
134 * both K and V
Madan Jampanibcf1a482015-06-24 19:05:56 -0700135 * @param timestampProvider provider of timestamps for K and V
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700136 * @param peerUpdateFunction function that provides a set of nodes to immediately
137 * update to when there writes to the map
138 * @param eventExecutor executor to use for processing incoming
139 * events from peers
140 * @param communicationExecutor executor to use for sending events to peers
141 * @param backgroundExecutor executor to use for background anti-entropy
142 * tasks
143 * @param tombstonesDisabled true if this map should not maintain
144 * tombstones
145 * @param antiEntropyPeriod period that the anti-entropy task should run
Jonathan Hartca335e92015-03-05 10:34:32 -0800146 * @param antiEntropyTimeUnit time unit for anti-entropy period
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700147 * @param convergeFaster make anti-entropy try to converge faster
Jonathan Hartca335e92015-03-05 10:34:32 -0800148 * @param persistent persist data to disk
Jonathan Hartdb3af892015-01-26 13:19:07 -0800149 */
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700150 EventuallyConsistentMapImpl(String mapName,
151 ClusterService clusterService,
152 ClusterCommunicationService clusterCommunicator,
153 KryoNamespace.Builder serializerBuilder,
Madan Jampanibcf1a482015-06-24 19:05:56 -0700154 BiFunction<K, V, Timestamp> timestampProvider,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700155 BiFunction<K, V, Collection<NodeId>> peerUpdateFunction,
156 ExecutorService eventExecutor,
157 ExecutorService communicationExecutor,
158 ScheduledExecutorService backgroundExecutor,
159 boolean tombstonesDisabled,
160 long antiEntropyPeriod,
161 TimeUnit antiEntropyTimeUnit,
Jonathan Hartca335e92015-03-05 10:34:32 -0800162 boolean convergeFaster,
163 boolean persistent) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700164 this.mapName = mapName;
Madan Jampani3d76c942015-06-29 23:37:10 -0700165 items = Maps.newConcurrentMap();
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800166 senderPending = Maps.newConcurrentMap();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700167 destroyedMessage = mapName + ERROR_DESTROYED;
Madan Jampani28726282015-02-19 11:40:23 -0800168
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700169 this.clusterService = clusterService;
170 this.clusterCommunicator = clusterCommunicator;
Madan Jampani3d76c942015-06-29 23:37:10 -0700171 this.localNodeId = clusterService.getLocalNode().id();
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700172
173 this.serializer = createSerializer(serializerBuilder);
174
Madan Jampanibcf1a482015-06-24 19:05:56 -0700175 this.timestampProvider = timestampProvider;
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700176
177 if (peerUpdateFunction != null) {
178 this.peerUpdateFunction = peerUpdateFunction;
179 } else {
180 this.peerUpdateFunction = (key, value) -> clusterService.getNodes().stream()
181 .map(ControllerNode::id)
Madan Jampani3d76c942015-06-29 23:37:10 -0700182 .filter(nodeId -> !nodeId.equals(localNodeId))
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700183 .collect(Collectors.toList());
184 }
185
186 if (eventExecutor != null) {
187 this.executor = eventExecutor;
188 } else {
189 // should be a normal executor; it's used for receiving messages
190 this.executor =
191 Executors.newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-fg-%d"));
192 }
193
194 if (communicationExecutor != null) {
195 this.communicationExecutor = communicationExecutor;
196 } else {
197 // sending executor; should be capped
198 //TODO this probably doesn't need to be bounded anymore
199 this.communicationExecutor =
200 newFixedThreadPool(8, groupedThreads("onos/ecm", mapName + "-publish-%d"));
201 }
202
Jonathan Hartca335e92015-03-05 10:34:32 -0800203 this.persistent = persistent;
204
205 if (this.persistent) {
206 String dataDirectory = System.getProperty("karaf.data", "./data");
207 String filename = dataDirectory + "/" + "mapdb-ecm-" + mapName;
208
209 ExecutorService dbExecutor =
210 newFixedThreadPool(1, groupedThreads("onos/ecm", mapName + "-dbwriter"));
211
212 persistentStore = new MapDbPersistentStore<>(filename, dbExecutor, serializer);
Madan Jampani3d76c942015-06-29 23:37:10 -0700213 persistentStore.readInto(items);
Jonathan Hartca335e92015-03-05 10:34:32 -0800214 } else {
215 this.persistentStore = null;
216 }
217
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700218 if (backgroundExecutor != null) {
219 this.backgroundExecutor = backgroundExecutor;
220 } else {
221 this.backgroundExecutor =
222 newSingleThreadScheduledExecutor(groupedThreads("onos/ecm", mapName + "-bg-%d"));
223 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800224
Jonathan Hartaaa56572015-01-28 21:56:35 -0800225 // start anti-entropy thread
Madan Jampani3d76c942015-06-29 23:37:10 -0700226 this.backgroundExecutor.scheduleAtFixedRate(this::sendAdvertisement,
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700227 initialDelaySec, antiEntropyPeriod,
228 antiEntropyTimeUnit);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800229
Jonathan Hartdb3af892015-01-26 13:19:07 -0800230 updateMessageSubject = new MessageSubject("ecm-" + mapName + "-update");
231 clusterCommunicator.addSubscriber(updateMessageSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700232 serializer::decode,
233 this::processUpdates,
234 this.executor);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800235
Jonathan Hartaaa56572015-01-28 21:56:35 -0800236 antiEntropyAdvertisementSubject = new MessageSubject("ecm-" + mapName + "-anti-entropy");
237 clusterCommunicator.addSubscriber(antiEntropyAdvertisementSubject,
Madan Jampani3d76c942015-06-29 23:37:10 -0700238 serializer::decode,
239 this::handleAntiEntropyAdvertisement,
240 this.backgroundExecutor);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800241
Jonathan Hart6ec029a2015-03-24 17:12:35 -0700242 this.tombstonesDisabled = tombstonesDisabled;
243 this.lightweightAntiEntropy = !convergeFaster;
Madan Jampanie1356282015-03-10 19:05:36 -0700244 }
245
Jonathan Hartdb3af892015-01-26 13:19:07 -0800246 private KryoSerializer createSerializer(KryoNamespace.Builder builder) {
247 return new KryoSerializer() {
248 @Override
249 protected void setupKryoPool() {
250 // Add the map's internal helper classes to the user-supplied serializer
251 serializerPool = builder
Madan Jampani3d76c942015-06-29 23:37:10 -0700252 .register(KryoNamespaces.BASIC)
Madan Jampanidb5d06a2015-06-30 11:16:48 -0700253 .nextId(KryoNamespaces.BEGIN_USER_CUSTOM_ID)
Madan Jampani3e033bd2015-04-08 13:03:49 -0700254 .register(LogicalTimestamp.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800255 .register(WallClockTimestamp.class)
Jonathan Hartaaa56572015-01-28 21:56:35 -0800256 .register(AntiEntropyAdvertisement.class)
Madan Jampani3d76c942015-06-29 23:37:10 -0700257 .register(UpdateEntry.class)
258 .register(MapValue.class)
259 .register(MapValue.Digest.class)
Jonathan Hartdb3af892015-01-26 13:19:07 -0800260 .build();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800261 }
262 };
263 }
264
265 @Override
266 public int size() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800267 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700268 // TODO: Maintain a separate counter for tracking live elements in map.
269 return Maps.filterValues(items, MapValue::isAlive).size();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800270 }
271
272 @Override
273 public boolean isEmpty() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800274 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700275 return size() == 0;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800276 }
277
278 @Override
279 public boolean containsKey(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800280 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800281 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani3d76c942015-06-29 23:37:10 -0700282 return get(key) != null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800283 }
284
285 @Override
286 public boolean containsValue(V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800287 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800288 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani3d76c942015-06-29 23:37:10 -0700289 return items.values()
290 .stream()
291 .filter(MapValue::isAlive)
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700292 .anyMatch(v -> value.equals(v.get()));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800293 }
294
295 @Override
296 public V get(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800297 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800298 checkNotNull(key, ERROR_NULL_KEY);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800299
Madan Jampani3d76c942015-06-29 23:37:10 -0700300 MapValue<V> value = items.get(key);
301 return (value == null || value.isTombstone()) ? null : value.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800302 }
303
304 @Override
305 public void put(K key, V value) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800306 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800307 checkNotNull(key, ERROR_NULL_KEY);
308 checkNotNull(value, ERROR_NULL_VALUE);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800309
Madan Jampani3d76c942015-06-29 23:37:10 -0700310 MapValue<V> newValue = new MapValue<>(value, timestampProvider.apply(key, value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700311 if (putInternal(key, newValue)) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700312 notifyPeers(new UpdateEntry<>(key, newValue), peerUpdateFunction.apply(key, value));
Madan Jampanicab114c2015-07-23 00:14:19 -0700313 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800314 }
315 }
316
Jonathan Hartdb3af892015-01-26 13:19:07 -0800317 @Override
Madan Jampani43e9c9c2015-06-26 14:16:46 -0700318 public V remove(K key) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800319 checkState(!destroyed, destroyedMessage);
Jonathan Hart4f397e82015-02-04 09:10:41 -0800320 checkNotNull(key, ERROR_NULL_KEY);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700321 return removeAndNotify(key, null);
322 }
323
324 @Override
325 public void remove(K key, V value) {
326 checkState(!destroyed, destroyedMessage);
327 checkNotNull(key, ERROR_NULL_KEY);
328 checkNotNull(value, ERROR_NULL_VALUE);
329 removeAndNotify(key, value);
330 }
331
332 private V removeAndNotify(K key, V value) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700333 Timestamp timestamp = timestampProvider.apply(key, value);
334 Optional<MapValue<V>> tombstone = tombstonesDisabled || timestamp == null
335 ? Optional.empty() : Optional.of(MapValue.tombstone(timestamp));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700336 MapValue<V> previousValue = removeInternal(key, Optional.ofNullable(value), tombstone);
Madan Jampania0ac4872015-07-02 11:23:49 -0700337 if (previousValue != null) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700338 notifyPeers(new UpdateEntry<>(key, tombstone.orElse(null)),
339 peerUpdateFunction.apply(key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700340 if (previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700341 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampania0ac4872015-07-02 11:23:49 -0700342 }
343 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700344 return previousValue != null ? previousValue.get() : null;
Jonathan Hartdb3af892015-01-26 13:19:07 -0800345 }
346
Madan Jampani483d0a22015-08-19 17:33:00 -0700347 private MapValue<V> removeInternal(K key, Optional<V> value, Optional<MapValue<V>> tombstone) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700348 checkState(!destroyed, destroyedMessage);
349 checkNotNull(key, ERROR_NULL_KEY);
350 checkNotNull(value, ERROR_NULL_VALUE);
Madan Jampani483d0a22015-08-19 17:33:00 -0700351 tombstone.ifPresent(v -> checkState(v.isTombstone()));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700352
353 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700354 AtomicBoolean updated = new AtomicBoolean(false);
Madan Jampanid13f3b82015-07-01 17:37:50 -0700355 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
Madan Jampani3d76c942015-06-29 23:37:10 -0700356 items.compute(key, (k, existing) -> {
Madan Jampanid13f3b82015-07-01 17:37:50 -0700357 boolean valueMatches = true;
358 if (value.isPresent() && existing != null && existing.isAlive()) {
359 valueMatches = Objects.equals(value.get(), existing.get());
Madan Jampani3d76c942015-06-29 23:37:10 -0700360 }
Brian O'Connor6325dad2015-07-07 15:36:29 -0700361 if (existing == null) {
362 log.debug("ECMap Remove: Existing value for key {} is already null", k);
363 }
Madan Jampani483d0a22015-08-19 17:33:00 -0700364 if (valueMatches) {
365 if (existing == null) {
366 updated.set(tombstone.isPresent());
367 } else {
368 updated.set(!tombstone.isPresent() || tombstone.get().isNewerThan(existing));
369 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700370 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700371 if (updated.get()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700372 previousValue.set(existing);
373 return tombstone.orElse(null);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700374 } else {
375 return existing;
376 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700377 });
378 if (updated.get()) {
Madan Jampanid13f3b82015-07-01 17:37:50 -0700379 if (persistent) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700380 if (tombstone.isPresent()) {
381 persistentStore.update(key, tombstone.get());
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700382 } else {
Madan Jampani483d0a22015-08-19 17:33:00 -0700383 persistentStore.remove(key);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700384 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700385 }
Jonathan Hart5ec32ba2015-02-05 13:33:58 -0800386 }
Madan Jampanid13f3b82015-07-01 17:37:50 -0700387 return previousValue.get();
Jonathan Hart5ec32ba2015-02-05 13:33:58 -0800388 }
389
390 @Override
Madan Jampani4727a112015-07-16 12:12:58 -0700391 public V compute(K key, BiFunction<K, V, V> recomputeFunction) {
392 checkState(!destroyed, destroyedMessage);
393 checkNotNull(key, ERROR_NULL_KEY);
394 checkNotNull(recomputeFunction, "Recompute function cannot be null");
395
396 AtomicBoolean updated = new AtomicBoolean(false);
397 AtomicReference<MapValue<V>> previousValue = new AtomicReference<>();
398 MapValue<V> computedValue = items.compute(key, (k, mv) -> {
399 previousValue.set(mv);
400 V newRawValue = recomputeFunction.apply(key, mv == null ? null : mv.get());
401 MapValue<V> newValue = new MapValue<>(newRawValue, timestampProvider.apply(key, newRawValue));
402 if (mv == null || newValue.isNewerThan(mv)) {
403 updated.set(true);
404 return newValue;
405 } else {
406 return mv;
407 }
408 });
409 if (updated.get()) {
410 notifyPeers(new UpdateEntry<>(key, computedValue), peerUpdateFunction.apply(key, computedValue.get()));
411 EventuallyConsistentMapEvent.Type updateType = computedValue.isTombstone() ? REMOVE : PUT;
412 V value = computedValue.isTombstone()
413 ? previousValue.get() == null ? null : previousValue.get().get()
414 : computedValue.get();
415 if (value != null) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700416 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, updateType, key, value));
Madan Jampani4727a112015-07-16 12:12:58 -0700417 }
418 }
419 return computedValue.get();
420 }
421
422 @Override
Jonathan Hartdb3af892015-01-26 13:19:07 -0800423 public void putAll(Map<? extends K, ? extends V> m) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800424 checkState(!destroyed, destroyedMessage);
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800425 m.forEach(this::put);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800426 }
427
428 @Override
429 public void clear() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800430 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700431 Maps.filterValues(items, MapValue::isAlive)
432 .forEach((k, v) -> remove(k));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800433 }
434
435 @Override
436 public Set<K> keySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800437 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700438 return Maps.filterValues(items, MapValue::isAlive)
439 .keySet();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800440 }
441
442 @Override
443 public Collection<V> values() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800444 checkState(!destroyed, destroyedMessage);
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700445 return Collections2.transform(Maps.filterValues(items, MapValue::isAlive).values(), MapValue::get);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800446 }
447
448 @Override
449 public Set<Map.Entry<K, V>> entrySet() {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800450 checkState(!destroyed, destroyedMessage);
Madan Jampani3d76c942015-06-29 23:37:10 -0700451 return Maps.filterValues(items, MapValue::isAlive)
452 .entrySet()
453 .stream()
454 .map(e -> Pair.of(e.getKey(), e.getValue().get()))
455 .collect(Collectors.toSet());
456 }
Jonathan Hartdb3af892015-01-26 13:19:07 -0800457
Madan Jampani3d76c942015-06-29 23:37:10 -0700458 /**
459 * Returns true if newValue was accepted i.e. map is updated.
460 * @param key key
461 * @param newValue proposed new value
462 * @return true if update happened; false if map already contains a more recent value for the key
463 */
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700464 private boolean putInternal(K key, MapValue<V> newValue) {
465 checkState(!destroyed, destroyedMessage);
466 checkNotNull(key, ERROR_NULL_KEY);
467 checkNotNull(newValue, ERROR_NULL_VALUE);
468 checkState(newValue.isAlive());
469 counter.incrementCount();
Madan Jampani3d76c942015-06-29 23:37:10 -0700470 AtomicBoolean updated = new AtomicBoolean(false);
471 items.compute(key, (k, existing) -> {
472 if (existing == null || newValue.isNewerThan(existing)) {
473 updated.set(true);
Madan Jampani3d76c942015-06-29 23:37:10 -0700474 return newValue;
475 }
476 return existing;
477 });
478 if (updated.get() && persistent) {
479 persistentStore.update(key, newValue);
480 }
481 return updated.get();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800482 }
483
484 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800485 public void addListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800486 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800487
488 listeners.add(checkNotNull(listener));
489 }
490
491 @Override
Jonathan Hart539a6462015-01-27 17:05:43 -0800492 public void removeListener(EventuallyConsistentMapListener<K, V> listener) {
Thomas Vachuskaa132e3a2015-02-21 01:53:14 -0800493 checkState(!destroyed, destroyedMessage);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800494
495 listeners.remove(checkNotNull(listener));
496 }
497
498 @Override
499 public void destroy() {
500 destroyed = true;
501
502 executor.shutdown();
503 backgroundExecutor.shutdown();
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800504 communicationExecutor.shutdown();
Jonathan Hartdb3af892015-01-26 13:19:07 -0800505
Jonathan Hart584d2f32015-01-27 19:46:14 -0800506 listeners.clear();
507
Jonathan Hartdb3af892015-01-26 13:19:07 -0800508 clusterCommunicator.removeSubscriber(updateMessageSubject);
Jonathan Hart584d2f32015-01-27 19:46:14 -0800509 clusterCommunicator.removeSubscriber(antiEntropyAdvertisementSubject);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800510 }
511
Jonathan Hartaaa56572015-01-28 21:56:35 -0800512 private void notifyListeners(EventuallyConsistentMapEvent<K, V> event) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700513 listeners.forEach(listener -> listener.event(event));
Jonathan Hartdb3af892015-01-26 13:19:07 -0800514 }
515
Madan Jampani3d76c942015-06-29 23:37:10 -0700516 private void notifyPeers(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800517 queueUpdate(event, peers);
Jonathan Hartdb3af892015-01-26 13:19:07 -0800518 }
519
Madan Jampani3d76c942015-06-29 23:37:10 -0700520 private void queueUpdate(UpdateEntry<K, V> event, Collection<NodeId> peers) {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800521 if (peers == null) {
522 // we have no friends :(
523 return;
524 }
525 peers.forEach(node ->
Madan Jampani3d76c942015-06-29 23:37:10 -0700526 senderPending.computeIfAbsent(node, unusedKey -> new EventAccumulator(node)).add(event)
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800527 );
528 }
529
Jonathan Hart233a18a2015-03-02 17:24:58 -0800530 private boolean underHighLoad() {
531 return counter.get(LOAD_WINDOW) > HIGH_LOAD_THRESHOLD;
532 }
533
Madan Jampani3d76c942015-06-29 23:37:10 -0700534 private void sendAdvertisement() {
535 try {
Thomas Vachuska152f9fd2015-04-02 16:28:13 -0700536 if (underHighLoad() || destroyed) {
Jonathan Hart233a18a2015-03-02 17:24:58 -0800537 return;
538 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700539 pickRandomActivePeer().ifPresent(this::sendAdvertisementToPeer);
540 } catch (Exception e) {
541 // Catch all exceptions to avoid scheduled task being suppressed.
542 log.error("Exception thrown while sending advertisement", e);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800543 }
544 }
545
Madan Jampani3d76c942015-06-29 23:37:10 -0700546 private Optional<NodeId> pickRandomActivePeer() {
547 List<NodeId> activePeers = clusterService.getNodes()
548 .stream()
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700549 .map(ControllerNode::id)
550 .filter(id -> !localNodeId.equals(id))
Madan Jampani3d76c942015-06-29 23:37:10 -0700551 .filter(id -> clusterService.getState(id) == ControllerNode.State.ACTIVE)
552 .collect(Collectors.toList());
553 Collections.shuffle(activePeers);
554 return activePeers.isEmpty() ? Optional.empty() : Optional.of(activePeers.get(0));
555 }
556
557 private void sendAdvertisementToPeer(NodeId peer) {
558 clusterCommunicator.unicast(createAdvertisement(),
559 antiEntropyAdvertisementSubject,
560 serializer::encode,
561 peer)
562 .whenComplete((result, error) -> {
563 if (error != null) {
Madan Jampania0ac4872015-07-02 11:23:49 -0700564 log.debug("Failed to send anti-entropy advertisement to {}", peer, error);
Madan Jampani3d76c942015-06-29 23:37:10 -0700565 }
566 });
567 }
568
Jonathan Hartaaa56572015-01-28 21:56:35 -0800569 private AntiEntropyAdvertisement<K> createAdvertisement() {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700570 return new AntiEntropyAdvertisement<K>(localNodeId,
571 ImmutableMap.copyOf(Maps.transformValues(items, MapValue::digest)));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800572 }
573
574 private void handleAntiEntropyAdvertisement(AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700575 if (destroyed || underHighLoad()) {
576 return;
577 }
578 try {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700579 log.debug("Received anti-entropy advertisement from {} for {} with {} entries in it",
580 mapName, ad.sender(), ad.digest().size());
Madan Jampani3d76c942015-06-29 23:37:10 -0700581 antiEntropyCheckLocalItems(ad).forEach(this::notifyListeners);
Jonathan Hartaaa56572015-01-28 21:56:35 -0800582
Madan Jampani3d76c942015-06-29 23:37:10 -0700583 if (!lightweightAntiEntropy) {
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700584 // if remote ad has any entries that the local copy is missing, actively sync
585 // TODO: Missing keys is not the way local copy can be behind.
586 if (Sets.difference(ad.digest().keySet(), items.keySet()).size() > 0) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700587 // TODO: Send ad for missing keys and for entries that are stale
588 sendAdvertisementToPeer(ad.sender());
Jonathan Hartf893be82015-02-24 17:35:51 -0800589 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800590 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700591 } catch (Exception e) {
592 log.warn("Error handling anti-entropy advertisement", e);
HIGUCHI Yuta00c3f572015-02-25 07:33:50 -0800593 }
Jonathan Hartaaa56572015-01-28 21:56:35 -0800594 }
595
596 /**
Madan Jampani3d76c942015-06-29 23:37:10 -0700597 * Processes anti-entropy ad from peer by taking following actions:
598 * 1. If peer has an old entry, updates peer.
599 * 2. If peer indicates an entry is removed and has a more recent
600 * timestamp than the local entry, update local state.
Jonathan Hartaaa56572015-01-28 21:56:35 -0800601 */
Jonathan Hartaaa56572015-01-28 21:56:35 -0800602 private List<EventuallyConsistentMapEvent<K, V>> antiEntropyCheckLocalItems(
603 AntiEntropyAdvertisement<K> ad) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700604 final List<EventuallyConsistentMapEvent<K, V>> externalEvents = Lists.newLinkedList();
Jonathan Hartaaa56572015-01-28 21:56:35 -0800605 final NodeId sender = ad.sender();
Madan Jampani3d76c942015-06-29 23:37:10 -0700606 items.forEach((key, localValue) -> {
607 MapValue.Digest remoteValueDigest = ad.digest().get(key);
608 if (remoteValueDigest == null || localValue.isNewerThan(remoteValueDigest.timestamp())) {
Jonathan Hartaaa56572015-01-28 21:56:35 -0800609 // local value is more recent, push to sender
Madan Jampani3d76c942015-06-29 23:37:10 -0700610 queueUpdate(new UpdateEntry<>(key, localValue), ImmutableList.of(sender));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700611 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700612 if (remoteValueDigest != null
613 && remoteValueDigest.isNewerThan(localValue.digest())
614 && remoteValueDigest.isTombstone()) {
Madan Jampani483d0a22015-08-19 17:33:00 -0700615 MapValue<V> tombstone = MapValue.tombstone(remoteValueDigest.timestamp());
Madan Jampanid13f3b82015-07-01 17:37:50 -0700616 MapValue<V> previousValue = removeInternal(key,
617 Optional.empty(),
Madan Jampani483d0a22015-08-19 17:33:00 -0700618 Optional.of(tombstone));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700619 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700620 externalEvents.add(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800621 }
622 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700623 });
Jonathan Hartaaa56572015-01-28 21:56:35 -0800624 return externalEvents;
625 }
626
Madan Jampani3d76c942015-06-29 23:37:10 -0700627 private void processUpdates(Collection<UpdateEntry<K, V>> updates) {
628 if (destroyed) {
629 return;
Jonathan Hartaaa56572015-01-28 21:56:35 -0800630 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700631 updates.forEach(update -> {
632 final K key = update.key();
633 final MapValue<V> value = update.value();
Madan Jampani483d0a22015-08-19 17:33:00 -0700634 if (value == null || value.isTombstone()) {
635 MapValue<V> previousValue = removeInternal(key, Optional.empty(), Optional.ofNullable(value));
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700636 if (previousValue != null && previousValue.isAlive()) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700637 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, REMOVE, key, previousValue.get()));
Madan Jampanid13f3b82015-07-01 17:37:50 -0700638 }
Madan Jampani4f1f4cd2015-07-08 23:05:35 -0700639 } else if (putInternal(key, value)) {
Madan Jampanicab114c2015-07-23 00:14:19 -0700640 notifyListeners(new EventuallyConsistentMapEvent<>(mapName, PUT, key, value.get()));
Jonathan Hartaaa56572015-01-28 21:56:35 -0800641 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700642 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800643 }
644
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800645 // TODO pull this into the class if this gets pulled out...
646 private static final int DEFAULT_MAX_EVENTS = 1000;
647 private static final int DEFAULT_MAX_IDLE_MS = 10;
648 private static final int DEFAULT_MAX_BATCH_MS = 50;
649 private static final Timer TIMER = new Timer("onos-ecm-sender-events");
Jonathan Hartdb3af892015-01-26 13:19:07 -0800650
Madan Jampani3d76c942015-06-29 23:37:10 -0700651 private final class EventAccumulator extends AbstractAccumulator<UpdateEntry<K, V>> {
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800652
653 private final NodeId peer;
654
655 private EventAccumulator(NodeId peer) {
656 super(TIMER, DEFAULT_MAX_EVENTS, DEFAULT_MAX_BATCH_MS, DEFAULT_MAX_IDLE_MS);
657 this.peer = peer;
658 }
659
660 @Override
Madan Jampani3d76c942015-06-29 23:37:10 -0700661 public void processItems(List<UpdateEntry<K, V>> items) {
662 Map<K, UpdateEntry<K, V>> map = Maps.newHashMap();
663 items.forEach(item -> map.compute(item.key(), (key, existing) ->
Madan Jampani92c64eb2015-07-23 15:37:07 -0700664 item.isNewerThan(existing) ? item : existing));
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800665 communicationExecutor.submit(() -> {
Madan Jampani3d76c942015-06-29 23:37:10 -0700666 clusterCommunicator.unicast(ImmutableList.copyOf(map.values()),
Madan Jampani175e8fd2015-05-20 14:10:45 -0700667 updateMessageSubject,
668 serializer::encode,
669 peer)
670 .whenComplete((result, error) -> {
671 if (error != null) {
Madan Jampani3d76c942015-06-29 23:37:10 -0700672 log.debug("Failed to send to {}", peer, error);
Madan Jampani175e8fd2015-05-20 14:10:45 -0700673 }
674 });
Brian O'Connoreeaea2c2015-03-05 16:24:34 -0800675 });
Jonathan Hartdb3af892015-01-26 13:19:07 -0800676 }
677 }
Madan Jampani3d76c942015-06-29 23:37:10 -0700678}