Ayende @ Rahien

Robert commented on Implementing CreateSequentialUuid()

Tue, 21 Sep 2010 08:56:33 GMT

Use Ticks - that gives you an always increasing number. Then every machine has a unique ID number. Figure out the precedence used in sorting. Shove the ticks into whatever positions in the GUID are more significant, find a position that is less significant than the where the ticks go and put the machine ID # in that. Sequential guids. Different ticks - always increasing. Same tick? Every machiine can make a GUID on the same tick and the IDS will now be significant and make them sequential up until the next tick.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 21 Sep 2010 08:16:05 GMT

From, I added it to the queue, will be published in about 1 week

From commented on Implementing CreateSequentialUuid()

Mon, 20 Sep 2010 23:41:14 GMT

Ayende: What solution did you end up with ? or havent decided yet ?

Andrew commented on Implementing CreateSequentialUuid()

Thu, 16 Sep 2010 11:59:11 GMT

Martin: Yep sorry. One idea for having multiple machines generating the same GUIDs is to perhaps: 1) Generate a random GUID on application startup (one time only) that is added to every GUID made by that server 2) OR; get a one time GUID assigned by a central server (?) so that it is guaranteed to be unique Then each server will have its own namespace of GUIDs.

Martin commented on Implementing CreateSequentialUuid()

Thu, 16 Sep 2010 02:39:55 GMT

Andrew: My option that i wrote earlier is like that and includes also a global identifier. The problem with the internal counter is that two guids created at the same time (tick) on two different machines wont necessary be truly sequential. The counter at one machine can be at 1000 and 2000 at another. I cant think of a better option though.

Andrew commented on Implementing CreateSequentialUuid()

Wed, 15 Sep 2010 12:09:07 GMT

Can you maybe keep another counter in memory (sequence) so that you generate IDs like

Ayende Rahien commented on Implementing CreateSequentialUuid()

Wed, 15 Sep 2010 07:36:59 GMT

Andrew, Two guids created on the same tick wouldn't be sequential

Andrew commented on Implementing CreateSequentialUuid()

Wed, 15 Sep 2010 00:32:01 GMT

I was thinking along the same lines as Imram; why not just use DateTime.Ticks as your 'guid'.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 21:56:00 GMT

Kargath, Multiple masters. And yes, there are versions. But documents etags don't need to be unique globally, just per machine.

Karhgath commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 16:06:59 GMT

Can you have multiple masters in your replication scheme? Or just a single master/many slaves relationship? Do you version each object in Raven and thus have an etags history? (you talked about changes) Like document A with etags 1,2,3,4,5(current). Are you using etags that are unique across documents (globally), and must remains unique because you use them for something else? SInce you're talking about Guid, I assume so. I also assume that you want your etag to be in a format compatible with Guid? All these are restrictions that makes this case hard indeed. Let me think about it. I can see the problem if do you track changes, and even moreso if your etags needs to be globally unique and follow a guid format.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 14:22:54 GMT

Karhgath, The etag will change on each document change, but for replication purposes (among others), it is important to be able to capture all changes.

Karhgath commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 14:06:32 GMT

@Ayende Aren't etag actually not supposed to be unique/sortable across URL/entity/resource? I don't know why you're using etag in a sorting manner across entities since it shouldn't be used as such at first glance. What exactly are you doing with your etag that requires this? As far as I know, I've only used etag as a comparison parameter to check if a resource changed, not to sort em. Maybe you're using the wrong tool? As you can see by the response, this is non-trivial and probably has a better and simpler solution than those kinds of ids.

Imran commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 12:52:07 GMT

Also if you need per process uniqueness you could stick a discriminator value (possibly a guid) to the end of the tick value to handle date time collisions on the same machine.

Imran commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 12:40:07 GMT

Since you stated clocks can be assumed to be more or less in sync and you mentioned previously that duplicate identifiers are not a problem then why can't you just something like ticks since some reference date e.g. ticks since 1900 or something of that sort. Maybe I am over simplifying this.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 12:16:33 GMT

Ants, I know, but for my scenarios, it doesn't matter

Ants Aasma commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 12:10:47 GMT

Clocks are never 100% accurate, so sooner or later you can observe a situation where you see that event A, with ticks value T_A has happened on machine A, and a tiny bit later machine B thinks that event B with ticks value T_B not happened, even though T_B < T_A. I don't know what you're going to use this for, so this might not be an issue for your usecase.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 11:07:02 GMT

Venu, Except that this creates a big problem in the sense that you need to persist the values, get the value on startup, etc. There are simpler solutions

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 11:03:11 GMT

Steve, Have fun making it work correctly without locks in a multi threaded env.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 11:01:56 GMT

Agarwal, The reason for the requirements is that I am using this guid as the etag for documents, and I need to compare that to previous known etag to know if I see this before or not.

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 11:00:01 GMT

Josh, It doesn't have to be numerically sequential, no. It just have to always sort properly

Ayende Rahien commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 10:59:12 GMT

