Cooncat Publishing

So far in this series, I’ve been describing a scheme for Unique ID’s. We’ve gone through the mental gyrations of what the parts of an ID should consist of, but haven’t come to a conclusion yet of the final format. As you’ve seen by now, the more characters we have available, the more comprehensive our ID format can be. With registration, we can also cut down the size to a short string.

Before we cut it down to it’s minimum, though, let’s look at values. I’d like to format to not only be able to store unique ID’s, but also values so that we can map relationships against a number. Once we find a minimal length for useful numbers, then we can determine how to wedge our ID scenario into that space.

Through the many years I’ve been crunching number, I’ve been bitten so many times by software, especially Microsoft Excel, using floating point values. For the unaware, when a program stores a value, it has a choice — it can either store it as an integer, or use much less space by storing an approximation. The software very seldom tells you this, and if you rely on your numbers, your computer lies to you. I just can’t describe how wrong that situation is. By the time you notice the tiny bit off you are, you’re already layers deep in hundreds of calculations. Good accounting programs store numbers as integers, and even in MS Access currency is normally stored as an integer with four decimal places.

Hey, I don’t mind if a computer program can’t store pi accurately, but I want it to tell me that what it displays is an approximation if I need to know that for my purposes. So if it’s an approximation, how was it done? Was it truncated, rounded up, rounded down, an exact half? If a computer makes a mess of things on my behalf, I want to know about it.

When computers give you a number, such as 5,000, there is no information as to how many significant digits there are in that number. If this represents 5 boxes of 1000 paper clips, you can be pretty sure that each box is almost exact, maybe have one or two extra clips in it. But I could have derived this from the number of feet I guessed was equal to one inch I measured on a map. If I make a mess of things, I want to be able to document it.

If I know that a value is wonky, I can, if needed, use techniques such as significance arithmetic to make known how much an end result is off. It makes a big difference if the basis of the number is measured or counted.

Now we can start to enumerate the relationship of a value to a stored number in a computer: the basis of how it was derived, the number of significant digits, the accuracy of the final digit, it’s sign, and exponent. Some of these can be encapsulated in the way most computers store a floating point number; sign, exponent, and fraction are encapsulated in 32 or 64 bits of binary data.

Time pervades all things. I remember in my first Geometry class, the teacher talked about three dimensions, and time being the fourth. This concept bothered me for months, it just didn’t seem right to me. A line, for instance, cannot be if it doesn’t exist for a period of time. And when old teach was trying to describe to us what a point was, the geometric concept of it, my confusion cleared up. A point, he said, had no length, breadth, or height, it was only a point. At which one of my little imaginary friends whispered in my ear, “But it has time. It is a point in time.”

I digress from the subject at hand to make my own point. Mankind’s understanding of the true nature of time is weak. We may think we can go back and forth in time if we can just find a De Lorean and build a flux capacitor out of junk parts in the garage. Or we can accept Stephen King’s explanation of the Langoliers, that eat away the past after the present is gone.

In my previous missive on Unique ID’s, I went through all the mental hoops I could to describe how an ID generator could be itself identified by thread, process, computer, and public parts. Now, we’re only required a series of numbers to finish off the Unique ID. That could be as simple as a counting loop within the thread of execution, and we might want to keep that in mind.

But usually, computer programs have a very simple way to get a time value, and that can come to our aid. At the risk of defying the You Ain’t Gonna Need It (YAGNI) concept, we’ll go on to figure out how we can incorporate time into our Unique ID’s, or at least leave room for implentation if we want.

Suppose we have gone through all the hoops to figure out “the best thing to do” for our computer process, and we have two or more items of equal weight (whatever we’ve defined that to be) in contention to be the winner. We could pick a random choice, or as random as our machine will give us, and hope that luck will lead us clearly to our goals. But if we keep arriving at this same decision, we could end up that a value is never chosen, that our luck has gone sour and karma has caught up with us. So, one way out of this mess is to choose the oldest value.

Having a timestamp at this point in the consideration process is extremely handy, in that we don’t need to implement another decision level. We just pick the ID with the smallest time value. Next time we’re at this juncture, our old value will have been gone, and we’ll pick the oldest ID now available.

