Auto-generated ids should put the mac address before the timestamp

[jpountz]

Given that the terms dictionary has the structure of a trie, it compresses better when there are shared prefixes. By putting the mac address before the timestamp in our auto-generated ids, the _uid field would compress better. I suspect it will also slightly help for stored fields since there will be longer sequences of bytes that are shared across values (the mac address followed by the first bytes of the timestamp).

[mikemccand]

This is a good idea! I'll try this, and test indexing perf. I think it should give smaller terms dict and shouldn't impact lookup performance, except maybe from more free RAM for the OS.

[jpountz]

For the record I was running simulations of disk space savings related to #18154 and found out that this change would reduce disk usage for the uid field by about 30% for a single node cluster (so there is a single mac address) that indexes about 100 docs per second (the rate is important as higher rates mean that timestamps have longer common prefixes). Also the size reduction is similar to the disk overhead of having points and doc values enabled on a float field that stores random values, so these savings should be noticeable for applications that store small documents.

[jpountz]

We could also go further and interleave the bytes of the timestamp and the sequence number.

[mikemccand]

I simulated "100 docs / sec" by forcing the timestamp to advance by 10 msec on each ID on current master:

diff --git a/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java b/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
index d1a22a1..2422399 100644
--- a/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
+++ b/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
@@ -57,7 +57,9 @@ class TimeBasedUUIDGenerator implements UUIDGenerator {
             // Don't let timestamp go backwards, at least "on our watch" (while this JVM is running).  We are still vulnerable if we are
             // shut down, clock goes backwards, and we restart... for this we randomize the sequenceNumber on init to decrease chance of
             // collision:
-            timestamp = Math.max(lastTimestamp, timestamp);
+            // nocommit
+            timestamp = Math.max(lastTimestamp+10, timestamp);
+            //timestamp = Math.max(lastTimestamp, timestamp);

             if (sequenceId == 0) {
                 // Always force the clock to increment whenever sequence number is 0, in case we have a long time-slip backwards:

I ran that 6 times and got these total docs/sec:

mike@beast2:/l/es.dev$ grep "Total docs/sec" before*.log
before1.log:Total docs/sec: 54424.1
before2.log:Total docs/sec: 54471.2
before3.log:Total docs/sec: 53751.9
before4.log:Total docs/sec: 54300.0
before5.log:Total docs/sec: 54890.4
before6.log:Total docs/sec: 54452.5

and index sizes:

mike@beast2:/l/es.dev$ grep "index size" before*.log
before1.log:index size 4310740 KB
before2.log:index size 4305668 KB
before3.log:index size 4307560 KB
before4.log:index size 4312356 KB
before5.log:index size 4311084 KB
before6.log:index size 4300544 KB

Then I tried this patch, swapping the MAC address and timestamp, and also simulating "100 docs/sec":

diff --git a/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java b/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
index d1a22a1..7f30067 100644
--- a/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
+++ b/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
@@ -57,7 +57,9 @@ class TimeBasedUUIDGenerator implements UUIDGenerator {
             // Don't let timestamp go backwards, at least "on our watch" (while this JVM is running).  We are still vulnerable if we are
             // shut down, clock goes backwards, and we restart... for this we randomize the sequenceNumber on init to decrease chance of
             // collision:
-            timestamp = Math.max(lastTimestamp, timestamp);
+            // nocommit
+            //timestamp = Math.max(lastTimestamp, timestamp);
+            timestamp = Math.max(lastTimestamp+10, timestamp);

             if (sequenceId == 0) {
                 // Always force the clock to increment whenever sequence number is 0, in case we have a long time-slip backwards:
@@ -70,10 +72,16 @@ class TimeBasedUUIDGenerator implements UUIDGenerator {
         final byte[] uuidBytes = new byte[15];

         // Only use lower 6 bytes of the timestamp (this will suffice beyond the year 10000):
-        putLong(uuidBytes, timestamp, 0, 6);
+        //putLong(uuidBytes, timestamp, 0, 6);

         // MAC address adds 6 bytes:
-        System.arraycopy(SECURE_MUNGED_ADDRESS, 0, uuidBytes, 6, SECURE_MUNGED_ADDRESS.length);
+        //System.arraycopy(SECURE_MUNGED_ADDRESS, 0, uuidBytes, 6, SECURE_MUNGED_ADDRESS.length);
+
+        // Only use lower 6 bytes of the timestamp (this will suffice beyond the year 10000):
+        putLong(uuidBytes, timestamp, 6, 6);
+
+        // MAC address adds 6 bytes:
+        System.arraycopy(SECURE_MUNGED_ADDRESS, 0, uuidBytes, 0, SECURE_MUNGED_ADDRESS.length);

         // Sequence number adds 3 bytes:
         putLong(uuidBytes, sequenceId, 12, 3);

mike@beast2:/l/es.dev$ grep "Total docs/sec" after*.log
after1.log:Total docs/sec: 53288.5
after2.log:Total docs/sec: 53840.9
after3.log:Total docs/sec: 54685.0
after4.log:Total docs/sec: 52242.2
after5.log:Total docs/sec: 54789.3
after6.log:Total docs/sec: 54465.0
mike@beast2:/l/es.dev$

and index sizes:

mike@beast2:/l/es.dev$ grep "index size" after*.log
after1.log:index size 4232136 KB
after2.log:index size 4231428 KB
after3.log:index size 4242724 KB
after4.log:index size 4232464 KB
after5.log:index size 4221880 KB
after6.log:index size 4227432 KB

Results are noisy but it seems like the change may slow indexing some? Thinking about it more, I think those added 9 byte (after the 6 MAC address bytes are base64 encoded) common prefix adds a non-trivial cost because on each ID lookup the FST must walk each of those 9 bytes before getting to the "interesting" bytes (that change across documents). We could maybe optimize such cases, by having the FST record its common prefix, and doing a (faster) check on each incoming ID.

We could maybe do the opposite, and "rotate" the timestamp so that the leading bytes change more frequently (it's a long value, milliseconds). This would make a larger index but maybe faster lookups.

It did make the overall index maybe ~2.8% smaller.

[jpountz]

This is interesting. This probably also means that prepending the type in the uid is a mistake.

[mikemccand]

This probably also means that prepending the type in the uid is a mistake.

Hmm, indeed.

Must we even prefix type# in the auto-id case? I guess at read time there are places where we expect to parse a _uid value back into its type and id?

[jpountz]

It looks tricky to me to remove the type from the uid without removing the concept of type entirely. However something we could explore would be to put the type in the end of the uid in the auto-generated case (or in all cases actually) and/or to make mappings generate unique ids for each type so that we can use these (short) ids in the uids rather than the actual type names.

[polyfractal]

Obligatory stats nerd interjection: the difference in the two indexing speeds is not statistically significant. Two-tailed, unpaired, unequal variance t-test gives a p = 0.2889, which is greater than the standard 0.05 threshold.

The change in index size is statistically significant though: p = 5.773 x 10^-09

Obviously this is on a small sample size, so the indexing speed significance may change if more samples are added (a true mean shift, or an increase in variance, etc). But from the current data I don't think we can draw any conclusions.

[mikemccand]

Aha, thank you @polyfractal. So we really can't conclude there is any meaningful difference yet ... too much noise in the measurement.

I'll run it some more times :)

[mikemccand]

OK I ran some more trials ... maybe @polyfractal you could run the statistical analysis again? Thanks!

Before docs/sec (now 20 trials):

54424.1
54803.8
56129.1
53756.7
53817.1
54910.2
53056.8
53524.4
52600.5
53839.0
52737.8
54471.2
54252.8
53751.9
54300.0
54890.4
54452.5
52735.3
53426.8
54348.3

After docs/sec:

53288.5
53578.1
52666.7
52669.9
51953.5
52132.6
54437.0
53650.7
52747.6
53737.2
51327.8
53840.9
53180.1
54685.0
52242.2
54789.3
54465.0
53210.0
54774.2
53202.8

[polyfractal]

Ok, now it's statistically significant :)

p = 0.02701