Ants, Note that I am explicitly stating that clock sync is a given. Therefor, you can relay on the clocks of the different systems to be accurate. More formally: Time T is defined as the Ticks value on each machine, all references to prior / after with regards to the different machines refer to the current Ticks value, which was synced to be identical at a previous point in time.

Set commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 09:55:55 GMT

>just because sql server accuracy when getting time is only 1/300th of a millisecond. Not with SQL Server 2008, there are more datetime formats now.

Rafal commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 08:31:16 GMT

And will there be a solution to this riddle? Because I suppose it will be based on some assumptions not mentioned here that weaken the requirements a bit.

Venu commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 05:55:16 GMT

Ayende Assuming that you you already have the implementation of generating sequential guids, and since you mention that this problem manifests itself only when the machine reboots, can't you have a guid tracker componenet in each server. When there is a reboot, it would ask every machine in the cluster (using gossip protocol???) what their current max guid value is (or what it should be at a future time) and use that to compute what its new base/seed ought to be. -Venu

Steve commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 05:55:05 GMT

I wouldn't get too clever. I'd create something similar to Oracle's concept of a sequence generator either in the database or outside as a service. Start off with a seed Guid, write a routine to increment it by 1, and then persist it so it maintains state between reboots. It'd have to have some lock, or be a singleton or something to insure uniqueness, but even so I suspect you could generate these pretty fast.

Martin commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 04:29:06 GMT

I guess it cant really get to be more precise than ticks. So to make it unique you have to create your own rules / assumptions, which you can base your logic on. For an example, that ids created on one machine is always created after or before another machine (if the exact same date time). That should make it possible to know how to handle the id in the logic (depending on what you need to use it for). The first thing that comes to my mind is creating a structure like this Days/Ticks Offset - Global id - Internal Counter If you want it to be 16 bytes as a guid. Date and time could be split into days and ticks, and allocated 6 bytes, If you let the days take up 2 bytes it will give you an increasing number for next 179 years (approx. if you use 1/1-2010 as an offset date), and then let the ticks take up the last 4 bytes. If a limit of 65536 for the global id is okay it will take up 2 bytes. If the global id is used per document, database, process, shard is up to you. You just have to assign it before it starts creating ids, Then there is 8 bytes left for the internal counter, which is used to assure that the number is sequential if two ids is generated at the exact same time (using the same "global id"). This somewhat mimics the guid.comb, but is precise down to ticks and contains a consistent rule you can use in your logic when handling the ids. Basically of course it is just a very long number. Ids generated after the predefined offset date will be something like: days ..........ticks .......global....internal id 00001 0123456789 00001 000...........01 00001 0123456789 00001 000...........02 00001 0123456789 00002 000...........01 00001 0123456789 00002 000...........02 00001 0123456789 00002 000...........03 They are sequential with the precision of ticks and the rule that one is always created before or after another (depending on the global id) if created at the exact same time, and truly sequential within that "global id". The only other alternative that i can think of is a central service handing out ids (which i assume you dont want). At least if it should be sequential you dont want anything to be random. ... on a different note. A few things I have never understood about the Guid.Comb implementation in Nhiberntate is why it doesnt use a more recent offset date. Also there is no reason to divide the ticks with 3.333... just because sql server accuracy when getting time is only 1/300th of a millisecond. Also the actual type of the guid created should be of type "SqlGuid" and not "Guid" for sorting correctly (if used in code), as far as i remember. Martin ... im really tired so probably i am not thinking clearly ... :)

Ivan Krivyakov commented on Implementing CreateSequentialUuid()

Tue, 14 Sep 2010 03:42:42 GMT

Sorry if someone already proposed it - I would use machine specific guid (for uniqueness) plus a timestamp (for increment). That is, if you don't care about the number of bits it consumes.

Agarwal / Simon Labrecque commented on Implementing CreateSequentialUuid()

Mon, 13 Sep 2010 23:01:42 GMT

josh, I fully agree that duplicates are usually bad, and that time sync isn't reliable; but I'm working within the hypothesis Ayende has given us. That said, I too would like to know *why* this problem needs solving. In my day job, I tend to fight anyone coming to see me with the solution; I'd rather like to see the problem, then insure that the chosen solution is the best. So, why do you need this "special" ever-incrementing GUID, Ayende? ;)

Alois Kraus commented on Implementing CreateSequentialUuid()

Mon, 13 Sep 2010 19:26:55 GMT

Well the point is that you need the time. My previous guid approach can very simple be enhanced to e.g. shave off 8 redundant bytes and fill the rest with the true guids from the OS or Guid.CreateNew. That way you have shortened time stamps with a range of e.g. 30 years if you use an int for both and stil have 8 bytes left which can be taken from the "true" guid approach the OS uses. Yours, Alois Kraus

josh commented on Implementing CreateSequentialUuid()

Mon, 13 Sep 2010 18:56:34 GMT

Agarwal / Simon, Duplicates are a bad idea generally; and completely opposite the point of a GUID, which should be unique everywhere. Also, Time sync isn't always reliable. Given the precision sensitivity (milliseconds/nanoseconds), you just can't absolutely ensure that level of sync. In my experience anyway.