Repository: hbase Updated Branches: refs/heads/branch-1 604c9b2cc -> 4d5ac316b
HBASE-14708 Use copy on write Map for region location cache Summary: Create and use a copy on write map for region location. - Create a copy on write map backed by a sorted array. - Create a test for both comparing each with a jdk provided map. - Change MetaCache to use the new map. Test Plan: - org.apache.hadoop.hbase.client.TestFromClientSide - TestHCM Differential Revision: https://reviews.facebook.net/D49545 Project: http://git-wip-us.apache.org/repos/asf/hbase/repo Commit: http://git-wip-us.apache.org/repos/asf/hbase/commit/4d5ac316 Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/4d5ac316 Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/4d5ac316 Branch: refs/heads/branch-1 Commit: 4d5ac316b626baa43880a1b65916e008e3d73b69 Parents: 604c9b2 Author: Elliott Clark <ecl...@apache.org> Authored: Tue Oct 27 12:16:37 2015 -0700 Committer: Elliott Clark <ecl...@apache.org> Committed: Tue Nov 17 11:01:52 2015 -0800 ---------------------------------------------------------------------- .../apache/hadoop/hbase/MetaTableAccessor.java | 4 +- .../apache/hadoop/hbase/client/MetaCache.java | 25 +- .../hadoop/hbase/types/CopyOnWriteArrayMap.java | 974 +++++++++++++++++++ .../hadoop/hbase/types/TestCopyOnWriteMaps.java | 311 ++++++ 4 files changed, 1299 insertions(+), 15 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/hbase/blob/4d5ac316/hbase-client/src/main/java/org/apache/hadoop/hbase/MetaTableAccessor.java ---------------------------------------------------------------------- diff --git a/hbase-client/src/main/java/org/apache/hadoop/hbase/MetaTableAccessor.java b/hbase-client/src/main/java/org/apache/hadoop/hbase/MetaTableAccessor.java index 0823094..6626485 100644 --- a/hbase-client/src/main/java/org/apache/hadoop/hbase/MetaTableAccessor.java +++ b/hbase-client/src/main/java/org/apache/hadoop/hbase/MetaTableAccessor.java @@ -740,7 +740,9 @@ public class MetaTableAccessor { // iterate until all serverName columns are seen int replicaId = 0; byte[] serverColumn = getServerColumn(replicaId); - SortedMap<byte[], byte[]> serverMap = infoMap.tailMap(serverColumn, false); + SortedMap<byte[], byte[]> serverMap = null; + serverMap = infoMap.tailMap(serverColumn, false); + if (serverMap.isEmpty()) return new RegionLocations(locations); for (Map.Entry<byte[], byte[]> entry : serverMap.entrySet()) { http://git-wip-us.apache.org/repos/asf/hbase/blob/4d5ac316/hbase-client/src/main/java/org/apache/hadoop/hbase/client/MetaCache.java ---------------------------------------------------------------------- diff --git a/hbase-client/src/main/java/org/apache/hadoop/hbase/client/MetaCache.java b/hbase-client/src/main/java/org/apache/hadoop/hbase/client/MetaCache.java index a9ce173..c9f5e02 100644 --- a/hbase-client/src/main/java/org/apache/hadoop/hbase/client/MetaCache.java +++ b/hbase-client/src/main/java/org/apache/hadoop/hbase/client/MetaCache.java @@ -21,10 +21,9 @@ package org.apache.hadoop.hbase.client; import java.util.Map; import java.util.Map.Entry; import java.util.Set; -import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; -import java.util.concurrent.ConcurrentSkipListMap; -import java.util.concurrent.ConcurrentSkipListSet; +import java.util.concurrent.ConcurrentNavigableMap; +import java.util.concurrent.CopyOnWriteArraySet; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.hadoop.hbase.classification.InterfaceAudience; @@ -36,6 +35,7 @@ import org.apache.hadoop.hbase.KeyValue.KVComparator; import org.apache.hadoop.hbase.RegionLocations; import org.apache.hadoop.hbase.ServerName; import org.apache.hadoop.hbase.TableName; +import org.apache.hadoop.hbase.types.CopyOnWriteArrayMap; import org.apache.hadoop.hbase.util.Bytes; /** @@ -49,16 +49,16 @@ public class MetaCache { /** * Map of table to table {@link HRegionLocation}s. */ - private final ConcurrentMap<TableName, ConcurrentSkipListMap<byte[], RegionLocations>> + private final ConcurrentMap<TableName, ConcurrentNavigableMap<byte[], RegionLocations>> cachedRegionLocations = - new ConcurrentHashMap<TableName, ConcurrentSkipListMap<byte[], RegionLocations>>(); + new CopyOnWriteArrayMap<>(); // The presence of a server in the map implies it's likely that there is an // entry in cachedRegionLocations that map to this server; but the absence // of a server in this map guarentees that there is no entry in cache that // maps to the absent server. // The access to this attribute must be protected by a lock on cachedRegionLocations - private final Set<ServerName> cachedServers = new ConcurrentSkipListSet<ServerName>(); + private final Set<ServerName> cachedServers = new CopyOnWriteArraySet<>(); private final MetricsConnection metrics; @@ -70,13 +70,10 @@ public class MetaCache { * Search the cache for a location that fits our table and row key. * Return null if no suitable region is located. * - * - * @param tableName - * @param row * @return Null or region location found in cache. */ public RegionLocations getCachedLocation(final TableName tableName, final byte [] row) { - ConcurrentSkipListMap<byte[], RegionLocations> tableLocations = + ConcurrentNavigableMap<byte[], RegionLocations> tableLocations = getTableLocations(tableName); Entry<byte[], RegionLocations> e = tableLocations.floorEntry(row); @@ -192,15 +189,15 @@ public class MetaCache { * @param tableName * @return Map of cached locations for passed <code>tableName</code> */ - private ConcurrentSkipListMap<byte[], RegionLocations> + private ConcurrentNavigableMap<byte[], RegionLocations> getTableLocations(final TableName tableName) { // find the map of cached locations for this table - ConcurrentSkipListMap<byte[], RegionLocations> result; + ConcurrentNavigableMap<byte[], RegionLocations> result; result = this.cachedRegionLocations.get(tableName); // if tableLocations for this table isn't built yet, make one if (result == null) { - result = new ConcurrentSkipListMap<byte[], RegionLocations>(Bytes.BYTES_COMPARATOR); - ConcurrentSkipListMap<byte[], RegionLocations> old = + result = new CopyOnWriteArrayMap<>(Bytes.BYTES_COMPARATOR); + ConcurrentNavigableMap<byte[], RegionLocations> old = this.cachedRegionLocations.putIfAbsent(tableName, result); if (old != null) { return old; http://git-wip-us.apache.org/repos/asf/hbase/blob/4d5ac316/hbase-common/src/main/java/org/apache/hadoop/hbase/types/CopyOnWriteArrayMap.java ---------------------------------------------------------------------- diff --git a/hbase-common/src/main/java/org/apache/hadoop/hbase/types/CopyOnWriteArrayMap.java b/hbase-common/src/main/java/org/apache/hadoop/hbase/types/CopyOnWriteArrayMap.java new file mode 100644 index 0000000..41056b2 --- /dev/null +++ b/hbase-common/src/main/java/org/apache/hadoop/hbase/types/CopyOnWriteArrayMap.java @@ -0,0 +1,974 @@ +/** + * 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 org.apache.hadoop.hbase.types; + +import org.apache.hadoop.hbase.classification.InterfaceAudience; +import org.apache.hadoop.hbase.classification.InterfaceStability; + +import java.util.AbstractMap; +import java.util.Collection; +import java.util.Comparator; +import java.util.Iterator; +import java.util.Map; +import java.util.NavigableSet; +import java.util.Set; +import java.util.SortedSet; +import java.util.concurrent.ConcurrentNavigableMap; + +/** + * A Map that keeps a sorted array in order to provide the concurrent map interface. + * Keeping a sorted array means that it's much more cache line friendly, making reads faster + * than the tree version. + * + * In order to make concurrent reads and writes safe this does a copy on write. + * There can only be one concurrent write at a time. + */ +@InterfaceAudience.Private +@InterfaceStability.Stable +public class CopyOnWriteArrayMap<K, V> extends AbstractMap<K, V> + implements Map<K, V>, ConcurrentNavigableMap<K, V> { + private final Comparator<? super K> keyComparator; + private volatile ArrayHolder<K, V> holder; + + public CopyOnWriteArrayMap() { + this(new Comparator<K>() { + @Override + public int compare(K o1, K o2) { + return ((Comparable) o1).compareTo(o2); + } + }); + } + + public CopyOnWriteArrayMap(final Comparator<? super K> keyComparator) { + this.keyComparator = keyComparator; + this.holder = new ArrayHolder<>(keyComparator, new Comparator<Entry<K, V>>() { + @Override + public int compare(Entry<K, V> o1, Entry<K, V> o2) { + return keyComparator.compare(o1.getKey(), o2.getKey()); + } + }); + } + + private CopyOnWriteArrayMap(final Comparator<? super K> keyComparator, ArrayHolder<K, V> holder) { + this.keyComparator = keyComparator; + this.holder = holder; + } + + /* + Un synchronized read operations. + + No locking. + No waiting + No copying. + + These should all be FAST. + */ + + @Override + public Comparator<? super K> comparator() { + return keyComparator; + } + + @Override + public ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { + ArrayHolder<K, V> current = this.holder; + int index = current.find(fromKey); + + if (!inclusive && index >= 0) { + index++; + } else if (index < 0) { + index = -(index + 1); + } + return new CopyOnWriteArrayMap<>( + this.keyComparator, + new ArrayHolder<>( + current.entries, + index, + current.endIndex, + current.keyComparator, + current.comparator)); + } + + @Override + public ConcurrentNavigableMap<K, V> tailMap(K fromKey) { + return this.tailMap(fromKey, true); + } + + @Override + public K firstKey() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.startIndex].getKey(); + } + + @Override + public K lastKey() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.endIndex - 1].getKey(); + } + + @Override + public Entry<K, V> lowerEntry(K key) { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + + int index = current.find(key); + + // There's a key exactly equal. + if (index >= 0) { + index -= 1; + } else { + index = -(index + 1) - 1; + } + + if (index < current.startIndex || index >= current.endIndex) { + return null; + } + return current.entries[index]; + } + + @Override + public K lowerKey(K key) { + Map.Entry<K, V> entry = lowerEntry(key); + if (entry == null) { + return null; + } + return entry.getKey(); + } + + @Override + public Entry<K, V> floorEntry(K key) { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + int index = current.find(key); + if (index < 0) { + index = -(index + 1) - 1; + } + if (index < current.startIndex || index >= current.endIndex) { + return null; + } + + return current.entries[index]; + } + + @Override + public K floorKey(K key) { + Map.Entry<K, V> entry = floorEntry(key); + if (entry == null) { + return null; + } + return entry.getKey(); + } + + @Override + public Entry<K, V> ceilingEntry(K key) { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + int index = current.find(key); + if (index < 0) { + index = -(index + 1); + } + if (index < current.startIndex || index >= current.endIndex) { + return null; + } + + return current.entries[index]; + } + + @Override + public K ceilingKey(K key) { + Map.Entry<K, V> entry = ceilingEntry(key); + if (entry == null) { + return null; + } + return entry.getKey(); + } + + @Override + public Entry<K, V> higherEntry(K key) { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + int index = current.find(key); + + // There's a key exactly equal. + if (index >= 0) { + index += 1; + } else { + index = -(index + 1); + } + + if (index < current.startIndex || index >= current.endIndex) { + return null; + } + return current.entries[index]; + } + + @Override + public K higherKey(K key) { + Map.Entry<K, V> entry = higherEntry(key); + if (entry == null) { + return null; + } + return entry.getKey(); + } + + @Override + public Entry<K, V> firstEntry() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.startIndex]; + } + + @Override + public Entry<K, V> lastEntry() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.endIndex - 1]; + } + + @Override + public int size() { + return holder.getLength(); + } + + @Override + public boolean isEmpty() { + return holder.getLength() == 0; + } + + @Override + public boolean containsKey(Object key) { + ArrayHolder<K, V> current = this.holder; + int index = current.find((K) key); + return index >= 0; + } + + @Override + public V get(Object key) { + + ArrayHolder<K, V> current = this.holder; + int index = current.find((K) key); + if (index >= 0) { + return current.entries[index].getValue(); + } + return null; + } + + @Override + public NavigableSet<K> keySet() { + return new ArrayKeySet<>(this.holder); + } + + @Override + public Collection<V> values() { + return new ArrayValueCollection<>(this.holder); + } + + @Override + public Set<Entry<K, V>> entrySet() { + return new ArrayEntrySet<>(this.holder); + } + + /* + Synchronized write methods. + + Every method should be synchronized. + Only one modification at a time. + + These will be slow. + */ + + + @Override + public synchronized V put(K key, V value) { + ArrayHolder<K, V> current = this.holder; + int index = current.find(key); + COWEntry<K, V> newEntry = new COWEntry<>(key, value); + if (index >= 0) { + this.holder = current.replace(index, newEntry); + return current.entries[index].getValue(); + } else { + this.holder = current.insert(-(index + 1), newEntry); + } + return null; + } + + @Override + public synchronized V remove(Object key) { + + ArrayHolder<K, V> current = this.holder; + int index = current.find((K) key); + if (index >= 0) { + this.holder = current.remove(index); + return current.entries[index].getValue(); + } + return null; + } + + @Override + public synchronized void clear() { + this.holder = new ArrayHolder<>(this.holder.keyComparator, this.holder.comparator); + } + + @Override + public synchronized V putIfAbsent(K key, V value) { + ArrayHolder<K, V> current = this.holder; + int index = current.find(key); + + if (index < 0) { + COWEntry<K, V> newEntry = new COWEntry<>(key, value); + this.holder = current.insert(-(index + 1), newEntry); + return value; + } + return current.entries[index].getValue(); + } + + @Override + public synchronized boolean remove(Object key, Object value) { + ArrayHolder<K, V> current = this.holder; + int index = current.find((K) key); + + if (index >= 0 && current.entries[index].getValue().equals(value)) { + this.holder = current.remove(index); + return true; + } + return false; + } + + @Override + public synchronized boolean replace(K key, V oldValue, V newValue) { + ArrayHolder<K, V> current = this.holder; + int index = current.find(key); + + if (index >= 0 && current.entries[index].getValue().equals(oldValue)) { + COWEntry<K, V> newEntry = new COWEntry<>(key, newValue); + this.holder = current.replace(index, newEntry); + return true; + } + return false; + } + + @Override + public synchronized V replace(K key, V value) { + ArrayHolder<K, V> current = this.holder; + int index = current.find(key); + + if (index >= 0) { + COWEntry<K, V> newEntry = new COWEntry<>(key, value); + this.holder = current.replace(index, newEntry); + return current.entries[index].getValue(); + } + return null; + } + + @Override + public Entry<K, V> pollFirstEntry() { + throw new UnsupportedOperationException(); + } + + @Override + public Entry<K, V> pollLastEntry() { + throw new UnsupportedOperationException(); + } + + @Override + public ConcurrentNavigableMap<K, V> descendingMap() { + throw new UnsupportedOperationException(); + } + + @Override + public NavigableSet<K> navigableKeySet() { + throw new UnsupportedOperationException(); + } + + @Override + public ConcurrentNavigableMap<K, V> subMap(K fromKey, K toKey) { + throw new UnsupportedOperationException(); + } + + @Override + public ConcurrentNavigableMap<K, V> headMap(K toKey) { + throw new UnsupportedOperationException(); + } + + @Override + public ConcurrentNavigableMap<K, V> subMap(K fromKey, + boolean fromInclusive, + K toKey, + boolean toInclusive) { + throw new UnsupportedOperationException(); + } + + @Override + public ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) { + throw new UnsupportedOperationException(); + } + + @Override + public NavigableSet<K> descendingKeySet() { + throw new UnsupportedOperationException(); + } + + private final class ArrayKeySet<K, V> implements NavigableSet<K> { + + private final ArrayHolder<K, V> holder; + + private ArrayKeySet(ArrayHolder<K, V> holder) { + this.holder = holder; + } + + @Override + public int size() { + return holder.getLength(); + } + + @Override + public boolean isEmpty() { + return holder.getLength() == 0; + } + + @Override + public boolean contains(Object o) { + ArrayHolder<K, V> current = this.holder; + + for (int i = current.startIndex; i < current.endIndex; i++) { + if (current.entries[i].getValue().equals(o)) { + return true; + } + } + return false; + } + + @Override + public K lower(K k) { + throw new UnsupportedOperationException(); + } + + @Override + public K floor(K k) { + throw new UnsupportedOperationException(); + } + + @Override + public K ceiling(K k) { + throw new UnsupportedOperationException(); + } + + @Override + public K higher(K k) { + throw new UnsupportedOperationException(); + } + + @Override + public K pollFirst() { + throw new UnsupportedOperationException(); + } + + @Override + public K pollLast() { + throw new UnsupportedOperationException(); + } + + @Override + public Iterator<K> iterator() { + return new ArrayKeyIterator<>(this.holder); + } + + @Override + public NavigableSet<K> descendingSet() { + throw new UnsupportedOperationException(); + } + + @Override + public Iterator<K> descendingIterator() { + throw new UnsupportedOperationException(); + } + + @Override + public NavigableSet<K> subSet(K fromElement, + boolean fromInclusive, + K toElement, + boolean toInclusive) { + throw new UnsupportedOperationException(); + } + + @Override + public NavigableSet<K> headSet(K toElement, boolean inclusive) { + throw new UnsupportedOperationException(); + } + + @Override + public NavigableSet<K> tailSet(K fromElement, boolean inclusive) { + throw new UnsupportedOperationException(); + } + + @Override + public Comparator<? super K> comparator() { + return (Comparator<? super K>) keyComparator; + } + + @Override + public SortedSet<K> subSet(K fromElement, K toElement) { + return null; + } + + @Override + public SortedSet<K> headSet(K toElement) { + return null; + } + + @Override + public SortedSet<K> tailSet(K fromElement) { + return null; + } + + @Override + public K first() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.startIndex].getKey(); + } + + @Override + public K last() { + ArrayHolder<K, V> current = this.holder; + if (current.getLength() == 0) { + return null; + } + return current.entries[current.endIndex - 1].getKey(); + } + + @Override + public Object[] toArray() { + throw new UnsupportedOperationException(); + } + + @Override + public <T> T[] toArray(T[] a) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean add(K k) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean remove(Object o) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean containsAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends K> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean retainAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean removeAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + throw new UnsupportedOperationException(); + } + } + + private final class ArrayValueCollection<K, V> implements Collection<V> { + + private final ArrayHolder<K, V> holder; + + private ArrayValueCollection(ArrayHolder<K, V> holder) { + this.holder = holder; + } + + @Override + public int size() { + return holder.getLength(); + } + + @Override + public boolean isEmpty() { + return holder.getLength() == 0; + } + + @Override + public boolean contains(Object o) { + throw new UnsupportedOperationException(); + } + + @Override + public Iterator<V> iterator() { + return new ArrayValueIterator<>(this.holder); + } + + @Override + public Object[] toArray() { + throw new UnsupportedOperationException(); + } + + @Override + public <T> T[] toArray(T[] a) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean add(V v) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean remove(Object o) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean containsAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends V> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean removeAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean retainAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + throw new UnsupportedOperationException(); + } + + @Override + public boolean equals(Object o) { + return false; + } + + @Override + public int hashCode() { + return 0; + } + } + + private final class ArrayKeyIterator<K, V> implements Iterator<K> { + int index; + private final ArrayHolder<K, V> holder; + + private ArrayKeyIterator(ArrayHolder<K, V> holder) { + this.holder = holder; + index = holder.startIndex; + } + + + @Override + public boolean hasNext() { + return index < holder.endIndex; + } + + @Override + public K next() { + return holder.entries[index++].getKey(); + } + + @Override + public void remove() { + throw new UnsupportedOperationException("remove"); + } + } + + private final class ArrayValueIterator<K, V> implements Iterator<V> { + int index; + private final ArrayHolder<K, V> holder; + + private ArrayValueIterator(ArrayHolder<K, V> holder) { + this.holder = holder; + index = holder.startIndex; + } + + + @Override + public boolean hasNext() { + return index < holder.endIndex; + } + + @Override + public V next() { + return holder.entries[index++].getValue(); + } + + @Override + public void remove() { + throw new UnsupportedOperationException("remove"); + } + } + + private final class ArrayEntryIterator<K, V> implements Iterator<Map.Entry<K, V>> { + + int index; + private final ArrayHolder<K, V> holder; + + private ArrayEntryIterator(ArrayHolder<K, V> holder) { + this.holder = holder; + this.index = holder.startIndex; + } + + @Override + public boolean hasNext() { + return index < holder.endIndex; + } + + @Override + public Entry<K, V> next() { + return holder.entries[index++]; + } + + @Override + public void remove() { + throw new UnsupportedOperationException("remove"); + } + } + + private final class ArrayEntrySet<K, V> implements Set<Map.Entry<K, V>> { + private final ArrayHolder<K, V> holder; + + private ArrayEntrySet(ArrayHolder<K, V> holder) { + this.holder = holder; + } + + @Override + public int size() { + return holder.getLength(); + } + + @Override + public boolean isEmpty() { + return holder.getLength() == 0; + } + + @Override + public boolean contains(Object o) { + return false; + } + + @Override + public Iterator<Entry<K, V>> iterator() { + return new ArrayEntryIterator<>(this.holder); + } + + @Override + public Object[] toArray() { + throw new UnsupportedOperationException(); + } + + @Override + public <T> T[] toArray(T[] a) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean add(Entry<K, V> kvEntry) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean remove(Object o) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean containsAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends Entry<K, V>> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean retainAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public boolean removeAll(Collection<?> c) { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() { + throw new UnsupportedOperationException(); + } + } + + private final static class ArrayHolder<K, V> { + private final COWEntry<K, V>[] entries; + private final int startIndex; + private final int endIndex; + private final Comparator<? super K> keyComparator; + private final Comparator<Map.Entry<K, V>> comparator; + + + int getLength() { + return endIndex - startIndex; + } + + + /** + * Binary search for a given key + * @param needle The key to look for in all of the entries + * @return Same return value as Arrays.binarySearch. + * Positive numbers mean the index. + * Otherwise (-1 * insertion point) - 1 + */ + int find(K needle) { + int begin = startIndex; + int end = endIndex - 1; + + while (begin <= end) { + int mid = begin + ((end - begin) / 2); + K midKey = entries[ mid].key; + int compareRes = keyComparator.compare(midKey, needle); + + // 0 means equals + // We found the key. + if (compareRes == 0) { + return mid; + } else if (compareRes < 0) { + // midKey is less than needle so we need + // to look at farther up + begin = mid + 1; + } else { + // midKey is greater than needle so we + // need to look down. + end = mid - 1; + } + } + + return (-1 * begin) - 1; + } + + ArrayHolder<K, V> replace(int index, COWEntry<K, V> newEntry) { + // TODO should this restart the array back at start index 0 ? + COWEntry<K, V>[] newEntries = entries.clone(); + newEntries[index] = newEntry; + return new ArrayHolder<>(newEntries, startIndex, endIndex, keyComparator, comparator); + } + + ArrayHolder<K, V> remove(int index) { + COWEntry<K,V>[] newEntries = new COWEntry[getLength() - 1]; + System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); + System.arraycopy(this.entries, index + 1, newEntries, index, entries.length - index - 1); + return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); + } + + ArrayHolder<K, V> insert(int index, COWEntry<K, V> newEntry) { + COWEntry<K,V>[] newEntries = new COWEntry[getLength() + 1]; + System.arraycopy(this.entries, startIndex, newEntries, 0, index - startIndex); + newEntries[index] = newEntry; + System.arraycopy(this.entries, index, newEntries, index + 1, getLength() - index); + return new ArrayHolder<>(newEntries, 0, newEntries.length, keyComparator, comparator); + } + + private ArrayHolder( + final Comparator<? super K> keyComparator, + final Comparator<Map.Entry<K, V>> comparator) { + this.endIndex = 0; + this.startIndex = 0; + this.entries = new COWEntry[] {}; + this.keyComparator = keyComparator; + this.comparator = comparator; + } + + private ArrayHolder(COWEntry[] entries, + int startIndex, int endIndex, + final Comparator<? super K> keyComparator, + Comparator<Map.Entry<K, V>> comparator) { + this.entries = entries; + this.startIndex = startIndex; + this.endIndex = endIndex; + this.keyComparator = keyComparator; + this.comparator = comparator; + } + } + + private final static class COWEntry<K, V> implements Map.Entry<K, V> { + K key = null; + V value = null; + + COWEntry(K key, V value) { + this.key = key; + this.value = value; + } + + @Override + public K getKey() { + return key; + } + + @Override + public V getValue() { + return value; + } + + @Override + public V setValue(V value) { + V oldValue = this.value; + this.value = value; + return oldValue; + } + } +} http://git-wip-us.apache.org/repos/asf/hbase/blob/4d5ac316/hbase-common/src/test/java/org/apache/hadoop/hbase/types/TestCopyOnWriteMaps.java ---------------------------------------------------------------------- diff --git a/hbase-common/src/test/java/org/apache/hadoop/hbase/types/TestCopyOnWriteMaps.java b/hbase-common/src/test/java/org/apache/hadoop/hbase/types/TestCopyOnWriteMaps.java new file mode 100644 index 0000000..a3c892a --- /dev/null +++ b/hbase-common/src/test/java/org/apache/hadoop/hbase/types/TestCopyOnWriteMaps.java @@ -0,0 +1,311 @@ +/** + * 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 org.apache.hadoop.hbase.types; + +import org.apache.hadoop.hbase.testclassification.SmallTests; +import org.junit.Before; +import org.junit.Test; +import org.junit.experimental.categories.Category; + +import java.util.Map; +import java.util.concurrent.ConcurrentNavigableMap; +import java.util.concurrent.ConcurrentSkipListMap; +import java.util.concurrent.ThreadLocalRandom; + +import static org.junit.Assert.*; + +@Category(SmallTests.class) +public class TestCopyOnWriteMaps { + + private static final int MAX_RAND = 10 * 1000 * 1000; + private ConcurrentNavigableMap<Long, Long> m; + private ConcurrentSkipListMap<Long, Long> csm; + + @Before + public void setUp() { + m = new CopyOnWriteArrayMap<>(); + csm = new ConcurrentSkipListMap<>(); + + for ( long i = 0 ; i < 10000; i++ ) { + long o = ThreadLocalRandom.current().nextLong(MAX_RAND); + m.put(i, o); + csm.put(i,o); + } + long o = ThreadLocalRandom.current().nextLong(MAX_RAND); + m.put(0L, o); + csm.put(0L,o); + } + + @Test + public void testSize() throws Exception { + assertEquals("Size should always be equal", m.size(), csm.size()); + } + + @Test + public void testIsEmpty() throws Exception { + m.clear(); + assertTrue(m.isEmpty()); + m.put(100L, 100L); + assertFalse(m.isEmpty()); + m.remove(100L); + assertTrue(m.isEmpty()); + } + + @Test + public void testFindOnEmpty() throws Exception { + m.clear(); + assertTrue(m.isEmpty()); + assertNull(m.get(100L)); + assertFalse(m.containsKey(100L)); + assertEquals(0, m.tailMap(100L).entrySet().size()); + } + + + @Test + public void testLowerKey() throws Exception { + + assertEquals(csm.lowerKey(400L), m.lowerKey(400L)); + assertEquals(csm.lowerKey(-1L), m.lowerKey(-1L)); + + for ( int i =0 ; i < 100; i ++) { + Long key = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.lowerKey(key), m.lowerKey(key)); + } + } + + @Test + public void testFloorEntry() throws Exception { + for ( int i =0 ; i < 100; i ++) { + Long key = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.floorEntry(key), m.floorEntry(key)); + } + } + + @Test + public void testFloorKey() throws Exception { + for ( int i =0 ; i < 100; i ++) { + Long key = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.floorKey(key), m.floorKey(key)); + } + } + + @Test + public void testCeilingKey() throws Exception { + + assertEquals(csm.ceilingKey(4000L), m.ceilingKey(4000L)); + assertEquals(csm.ceilingKey(400L), m.ceilingKey(400L)); + assertEquals(csm.ceilingKey(-1L), m.ceilingKey(-1L)); + + for ( int i =0 ; i < 100; i ++) { + Long key = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.ceilingKey(key), m.ceilingKey(key)); + } + } + + @Test + public void testHigherKey() throws Exception { + + assertEquals(csm.higherKey(4000L), m.higherKey(4000L)); + assertEquals(csm.higherKey(400L), m.higherKey(400L)); + assertEquals(csm.higherKey(-1L), m.higherKey(-1L)); + + for ( int i =0 ; i < 100; i ++) { + Long key = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.higherKey(key), m.higherKey(key)); + } + } + + @Test + public void testRemove() throws Exception { + for (Map.Entry<Long, Long> e:csm.entrySet()) { + assertEquals(csm.remove(e.getKey()), m.remove(e.getKey())); + assertEquals(null, m.remove(e.getKey())); + } + } + + @Test + public void testReplace() throws Exception { + for (Map.Entry<Long, Long> e:csm.entrySet()) { + Long newValue = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.replace(e.getKey(), newValue), m.replace(e.getKey(), newValue)); + } + assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); + } + + @Test + public void testReplace1() throws Exception { + for (Map.Entry<Long, Long> e: csm.entrySet()) { + Long newValue = ThreadLocalRandom.current().nextLong(); + assertEquals(csm.replace(e.getKey(), e.getValue() + 1, newValue), + m.replace(e.getKey(), e.getValue() + 1, newValue)); + assertEquals(csm.replace(e.getKey(), e.getValue(), newValue), + m.replace(e.getKey(), e.getValue(), newValue)); + assertEquals(newValue, m.get(e.getKey())); + assertEquals(csm.get(e.getKey()), m.get(e.getKey())); + } + assertEquals(null, m.replace(MAX_RAND + 100L, ThreadLocalRandom.current().nextLong())); + } + + @Test + public void testMultiAdd() throws InterruptedException { + + Thread[] threads = new Thread[10]; + for ( int i =0 ; i<threads.length; i++) { + threads[i] = new Thread(new Runnable() { + @Override + public void run() { + for ( int j = 0; j < 5000; j++) { + m.put(ThreadLocalRandom.current().nextLong(), + ThreadLocalRandom.current().nextLong()); + } + } + }); + } + + for (Thread thread1 : threads) { + thread1.start(); + } + + for (Thread thread2 : threads) { + thread2.join(); + } + } + + @Test + public void testFirstKey() throws Exception { + assertEquals(csm.firstKey(), m.firstKey()); + } + + @Test + public void testLastKey() throws Exception { + assertEquals(csm.lastKey(), m.lastKey()); + } + + @Test + public void testFirstEntry() throws Exception { + assertEquals(csm.firstEntry().getKey(), m.firstEntry().getKey()); + assertEquals(csm.firstEntry().getValue(), m.firstEntry().getValue()); + assertEquals(csm.firstEntry(), m.firstEntry()); + } + + @Test + public void testLastEntry() throws Exception { + assertEquals(csm.lastEntry().getKey(), m.lastEntry().getKey()); + assertEquals(csm.lastEntry().getValue(), m.lastEntry().getValue()); + assertEquals(csm.lastEntry(), m.lastEntry()); + } + + @Test + public void testKeys() throws Exception { + for (Long key:csm.keySet()) { + //assertTrue(m.containsKey(key)); + assertNotNull(m.get(key)); + assertNotNull(m.remove(key)); + assertNull(m.get(key)); + } + } + + @Test + public void testValues() throws Exception { + for (Long value:m.values()) { + assertTrue(csm.values().contains(value)); + assertTrue(m.containsValue(value)); + } + } + + @Test + public void testTailMap() throws Exception { + Map<Long, Long> fromCsm = csm.tailMap(50L); + Map<Long, Long> fromM = m.tailMap(50L); + assertEquals(fromCsm, fromM); + for (Long value:m.keySet()) { + assertEquals(csm.tailMap(value), m.tailMap(value)); + } + + for ( long i = 0 ; i < 100; i++ ) { + long o = ThreadLocalRandom.current().nextLong(MAX_RAND); + assertEquals(csm.tailMap(o), m.tailMap(o)); + } + } + + @Test + public void testTailMapExclusive() throws Exception { + m.clear(); + m.put(100L, 100L); + m.put(101L, 101L); + m.put(101L, 101L); + m.put(103L, 103L); + m.put(99L, 99L); + m.put(102L, 102L); + + long n = 100L; + CopyOnWriteArrayMap<Long,Long> tm99 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(99L, false); + for (Map.Entry<Long,Long> e:tm99.entrySet()) { + assertEquals(new Long(n), e.getKey()); + assertEquals(new Long(n), e.getValue()); + n++; + } + } + + @Test + public void testTailMapInclusive() throws Exception { + m.clear(); + m.put(100L, 100L); + m.put(101L, 101L); + m.put(101L, 101L); + m.put(103L, 103L); + m.put(99L, 99L); + m.put(102L, 102L); + + long n = 102; + CopyOnWriteArrayMap<Long,Long> tm102 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(102L, true); + for (Map.Entry<Long,Long> e:tm102.entrySet()) { + assertEquals(new Long(n), e.getKey()); + assertEquals(new Long(n), e.getValue()); + n++; + } + n = 99; + CopyOnWriteArrayMap<Long,Long> tm98 = (CopyOnWriteArrayMap<Long, Long>) m.tailMap(98L, true); + for (Map.Entry<Long,Long> e:tm98.entrySet()) { + assertEquals(new Long(n), e.getKey()); + assertEquals(new Long(n), e.getValue()); + n++; + } + } + + @Test + public void testPut() throws Exception { + m.clear(); + m.put(100L, 100L); + m.put(101L, 101L); + m.put(101L, 101L); + m.put(103L, 103L); + m.put(99L, 99L); + m.put(102L, 102L); + long n = 99; + + for (Map.Entry<Long, Long> e:m.entrySet()) { + assertEquals(new Long(n), e.getKey()); + assertEquals(new Long(n), e.getValue()); + n++; + } + assertEquals(5, m.size()); + assertEquals(false, m.isEmpty()); + } +} \ No newline at end of file