One of the downsides of doing this is that we’re now shifting our decision process from a comparison of whole ID’s to a relation of embedded values. That will add additional complexity to our program thread, and we’ll only be able to determine its effectiveness when we finally get to implementation.

If we look back at the original spec for UUID’s, we see that time is captured at 100 nanosecond intervals, or 10 million of these values per second is our granularity. When programming, though, we’re very lucky if we can get anything better than granularity to the second without using an external library or weird procedure. I’ll suggest here, then, we keep our programming simple and call seconds as “close enough” for our purpose. This will probably bite me in the butt later as well, because YAGNI.

So, let’s look at the value that gets returned when we ask for a POSIX time value. It is “the number of seconds elapsed since midnight UTC of January 1, 1970, not counting leap seconds.” If we store this value in 32 bits of information, we’ll run out of space on January 19th, 2038. But this doesn’t bother us, as we’re adamant to store our ID in base 32, and that will get us through the rest of this millennium with seven characters.

Something cropped up when I was originally researching UUID’s for this project a few years back, what do you do when someone sets the clock backwards? Well, we could just ignore it if we trusted our system to check for duplicate values. That’s not in my nature, though, as we should try to do always be doing right thing when dealing with lower level functionality.

The UUID spec says they would use a Clock ID set at a random value, then increment the ID by one if a reset was detected. Well, that’s fine, it keeps the ID unique. But it doesn’t help with the sorting, because you’d have to intersperse the clock ID into the right spot in the series somehow. Thankfully, these resets are few and far between, and hopefully the clock resets on a fairly regular basis.

That just about wipes me out as far as using time as part of our Unique ID scheme. I ain’t gonna use it, mostly because of the shifting context problem. We’ll think about keeping space for it in our final version, as we can capture it with eight characters.

Is a UUID really unique? This post seems to think there are problems. http://blog.joeware.net/2005/06/19/42/

There are several types of UUID’s, the most common being (supposedly) randomly generated, and one based on time and MAC addresses. There are problems with each of these.

The above link has good opinions on the fallacy of randomly generated addresses. Besides bad implementations, there is also a great reason for not using them — they are so damn unique, there is no way to look them up unless you have a database of all which are in use. You can’t specify ranges where you can divide the database into segments.

MAC addresses have nothing to do with Apple Macintosh computers, although the computers have MAC addresses in them. MAC addresses are unique identifiers brazed in read-only on your computer’s network card. Ranges of MAC addresses are doled out by a central authority to network card manufacturers.

There is something obviously wrong with that scheme in that we’re expecting the network card manufacturers to police themselves to ensure that addresses aren’t duplicated. When you pay sixteen dollars for a piece of hardware, made in the poorest manufacturing environment in the world, do you really feel that good that the manufacturer has paid their dues and been in compliance with this directive, that isn’t even backed by law? OK, but just be sure you take that painted wooden play block out of the baby’s mouth.

If that wasn’t enough, there’s a real possibility that someone has set up duplicate MAC addresses on their LAN intentionally. Some ISP’s (Internet Service Providers) and wireless configurations use MAC addresses to allow access to the next network over. Of course, you and I wouldn’t come up with a scheme like that since it relies only on the obscurity of the address, and not a shared secret or hashed password. But that’s the nature of the market.

So what happens is that the customer registers his MAC address with the ISP, and is now allowed into the network as long as he’s using that ethernet card. Later on, the customer trades in his computer, or replaces the ethernet card that’s gone bum, or sticks a router in between his computer and the internet. Whatever he’s done, he needs to change is MAC address; either register his new one with the ISP, or change the new hardware back to the old MAC address. Given the choice, he will probably not want to spend quality time listening to muzak while waiting for customer service to answer the phone and then find someone at the ISP that has a clue.

So, especially with the “insert a router in the mix” scenario, there’s a good possibility that there is a duplicate MAC address on the LAN. Intentionally done, with good intentions. The intentions don’t even have to be good, as one could use this scheme to leech access from the ISP from multiple locations.

