Alternative schemes for Elasticsearch generated document IDs?

[cdahlqvist]

I have recently run some benchmarks simulating dense nodes, and have noticed that heap usage related to storage of document IDs is the main driver behind heap usage for at least some types of data. To see how different types of document IDs perform/behave, I created a Rally challenge based on the rally-eventdata-track to index ~25GB data into single-shard indices using a few different types of document IDs.

I imported the metrics in Elasticsearch and got the following when visualizing it in Kibana:

1. Heap usage per 120M documents by type of document ID

2. Index size on disk for 120M documents by type of document ID

Most of the alternative ID types tested contains a large random portion (UUID4, SHA*). It is interesting to see that the autogenerated IDs seem to take up less space on disk but use more than twice the amount of heap compared to the other types of IDs.

As using autogenerated IDs give a speed advantage at indexing time, I think it would be great to make the format/.structure of autogenerated IDs configurable per index so the user can choose between optimizing for heap or disk usage. This does not need to support arbitrary formats, but one option that is more efficient with respect to heap usage would be useful.

[elasticmachine]

Pinging @elastic/es-search-aggs

[colings86]

As using autogenerated IDs give a speed advantage at indexing time, I think it would be great to make the format/.structure of autogenerated IDs configurable per index so the user can choose between optimizing for heap or disk usage.

It would be useful to know the indexing speed for each of these options too since we would want to be clear with the user whether choosing a particular option also influences the indexing speed as well as heap usage and index size

[cdahlqvist]

@colings86 I can set up and run this challenge against an Elastic Cloud cluster for comparison. It indexes the same amount of data using the following 3 main ID schemes:

• Autogenerated IDs
• UUIDs (uuid4)
• UUID (uuid4) prefixed by hex-encoded epoch

Details about the ID generation can be found here.

[cdahlqvist]

@colings86 I ran the challenge overnight and got the following average indexing throughout when indexing 100 million documents (~20GB shard size) against a single 32GB Elastic Cloud node:

• Autogenerated IDs: 25.5k EPS
• UUIDs (uuid4): 18.9k EPS
• UUID (uuid4) prefixed by hex-encoded epoch: 22.2k EPS

I used these document ID types as an example and am not suggesting we necessarily use one of them. The ideal solution would be if we could create a variation of the currently used scheme that has similar heap usage profile as these alternative ID types while still retaining the characteristics that make autogenerated IDs so fast to index.

[DaveCTurner]

the characteristics that make autogenerated IDs so fast to index

One of these characteristics is that we know the provenance of an autogenerated ID, so we know whether we can skip the checks for the existence of another document with the same ID. With externally-provided IDs we always have to check. Importantly, this is independent of the format of the ID.

[cdahlqvist]

@DaveCTurner Excellent. I remember that but was not sure if it was still in place or not. I assume that means that if we created an alternate autogenerated ID format that has a different heap usage profile, it would by default then also be faster than my benchmarks as we also for this format would be able to skip the checks?

[DaveCTurner]

In theory yes, although nothing is certain in these situations without measurement.

However, it puzzles me that autogenerated IDs take up approximately twice the terms memory of the other formats. A nice round multiple like that makes me wonder if we are perhaps double-counting something, or mistakenly generating twice as many terms or something like that?

[jpountz]

The 2x factor is probably a coincidence. However it's expected that patterns that compress well also require more memory. Memory usage is due to the FST that records shared prefixes of terms per block of 25-40 terms, so the number of prefixes that are recorded in the FST doesn't depend too much on the pattern, but the length of the recorded prefixes does.

Even in the worst case, these numbers are pretty good in my opinion: 40MB of terms dictionary still gives a memory/disk ratio of 1.6%. Though I agree it is a bit disappointing to spend most memory on the _id field for an append-only use-case.

[cdahlqvist]

@DaveCTurner helped me set up a build where I could test a few different permutations of the current autogenerated ID format. Of the 6 variations I tested (auto-v2 - auto-v7), a few seemed to perform significantly better than the existing scheme. For each ID type I indexed 100 million documents from the rally-eventdata-track into a single shard index (Rally ran on the same host as Elasticsearch):

The auto-v4 version (code below) was a bit faster (~2.5%, which could be due to cloud variability), took up 13% less space on disk (not forcemerged, so could be down to the test ending at a different stage in the merging cycle) and used almost 40% less heap compared to the default auto format.

This type of ID was generated by simply rearranging the order of the various components that make up the current ID:

// We start with the MAC address
byte[] macAddress = macAddress();
assert macAddress.length == 6;
System.arraycopy(macAddress, 0, uuidBytes, i, macAddress.length); 
i += macAddress.length;

// Then we put the remaining bytes, which will likely not be compressed at all.
uuidBytes[i++] = (byte) (timestamp >>> 8);
uuidBytes[i++] = (byte) (sequenceId >>> 8);
uuidBytes[i++] = (byte) timestamp;

uuidBytes[i++] = (byte) sequenceId;
// changes every 65k docs, so potentially every second if you have a steady indexing rate
uuidBytes[i++] = (byte) (sequenceId >>> 16);

// Now we start focusing on compression and put bytes that should not change too often.
uuidBytes[i++] = (byte) (timestamp >>> 16); // changes every ~65 secs
uuidBytes[i++] = (byte) (timestamp >>> 24); // changes every ~4.5h
uuidBytes[i++] = (byte) (timestamp >>> 32); // changes every ~50 days
uuidBytes[i++] = (byte) (timestamp >>> 40); // changes every 35 years

assert i == uuidBytes.length;

Another version that also performed quite well was auto-v2:

// Initially we put the remaining bytes, which will likely not be compressed at all.
uuidBytes[i++] = (byte) (timestamp >>> 8);
uuidBytes[i++] = (byte) (sequenceId >>> 8);
uuidBytes[i++] = (byte) timestamp;

uuidBytes[i++] = (byte) sequenceId;
// changes every 65k docs, so potentially every second if you have a steady indexing rate
uuidBytes[i++] = (byte) (sequenceId >>> 16);

// Now we start focusing on compression and put bytes that should not change too often.
uuidBytes[i++] = (byte) (timestamp >>> 16); // changes every ~65 secs
uuidBytes[i++] = (byte) (timestamp >>> 24); // changes every ~4.5h
uuidBytes[i++] = (byte) (timestamp >>> 32); // changes every ~50 days
uuidBytes[i++] = (byte) (timestamp >>> 40); // changes every 35 years
byte[] macAddress = macAddress();
assert macAddress.length == 6;
System.arraycopy(macAddress, 0, uuidBytes, i, macAddress.length);
i += macAddress.length;

assert i == uuidBytes.length;