diff --git a/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMap.java b/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMap.java
index c6d300c..af2bb74 100644
--- a/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMap.java
+++ b/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMap.java
@@ -20,6 +20,7 @@
 import com.google.common.cache.CacheLoader;
 import com.google.common.cache.LoadingCache;
 import com.google.common.collect.Maps;
+
 import org.onlab.util.HexString;
 import org.onlab.util.SharedExecutors;
 import org.onlab.util.Tools;
@@ -33,6 +34,7 @@
 import org.slf4j.Logger;
 
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Objects;
@@ -92,18 +94,25 @@
     private static final String ERROR_NULL_KEY = "Key cannot be null";
     private static final String ERROR_NULL_VALUE = "Null values are not allowed";
 
-    private final LoadingCache<K, String> keyCache = CacheBuilder.newBuilder()
+    // String representation of serialized byte[] -> original key Object
+    private final LoadingCache<String, K> keyCache = CacheBuilder.newBuilder()
             .softValues()
-            .build(new CacheLoader<K, String>() {
+            .build(new CacheLoader<String, K>() {
 
                 @Override
-                public String load(K key) {
-                    return HexString.toHexString(serializer.encode(key));
+                public K load(String key) {
+                    return serializer.decode(HexString.fromHexString(key));
                 }
             });
 
+    protected String sK(K key) {
+        String s = HexString.toHexString(serializer.encode(key));
+        keyCache.put(s, key);
+        return s;
+    }
+
     protected K dK(String key) {
-        return serializer.decode(HexString.fromHexString(key));
+        return keyCache.getUnchecked(key);
     }
 
     public DefaultAsyncConsistentMap(String name,
@@ -207,7 +216,7 @@
     public CompletableFuture<Boolean> containsKey(K key) {
         checkNotNull(key, ERROR_NULL_KEY);
         final MeteringAgent.Context timer = monitor.startTimer(CONTAINS_KEY);
-        return database.mapContainsKey(name, keyCache.getUnchecked(key))
+        return database.mapContainsKey(name, sK(key))
                 .whenComplete((r, e) -> timer.stop(e));
     }
 
@@ -223,7 +232,7 @@
     public CompletableFuture<Versioned<V>> get(K key) {
         checkNotNull(key, ERROR_NULL_KEY);
         final MeteringAgent.Context timer = monitor.startTimer(GET);
-        return database.mapGet(name, keyCache.getUnchecked(key))
+        return database.mapGet(name, sK(key))
                 .whenComplete((r, e) -> timer.stop(e))
                 .thenApply(v -> v != null ? v.map(serializer::decode) : null);
     }
@@ -328,10 +337,7 @@
     public CompletableFuture<Set<K>> keySet() {
         final MeteringAgent.Context timer = monitor.startTimer(KEY_SET);
         return database.mapKeySet(name)
-                .thenApply(s -> s
-                        .stream()
-                        .map(this::dK)
-                        .collect(Collectors.toSet()))
+                .thenApply(s -> newMappingKeySet(s))
                 .whenComplete((r, e) -> timer.stop(e));
     }
 
@@ -351,10 +357,7 @@
         final MeteringAgent.Context timer = monitor.startTimer(ENTRY_SET);
         return database.mapEntrySet(name)
                 .whenComplete((r, e) -> timer.stop(e))
-                .thenApply(s -> s
-                        .stream()
-                        .map(this::mapRawEntry)
-                        .collect(Collectors.toSet()));
+                .thenApply(s -> newMappingEntrySet(s));
     }
 
     @Override
@@ -413,17 +416,31 @@
         checkIfUnmodifiable();
     }
 
+    private Set<K> newMappingKeySet(Set<String> s) {
+        return new MappingSet<>(s, Collections::unmodifiableSet,
+                                this::sK, this::dK);
+    }
+
+    private Set<Entry<K, Versioned<V>>> newMappingEntrySet(Set<Entry<String, Versioned<byte[]>>> s) {
+        return new MappingSet<>(s, Collections::unmodifiableSet,
+                                this::reverseMapRawEntry, this::mapRawEntry);
+    }
+
     private Map.Entry<K, Versioned<V>> mapRawEntry(Map.Entry<String, Versioned<byte[]>> e) {
         return Maps.immutableEntry(dK(e.getKey()), e.getValue().<V>map(serializer::decode));
     }
 
+    private Map.Entry<String, Versioned<byte[]>> reverseMapRawEntry(Map.Entry<K, Versioned<V>> e) {
+        return Maps.immutableEntry(sK(e.getKey()), e.getValue().map(serializer::encode));
+    }
+
     private CompletableFuture<UpdateResult<K, V>> updateAndGet(K key,
                                                                Match<V> oldValueMatch,
                                                                Match<Long> oldVersionMatch,
                                                                V value) {
         beforeUpdate(key);
         return database.mapUpdate(name,
-                keyCache.getUnchecked(key),
+                sK(key),
                 oldValueMatch.map(serializer::encode),
                 oldVersionMatch,
                 value == null ? null : serializer.encode(value))
diff --git a/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/MappingSet.java b/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/MappingSet.java
new file mode 100644
index 0000000..9bf80a7
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onosproject/store/consistent/impl/MappingSet.java
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2015 Open Networking Laboratory
+ *
+ * Licensed 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.onosproject.store.consistent.impl;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+
+import com.google.common.collect.Iterators;
+
+/**
+ * Set view backed by Set with element type {@code <BACK>} but returns
+ * element as {@code <OUT>} for convenience.
+ *
+ * @param <BACK> Backing {@link Set} element type.
+ *        MappingSet will follow this type's equality behavior.
+ * @param <OUT> external facing element type.
+ *        MappingSet will ignores equality defined by this type.
+ */
+class MappingSet<BACK, OUT> implements Set<OUT> {
+
+    private final Set<BACK> backedSet;
+    private final Function<OUT, BACK> toBack;
+    private final Function<BACK, OUT> toOut;
+
+    public MappingSet(Set<BACK> backedSet,
+                      Function<Set<BACK>, Set<BACK>> supplier,
+                      Function<OUT, BACK> toBack, Function<BACK, OUT> toOut) {
+        this.backedSet = supplier.apply(backedSet);
+        this.toBack = toBack;
+        this.toOut = toOut;
+    }
+
+    @Override
+    public int size() {
+        return backedSet.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return backedSet.isEmpty();
+    }
+
+    @Override
+    public boolean contains(Object o) {
+        return backedSet.contains(toBack.apply((OUT) o));
+    }
+
+    @Override
+    public Iterator<OUT> iterator() {
+        return Iterators.transform(backedSet.iterator(), toOut::apply);
+    }
+
+    @Override
+    public Object[] toArray() {
+        return backedSet.stream()
+                .map(toOut)
+                .toArray();
+    }
+
+    @Override
+    public <T> T[] toArray(T[] a) {
+        return backedSet.stream()
+                .map(toOut)
+                .toArray(size -> {
+                    if (size < a.length) {
+                        return (T[]) new Object[size];
+                    } else {
+                        Arrays.fill(a, null);
+                        return a;
+                    }
+                });
+    }
+
+    @Override
+    public boolean add(OUT e) {
+        return backedSet.add(toBack.apply(e));
+    }
+
+    @Override
+    public boolean remove(Object o) {
+        return backedSet.remove(toBack.apply((OUT) o));
+    }
+
+    @Override
+    public boolean containsAll(Collection<?> c) {
+        return c.stream()
+            .map(e -> toBack.apply((OUT) e))
+            .allMatch(backedSet::contains);
+    }
+
+    @Override
+    public boolean addAll(Collection<? extends OUT> c) {
+        return backedSet.addAll(c.stream().map(toBack).collect(Collectors.toList()));
+    }
+
+    @Override
+    public boolean retainAll(Collection<?> c) {
+        return backedSet.retainAll(c.stream()
+                .map(x -> toBack.apply((OUT) x))
+                .collect(Collectors.toList()));
+    }
+
+    @Override
+    public boolean removeAll(Collection<?> c) {
+        return backedSet.removeAll(c.stream()
+                .map(x -> toBack.apply((OUT) x))
+                .collect(Collectors.toList()));
+    }
+
+    @Override
+    public void clear() {
+        backedSet.clear();
+    }
+}
diff --git a/core/store/dist/src/test/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMapTest.java b/core/store/dist/src/test/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMapTest.java
new file mode 100644
index 0000000..3f6402c
--- /dev/null
+++ b/core/store/dist/src/test/java/org/onosproject/store/consistent/impl/DefaultAsyncConsistentMapTest.java
@@ -0,0 +1,369 @@
+/*
+ * Copyright 2015 Open Networking Laboratory
+ *
+ * Licensed 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.onosproject.store.consistent.impl;
+
+import static java.util.Collections.unmodifiableCollection;
+import static java.util.Collections.unmodifiableSet;
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.*;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Objects;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.function.Consumer;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.onosproject.core.ApplicationId;
+import org.onosproject.core.DefaultApplicationId;
+import org.onosproject.store.service.Serializer;
+import org.onosproject.store.service.Transaction;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import net.kuujo.copycat.Task;
+import net.kuujo.copycat.cluster.Cluster;
+import net.kuujo.copycat.resource.ResourceState;
+
+/**
+ *
+ */
+public class DefaultAsyncConsistentMapTest {
+
+    private static final ApplicationId APP_ID = new DefaultApplicationId(42, "what");
+
+    private static final TestData KEY1A = new TestData("One", "a");
+    private static final TestData KEY1B = new TestData("One", "b");
+
+    private static final TestData VALUE2A = new TestData("Two", "a");
+    private static final TestData VALUE2B = new TestData("Two", "b");
+
+    @Before
+    public void setUp() throws Exception {
+    }
+
+    @After
+    public void tearDown() throws Exception {
+    }
+
+    @Test
+    public void testKeySet() throws Exception {
+        DefaultAsyncConsistentMap<TestData, TestData> map;
+        String name = "map_name";
+        Database database = new TestDatabase();
+        Serializer serializer = Serializer.forTypes(TestData.class);
+
+        map = new DefaultAsyncConsistentMap<>(name, APP_ID, database, serializer,
+                                            false, false, false);
+        map.put(KEY1A, VALUE2A);
+        map.put(KEY1B, VALUE2A);
+
+        Set<TestData> set = map.keySet().get();
+        assertEquals("Should contain 2 keys",
+                2, set.size());
+        assertThat(set.contains(KEY1A), is(true));
+        assertThat(set.contains(KEY1B), is(true));
+        assertThat(set.contains(new TestData("One", "a")), is(true));
+    }
+
+    @Test
+    public void testEntrySet() throws Exception {
+        DefaultAsyncConsistentMap<TestData, TestData> map;
+        String name = "map_name";
+        Database database = new TestDatabase();
+        Serializer serializer = Serializer.forTypes(TestData.class);
+
+        map = new DefaultAsyncConsistentMap<>(name, APP_ID, database, serializer,
+                                            false, false, false);
+        map.put(KEY1A, VALUE2A);
+        map.put(KEY1B, VALUE2A);
+
+        assertEquals("Should contain 2 entry",
+                     2,
+                     map.entrySet().get().size());
+    }
+
+    /**
+     * Object to be used as a test data.
+     *
+     * {@link Object#equals(Object)} use only part of it's fields.
+     *
+     * As a result there can be 2 instances which the
+     * serialized bytes are not-equal but
+     * {@link Object#equals(Object)}-wise they are equal.
+     */
+    public static class TestData {
+
+        private final String theKey;
+
+        @SuppressWarnings("unused")
+        private final String notUsedForEquals;
+
+        public TestData(String theKey, String notUsedForEquals) {
+            this.theKey = theKey;
+            this.notUsedForEquals = notUsedForEquals;
+        }
+
+        @Override
+        public int hashCode() {
+            return Objects.hashCode(theKey);
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj instanceof TestData) {
+                TestData that = (TestData) obj;
+                return Objects.equals(this.theKey, that.theKey);
+            }
+            return false;
+        }
+
+        @Override
+        public String toString() {
+            return MoreObjects.toStringHelper(this)
+                    .add("theKey", theKey)
+                    .add("notUsedForEquals", notUsedForEquals)
+                    .toString();
+        }
+    }
+
+    /**
+     * {@link Database} implementation for testing.
+     *
+     * There is only 1 backing Map, {@code mapName} will be ignored.
+     */
+    public class TestDatabase implements Database {
+
+        Map<String, Versioned<byte[]>> map = new ConcurrentHashMap<>();
+
+        @Override
+        public CompletableFuture<Set<String>> maps() {
+            return CompletableFuture.completedFuture(ImmutableSet.of());
+        }
+
+        @Override
+        public CompletableFuture<Map<String, Long>> counters() {
+            return CompletableFuture.completedFuture(ImmutableMap.of());
+        }
+
+        @Override
+        public CompletableFuture<Integer> mapSize(String mapName) {
+            return CompletableFuture.completedFuture(map.size());
+        }
+
+        @Override
+        public CompletableFuture<Boolean> mapIsEmpty(String mapName) {
+            return CompletableFuture.completedFuture(map.isEmpty());
+        }
+
+        @Override
+        public CompletableFuture<Boolean> mapContainsKey(String mapName,
+                                                         String key) {
+            return CompletableFuture.completedFuture(map.containsKey(key));
+        }
+
+        @Override
+        public CompletableFuture<Boolean> mapContainsValue(String mapName,
+                                                           byte[] value) {
+            return CompletableFuture.completedFuture(map.containsValue(value));
+        }
+
+        @Override
+        public CompletableFuture<Versioned<byte[]>> mapGet(String mapName,
+                                                           String key) {
+            return CompletableFuture.completedFuture(map.get(key));
+        }
+
+        @Override
+        public synchronized CompletableFuture<Result<UpdateResult<String, byte[]>>> mapUpdate(String mapName,
+                                                                                 String key,
+                                                                                 Match<byte[]> valueMatch,
+                                                                                 Match<Long> versionMatch,
+                                                                                 byte[] value) {
+
+            boolean updated = false;
+            final Versioned<byte[]> oldValue;
+            final Versioned<byte[]> newValue;
+
+            Versioned<byte[]> old = map.getOrDefault(key, new Versioned<byte[]>(null, 0));
+            if (valueMatch.matches(old.value()) && versionMatch.matches(old.version())) {
+                updated = true;
+                oldValue = old;
+                newValue = new Versioned<>(value, old.version() + 1);
+                map.put(key, newValue);
+            } else {
+                updated = false;
+                oldValue = old;
+                newValue = old;
+            }
+            return CompletableFuture.completedFuture(
+                             Result.ok(new UpdateResult<String, byte[]>(updated,
+                                            mapName, key, oldValue, newValue)));
+        }
+
+        @Override
+        public CompletableFuture<Result<Void>> mapClear(String mapName) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Set<String>> mapKeySet(String mapName) {
+            return CompletableFuture.completedFuture(unmodifiableSet(map.keySet()));
+        }
+
+        @Override
+        public CompletableFuture<Collection<Versioned<byte[]>>> mapValues(String mapName) {
+            return CompletableFuture.completedFuture(unmodifiableCollection(map.values()));
+        }
+
+        @Override
+        public CompletableFuture<Set<Entry<String, Versioned<byte[]>>>> mapEntrySet(String mapName) {
+            return CompletableFuture.completedFuture(unmodifiableSet(map.entrySet()));
+        }
+
+        @Override
+        public CompletableFuture<Long> counterAddAndGet(String counterName,
+                                                        long delta) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Long> counterGetAndAdd(String counterName,
+                                                        long delta) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Void> counterSet(String counterName,
+                                                  long value) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Boolean> counterCompareAndSet(String counterName,
+                                                               long expectedValue,
+                                                               long update) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Long> counterGet(String counterName) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Long> queueSize(String queueName) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Void> queuePush(String queueName,
+                                                 byte[] entry) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<byte[]> queuePop(String queueName) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<byte[]> queuePeek(String queueName) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<CommitResponse> prepareAndCommit(Transaction transaction) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Boolean> prepare(Transaction transaction) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<CommitResponse> commit(Transaction transaction) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Boolean> rollback(Transaction transaction) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public String name() {
+            return "name";
+        }
+
+        @Override
+        public ResourceState state() {
+            return ResourceState.HEALTHY;
+        }
+
+        @Override
+        public Cluster cluster() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public Database addStartupTask(Task<CompletableFuture<Void>> task) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public Database addShutdownTask(Task<CompletableFuture<Void>> task) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public CompletableFuture<Database> open() {
+            return CompletableFuture.completedFuture(this);
+        }
+
+        @Override
+        public boolean isOpen() {
+            return true;
+        }
+
+        @Override
+        public CompletableFuture<Void> close() {
+            return CompletableFuture.completedFuture(null);
+        }
+
+        @Override
+        public boolean isClosed() {
+            return false;
+        }
+
+        @Override
+        public void registerConsumer(Consumer<StateMachineUpdate> consumer) {
+        }
+
+        @Override
+        public void unregisterConsumer(Consumer<StateMachineUpdate> consumer) {
+        }
+    }
+
+}