Over a million developers have joined DZone.

Caching Immutable Id Lookups in Neo4j

· Java Zone

Discover how AppDynamics steps in to upgrade your performance game and prevent your enterprise from these top 10 Java performance problems, brought to you in partnership with AppDynamics.

GiveMeTheCache

If you’ve been following my blog for a while, you probably know I like using YourKit and Gatling for testing end to end requests in Neo4j. Today however we are going to do something a little different. We are going to be micro-benchmarking a very small piece of code within our Unmanaged Extension using a Java library called JMH.

In Neo4j 2.2 and up the Java API has been made a little easier to use. While in 2.1 you had to do this to get a node:

final Node node = IteratorUtil.singleOrNull(
      db.findNodesByLabelAndProperty(Labels.Segment, "segmentId", segmentId));

Or even worse, if you didn’t know about the IteratorUtil.singleOrNull helper:

final ResourceIterable<Node> nodes = 
       db.findNodesByLabelAndProperty(Labels.Segment, "segmentId", segmentId);

final Node node;

try (ResourceIterator<Node> nodeIter = nodes.iterator()) {
     node = (nodeIter.hasNext() ? nodeIter.next() : null);
}

Now you can simply do this:

final Node node = db.findNode(Labels.Segment, "segmentId", segmentId);

This new helper makes finding a node by a property and Label much easier. Hopefully you’ve created Unique Constraints or Indexes for all properties you’ll use to look nodes up. Now let’s see just how fast this runs. We’re going to create a method in an Unmanaged Extension that will take a list of ids and look them up. We will capture the number it found and use that for our result.

    @POST
    @Path("/lookup")
    public String Lookup(String body, @Context GraphDatabaseService db) throws IOException {
        ArrayList<Long> idsFound = new ArrayList<>();
        HashMap<String, List<Integer>> input;
        input = objectMapper.readValue(body, HashMap.class);
        List<Integer> segmentIds = input.get("segmentIds");

        try (Transaction tx = db.beginTx()) {
            for (int segmentId : segmentIds) {
                final Node node = db.findNode(Labels.Segment, "segmentId", segmentId);

                if (node != null) {
                    idsFound.add(node.getId());
                }
            }
            tx.success();
        }

        return idsFound.toString();
    }

Why am I using a list of ids instead of a single lookup? Well because I want to show you what happens as two variables change. One, the number of nodes in our index, and two, the number of lookups done in a single method.

@State(Scope.Benchmark)
public class ServiceTest {

    private Service service;
    private GraphDatabaseService db;

    @Param({"10000", "100000", "1000000"})
    public int size;

We’ll use @Param and try three different sized graphs, at 10k, 100k, and 1M nodes. We’ll use the size parameter when we create our graph:

    public void populate(GraphDatabaseService db) {
        Transaction tx = db.beginTx();
        try {
            for(int loop = 1; loop < size; loop = loop+1) {
                Node identity = db.createNode(Labels.Segment);
                identity.setProperty("segmentId", loop);

                if(loop % 1_000 == 0){
                    tx.success();
                    tx.close();
                    tx = db.beginTx();
                }
            }
            tx.success();
        } finally {
            tx.close();
        }
    }

You’ll notice I commit and start a new transaction every 1000 nodes created. I do this because we don’t to have to commit 1 million nodes all at once, it eats up too much memory. Before each Test I will setup my graph, migrate it (which creates the constraints) and populate our graph.

    @Setup
    public void prepare() {
        db = new TestGraphDatabaseFactory().newImpermanentDatabase();
        service = new Service(db);
        service.migrate(db);
        populate(db);
    }

Now we’re finally ready to create a benchmark. Our benchmark will warmup 10 times, and perform 5 measurements forking the JVM 3 times and reporting the average time it took to run.

