Explore using timebased decentralized UUID for autogenerated IDs

[s1monw]

Today we use UUIDs which are very costly to compute since they use SecureRandom and they have some properties that might not play very well / or as well as they could with the Lucene internal datastructures since they don't share a common prefix. With a time based ID we can potentially remove the need for bloom fitlers on the ID fields since the shared prefixes across the IDs might be all in memory and that would speedup updates dramatically. Something along the lines of flake ids would be very interesting since it has this property

[GaelTadh]

What we are proposing is since a machine may have several es instances running in parallel. We will generate a secure xor of the mac address, prefixed by a 64bit timestamp and postfixed by an atomic counter.

timestamp64bit-macAddr-counter

[mikemccand]

+1 for prefixing the ID with timestamp, or anything "predictable": this is better for Lucene's term dictionary since sometimes it will be able to short-circuit a lookup and know the ID cannot reside in a given segment. It's also important that the IDs are fixed-length, so that all terms happen in the "leaf blocks" of the dictionary. Finally, something like base36 is best, since we tell the terms dict writing to put 25 - 48 terms per block (so up to base 48 should be good too).

[GaelTadh]

@mikemccand why does the encoding matter ? Or do you mean between 36 and 48 bytes long ?

[mikemccand]

@GaelTadh what I mean is each digit should have no more than 48 values (and lower would be better: less scanning within a block). This is because the terms dictionary assigns terms into blocks of at most 48 terms at once.

However ... thinking about this more, I think this matters less, since the IDs won't be sequential here.

[GaelTadh]

Ahh ok that makes sense.

[GaelTadh]

I used jmh (http://openjdk.java.net/projects/code-tools/jmh/) to do some micro benchmarks on the following code :

,,,,

@GenerateMicroBenchmark
public void secureRandomUUID(){
    randomBase64UUID(SecureRandomHolder.INSTANCE);
}

@GenerateMicroBenchmark
public void insecureRandomUUID(){
    randomBase64UUID(new Random());
}


@GenerateMicroBenchmark
public void timestampUUID(){
    timestampBase64UUID();
}

,,,

Which gave the following output :

Benchmark	Mode	Samples	Mean	Mean error	Units
o.s.UUIDBenchmark.insecureRandomUUID	thrpt	200	5155.120	16.137	ops/ms
o.s.UUIDBenchmark.secureRandomUUID	thrpt	200	469.264	3.287	ops/ms
o.s.UUIDBenchmark.timestampUUID	thrpt	200	5703.520	13.350	ops/ms

[GaelTadh]

I'm gonna run these again and remove the new call from insecureRandom.

[GaelTadh]

Benchmark	Mode	Samples	Mean	Mean error	Units
o.s.UUIDBenchmark.insecureRandomUUID	thrpt	200	7348.913	16.807	ops/ms
o.s.UUIDBenchmark.secureRandomUUID	thrpt	200	475.986	1.489	ops/ms
o.s.UUIDBenchmark.timestampUUID	thrpt	200	5698.841	23.908	ops/ms