Re: [PATCH] Time-based RFC 4122 UUID generator

[Helge Deller <deller@gmx.de>]

On Wednesday 21 November 2007, Theodore Tso wrote:
> On Tue, Nov 20, 2007 at 10:59:58PM +0100, Helge Deller wrote:
> > > Even with a futex? Or userspace atomics? 
> > 
> > Yes, you'll need a futex or similiar.
> >
> > The problem is then more, where will you put that futex to be able
> > to protect against other processes ?
> > 
> > Best solution is probably shared memory, but then the question will
> > be, who is allowed to access this memory/futex ?
> >
> > Will any process (shared library) be allowed to read/write/delete it?
> >
> > At this stage you then suddenly run from a locking-problem into a
> > security problem, which is probably equally hard to solve.
> 
> Basically, the only way to solve this problem 100% in userspace would
> be with a userspace daemon running as a privileged user, and some kind
> of Unix domain socket.

Yes, probably.
 
> Patches to implement this in the e2fsprogs UUID library would be
> greatfully accepted.
> 
> > Sounds simple and is probably fast enough.
> >
> > But do you really want to add then another daemon to the Linux
> > system, just in case "some" application needs somewhen a UUID ?
> > 
> > And I think such an implementation is more complex, would need more
> > memory, file handles, and so on than this simple kernel patch.
> 
> Well, it probably is less code, but keep in mind to really get things
> right, you need to store the UUID counter on disk, so there is some
> complexity which is needed in userspace anyway.

Yes, it's at least needed for the case when the wall clock is wrong.
If it's syncronized with NTP (or similiar), it's not really needed.

Anyway, if this patch is accepted, I'll be happy send patches against the 
various bootup scripts to save the last seq_number at shutdown and
restore it at bootup. Maybe something similiar as the /var/lib/random-seed
which is saved by /etc/init.d/halt in Fedora.
 
> One bigger question which is why do you want to use time-based UUID's?
> With the kernels random number generator, the random UUID's should be
> quite good enough for your purposes.

The big difference between random UUIDs and time-based UUIDs is that
time-based UUIDs can be used more efficiently as indexing keys in databases.
The true randomness of random UUIDs just break performance, while
with some further tricks you can get time-based UUIDs easily sorted.
At least we saw a big speed difference when we used time-based keys, as
they e.g. were used on Windows with MS SQL server. On Linux I personally 
would like to see a similiar speedup and for that really unique time-based
UUIDs are needed.

> > I think mkfs was a very bad example from my side. I should not have
> > mentioned this one.  Nevertheless, time-based UUIDs are used in
> > quite many other and more critical applications than e2fsprogs
> > tools.
> 
> Actually, these days e2fsprogs uses random-based UUID's.

Yes, but still libuuid from e2fsprogs does a good job for what's really 
needed and sufficient for the e2fsprogs tools like mkfs.
Sadly the time-based variant of libuuid still hase some way to go.
Initially I really wanted to send patches for libuuid to fix the 
time-based variant, but now I really think the kernel-solution is 
the better, smaller, cleaner and more reliable approach.

Helge
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/