    @Benchmark
    @Warmup(iterations = 10)
    @Measurement(iterations = 5)
    @Fork(3)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    public void measureOneLookup() throws IOException {
        service.Lookup("{\"segmentIds\":[9781]}", db);
    }

I’m using IntelliJ and running it with the JMH Plugin. After about 5 minutes we get our results:

Benchmark                      (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureOneLookup    10000  avgt   15  0.032 ± 0.000  ms/op
ServiceTest.measureOneLookup   100000  avgt   15  0.035 ± 0.001  ms/op
ServiceTest.measureOneLookup  1000000  avgt   15  0.042 ± 0.001  ms/op

So a single lookup is complete in 0.032ms to 0.42ms. Practically no time at all. It does get a little slower as our size gets bigger but that makes sense. Now let’s try measuring 10 lookups in the same method.

Benchmark                       (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureTenLookups    10000  avgt   15  0.102 ± 0.001  ms/op
ServiceTest.measureTenLookups   100000  avgt   15  0.103 ± 0.002  ms/op
ServiceTest.measureTenLookups  1000000  avgt   15  0.112 ± 0.002  ms/op

Our numbers moved up, but they are still pretty reasonable. One more time with 1000 lookups in the same method:

Benchmark                        (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measure1000Lookups    10000  avgt   15  7.781 ± 0.235  ms/op
ServiceTest.measure1000Lookups   100000  avgt   15  8.223 ± 0.166  ms/op
ServiceTest.measure1000Lookups  1000000  avgt   15  9.273 ± 0.101  ms/op

Now we are up to 9ms or so to make these 1000 lookups. In the great majority of use cases, a traversal will start from just one starting node, or a few of them. In the rare case where the traversal needs to look at data from hundreds of nodes, it may be worth the effort to add a cache. So let’s give that a shot and benchmark the same tests to compare.

    private static final LoadingCache<Integer, Long> segments = CacheBuilder.newBuilder()
            .maximumSize(1000000)
            .build(
                    new CacheLoader<Integer, Long>() {
                        public Long load(Integer segmentId) {
                            return getSegmentNodeId(segmentId);
                        }
                    });

    private static Long getSegmentNodeId(Integer segmentId){
        final Node node = db.findNode(Labels.Segment, "segmentId", segmentId);
        return node.getId();
    }

Up here we are creating a LoadingCache that will take an Integer as a Key and return a Node ID as our cached value. It is important that the cache is done this way and not by caching whole nodes. If you cache the whole node, then you have to worry about cache invalidation every time you add/remove or change a property. By just caching the Node ids, we don’t have to worry (assuming our key hold values that are immutable). So let’s take a look at our cached lookup implementation:

    @POST
    @Path("/cachedlookup")
    public String CachedLookup(String body, @Context GraphDatabaseService db) throws IOException, ExecutionException {
        ArrayList<Long> idsFound = new ArrayList<>();
        HashMap<String, List<Integer>> input;
        input = objectMapper.readValue(body, HashMap.class);
        List<Integer> segmentIds = input.get("segmentIds");

        try (Transaction tx = db.beginTx()) {
            for (int segmentId : segmentIds) {
                final Node node = db.getNodeById(segments.get(segmentId));

                if (node != null) {
                    idsFound.add(node.getId());
                }
            }
            tx.success();
        }

        return idsFound.toString();
    }

As you can see, it uses the node id to simply getNodeById and go from there. So let’s run our benchmarks again and see what we get:

Benchmark                            (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureOneCachedLookup    10000  avgt   15  0.011 ± 0.000  ms/op
ServiceTest.measureOneCachedLookup   100000  avgt   15  0.011 ± 0.000  ms/op
ServiceTest.measureOneCachedLookup  1000000  avgt   15  0.012 ± 0.000  ms/op

A single lookup here takes about half the time, but still a very small amount of time. When we bump up 10 lookups we are almost the same speed as a single lookup and roughly 10x better than using the index for lookups.

Benchmark                             (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureTenCachedLookups    10000  avgt   15  0.013 ± 0.000  ms/op
ServiceTest.measureTenCachedLookups   100000  avgt   15  0.013 ± 0.000  ms/op
ServiceTest.measureTenCachedLookups  1000000  avgt   15  0.014 ± 0.000  ms/op

Now once we move up to doing 1000 lookups we see a real difference. 9ms vs 0.3ms. That’s 30x better than our original attempt.

Benchmark                              (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measure1000CachedLookups    10000  avgt   15  0.323 ± 0.003  ms/op
ServiceTest.measure1000CachedLookups   100000  avgt   15  0.320 ± 0.004  ms/op
ServiceTest.measure1000CachedLookups  1000000  avgt   15  0.316 ± 0.003  ms/op

If you’ve seen the Neo4j Internals blog post you will immediately recognize why it’s so much faster. In the search case we are looking for a node id in a b-tree, in the cache case we are going to it almost directly. This is the same reason Neo4j is so much faster at joins than your RDBMS. It doesn’t have to lookup foreign keys in an index, it goes to them directly.

So the takeaway here is, only resort to this type of internal caching if you are performing lots of lookups in your queries and performance is critical. One last thing… if you do delete nodes, make sure to call cache.invalidate(value) just to be safe.

As always, code is available on github.

Update: Can we go faster? Yes we can. Let’s add a high performance primitives collection library to our project called Koloboke from Open HFT.

        <dependency>
            <groupId>net.openhft</groupId>
            <artifactId>koloboke-api-jdk6-7</artifactId>
            <version>0.6.6</version>
        </dependency>
        <dependency>
            <groupId>net.openhft</groupId>
            <artifactId>koloboke-impl-jdk6-7</artifactId>
            <version>0.6.6</version>
            <scope>runtime</scope>
        </dependency>

We’ll create an Integer Long Map that is mutable so we can add and remove entries as needed.

private static IntLongMap segmentMap = HashIntLongMaps.newMutableMap();

We’ll add a new method that looks just like the others except it will use “computeIfAbsent” to either get an existing Node Id for a Segment, or find it in the index. If you are using Java 7:

for (int segmentId : segmentIds) {
                final Node node = db.getNodeById(
                        segmentMap.computeIfAbsent(segmentId, new GetSegmentNodeId()));

You’ll need to create an IntToLongFunction class:

    class GetSegmentNodeId implements IntToLongFunction {
        @Override
        public long applyAsLong(int segment) {
            return  db.findNode(Labels.Segment, "segmentId", segment).getId();
        }
    }

If you are on Java 8 (make sure you use “-jdk8″ in your dependencies) and you can just use a lambda:

            for (int segmentId : segmentIds) {
                final Node node = db.getNodeById(
                        segmentMap.computeIfAbsent(segmentId,
                                key -> db.findNode(Labels.Segment, "segmentId", segmentId).getId()));
            }

How much faster is it…

Benchmark                             (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureOneCachedLookup2    10000  avgt   15  0.004 ± 0.000  ms/op
ServiceTest.measureOneCachedLookup2   100000  avgt   15  0.004 ± 0.000  ms/op
ServiceTest.measureOneCachedLookup2  1000000  avgt   15  0.004 ± 0.000  ms/op

Benchmark                              (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measureTenCachedLookups2    10000  avgt   15  0.006 ± 0.000  ms/op
ServiceTest.measureTenCachedLookups2   100000  avgt   15  0.006 ± 0.000  ms/op
ServiceTest.measureTenCachedLookups2  1000000  avgt   15  0.007 ± 0.000  ms/op

Benchmark                               (size)  Mode  Cnt  Score   Error  Units
ServiceTest.measure1000CachedLookups2    10000  avgt   15  0.231 ± 0.002  ms/op
ServiceTest.measure1000CachedLookups2   100000  avgt   15  0.231 ± 0.003  ms/op
ServiceTest.measure1000CachedLookups2  1000000  avgt   15  0.231 ± 0.005  ms/op

…about twice as fast in the single and ten lookup tests, and 50% faster in the 1000 lookup test.

Another Update: This collection is not concurrent, so you’ll have to pre-load all the nodes you are going to cache before using it. If you plan on adding nodes to the cache while the system is running you’ll have to catch any ConcurrentModificationExceptions and retry, so that makes things a little messier than the Guava Loading Cache which handles concurrency for you.

The Java Zone is brought to you in partnership with AppDynamics. AppDynamics helps you gain the fundamentals behind application performance, and implement best practices so you can proactively analyze and act on performance problems as they arise, and more specifically with your Java applications. Start a Free Trial.

Topics:

Published at DZone with permission of Max De Marzi, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}