hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From syuanji...@apache.org
Subject [03/26] hbase git commit: HBASE-14708 Use copy on write Map for region location cache
Date Thu, 19 Nov 2015 07:33:37 GMT
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/a591df10
Tree: http://git-wip-us.apache.org/repos/asf/hbase/tree/a591df10
Diff: http://git-wip-us.apache.org/repos/asf/hbase/diff/a591df10

Branch: refs/heads/hbase-12439
Commit: a591df1073c81a0fd1029f4a0db62d7ef8a95207
Parents: a48d309
Author: Elliott Clark <eclark@apache.org>
Authored: Tue Oct 27 12:16:37 2015 -0700
Committer: Elliott Clark <eclark@apache.org>
Committed: Tue Nov 17 10:52:43 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 | 312 ++++++
 4 files changed, 1300 insertions(+), 15 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/hbase/blob/a591df10/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 a1303e6..3d40c70 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
@@ -972,7 +972,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/a591df10/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 b23ca70..bec4845 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;
@@ -35,6 +34,7 @@ import org.apache.hadoop.hbase.RegionLocations;
 import org.apache.hadoop.hbase.ServerName;
 import org.apache.hadoop.hbase.TableName;
 import org.apache.hadoop.hbase.classification.InterfaceAudience;
+import org.apache.hadoop.hbase.types.CopyOnWriteArrayMap;
 import org.apache.hadoop.hbase.util.Bytes;
 
 /**
@@ -48,16 +48,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;
 
@@ -69,13 +69,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);
@@ -194,15 +191,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/a591df10/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/a591df10/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..2d20fb2
--- /dev/null
+++ b/hbase-common/src/test/java/org/apache/hadoop/hbase/types/TestCopyOnWriteMaps.java
@@ -0,0 +1,312 @@
+/**
+ * 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.MiscTests;
+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({MiscTests.class, 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


Mime
View raw message