Repository: graphhopper/graphhopper
Pull request #1784 (2019-11-11 08:07:01)

String index
This PR introduces a flexible storage to store key-value String pairs for every edge and will replace the NameIndex, so that we can store translated name tags ala name_ru, ref-tags separately or even arbitrary tags per edge. (It is basically a Map ala `Map<Long, Map<String, String>>` except that you cannot define Long when you put it and get it returned when you add the `Map<String, String>`.)

This PR only introduces the index, we still need a method like `edge.putExtra("key", "value")` and we could also introduce a generic StringPathDetails and replace StreetNameDetails. Related also to #1772.

The index has the following limitations:

 * append-only storage. I.e. updating existing key-value pairs for one edge is only possible via allocating more space
 * supports up to `32768-1` unique keys (max length of each is 65k) and holds them in-memory
 * arbitrary values with a length of 255 bytes (UTF-8). Is mostly sufficient, also for names.
 * it does a simple duplicate detection to reduce storage size, but does this only for identical keys or identical values or fully equal entry maps (no partial strings)

TODOs:

 - [x] the simpleCache brings 10% smaller size on disk but makes everything a bit more complicated
 - [x] store ints even if it needs to be split over 2 segments => use get+setBytes (or use padding?)
 - [x] is storing all tags already possible? Yes! How large does the index get => 221MB for Germany i.e. increases the total size by only 15% (5310 unique keys - make sure to exclude our artificial tags like estimated_center/distance and duration. Maybe also all tags that are already handled in our parsers)
 - [x] compare speed for bigger and smaller maps - looks good
 - [x] improve storage size further for larger maps like Germany. Trying to use [lz4-java](https://github.com/graphhopper/graphhopper/compare/getall_prototype...lz4_string_index) failed and even increased the size for the compressed data. But a very interesting tool is [zstd that can be trained](https://github.com/facebook/zstd/#the-case-for-small-data-compression) to specific data which would be likely beneficial for OSM data. A similar tool is http://ed-von-schleck.github.io/shoco/ but for now we'll keep every as it is.


Patch:
diff --git a/NOTICE.md b/NOTICE.md
index d834568aa..618234ebc 100644
--- a/NOTICE.md
+++ b/NOTICE.md
@@ -16,6 +16,7 @@ The core module includes the following software:
  * java-string-similarity - we copied the implementation of JaroWinkler (MIT license)
  * com.fasterxml.jackson.core:jackson-annotations (Apache License)
  * org.locationtech:jts (EDL), see #1039
+ * AngleCalc.atan2 from Jim Shima, 1999 (public domain)
 
 reader-osm:
 
diff --git a/api/src/main/java/com/graphhopper/util/AngleCalc.java b/api/src/main/java/com/graphhopper/util/AngleCalc.java
index 195da6032..8f7473db4 100644
--- a/api/src/main/java/com/graphhopper/util/AngleCalc.java
+++ b/api/src/main/java/com/graphhopper/util/AngleCalc.java
@@ -23,7 +23,7 @@ import static java.lang.Math.toRadians;
 /**
  * Calculates the angle of a turn, defined by three points. The fast atan2 method is from Jim Shima,
  * 1999, http://www.dspguru.com/dsp/tricks/fixed-point-atan2-with-self-normalization
- * <p>
+ * and stands under public domain.
  *
  * @author Johannes Pelzer
  * @author Peter Karich
diff --git a/core/src/main/java/com/graphhopper/search/NameIndex.java b/core/src/main/java/com/graphhopper/search/NameIndex.java
deleted file mode 100644
index 86ae29188..000000000
--- a/core/src/main/java/com/graphhopper/search/NameIndex.java
+++ /dev/null
@@ -1,151 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH 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 com.graphhopper.search;
-
-import com.graphhopper.storage.DataAccess;
-import com.graphhopper.storage.Directory;
-import com.graphhopper.storage.Storable;
-import com.graphhopper.util.BitUtil;
-import com.graphhopper.util.Helper;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-/**
- * @author Ottavio Campana
- * @author Peter Karich
- */
-public class NameIndex implements Storable<NameIndex> {
-    private static final Logger logger = LoggerFactory.getLogger(NameIndex.class);
-    private static final long START_POINTER = 1;
-    private final DataAccess names;
-    private long bytePointer = START_POINTER;
-    // minor optimization for the previous stored name
-    private String lastName;
-    private long lastIndex;
-
-    public NameIndex(Directory dir) {
-        names = dir.find("names");
-    }
-
-    @Override
-    public NameIndex create(long initBytes) {
-        names.create(initBytes);
-        return this;
-    }
-
-    @Override
-    public boolean loadExisting() {
-        if (names.loadExisting()) {
-            bytePointer = BitUtil.LITTLE.combineIntsToLong(names.getHeader(0), names.getHeader(4));
-            return true;
-        }
-
-        return false;
-    }
-
-    /**
-     * @return the byte pointer to the name
-     */
-    public long put(String name) {
-        if (name == null || name.isEmpty()) {
-            return 0;
-        }
-        if (name.equals(lastName)) {
-            return lastIndex;
-        }
-        byte[] bytes = getBytes(name);
-        long oldPointer = bytePointer;
-        names.ensureCapacity(bytePointer + 1 + bytes.length);
-        byte[] sizeBytes = new byte[]{
-                (byte) bytes.length
-        };
-        names.setBytes(bytePointer, sizeBytes, sizeBytes.length);
-        bytePointer++;
-        names.setBytes(bytePointer, bytes, bytes.length);
-        bytePointer += bytes.length;
-        lastName = name;
-        lastIndex = oldPointer;
-        return oldPointer;
-    }
-
-    private byte[] getBytes(String name) {
-        byte[] bytes = null;
-        for (int i = 0; i < 2; i++) {
-            bytes = name.getBytes(Helper.UTF_CS);
-            // we have to store the size of the array into *one* byte
-            if (bytes.length > 255) {
-                String newName = name.substring(0, 256 / 4);
-                logger.info("Way name is too long: " + name + " truncated to " + newName);
-                name = newName;
-                continue;
-            }
-            break;
-        }
-        if (bytes.length > 255) {
-            // really make sure no such problem exists
-            throw new IllegalStateException("Way name is too long: " + name);
-        }
-        return bytes;
-    }
-
-    public String get(long pointer) {
-        if (pointer < 0)
-            throw new IllegalStateException("Pointer to access NameIndex cannot be negative:" + pointer);
-
-        // default
-        if (pointer == 0)
-            return "";
-
-        byte[] sizeBytes = new byte[1];
-        names.getBytes(pointer, sizeBytes, 1);
-        int size = sizeBytes[0] & 0xFF;
-        byte[] bytes = new byte[size];
-        names.getBytes(pointer + sizeBytes.length, bytes, size);
-        return new String(bytes, Helper.UTF_CS);
-    }
-
-    @Override
-    public void flush() {
-        names.setHeader(0, BitUtil.LITTLE.getIntLow(bytePointer));
-        names.setHeader(4, BitUtil.LITTLE.getIntHigh(bytePointer));
-        names.flush();
-    }
-
-    @Override
-    public void close() {
-        names.close();
-    }
-
-    @Override
-    public boolean isClosed() {
-        return names.isClosed();
-    }
-
-    public void setSegmentSize(int segments) {
-        names.setSegmentSize(segments);
-    }
-
-    @Override
-    public long getCapacity() {
-        return names.getCapacity();
-    }
-
-    public void copyTo(NameIndex nameIndex) {
-        names.copyTo(nameIndex.names);
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/search/StringIndex.java b/core/src/main/java/com/graphhopper/search/StringIndex.java
new file mode 100644
index 000000000..907b3561e
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/search/StringIndex.java
@@ -0,0 +1,350 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH 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 com.graphhopper.search;
+
+import com.graphhopper.storage.DataAccess;
+import com.graphhopper.storage.Directory;
+import com.graphhopper.storage.Storable;
+import com.graphhopper.util.BitUtil;
+import com.graphhopper.util.Helper;
+
+import java.util.*;
+
+/**
+ * @author Peter Karich
+ */
+public class StringIndex implements Storable<StringIndex> {
+    private static final long EMPTY_POINTER = 0, START_POINTER = 1;
+    // Store the key index in 2 bytes. Use negative values for marking the value as duplicate.
+    static final int MAX_UNIQUE_KEYS = (1 << 15);
+    // Store string value as byte array and store the length into 1 byte
+    private static final int MAX_LENGTH = (1 << 8) - 1;
+    boolean throwExceptionIfTooLong = false;
+    private final DataAccess keys;
+    // storage layout per entry:
+    // 1 byte    | 2 bytes  | 1 byte      | x    | 2 bytes  | 1 byte      | x    | 2 bytes  (dup example) | 4 bytes | ...
+    // vals count| key_idx_0| val_length_0| val_0| key_idx_1| val_length_1| val_1| -key_idx_2             | delta_2 | key_idx_3 | val_length_3 | val_3
+    // Drawback: we need to loop through the entries to get the start of val_x.
+    // Note, that we detect duplicate values via smallCache and then use the negative key index as 'duplicate' marker.
+    // We then store only the delta (signed int) instead the absolute unsigned long value to reduce memory usage when duplicate entries.
+    private final DataAccess vals;
+    // array.indexOf could be faster than hashmap.get if not too many keys or even sort keys and use binarySearch
+    private final Map<String, Integer> keysInMem = new LinkedHashMap<>();
+    private final List<String> keyList = new ArrayList<>();
+    private final Map<String, Long> smallCache;
+    private long bytePointer = START_POINTER;
+    private long lastEntryPointer = -1;
+    private Map<String, String> lastEntryMap;
+
+    public StringIndex(Directory dir) {
+        this(dir, 1000);
+    }
+
+    /**
+     * Specify a larger cacheSize to reduce disk usage. Note that this increases the memory usage of this object.
+     */
+    public StringIndex(Directory dir, final int cacheSize) {
+        keys = dir.find("string_index_keys");
+        keys.setSegmentSize(10 * 1024);
+        vals = dir.find("string_index_vals");
+        smallCache = new LinkedHashMap<String, Long>(cacheSize, 0.75f, true) {
+            @Override
+            protected boolean removeEldestEntry(Map.Entry<String, Long> entry) {
+                return size() > cacheSize;
+            }
+        };
+    }
+
+    @Override
+    public StringIndex create(long initBytes) {
+        keys.create(initBytes);
+        vals.create(initBytes);
+        // add special empty case to have a reliable duplicate detection via negative keyIndex
+        keysInMem.put("", 0);
+        keyList.add("");
+        return this;
+    }
+
+    @Override
+    public boolean loadExisting() {
+        if (vals.loadExisting()) {
+            if (!keys.loadExisting())
+                throw new IllegalStateException("Loaded values but cannot load keys");
+            bytePointer = BitUtil.LITTLE.combineIntsToLong(vals.getHeader(0), vals.getHeader(4));
+
+            // load keys into memory
+            int count = keys.getShort(0);
+            long keyBytePointer = 2;
+            for (int i = 0; i < count; i++) {
+                int keyLength = keys.getShort(keyBytePointer);
+                keyBytePointer += 2;
+
+                byte[] keyBytes = new byte[keyLength];
+                keys.getBytes(keyBytePointer, keyBytes, keyLength);
+                String valueStr = new String(keyBytes, Helper.UTF_CS);
+                keysInMem.put(valueStr, keysInMem.size());
+                keyList.add(valueStr);
+                keyBytePointer += keyLength;
+            }
+            return true;
+        }
+
+        return false;
+    }
+
+    Set<String> getKeys() {
+        return keysInMem.keySet();
+    }
+
+    /**
+     * This method writes the specified key-value pairs into the storage.
+     *
+     * @return entryPointer to later fetch the entryMap via get
+     */
+    public long add(Map<String, String> entryMap) {
+        if (entryMap.isEmpty())
+            return EMPTY_POINTER;
+        else if (entryMap.size() > 200)
+            throw new IllegalArgumentException("Cannot store more than 200 entries per entry");
+
+        // This is a very important compressing mechanism due to the nature of OSM. Make this faster via precalculated hastcodes?
+        if (entryMap.equals(lastEntryMap))
+            return lastEntryPointer;
+
+        lastEntryMap = entryMap;
+        lastEntryPointer = bytePointer;
+        // while adding there could be exceptions and we need to avoid that the bytePointer is modified
+        long currentPointer = bytePointer;
+
+        vals.ensureCapacity(currentPointer + 1);
+        vals.setByte(currentPointer, (byte) entryMap.size());
+        currentPointer += 1;
+        for (Map.Entry<String, String> entry : entryMap.entrySet()) {
+            String key = entry.getKey(), value = entry.getValue();
+            Integer keyIndex = keysInMem.get(key);
+            if (keyIndex == null) {
+                keyIndex = keysInMem.size();
+                if (keyIndex >= MAX_UNIQUE_KEYS)
+                    throw new IllegalArgumentException("Cannot store more than " + MAX_UNIQUE_KEYS + " unique keys");
+                keysInMem.put(key, keyIndex);
+                keyList.add(key);
+            }
+
+            if (value == null || value.isEmpty()) {
+                vals.ensureCapacity(currentPointer + 3);
+                vals.setShort(currentPointer, keyIndex.shortValue());
+                // ensure that also in case of MMap value is set to 0
+                vals.setByte(currentPointer + 2, (byte) 0);
+                currentPointer += 3;
+            } else {
+                Long existingRef = smallCache.get(value);
+                if (existingRef != null) {
+                    long delta = lastEntryPointer - existingRef;
+                    if (delta < Integer.MAX_VALUE && delta > Integer.MIN_VALUE) {
+                        vals.ensureCapacity(currentPointer + 2 + 4);
+                        vals.setShort(currentPointer, (short) -keyIndex);
+                        currentPointer += 2;
+                        // do not store valueBytes.length as we know it already: it is 4!
+                        byte[] valueBytes = new byte[4];
+                        BitUtil.LITTLE.fromInt(valueBytes, (int) delta);
+                        vals.setBytes(currentPointer, valueBytes, valueBytes.length);
+                        currentPointer += valueBytes.length;
+                        continue;
+                    } else {
+                        smallCache.remove(value);
+                    }
+                }
+
+                byte[] valueBytes = getBytesForString("Value for key" + key, value);
+                // only cache value if storing via duplicate marker is valuable (the delta costs 4 bytes minus 1 due to omitted valueBytes.length storage)
+                if (valueBytes.length > 3)
+                    smallCache.put(value, currentPointer);
+
+                vals.ensureCapacity(currentPointer + 2 + 1 + valueBytes.length);
+                vals.setShort(currentPointer, keyIndex.shortValue());
+                currentPointer += 2;
+                vals.setByte(currentPointer, (byte) valueBytes.length);
+                currentPointer++;
+                vals.setBytes(currentPointer, valueBytes, valueBytes.length);
+                currentPointer += valueBytes.length;
+            }
+        }
+        bytePointer = currentPointer;
+        return lastEntryPointer;
+    }
+
+    public Map<String, String> getAll(final long entryPointer) {
+        if (entryPointer < 0)
+            throw new IllegalStateException("Pointer to access StringIndex cannot be negative:" + entryPointer);
+
+        if (entryPointer == EMPTY_POINTER)
+            return Collections.emptyMap();
+
+        int keyCount = vals.getByte(entryPointer) & 0xFF;
+        if (keyCount == 0)
+            return Collections.emptyMap();
+
+        Map<String, String> map = new HashMap<>(keyCount);
+        long tmpPointer = entryPointer + 1;
+        for (int i = 0; i < keyCount; i++) {
+            int currentKeyIndex = vals.getShort(tmpPointer);
+            tmpPointer += 2;
+
+            if (currentKeyIndex < 0) {
+                currentKeyIndex = -currentKeyIndex;
+                byte[] valueBytes = new byte[4];
+                vals.getBytes(tmpPointer, valueBytes, valueBytes.length);
+                tmpPointer += 4;
+
+                long dupPointer = entryPointer - BitUtil.LITTLE.toInt(valueBytes);
+                dupPointer += 2;
+                if (dupPointer > bytePointer)
+                    throw new IllegalStateException("dup marker should exist but points into not yet allocated area " + dupPointer + " > " + bytePointer);
+                putIntoMap(map, dupPointer, currentKeyIndex);
+            } else {
+                int valueLength = putIntoMap(map, tmpPointer, currentKeyIndex);
+                tmpPointer += 1 + valueLength;
+            }
+        }
+
+        // value for specified key does not existing for the specified pointer
+        return map;
+    }
+
+    private int putIntoMap(Map<String, String> map, long tmpPointer, int currentKeyIndex) {
+        int valueLength = vals.getByte(tmpPointer) & 0xFF;
+        tmpPointer++;
+        String valueStr;
+        if (valueLength == 0) {
+            valueStr = "";
+        } else {
+            byte[] valueBytes = new byte[valueLength];
+            vals.getBytes(tmpPointer, valueBytes, valueBytes.length);
+            valueStr = new String(valueBytes, Helper.UTF_CS);
+        }
+
+        map.put(keyList.get(currentKeyIndex), valueStr);
+        return valueLength;
+    }
+
+    public String get(final long entryPointer, String key) {
+        if (entryPointer < 0)
+            throw new IllegalStateException("Pointer to access StringIndex cannot be negative:" + entryPointer);
+
+        if (entryPointer == EMPTY_POINTER)
+            return "";
+
+        int keyCount = vals.getByte(entryPointer) & 0xFF;
+        if (keyCount == 0)
+            return null;
+
+        Integer keyIndex = keysInMem.get(key);
+        // specified key is not known to the StringIndex
+        if (keyIndex == null)
+            return null;
+
+        long tmpPointer = entryPointer + 1;
+        for (int i = 0; i < keyCount; i++) {
+            int currentKeyIndex = vals.getShort(tmpPointer);
+            tmpPointer += 2;
+            if (Math.abs(currentKeyIndex) == keyIndex) {
+                if (currentKeyIndex < 0) {
+                    byte[] valueBytes = new byte[4];
+                    vals.getBytes(tmpPointer, valueBytes, valueBytes.length);
+                    tmpPointer = entryPointer - BitUtil.LITTLE.toInt(valueBytes);
+                    tmpPointer += 2;
+                    if (tmpPointer > bytePointer)
+                        throw new IllegalStateException("dup marker " + bytePointer + " should exist but points into not yet allocated area " + tmpPointer);
+                }
+
+                int valueLength = vals.getByte(tmpPointer) & 0xFF;
+                if (valueLength == 0)
+                    return "";
+
+                tmpPointer++;
+                byte[] valueBytes = new byte[valueLength];
+                vals.getBytes(tmpPointer, valueBytes, valueBytes.length);
+                return new String(valueBytes, Helper.UTF_CS);
+            }
+            int valueLength = vals.getByte(tmpPointer) & 0xFF;
+            tmpPointer += 1 + valueLength;
+        }
+
+        // value for specified key does not existing for the specified pointer
+        return null;
+    }
+
+    private byte[] getBytesForString(String info, String name) {
+        byte[] bytes = name.getBytes(Helper.UTF_CS);
+        if (bytes.length > MAX_LENGTH) {
+            String newString = new String(bytes, 0, MAX_LENGTH, Helper.UTF_CS);
+            if (throwExceptionIfTooLong)
+                throw new IllegalStateException(info + " is too long: " + name + " truncated to " + newString);
+            return newString.getBytes(Helper.UTF_CS);
+        }
+
+        return bytes;
+    }
+
+    @Override
+    public void flush() {
+        keys.ensureCapacity(2);
+        keys.setShort(0, (short) keysInMem.size());
+        long keyBytePointer = 2;
+        for (String key : keysInMem.keySet()) {
+            byte[] keyBytes = getBytesForString("key", key);
+            keys.ensureCapacity(keyBytePointer + 2 + keyBytes.length);
+            keys.setShort(keyBytePointer, (short) keyBytes.length);
+            keyBytePointer += 2;
+
+            keys.setBytes(keyBytePointer, keyBytes, keyBytes.length);
+            keyBytePointer += keyBytes.length;
+        }
+        keys.flush();
+
+        vals.setHeader(0, BitUtil.LITTLE.getIntLow(bytePointer));
+        vals.setHeader(4, BitUtil.LITTLE.getIntHigh(bytePointer));
+        vals.flush();
+    }
+
+    @Override
+    public void close() {
+        keys.close();
+        vals.close();
+    }
+
+    @Override
+    public boolean isClosed() {
+        return vals.isClosed() && keys.isClosed();
+    }
+
+    public void setSegmentSize(int segments) {
+        keys.setSegmentSize(segments);
+        vals.setSegmentSize(segments);
+    }
+
+    @Override
+    public long getCapacity() {
+        return vals.getCapacity() + keys.getCapacity();
+    }
+
+    public void copyTo(StringIndex stringIndex) {
+        keys.copyTo(stringIndex.keys);
+        vals.copyTo(stringIndex.vals);
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/storage/BaseGraph.java b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
index 4ede2e233..14e2ecd62 100644
--- a/core/src/main/java/com/graphhopper/storage/BaseGraph.java
+++ b/core/src/main/java/com/graphhopper/storage/BaseGraph.java
@@ -27,11 +27,12 @@ import com.graphhopper.routing.profiles.IntEncodedValue;
 import com.graphhopper.routing.util.AllEdgesIterator;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.search.NameIndex;
+import com.graphhopper.search.StringIndex;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
 import org.slf4j.LoggerFactory;
 
+import java.util.Collections;
 import java.util.Locale;
 
 import static com.graphhopper.util.Helper.nf;
@@ -57,9 +58,10 @@ class BaseGraph implements Graph {
     final DataAccess nodes;
     final BBox bounds;
     final NodeAccess nodeAccess;
+    private final static String STRING_IDX_NAME_KEY = "name";
+    final StringIndex stringIndex;
     // can be null if turn costs are not supported
     final TurnCostExtension turnCostExtension;
-    final NameIndex nameIndex;
     final BitUtil bitUtil;
     final EncodingManager encodingManager;
     final EdgeAccess edgeAccess;
@@ -103,7 +105,7 @@ class BaseGraph implements Graph {
         this.intsForFlags = encodingManager.getIntsForFlags();
         this.bitUtil = BitUtil.get(dir.getByteOrder());
         this.wayGeometry = dir.find("geometry");
-        this.nameIndex = new NameIndex(dir);
+        this.stringIndex = new StringIndex(dir);
         this.nodes = dir.find("nodes", DAType.getPreferredInt(dir.getDefaultType()));
         this.edges = dir.find("edges", DAType.getPreferredInt(dir.getDefaultType()));
         this.listener = listener;
@@ -344,7 +346,7 @@ class BaseGraph implements Graph {
         nodes.setSegmentSize(bytes);
         edges.setSegmentSize(bytes);
         wayGeometry.setSegmentSize(bytes);
-        nameIndex.setSegmentSize(bytes);
+        stringIndex.setSegmentSize(bytes);
         if (supportsTurnCosts()) {
             turnCostExtension.setSegmentSize(bytes);
         }
@@ -373,7 +375,7 @@ class BaseGraph implements Graph {
 
         initSize = Math.min(initSize, 2000);
         wayGeometry.create(initSize);
-        nameIndex.create(initSize);
+        stringIndex.create(initSize);
         if (supportsTurnCosts()) {
             turnCostExtension.create(initSize);
         }
@@ -387,7 +389,7 @@ class BaseGraph implements Graph {
     String toDetailsString() {
         return "edges:" + nf(edgeCount) + "(" + edges.getCapacity() / Helper.MB + "MB), "
                 + "nodes:" + nf(getNodes()) + "(" + nodes.getCapacity() / Helper.MB + "MB), "
-                + "name:(" + nameIndex.getCapacity() / Helper.MB + "MB), "
+                + "name:(" + stringIndex.getCapacity() / Helper.MB + "MB), "
                 + "geo:" + nf(maxGeoRef) + "(" + wayGeometry.getCapacity() / Helper.MB + "MB), "
                 + "bounds:" + bounds;
     }
@@ -433,8 +435,8 @@ class BaseGraph implements Graph {
         wayGeometry.flush();
         wayGeometry.close();
 
-        nameIndex.flush();
-        nameIndex.close();
+        stringIndex.flush();
+        stringIndex.close();
     }
 
     public void flush() {
@@ -443,8 +445,8 @@ class BaseGraph implements Graph {
             wayGeometry.flush();
         }
 
-        if (!nameIndex.isClosed())
-            nameIndex.flush();
+        if (!stringIndex.isClosed())
+            stringIndex.flush();
 
         setNodesHeader();
         setEdgesHeader();
@@ -458,8 +460,8 @@ class BaseGraph implements Graph {
     public void close() {
         if (!wayGeometry.isClosed())
             wayGeometry.close();
-        if (!nameIndex.isClosed())
-            nameIndex.close();
+        if (!stringIndex.isClosed())
+            stringIndex.close();
         edges.close();
         nodes.close();
         if (supportsTurnCosts()) {
@@ -468,7 +470,7 @@ class BaseGraph implements Graph {
     }
 
     long getCapacity() {
-        return edges.getCapacity() + nodes.getCapacity() + nameIndex.getCapacity()
+        return edges.getCapacity() + nodes.getCapacity() + stringIndex.getCapacity()
                 + wayGeometry.getCapacity() + (supportsTurnCosts() ? turnCostExtension.getCapacity() : 0);
     }
 
@@ -490,7 +492,7 @@ class BaseGraph implements Graph {
         if (!wayGeometry.loadExisting())
             throw new IllegalStateException("Cannot load geometry. corrupt file or directory? " + dir);
 
-        if (!nameIndex.loadExisting())
+        if (!stringIndex.loadExisting())
             throw new IllegalStateException("Cannot load name index. corrupt file or directory? " + dir);
 
         if (supportsTurnCosts() && !turnCostExtension.loadExisting())
@@ -623,7 +625,7 @@ class BaseGraph implements Graph {
         clonedG.loadEdgesHeader();
 
         // name
-        nameIndex.copyTo(clonedG.nameIndex);
+        stringIndex.copyTo(clonedG.stringIndex);
 
         // geometry
         setWayGeometryHeader();
@@ -969,11 +971,11 @@ class BaseGraph implements Graph {
     }
 
     private void setName(long edgePointer, String name) {
-        int nameIndexRef = (int) nameIndex.put(name);
-        if (nameIndexRef < 0)
+        int stringIndexRef = (int) stringIndex.add(Collections.singletonMap(STRING_IDX_NAME_KEY, name));
+        if (stringIndexRef < 0)
             throw new IllegalStateException("Too many names are stored, currently limited to int pointer");
 
-        edges.setInt(edgePointer + E_NAME, nameIndexRef);
+        edges.setInt(edgePointer + E_NAME, stringIndexRef);
     }
 
     GHBitSet getRemovedNodes() {
@@ -1354,8 +1356,10 @@ class BaseGraph implements Graph {
 
         @Override
         public String getName() {
-            int nameIndexRef = baseGraph.edges.getInt(edgePointer + baseGraph.E_NAME);
-            return baseGraph.nameIndex.get(nameIndexRef);
+            int stringIndexRef = baseGraph.edges.getInt(edgePointer + baseGraph.E_NAME);
+            String name = baseGraph.stringIndex.get(stringIndexRef, STRING_IDX_NAME_KEY);
+            // preserve backward compatibility (returns null if not explicitly set)
+            return name == null ? "" : name;
         }
 
         @Override
diff --git a/core/src/main/java/com/graphhopper/storage/DataAccess.java b/core/src/main/java/com/graphhopper/storage/DataAccess.java
index 622e04e1c..d1aa3b15d 100644
--- a/core/src/main/java/com/graphhopper/storage/DataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/DataAccess.java
@@ -70,12 +70,15 @@ public interface DataAccess extends Storable<DataAccess> {
 
     /**
      * Get bytes from position 'index'
-     * <p>
      *
      * @param values acts as output
      */
     void getBytes(long bytePos, byte[] values, int length);
 
+    void setByte(long currentPointer, byte value);
+
+    byte getByte(long currentPointer);
+
     /**
      * Set 4 bytes at the header space index to the specified value
      */
diff --git a/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java b/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
index d2bcd5368..681f20b62 100644
--- a/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/MMapDataAccess.java
@@ -42,14 +42,14 @@ import java.util.StringTokenizer;
 /**
  * A DataAccess implementation using a memory-mapped file, i.e. a facility of the
  * operating system to access a file like an area of RAM.
- *
+ * <p>
  * Java presents the mapped memory as a ByteBuffer, and ByteBuffer is not
  * thread-safe, which means that access to a ByteBuffer must be externally
  * synchronized.
- *
+ * <p>
  * This class itself is intended to be as thread-safe as other DataAccess
  * implementations are.
- *
+ * <p>
  * The exact behavior of memory-mapping is reported to be wildly platform-dependent.
  *
  * @author Peter Karich
@@ -334,6 +334,8 @@ public final class MMapDataAccess extends AbstractDataAccess {
     public final void setInt(long bytePos, int value) {
         int bufferIndex = (int) (bytePos >> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
+        if (index + 4 > segmentSizeInBytes)
+            throw new IllegalStateException("Padding required. Currently an int cannot be distributed over two segments. " + bytePos);
         ByteBuffer byteBuffer = segments.get(bufferIndex);
         synchronized (byteBuffer) {
             byteBuffer.putInt(index, value);
@@ -344,6 +346,8 @@ public final class MMapDataAccess extends AbstractDataAccess {
     public final int getInt(long bytePos) {
         int bufferIndex = (int) (bytePos >> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
+        if (index + 4 > segmentSizeInBytes)
+            throw new IllegalStateException("Padding required. Currently an int cannot be distributed over two segments. " + bytePos);
         ByteBuffer byteBuffer = segments.get(bufferIndex);
         synchronized (byteBuffer) {
             return byteBuffer.getInt(index);
@@ -356,7 +360,16 @@ public final class MMapDataAccess extends AbstractDataAccess {
         int index = (int) (bytePos & indexDivisor);
         ByteBuffer byteBuffer = segments.get(bufferIndex);
         synchronized (byteBuffer) {
-            byteBuffer.putShort(index, value);
+            if (index + 2 > segmentSizeInBytes) {
+                ByteBuffer byteBufferNext = segments.get(bufferIndex + 1);
+                synchronized (byteBufferNext) {
+                    // special case if short has to be written into two separate segments
+                    byteBuffer.put(index, (byte) value);
+                    byteBufferNext.put(0, (byte) (value >>> 8));
+                }
+            } else {
+                byteBuffer.putShort(index, value);
+            }
         }
     }
 
@@ -365,6 +378,15 @@ public final class MMapDataAccess extends AbstractDataAccess {
         int bufferIndex = (int) (bytePos >>> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
         ByteBuffer byteBuffer = segments.get(bufferIndex);
+        if (index + 2 > segmentSizeInBytes) {
+            ByteBuffer byteBufferNext = segments.get(bufferIndex + 1);
+            // never lock byteBuffer and byteBufferNext in a different order to avoid deadlocks (shouldn't happen)
+            synchronized (byteBuffer) {
+                synchronized (byteBufferNext) {
+                    return (short) ((byteBufferNext.get(0) & 0xFF) << 8 | byteBuffer.get(index) & 0xFF);
+                }
+            }
+        }
         synchronized (byteBuffer) {
             return byteBuffer.getShort(index);
         }
@@ -420,6 +442,28 @@ public final class MMapDataAccess extends AbstractDataAccess {
         }
     }
 
+    @Override
+    public void setByte(long bytePos, byte value) {
+        int bufferIndex = (int) (bytePos >>> segmentSizePower);
+        int index = (int) (bytePos & indexDivisor);
+        final ByteBuffer bb1 = segments.get(bufferIndex);
+        synchronized (bb1) {
+            bb1.position(index);
+            bb1.put(value);
+        }
+    }
+
+    @Override
+    public byte getByte(long bytePos) {
+        int bufferIndex = (int) (bytePos >>> segmentSizePower);
+        int index = (int) (bytePos & indexDivisor);
+        final ByteBuffer bb1 = segments.get(bufferIndex);
+        synchronized (bb1) {
+            bb1.position(index);
+            return bb1.get();
+        }
+    }
+
     @Override
     public long getCapacity() {
         long cap = 0;
diff --git a/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java b/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
index a6e0fc93c..5bd006953 100644
--- a/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/RAMDataAccess.java
@@ -17,8 +17,6 @@
  */
 package com.graphhopper.storage;
 
-import org.slf4j.LoggerFactory;
-
 import java.io.File;
 import java.io.IOException;
 import java.io.RandomAccessFile;
@@ -77,7 +75,7 @@ public class RAMDataAccess extends AbstractDataAccess {
     public RAMDataAccess create(long bytes) {
         if (segments.length > 0)
             throw new IllegalThreadStateException("already created");
-        
+
         setSegmentSize(segmentSizeInBytes);
         ensureCapacity(Math.max(10 * 4, bytes));
         return this;
@@ -189,7 +187,8 @@ public class RAMDataAccess extends AbstractDataAccess {
         assert segmentSizePower > 0 : "call create or loadExisting before usage!";
         int bufferIndex = (int) (bytePos >>> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
-        assert index + 4 <= segmentSizeInBytes : "integer cannot be distributed over two segments";
+        if (index + 4 > segmentSizeInBytes)
+            throw new IllegalStateException("Padding required. Currently an int cannot be distributed over two segments. " + bytePos);
         bitUtil.fromInt(segments[bufferIndex], value, index);
     }
 
@@ -198,12 +197,8 @@ public class RAMDataAccess extends AbstractDataAccess {
         assert segmentSizePower > 0 : "call create or loadExisting before usage!";
         int bufferIndex = (int) (bytePos >>> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
-        assert index + 4 <= segmentSizeInBytes : "integer cannot be distributed over two segments";
-        if (bufferIndex > segments.length) {
-            LoggerFactory.getLogger(getClass()).error(getName() + ", segments:" + segments.length
-                    + ", bufIndex:" + bufferIndex + ", bytePos:" + bytePos
-                    + ", segPower:" + segmentSizePower);
-        }
+        if (index + 4 > segmentSizeInBytes)
+            throw new IllegalStateException("Padding required. Currently an int cannot be distributed over two segments. " + bytePos);
         return bitUtil.toInt(segments[bufferIndex], index);
     }
 
@@ -212,8 +207,13 @@ public class RAMDataAccess extends AbstractDataAccess {
         assert segmentSizePower > 0 : "call create or loadExisting before usage!";
         int bufferIndex = (int) (bytePos >>> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
-        assert index + 2 <= segmentSizeInBytes : "integer cannot be distributed over two segments";
-        bitUtil.fromShort(segments[bufferIndex], value, index);
+        if (index + 2 > segmentSizeInBytes) {
+            // special case if short has to be written into two separate segments
+            segments[bufferIndex][index] = (byte) (value);
+            segments[bufferIndex + 1][0] = (byte) (value >>> 8);
+        } else {
+            bitUtil.fromShort(segments[bufferIndex], value, index);
+        }
     }
 
     @Override
@@ -221,8 +221,10 @@ public class RAMDataAccess extends AbstractDataAccess {
         assert segmentSizePower > 0 : "call create or loadExisting before usage!";
         int bufferIndex = (int) (bytePos >>> segmentSizePower);
         int index = (int) (bytePos & indexDivisor);
-        assert index + 2 <= segmentSizeInBytes : "integer cannot be distributed over two segments";
-        return bitUtil.toShort(segments[bufferIndex], index);
+        if (index + 2 > segmentSizeInBytes)
+            return (short) ((segments[bufferIndex + 1][0] & 0xFF) << 8 | (segments[bufferIndex][index] & 0xFF));
+        else
+            return bitUtil.toShort(segments[bufferIndex], index);
     }
 
     @Override
@@ -261,6 +263,22 @@ public class RAMDataAccess extends AbstractDataAccess {
         }
     }
 
+    @Override
+    public final void setByte(long bytePos, byte value) {
+        assert segmentSizePower > 0 : "call create or loadExisting before usage!";
+        int bufferIndex = (int) (bytePos >>> segmentSizePower);
+        int index = (int) (bytePos & indexDivisor);
+        segments[bufferIndex][index] = value;
+    }
+
+    @Override
+    public final byte getByte(long bytePos) {
+        assert segmentSizePower > 0 : "call create or loadExisting before usage!";
+        int bufferIndex = (int) (bytePos >>> segmentSizePower);
+        int index = (int) (bytePos & indexDivisor);
+        return segments[bufferIndex][index];
+    }
+
     @Override
     public void close() {
         super.close();
diff --git a/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java b/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
index 6079d4053..8e6831fa1 100644
--- a/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/RAMIntDataAccess.java
@@ -249,6 +249,16 @@ class RAMIntDataAccess extends AbstractDataAccess {
         throw new UnsupportedOperationException(toString() + " does not support byte based acccess. Use RAMDataAccess instead");
     }
 
+    @Override
+    public byte getByte(long bytePos) {
+        throw new UnsupportedOperationException(toString() + " does not support byte based acccess. Use RAMDataAccess instead");
+    }
+
+    @Override
+    public void setByte(long bytePos, byte value) {
+        throw new UnsupportedOperationException(toString() + " does not support byte based acccess. Use RAMDataAccess instead");
+    }
+
     @Override
     public void close() {
         super.close();
diff --git a/core/src/main/java/com/graphhopper/storage/StorableProperties.java b/core/src/main/java/com/graphhopper/storage/StorableProperties.java
index fc825aa08..35fe22f7e 100644
--- a/core/src/main/java/com/graphhopper/storage/StorableProperties.java
+++ b/core/src/main/java/com/graphhopper/storage/StorableProperties.java
@@ -139,7 +139,7 @@ public class StorableProperties implements Storable<StorableProperties> {
         put("edges.version", Constants.VERSION_EDGE);
         put("geometry.version", Constants.VERSION_GEOMETRY);
         put("location_index.version", Constants.VERSION_LOCATION_IDX);
-        put("name_index.version", Constants.VERSION_NAME_IDX);
+        put("string_index.version", Constants.VERSION_STRING_IDX);
         put("shortcuts.version", Constants.VERSION_SHORTCUT);
     }
 
@@ -148,7 +148,7 @@ public class StorableProperties implements Storable<StorableProperties> {
                 + get("edges.version") + ","
                 + get("geometry.version") + ","
                 + get("location_index.version") + ","
-                + get("name_index.version");
+                + get("string_index.version");
     }
 
     public synchronized boolean checkVersions(boolean silent) {
@@ -164,7 +164,7 @@ public class StorableProperties implements Storable<StorableProperties> {
         if (!check("location_index", Constants.VERSION_LOCATION_IDX, silent))
             return false;
 
-        if (!check("name_index", Constants.VERSION_NAME_IDX, silent))
+        if (!check("string_index", Constants.VERSION_STRING_IDX, silent))
             return false;
 
         if (!check("shortcuts", Constants.VERSION_SHORTCUT, silent))
diff --git a/core/src/main/java/com/graphhopper/storage/UnsafeDataAccess.java b/core/src/main/java/com/graphhopper/storage/UnsafeDataAccess.java
index 8681b5a88..6298d40be 100644
--- a/core/src/main/java/com/graphhopper/storage/UnsafeDataAccess.java
+++ b/core/src/main/java/com/graphhopper/storage/UnsafeDataAccess.java
@@ -217,6 +217,16 @@ public class UnsafeDataAccess extends AbstractDataAccess {
         }
     }
 
+    @Override
+    public final void setByte(long bytePos, byte value) {
+        UNSAFE.putByte(address + bytePos, value);
+    }
+
+    @Override
+    public final byte getByte(long bytePos) {
+        return UNSAFE.getByte(address + bytePos);
+    }
+
     @Override
     public final long getCapacity() {
         return capacity;
diff --git a/core/src/main/java/com/graphhopper/util/BitUtilBig.java b/core/src/main/java/com/graphhopper/util/BitUtilBig.java
index 82ed1b317..0aaffaf3b 100644
--- a/core/src/main/java/com/graphhopper/util/BitUtilBig.java
+++ b/core/src/main/java/com/graphhopper/util/BitUtilBig.java
@@ -32,18 +32,18 @@ public class BitUtilBig extends BitUtil {
         return (short) ((b[offset] & 0xFF) << 8 | (b[offset + 1] & 0xFF));
     }
 
-    @Override
-    public final int toInt(byte[] b, int offset) {
-        return (b[offset] & 0xFF) << 24 | (b[++offset] & 0xFF) << 16
-                | (b[++offset] & 0xFF) << 8 | (b[++offset] & 0xFF);
-    }
-
     @Override
     public void fromShort(byte[] bytes, short value, int offset) {
         bytes[offset] = (byte) (value >> 8);
         bytes[offset + 1] = (byte) (value);
     }
 
+    @Override
+    public final int toInt(byte[] b, int offset) {
+        return (b[offset] & 0xFF) << 24 | (b[++offset] & 0xFF) << 16
+                | (b[++offset] & 0xFF) << 8 | (b[++offset] & 0xFF);
+    }
+
     @Override
     public final void fromInt(byte[] bytes, int value, int offset) {
         bytes[offset] = (byte) (value >> 24);
diff --git a/core/src/main/java/com/graphhopper/util/BitUtilLittle.java b/core/src/main/java/com/graphhopper/util/BitUtilLittle.java
index 7e5e5d4bb..ad3c2a8a3 100644
--- a/core/src/main/java/com/graphhopper/util/BitUtilLittle.java
+++ b/core/src/main/java/com/graphhopper/util/BitUtilLittle.java
@@ -32,18 +32,18 @@ public class BitUtilLittle extends BitUtil {
         return (short) ((b[offset + 1] & 0xFF) << 8 | (b[offset] & 0xFF));
     }
 
-    @Override
-    public final int toInt(byte[] b, int offset) {
-        return (b[offset + 3] & 0xFF) << 24 | (b[offset + 2] & 0xFF) << 16
-                | (b[offset + 1] & 0xFF) << 8 | (b[offset] & 0xFF);
-    }
-
     @Override
     public void fromShort(byte[] bytes, short value, int offset) {
         bytes[offset + 1] = (byte) (value >>> 8);
         bytes[offset] = (byte) (value);
     }
 
+    @Override
+    public final int toInt(byte[] b, int offset) {
+        return (b[offset + 3] & 0xFF) << 24 | (b[offset + 2] & 0xFF) << 16
+                | (b[offset + 1] & 0xFF) << 8 | (b[offset] & 0xFF);
+    }
+
     @Override
     public final void fromInt(byte[] bytes, int value, int offset) {
         bytes[offset + 3] = (byte) (value >>> 24);
diff --git a/core/src/main/java/com/graphhopper/util/Constants.java b/core/src/main/java/com/graphhopper/util/Constants.java
index f868c1829..dfb83fc32 100644
--- a/core/src/main/java/com/graphhopper/util/Constants.java
+++ b/core/src/main/java/com/graphhopper/util/Constants.java
@@ -71,7 +71,7 @@ public class Constants {
     public static final int VERSION_SHORTCUT = 5;
     public static final int VERSION_GEOMETRY = 4;
     public static final int VERSION_LOCATION_IDX = 3;
-    public static final int VERSION_NAME_IDX = 3;
+    public static final int VERSION_STRING_IDX = 5;
     /**
      * The version without the snapshot string
      */
@@ -144,7 +144,7 @@ public class Constants {
 
     public static String getVersions() {
         return VERSION_NODE + "," + VERSION_EDGE + "," + VERSION_GEOMETRY + "," + VERSION_LOCATION_IDX
-                + "," + VERSION_NAME_IDX + "," + VERSION_SHORTCUT;
+                + "," + VERSION_STRING_IDX + "," + VERSION_SHORTCUT;
     }
 
     public static String getMajorVersion() {


Test patch:
diff --git a/core/src/test/java/com/graphhopper/search/NameIndexTest.java b/core/src/test/java/com/graphhopper/search/NameIndexTest.java
deleted file mode 100644
index ce2d331f5..000000000
--- a/core/src/test/java/com/graphhopper/search/NameIndexTest.java
+++ /dev/null
@@ -1,111 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH 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 com.graphhopper.search;
-
-import com.graphhopper.storage.RAMDirectory;
-import com.graphhopper.util.Helper;
-import org.junit.Test;
-
-import java.io.File;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-
-/**
- * @author Peter Karich
- */
-public class NameIndexTest {
-    @Test
-    public void testNoErrorOnLargeName() {
-        NameIndex index = new NameIndex(new RAMDirectory()).create(1000);
-        // 127 => bytes.length == 254
-        String str = "";
-        for (int i = 0; i < 127; i++) {
-            str += "ß";
-        }
-        long result = index.put(str);
-        assertEquals(127, index.get(result).length());
-    }
-
-    @Test
-    public void testPut() {
-        NameIndex index = new NameIndex(new RAMDirectory()).create(1000);
-        long result = index.put("Something Streetä");
-        assertEquals("Something Streetä", index.get(result));
-
-        long existing = index.put("Something Streetä");
-        assertEquals(result, existing);
-
-        result = index.put("testing");
-        assertEquals("testing", index.get(result));
-
-        assertEquals(0, index.put(""));
-        assertEquals(0, index.put(null));
-        assertEquals("", index.get(0));
-        index.close();
-    }
-
-    @Test
-    public void testCreate() {
-        NameIndex index = new NameIndex(new RAMDirectory()).create(1000);
-        String str1 = "nice";
-        long pointer1 = index.put(str1);
-
-        String str2 = "nice work äöß";
-        long pointer2 = index.put(str2);
-
-        assertEquals(str2, index.get(pointer2));
-        assertEquals(str1, index.get(pointer1));
-        index.close();
-    }
-
-    @Test
-    public void testTooLongNameNoError() {
-        NameIndex index = new NameIndex(new RAMDirectory()).create(1000);
-        // WTH are they doing in OSM? There are exactly two names in the full planet export which violates this limitation!
-        index.put("Бухарестская улица (http://ru.wikipedia.org/wiki/%D0%91%D1%83%D1%85%D0%B0%D1%80%D0%B5%D1%81%D1%82%D1%81%D0%BA%D0%B0%D1%8F_%D1%83%D0%BB%D0%B8%D1%86%D0%B0_(%D0%A1%D0%B0%D0%BD%D0%BA%D1%82-%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D0%B1%D1%83%D1%80%D0%B3))");
-
-        String str = "sdfsdfds";
-        for (int i = 0; i < 256 * 3; i++) {
-            str += "Б";
-        }
-        index.put(str);
-        index.close();
-    }
-
-    @Test
-    public void testFlush() {
-        String location = "./target/nameindex-store";
-        Helper.removeDir(new File(location));
-
-        NameIndex index = new NameIndex(new RAMDirectory(location, true).create()).create(1000);
-        long pointer = index.put("test");
-        index.flush();
-        index.close();
-
-        index = new NameIndex(new RAMDirectory(location, true));
-        assertTrue(index.loadExisting());
-        assertEquals("test", index.get(pointer));
-        // make sure bytePointer is correctly set after loadExisting
-        long newPointer = index.put("testing");
-        assertEquals(newPointer + ">" + pointer, pointer + "test".getBytes().length + 1, newPointer);
-        index.close();
-
-        Helper.removeDir(new File(location));
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/search/StringIndexTest.java b/core/src/test/java/com/graphhopper/search/StringIndexTest.java
new file mode 100644
index 000000000..c77f41144
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/search/StringIndexTest.java
@@ -0,0 +1,271 @@
+package com.graphhopper.search;
+
+import com.carrotsearch.hppc.LongArrayList;
+import com.graphhopper.Repeat;
+import com.graphhopper.storage.RAMDirectory;
+import com.graphhopper.util.Helper;
+import org.junit.Test;
+
+import java.io.File;
+import java.util.*;
+
+import static com.graphhopper.search.StringIndex.MAX_UNIQUE_KEYS;
+import static junit.framework.TestCase.assertTrue;
+import static org.junit.Assert.*;
+
+public class StringIndexTest {
+
+    private StringIndex create() {
+        return new StringIndex(new RAMDirectory()).create(1000);
+    }
+
+    Map<String, String> createMap(String... strings) {
+        if (strings.length % 2 != 0)
+            throw new IllegalArgumentException("Cannot create map from strings " + Arrays.toString(strings));
+        Map<String, String> map = new LinkedHashMap<>();
+        for (int i = 0; i < strings.length; i += 2) {
+            map.put(strings[i], strings[i + 1]);
+        }
+        return map;
+    }
+
+    @Test
+    public void putSame() {
+        StringIndex index = create();
+        long aPointer = index.add(createMap("a", "same name", "b", "same name"));
+
+        assertNull(index.get(aPointer, ""));
+        assertEquals("same name", index.get(aPointer, "a"));
+        assertEquals("same name", index.get(aPointer, "b"));
+        assertNull(index.get(aPointer, "c"));
+
+        index = create();
+        aPointer = index.add(createMap("a", "a name", "b", "same name"));
+        assertEquals("a name", index.get(aPointer, "a"));
+    }
+
+    @Test
+    public void putAB() {
+        StringIndex index = create();
+        long aPointer = index.add(createMap("a", "a name", "b", "b name"));
+
+        assertNull(index.get(aPointer, ""));
+        assertEquals("a name", index.get(aPointer, "a"));
+        assertEquals("b name", index.get(aPointer, "b"));
+    }
+
+    @Test
+    public void putEmpty() {
+        StringIndex index = create();
+        assertEquals(1, index.add(createMap("", "")));
+        assertEquals(5, index.add(createMap("", null)));
+        assertEquals(9, index.add(createMap(null, null)));
+        assertEquals("", index.get(0, ""));
+
+        assertEquals(13, index.add(createMap("else", "else")));
+    }
+
+    @Test
+    public void putMany() {
+        StringIndex index = create();
+        long aPointer = 0, tmpPointer = 0;
+
+        for (int i = 0; i < 10000; i++) {
+            aPointer = index.add(createMap("a", "a name " + i, "b", "b name " + i, "c", "c name " + i));
+            if (i == 567)
+                tmpPointer = aPointer;
+        }
+
+        assertEquals("b name 9999", index.get(aPointer, "b"));
+        assertEquals("c name 9999", index.get(aPointer, "c"));
+
+        assertEquals("a name 567", index.get(tmpPointer, "a"));
+        assertEquals("b name 567", index.get(tmpPointer, "b"));
+        assertEquals("c name 567", index.get(tmpPointer, "c"));
+    }
+
+    @Test
+    public void putManyKeys() {
+        StringIndex index = create();
+        // one key is already stored => empty key
+        for (int i = 1; i < MAX_UNIQUE_KEYS; i++) {
+            index.add(createMap("a" + i, "a name"));
+        }
+        try {
+            index.add(createMap("new", "a name"));
+            fail();
+        } catch (IllegalArgumentException ex) {
+        }
+    }
+
+    @Test
+    public void putDuplicate() {
+        StringIndex index = create();
+        long aPointer = index.add(createMap("a", "longer name", "b", "longer name"));
+        long bPointer = index.add(createMap("c", "longer other name"));
+        // value storage: 1 byte for count, 2 bytes for keyIndex and 4 bytes for delta of dup_marker and 3 bytes (keyIndex + length for "longer name")
+        assertEquals(aPointer + 1 + (2 + 4) + 3 + "longer name".getBytes(Helper.UTF_CS).length, bPointer);
+        // no de-duplication as too short:
+        long cPointer = index.add(createMap("temp", "temp"));
+        assertEquals(bPointer + 1 + 3 + "longer other name".getBytes(Helper.UTF_CS).length, cPointer);
+        assertEquals("longer name", index.get(aPointer, "a"));
+        assertEquals("longer name", index.get(aPointer, "b"));
+        assertEquals("longer other name", index.get(bPointer, "c"));
+        assertEquals("temp", index.get(cPointer, "temp"));
+
+        index = create();
+        index.add(createMap("a", "longer name", "b", "longer name"));
+        bPointer = index.add(createMap("a", "longer name", "b", "longer name"));
+        cPointer = index.add(createMap("a", "longer name", "b", "longer name"));
+        assertEquals(bPointer, cPointer);
+
+        assertEquals("{a=longer name, b=longer name}", index.getAll(aPointer).toString());
+        assertEquals("{a=longer name, b=longer name}", index.getAll(cPointer).toString());
+    }
+
+    @Test
+    public void testNoErrorOnLargeName() {
+        StringIndex index = create();
+        // 127 => bytes.length == 254
+        String str = "";
+        for (int i = 0; i < 127; i++) {
+            str += "ß";
+        }
+        long result = index.add(createMap("", str));
+        assertEquals(127, index.get(result, "").length());
+    }
+
+    @Test
+    public void testTooLongNameNoError() {
+        StringIndex index = create();
+        index.throwExceptionIfTooLong = true;
+        try {
+            index.add(createMap("", "Бухарестская улица (http://ru.wikipedia.org/wiki/%D0%91%D1%83%D1%85%D0%B0%D1%80%D0%B5%D1%81%D1%82%D1%81%D0%BA%D0%B0%D1%8F_%D1%83%D0%BB%D0%B8%D1%86%D0%B0_(%D0%A1%D0%B0%D0%BD%D0%BA%D1%82-%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D0%B1%D1%83%D1%80%D0%B3))"));
+            fail();
+        } catch (IllegalStateException ex) {
+        }
+
+        String str = "sdfsdfds";
+        for (int i = 0; i < 256 * 3; i++) {
+            str += "Б";
+        }
+        try {
+            index.add(createMap("", str));
+            fail();
+        } catch (IllegalStateException ex) {
+        }
+
+        index.throwExceptionIfTooLong = false;
+        long pointer = index.add(createMap("", "Бухарестская улица (http://ru.wikipedia.org/wiki/%D0%91%D1%83%D1%85%D0%B0%D1%80%D0%B5%D1%81%D1%82%D1%81%D0%BA%D0%B0%D1%8F_%D1%83%D0%BB%D0%B8%D1%86%D0%B0_(%D0%A1%D0%B0%D0%BD%D0%BA%D1%82-%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D0%B1%D1%83%D1%80%D0%B3))"));
+        assertTrue(index.get(pointer, "").startsWith("Бухарестская улица (h"));
+    }
+
+    @Test
+    public void testFlush() {
+        String location = "./target/stringindex-store";
+        Helper.removeDir(new File(location));
+
+        StringIndex index = new StringIndex(new RAMDirectory(location, true).create()).create(1000);
+        long pointer = index.add(createMap("", "test"));
+        index.flush();
+        index.close();
+
+        index = new StringIndex(new RAMDirectory(location, true));
+        assertTrue(index.loadExisting());
+        assertEquals("test", index.get(pointer, ""));
+        // make sure bytePointer is correctly set after loadExisting
+        long newPointer = index.add(createMap("", "testing"));
+        assertEquals(newPointer + ">" + pointer, pointer + 1 + 3 + "test".getBytes().length, newPointer);
+        index.close();
+
+        Helper.removeDir(new File(location));
+    }
+
+    @Test
+    public void testLoadKeys() {
+        String location = "./target/stringindex-store";
+        Helper.removeDir(new File(location));
+
+        StringIndex index = new StringIndex(new RAMDirectory(location, true).create()).create(1000);
+        long pointerA = index.add(createMap("c", "test value"));
+        assertEquals(2, index.getKeys().size());
+        long pointerB = index.add(createMap("a", "value", "b", "another value"));
+        // empty string is always the first key
+        assertEquals("[, c, a, b]", index.getKeys().toString());
+        index.flush();
+        index.close();
+
+        index = new StringIndex(new RAMDirectory(location, true));
+        assertTrue(index.loadExisting());
+        assertEquals("[, c, a, b]", index.getKeys().toString());
+        assertEquals("test value", index.get(pointerA, "c"));
+        assertNull(index.get(pointerA, "b"));
+
+        assertNull(index.get(pointerB, ""));
+        assertEquals("value", index.get(pointerB, "a"));
+        assertEquals("another value", index.get(pointerB, "b"));
+        assertEquals("{a=value, b=another value}", index.getAll(pointerB).toString());
+        index.close();
+
+        Helper.removeDir(new File(location));
+    }
+
+    @Test
+    public void testEmptyKey() {
+        StringIndex index = create();
+        long pointerA = index.add(createMap("", "test value"));
+        long pointerB = index.add(createMap("a", "value", "b", "another value"));
+
+        assertEquals("test value", index.get(pointerA, ""));
+        assertNull(index.get(pointerA, "a"));
+
+        assertEquals("value", index.get(pointerB, "a"));
+        assertNull(index.get(pointerB, ""));
+    }
+
+    @Test
+    @Repeat(times = 100)
+    public void testRandom() {
+        StringIndex index = create();
+        long seed = new Random().nextLong();
+        System.out.println("StringIndexText.testRandom seed:" + seed);
+        Random random = new Random(seed);
+        List<String> keys = createRandomList(random, "_key", 1000);
+        List<String> values = createRandomList(random, "_value", 5000);
+
+        int size = 20000;
+        LongArrayList pointers = new LongArrayList(size);
+        for (int i = 0; i < size; i++) {
+            Map<String, String> map = createRandomMap(random, keys, values);
+            long pointer = index.add(map);
+            try {
+                assertEquals("" + i, map.size(), index.getAll(pointer).size());
+            } catch (Exception ex) {
+                throw new RuntimeException(i + " " + map + ", " + pointer, ex);
+            }
+            pointers.add(pointer);
+        }
+
+        for (int i = 0; i < size; i++) {
+            Map<String, String> map = index.getAll(pointers.get(i));
+            assertTrue(i + " " + map, map.size() > 0);
+        }
+    }
+
+    private List<String> createRandomList(Random random, String postfix, int size) {
+        List<String> list = new ArrayList<>();
+        for (int i = 0; i < size; i++) {
+            list.add(random.nextInt(size * 5) + postfix);
+        }
+        return list;
+    }
+
+    private Map<String, String> createRandomMap(Random random, List<String> keys, List<String> values) {
+        int count = random.nextInt(10) + 2;
+        Map<String, String> map = new HashMap<>();
+        for (int i = 0; i < count; i++) {
+            map.put(keys.get(random.nextInt(keys.size())), values.get(random.nextInt(values.size())));
+        }
+        return map;
+    }
+}
\ No newline at end of file
diff --git a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
index 03f62f731..faedadd9d 100644
--- a/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
+++ b/core/src/test/java/com/graphhopper/storage/AbstractGraphStorageTester.java
@@ -953,7 +953,7 @@ public abstract class AbstractGraphStorageTester {
     }
 
     @Test
-    public void testNameIndex() {
+    public void testStringIndex() {
         graph = createGHStorage();
         EdgeIteratorState iter1 = graph.edge(0, 1, 10, true);
         iter1.setName("named street1");
diff --git a/core/src/test/java/com/graphhopper/storage/DataAccessTest.java b/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
index 1382ff73a..0734e4a5b 100644
--- a/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
+++ b/core/src/test/java/com/graphhopper/storage/DataAccessTest.java
@@ -331,6 +331,15 @@ public abstract class DataAccessTest {
         assertEquals(11111, index);
     }
 
+    @Test
+    public void testSet_GetByte() {
+        DataAccess da = createDataAccess(name);
+        da.create(300);
+        da.setByte(8, (byte) 120);
+        assertEquals(120, da.getByte(8));
+        da.close();
+    }
+
     @Test
     public void testSet_Get_Short_Long() {
         DataAccess da = createDataAccess(name);
@@ -354,6 +363,10 @@ public abstract class DataAccessTest {
             assertEquals(Short.MAX_VALUE / 3, da.getShort(7));
             // should be overwritten
             assertNotEquals(Short.MAX_VALUE / 3, da.getShort(8));
+
+            long pointer = da.getSegmentSize() - 1;
+            da.setShort(pointer, (short) (Short.MAX_VALUE / 3));
+            assertEquals(Short.MAX_VALUE / 3, da.getShort(pointer));
         }
         da.close();
     }
diff --git a/core/src/test/java/com/graphhopper/storage/RAMIntDataAccessTest.java b/core/src/test/java/com/graphhopper/storage/RAMIntDataAccessTest.java
index 8346f1540..4f72fac4c 100644
--- a/core/src/test/java/com/graphhopper/storage/RAMIntDataAccessTest.java
+++ b/core/src/test/java/com/graphhopper/storage/RAMIntDataAccessTest.java
@@ -30,4 +30,9 @@ public class RAMIntDataAccessTest extends DataAccessTest {
     public void testSet_GetBytes() {
         // should we implement this?
     }
+
+    @Override
+    public void testSet_GetByte() {
+        // should we implement this?
+    }
 }