Finally, MAC addresses are a lousy way to do generate unique ID’s that represent real-world data. That’s because in order to look up an unknown piece of information, you need a map of MAC addresses to computers. When collaborating with others outside your LAN, you’d have to replace your UUID’s to some central MAC address.

You also have a problem within one computer itself. You may want multiple programs to be able to generate unique ID’s, but there is only one MAC address per computer. So, you would have to have some locking mechanism so that more than one process can’t have access to the ID generator at a time. This scenario is even specified in the UUID specification document, www.opengroup.org/dce/info/draft-leach-uuids-guids-01.txt

Providing a system-wide lock makes programming a tool much harder; harder than it has to be. At a particular time, a process has a unique process id, which the computer uses to keep track and schedule each thing that’s going on. Well, with Linux 2.6 (the current version), there are a maximum of 1,073,741,824 process id’s. Encoding that many numbers in base32 takes six characters. And in the future, Linus and crew might up that number — you would think a million things going on with a computer at once would be enough for anybody!

So it’s probable that when implementing a unique ID with a process ID incorporated, we’ll need to cut this number down to size. That would mean some extra programming in order to have a registry of processes allowed to give out an ID. So we’re back to a locking mechanism, but arguably more effective, since you only need to register the process one time, and provide some way to clean up the mess after you’re done.

But let’s say we didn’t want to make a registry, and just confine our ID’s to the computer we’re using right now. After all, we don’t need to come up with an ID for the computer until we’re ready to share the information outside of it, right? So we can flag the ID with a code that says we’re only going to have it valid on the current computer, then list the process ID after it. We could even have a multithreaded program be able to give a short ID to each thread; creating a in-memory mapping within a single program would be fairly easy, you’d just map the thread id when creating the thread, if mapping is really needed.

Now, if we’re not using MAC addresses as the primary way to identify the computer, what’s the best way to go about it? More registries, please! We’ll want to make some kind of global registry so that an unknown value can be looked up, and if the author wants to share that information, then you’d be able to get its definition.

At the public side, we may want to consider a range of five characters, which our base32 converter tells us will provide over 35 million identifiers. So that’s how many public domains would be available, and is still in the realm of a Sqlite database lookup without making a small computer go dizzy. Five’s a good number, since a sequence of characters can be read off over the phone and copied down without the recipient losing track of the characters spoken.

Now we have to have some layers of redirection from the public identifier to the individual computer. For one, this gives us some sense of privacy. But even more important, this allows a large organization to give a level of autonomy to its divisions.

Two base32 characters provide up to 1024 values, while one character is 32. So with five more characters, we can allocate one character to the process id registration (32 processes per computer), 1024 computers per division, then 1024 divisions per public identifier. Now, I’m curious if that would be a good spread. What do you think?

Another way would be to have 1024 process id’s per computer, using two characters, then let the public ID have 32,768 computer id’s to dole out as they see fit. Any more than that, they’d just need to get another public ID. Now I feel better about using that spread.

If we wanted to go whole hog, then five characters would be enough to directly convert internal IP addresses to computer id’s, no matter if they used the 10.x.x.x, 172.x.x.x or 192.161.x.x scheme, or even a combination of those. But now that we’re at our five-character maximum, we have to allocate even more characters for our process id. And if the company started using sub-sub-nets, which may be common with virtualized OS’s, internal IP addresses can very possibly be duplicated, as I’ve seen with VirtualBox.

For giggles, the full range of IPv4 address space comes to 4000000 in base 32. Some expect exhaustions of address ranges as early as two years from now; but I just don’t think it’ll happen for a while. But if the world moves to IPv6, that’s over ten with 38 zeroes after it — way to big for us to make a usable ID format out of anyway.

Well, I think that about covers all the scenarios we’d want to identify who generated the ID. Note that I am not making any effort to conceal privacy, if one wants to keep the data anonymous then they will have to arrange for an anonymous computer to do their dirty work. I would rather forsake simple anonymity than to make our ID’s so that they are incompatible with any type of accountancy.

Now we need a series of unique numbers for our ID generator to use. Which will bring me to my next post, about the strange concept we call time ….