A RESTful Protocol to Add/Modify/Delete Elements of a Collection

I've been reading the SCIM specification recently.

[What does SCIM stand for? There's a moral-of-the-story here, by the way. SCIM originally stood for Simple Cloud Identity Management. Now it stands for System for Cross-domain Identity Management. The moral of the story is, if you're swayed by the buzzword of the day, you will be forced into embarrassing retreat at some point. Cross-domain Identity Management was what it was always about. What a shame someone felt the need to jump onto the cloud bandwagon.]

Anyway, coming back to the topic of this post, I realised that one of the aspects dealt with by the SCIM specification was a much more general problem that would benefit from a standard approach.

I was struck by the similarity of 3 types of operations in the SCIM protocol, though not impressed by any of them.

One set of operations deals with adding, modifying and deleting multi-valued attributes of a user, e.g., the set of addresses or email IDs.

A second set deals with adding, modifying and deleting users as members of a group.

SCIM uses a RESTful API, so for these sorts of partial updates to a larger entity, it uses PATCH. A single PATCH command can be used to simultaneously add, modify and delete attributes of an entity, or to add, modify and delete members of a group. [PATCH when used to update one or more single-valued attributes is fairly straightforward, so I'm not talking about that here.] I suspect that PATCH is so new that best practice around its use has yet to emerge, which accounts for some of the ugliness I'm about to describe.

A third set of operations is called 'bulk operations', and deals with a collection of operations on multiple entities, which could include add, modify and delete operations. This is physically formatted as a POST with nested POST, PATCH and DELETE operations as attributes within the document.

To my mind, these three situations are conceptually the same (a set of fine-grained operations grouped into a single composite operation), therefore the same mechanism should ideally be used for all of them.

As it turns out, SCIM uses many different mechanisms, all ugly.

1. Multi-valued attributes of a user:

(In the spec document linked above, scroll up and down a bit to search for these examples)

Some of the ugliness comes from passing 'operation:"delete"' as an attribute of the document. After arguing for years that a GET request with URL parameter "?operation=delete" is not RESTful, we can't now barefacedly offer a "RESTful" API that does the same thing. True, this is not a GET, so it's probably not as awful, but this is a really bad "smell" that suggests poor design at some level.

The syntax to replace a user's primary email address with another one and simultaneously demote the previous primary email address to the status of just another email address is more than just ugly, it's horrific. Do have a look for yourself, if you can keep from gagging.

2. Members of a group:

(In the spec document linked above, scroll up and down a bit to search for this example)

Deleting all members from a group is even uglier. There is nothing in the message to suggest that a deletion is taking place! There's a "meta" attribute that has a value equal to the set of attribute names whose (multiple) values are being deleted. If that confuses you, you now know what I mean.

3. Bulk operations:

The main operation is a POST to an arbitrary URI which could be called "/bulk" or something similar.

There are nested operations within it that reflect operations on various entities.

As you can see, these are 3 entirely different mechanisms for essentially the same desired behaviour. Can't we use the REST philosophy of polymorphic verbs to make this interface more uniform?

I would like to propose a simpler scheme that uses explicit identifiers for every sub-entity that may need to be independently manipulated (updated or deleted). This is similar to having resource identifiers, but at finer levels of granularity.

All three sets of operations should have a common structure like this:

PATCH /main-entities/29d70c13-8651-41ce-97f8-c82ccdfcd6d6

(or POST /bulk-operations)

Host: example.com

Accept: application/json

Authorization: Bearer h480djs93hd8

Content-Length: ...

{

  operations:

  [

    {

      operation: "POST",

      URI: " /sub-entities",

      sub-entity:

      {

      ...sub-entity attributes

      }

    },

    {

      operation: "PUT",

      URI: "/sub-entities/dced46ca-b96d-44dd-b494-41e5de9405b6",

      sub-entity:

      {

      ...sub-entity attributes

      }

    },

    {

      operation: "DELETE",

      URI: "/sub-entities/12feb1db-8031-4a23-8810-bccfffb13f56"

    }

  ]

}

i.e., the nested operations should be RESTful operations in their own right, with standard HTTP verbs and standard URIs using the enveloping entity's URI as their base URI. How do we know what the URIs of the sub-entities are? The server should generate one for every array element that is created (multi-valued attributes of an entity), and return those URIs with the "201 Created" response, as well as in response to any GET on the main entity. That will then provide a handle for the client to specify fine-grained operations on the sub-entities.

I also don't like the SCIM convention of returning a "200 OK" even for a bulk request where different sub-operations may have had different outcomes. This is as bad as HTTP tunnelling in SOAP where the HTTP response could be a cheery "200 OK", but the message inside contains a SOAP fault.

There is a WebDAV status code for exactly this kind of situation, - "207 Multi-Status". That's what should be used.

HTTP 1.1/207 Multi-Status

Content-type: application/json

{

  operation-results:

  [

    {

      operation: "POST",

      URI: "/sub-entities",

      status: "200 OK",

      Location: "/sub-entities/c44fcc7b-8881-4f0f-b5fb-b2344615cc34",

      request:

      {

      ...sub-entity attributes repeated for verification

      }

    },

    {

      operation: "PUT",

      URI: "/sub-entities/dced46ca-b96d-44dd-b494-41e5de9405b6",

      status: "409 Conflict"

    },

    {

      operation: "DELETE",

      URI: "/sub-entities/12feb1db-8031-4a23-8810-bccfffb13f56",

      status: "404 Not found"

    }

  ]

}

This is a clean syntax, easily understood, and uniformly applicable when dealing with attributes or sub-entities of an entity, or with bulk operations. All it requires is for resources and resource collections to be identifiable at finer levels of granularity as well, i.e., attributes that are array elements.

I don't believe that's too much of an ask. UUIDs are cheap and plentiful, and the alternative is an ugly mess.

An Optimistic Approach to Identity

I've been working in the Identity Management area for a few years now, and I've seen three different industries up close (banking, insurance and telecom). What I'm struck by in all these industries is that none of them has historically been customer-centric in their business approach. For decades, banks have always looked at their customers through the prism of accounts, insurance companies through policies, and telecom companies through billing accounts and sometimes carriage services (broadband or mobile services). And everywhere, the holy grail is the same - "single view of customer". Identity and Access Management (IAM) is the way these organisations aim to achieve single view of customer as well as other benefits.

However, IAM initiatives at organisations in all these industries have generally floundered. Why?

I believe that IAM is simple but subtle. That's why although it's not hard to design and deliver an IAM system, it's also treacherously easy to get it wrong.

Some of the major reasons why organisations struggle with IAM are these:

1. Rather than bite the bullet and create a top-level data entity called "customer" with its own unique identifier, organisations choose what they consider a cheaper compromise because of a misplaced belief that using a surrogate for customer (i.e., account, policy, billing account) would somehow do the job. Reality check: it doesn't, and it's more expensive in the long run.

2. Even where identifiers are created for customers, these are not carefully designed. The result is that many identifiers that are chosen have business meaning. It's quite funny at one level to see a system designed with a person's email address as their identifier, and where the major business pain point is that it's very hard to handle the situation where a customer changes their email address. (Why are we not surprised?) Quite often in such cases, there is no other way around the problem but to delete and re-create the customer record.

3. Even where organisations avoid the first two mistakes and embark on an IAM initiative to tie customer data across multiple systems to a new, unique and meaning-free customer ID, they run into logistical problems relating to the existing user base. They struggle to "marry" records across systems to the appropriate customer entity because of the sheer volume of data involved, the cost of changing existing systems, the unreliability of matching algorithms and the need to replace engines while the plane is flying, so to speak. The two problems with matching algorithms are false positives (two or more customers being assigned the same identifier) and false negatives (a customer being assigned two or more identifiers).

I have some suggestions that can make life easier.

1. Create a database external to all existing systems that will maintain mappings. [Resist the temptation to migrate customer attributes from other systems to this one. This is just a mapping database, not a customer master. Use Master Data Management (MDM) principles instead to keep data in source systems in sync.]

2. Use a universally unique and meaning-free identifier for customers. Version 4 (random) UUIDs are a great scheme to use.

3. Adopt an optimistic model of "eventual consistency". I.e., generate a new customer UUID corresponding to every system record, in effect assuming (in the case of a bank) that each account belongs to a different customer, then pare them down to reflect known relationships. 

a) You can generate UUIDs for a system in an optimistic way because the probability of two UUIDs conflicting is infinitesimally low, even if you have hundreds of millions of customers. You can check for duplicates out of band if you're paranoid.

b) Similarly, you can optimistically generate UUIDs in a federated way (i.e., each system generates its own UUIDs corresponding to its surrogate records). The probability of conflict is so low it's worth doing this and checking for duplicates out of band.

c) You can afford to start with a system with a large number of false negatives (but no false positives) because this corresponds to a siloed organisation with no "single view of customer". False positives are a greater danger, and we avoid that with this scheme.

d) You can use the existing intelligence in your systems (i.e., the knowledge of which records belong to the same customer) to merge customer UUIDs relating to the same physical customer by eliminating all but one of them at random. Since UUIDs are meaningless, it doesn't matter which one you keep and which ones you remove.

Now you're no worse off than you were before in terms of data quality (i.e., your data is just as clean in terms of known relationships). But structurally, you're far better off because you now have a customer data entity for the first time. As your data quality improves with more reliable mappings, the siloes effectively disappear and you get to a "single view of customer" with no more changes to data structures or processes.

In the case of a telecom company, your mapping database will now consist of three parts. The first part will map customer UUIDs to billing accounts. The second part will map customer UUIDs to product holdings (mobile, broadband and other carriage services, media products, etc.) The third part will map customer UUIDs to other customer UUIDs to reflect corporate organisational structures and household relationships. With this model, the many problems that telecom companies currently face will simply melt away.

- We can see all the product holdings of a customer to determine what else to sell them. We can see this at an individual customer level as well as at the level of a household or organisational unit.

- We can sell media products even to customers who haven't purchased an underlying carriage service

- We can group billing accounts independently of product holdings. In a household, the kids use various products but mum or dad alone may pay the bill.

As you can see, this kind of design isn't hard. But it requires conceptual clarity around the nature of Identity. As I said before, IAM is simple but subtle. It isn't hard to design and deliver an IAM system, but it's treacherously easy to get it wrong.

The Case for Watermarked UUIDs

UUIDs are my latest toy
They fill my little world with joy

Forgive me for waxing lyrical. The more I play with UUIDs, the more wonderful uses I find for them.

Take one-time tokens used for idempotence, for instance.

Joe Gregorio's nugget on how to use UUIDs with hashes to prevent spoofing got me thinking. What if the hash could be hidden in the UUID itself? UUIDs are so roomy and spacious, they can tuck a lot of things inside without losing their core property of universal uniqueness.

But first, a summary of Joe's piece for those too impatient to go over and read it.

Idempotence is (or should be!) a basic concept that all IT folk are familiar with. Performing an idempotent operation more than once has exactly the same effect as doing it once. The way this is commonly implemented is through the use of one-time tokens. [If you do a 'View Source' on your bank's transaction confirmation page (the one that asks "Are you sure?"), you may see a hidden form variable with a large random value. That's the one-time token the bank uses to ensure that you don't end up posting a transaction twice even if you hit the submit button twice. It's a wonderful way to ensure a measure of reliability over an unreliable Internet.]

Joe Gregorio suggests the use of UUIDs as one-time tokens for RESTful idempotent services, but also raises a potential problem with the use of raw UUIDs. Anyone can spoof a token by just generating a UUID. For a server to be able to recognise that a UUID is a genuine one-time token that it itself had handed out earlier, it would normally be expected to store the token somewhere so it can verify it when it's presented later on. But such a naive design would open the server up to a "resource exhaustion attack". A malicious user (or bot) can swamp the server with millions of requests for one-time tokens, and the server's database will rapidly fill up with useless UUIDs that are never going to be used.

To address this, Joe suggests a hash. If the generated UUID is combined with a secret string that only the server knows, and this combination is hashed, then the combination of UUID and hash will let the server validate its genuineness, because no one else can generate a valid hash for a random UUID without knowing the server's secret string. In Joe's model, the one-time token is not the raw UUID, but a combination of the UUID and a hash. With this design, the server doesn't have to store a one-time token when it's handed out, only when it's actually used to perform a transaction. The number of such UUIDs can be controlled, because spoofed UUIDs can be filtered out through a mere computational check.

I think this solution is elegant and ingenious, but I believe it can be made even more "clean".

A UUID looks like this:

e5b0eb4c-aeb9-411c-bf3f-cdd207096d3e

It consists of 5 groups of hex characters separated by hyphens, and the regular expression for it is

[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}

What I want to do is replace the last set of 12 hex characters with another one representing a hash (or at least part of a hash). Then, while the UUID will still look like a UUID (and indeed, will be a valid UUID), it is in effect "watermarked" by the server and can be verified by computation alone.

What do we lose?

Mathematically, we lose a great deal of uniqueness. We're now dealing with just 20 hex characters instead of 32 (It's not 24, because the 4 hyphens don't count). 20 characters are still a lot, and we actually get something back through the 12-character hash, because this is calculated not just on the 20-character UUID prefix but on the combination of the prefix and the server's secret string. So it's an independent 12-character hex string, and while it may be a more sparse range than its length may suggest, it's still something. So I don't believe we lose too much from a uniqueness perspective. UUIDs are so huge you can trim them and still not encounter conflicts.

Is there a danger that some random UUID out there may accidentally be computed as a valid watermarked UUID because its last 12 characters miraculously match the hash? Well, the probability of this is 1 in 16 raised to the power 12, which is about 1 in 3 quadrillion. I'd take my chances.

Architecturally, it would seem that we have introduced meaning into what should have been a meaningless identifier, and that would then open the door to implicit dependencies (tight coupling) and consequent brittleness. However, on closer inspection, there is no way an external system can seek to build any dependency on the structure of a watermarked UUID, because without a knowledge of the server's secret string, the hash cannot be externally calculated. The UUID remains necessarily opaque to all external parties. The implicit dependency of one part of the UUID on another would seem to be a limitation too, but this is by design! The "limitation" serves to exclude spoofed UUIDs.

And so, I believe there is no real downside to the use of watermarked UUIDs. On the contrary, they retain the visual elegance of plain UUIDs and furthermore simplify the design of idempotent services by encapsulating the entire token-validation function within the service with no leakage through to the interface.

I've written a couple of classes in Java that should help developers get started (no warranties, of course). The base class is called TokenWatermarker, and it performs the basic hashing and string concatenating logic on any token string. It can watermark LUIDs, for example. It also performs verification of previously watermarked tokens, of course. Then there's the UUIDWatermarker class that extends TokenWatermarker and provides the same capability for UUIDs.

Running the compiled classes using "java TokenWatermarker" or "java UUIDWatermarker" will print out a sample output that will show you how these classes work.

Enjoy!

The Case for Locally Unique IDs (LUIDs)

It should be no surprise to regular readers of this blog that I am in love with UUIDs. As I have said before, they are an inexhaustible source of identifiers that are meaningless (not a pejorative term!) and whose generation can be distributed/federated without danger of duplication. As a result, they are an extremely powerful means of providing a uniform and federated identity scheme.

As a SOA-indoctrinated IT practitioner, I am loathe to expose domain-specific entity identifiers to the larger world because such leakage leads to tight coupling and brittle integration. Yet identifiers of "resources" must often be exposed. How do we do this? Even "best practice" guidelines fail to adequately admonish designers against exposing domain-specific identifiers. [e.g., Subbu Allamaraju's otherwise excellent RESTful Web Services Cookbook talks about "opaque" URIs in recipe 4.2 but ends up recommending the use of internal entity identifiers in recipe 3.10 :-(.]

My point is simple. If the 'employee' table in my application's database looks like this

+------+--------------+---------------+-------------+
| id   | first_name   | last_name     | dob         |
+------+--------------+---------------+-------------+
| 1122 | John         | Doe           | 12-Jan-1960 |
+------+--------------+---------------+-------------+
| 3476 | Jane         | Doe           | 08-Sep-1964 |
+------+--------------+---------------+-------------+
| 6529 | Joe          | Bloggs        | 15-Jun-1970 |
+------+--------------+---------------+-------------+

I do not want to be exposing resources that look like these

/employees/1122
/employees/3476
/employees/6529

I don't want to expose my application's local primary keys to the entire world. They may be "meaningless" but they're still coupled to my domain's internal data structures. I need something else.

My standard solution so far has been the magnificent UUID. I add a candidate key column to my table, like so

+------+--------------+---------------+-------------+--------------------------------------+
| id   | first_name   | last_name     | dob         | UUID                                 |
+------+--------------+---------------+-------------+--------------------------------------+
| 1122 | John         | Doe           | 12-Jan-1960 | 4885c205-8248-4e5b-9c45-4d042e7cc992 |
+------+--------------+---------------+-------------+--------------------------------------+
| 3476 | Jane         | Doe           | 08-Sep-1964 | cdbf87dd-93cb-4c53-9c5d-718c596b0a00 |
+------+--------------+---------------+-------------+--------------------------------------+
| 6529 | Joe          | Bloggs        | 15-Jun-1970 | 73feb1bf-e687-4d58-9750-5bf98ca7b9fa |
+------+--------------+---------------+-------------+--------------------------------------+

or I maintain a separate mapping table, like so

+------+--------------------------------------+
| id   | UUID                                 |
+------+--------------------------------------+
| 1122 | 4885c205-8248-4e5b-9c45-4d042e7cc992 |
+------+--------------------------------------+
| 3476 | cdbf87dd-93cb-4c53-9c5d-718c596b0a00 |
+------+--------------------------------------+
| 6529 | 73feb1bf-e687-4d58-9750-5bf98ca7b9fa |
+------+--------------------------------------+

and I expose my resources like so

/employees/4885c205-8248-4e5b-9c45-4d042e7cc992
/employees/cdbf87dd-93cb-4c53-9c5d-718c596b0a00
/employees/73feb1bf-e687-4d58-9750-5bf98ca7b9fa

I've still got unique identifiers, they're guaranteed not to conflict with anything else in time and space, and more importantly, my domain-specific identifiers remain hidden. I can now even change my entire domain model, including identifiers, and still preserve my external contracts. That's SOA.

But the sad fact of the matter is that many legacy systems and packaged software do not readily support UUID datatypes or even char(36) columns for various reasons. I have recently heard of a far-sighted software vendor that has provided for a "Public ID" field in their database tables for this precise reason, i.e., to allow an externally visible identifier to be specified for their entities. But alas, the column is defined to be varchar(20), much too small to hold a UUID.

It occurred to me that there is nothing sacrosanct about a 128-bit UUID (expressed as a 36-character string). It's just that the larger a random number gets, the more remote the probability of conflict with another such random number. 128 bits is a nice, safe length. But smaller lengths also have the same property, only with a lower degree of confidence.

The constraints of vendor packages like the one I described above led me to postulate the concept of the LUID (Locally Unique ID). This is just a string that is smaller than 32 hex digits (a UUID has 32 hex digits and 4 hyphens in-between). I call this a Locally Unique ID because the smaller it gets, the lower the confidence with which we can claim it to be universally unique. But we may still be able to rely on its uniqueness within a local system. If I'm only holding details of a few thousand employees (or even a few million customers) in my database, an LUID may still be expected to provide unique identifiers with a reasonable degree of confidence.

That vendor package definitely cannot hold a UUID such as "2607881a-fec1-4e5d-a7fc-f87527c93e2d" in its "Public ID" field, but a 20-character substring such as "4e5da7fcf87527c93e2d" is definitely possible.

Accordingly, I've written a Java class called LUID with static methods

String randomLUID( int _length ) and
String getLUID( String _uuidString, int _length )

The first generates a random hex string of the desired length (without hyphens). The second chops a regular UUID down to a hex string of the required length, again without hyphens.

You can download the class from here. Just running the compiled class with "java LUID" will result in some test output which should illustrate how it works. Feel free to incorporate it into your own projects, but be warned that there is no warranty ;-).

Of course, there is a limit to how small an LUID can become before it loses its utility, but I'm not going to draw an arbitrary line in the sand over this. The class above represents mechanism, not policy. Application designers need to think about what makes sense in their context. An LUID of the appropriate length can enable them to implement SOA Best Practice by decoupling externally visible resource identifiers from internal entity identifiers (another example of the difference between Pat Helland's Data on the Outside and Data on the Inside) when a standard UUID cannot be used.

Bottomline: If you can use a standard UUID, do so. If you can't, consider using an LUID of the kind I've described. But always hide the specifics of your application domain (which include entity identifiers) when exposing interfaces to the outside. That's non-negotiable if you want to be SOA-compliant.

Update 27/06/2010:
I should perhaps make it clear what my proposal is really about, because judging from a reader comment, I think I may have created the impression that all I want is for entity identifiers to be "meaningless" in order to be opaque. That's actually not what I mean.

To be blunt, I believe that any entity/resource that is to be uniquely identified from the outside needs _two_ identifiers (i.e., two candidate keys). One of them is the "natural" primary key of the entity within the domain application. The other is a new and independent identifier that is required to support the exposure of this entity through a service interface (whether SOAP or REST). There should be no way to derive this new key from the old one. The two keys should be independently unique, and the only way to derive one from the other should be through column-to-column mapping, either within the same table or through a separate mapping table as I showed above.

To repeat what I wrote in the comments section in reply to this reader:

There was a content management system that generated (meaningless) IDs for all documents stored in it, and returned the document ID to a client application that requested storage, as part of a URI. At one stage, it became necessary to move some of the documents (grouped by a certain logical category) to another instance of the CMS, and all the document IDs obviously changed when reloaded onto the other instance. The client application unfortunately had references to the old IDs. Even if we had managed to switch the host name through some smart content-based routing (there was enough metadata to know which set of documents was being referred to), the actual document ids were all mixed up.

If we had instead maintained two sets of IDs and _mapped_ the automatically generated internal ID of each document to a special externally-visible ID and returned the latter to the client, we could have simply changed the mapping table when moving documents to the new CMS instance and the clients would have been insulated from the change. As it turned out, the operations team had to sweat a lot to update references on the calling system's databases also.

I hope it's clear now.

1. Entity only seen within the domain => single primary key is sufficient
2. Entity visible outside the domain => two candidate keys are required, as well as a mapping (not an automated translation) between the two.
3. UUID feasible for the new candidate key => use a UUID
4. UUID not possible for some reason => use a Locally Unique ID or LUID of appropriate length (code included)

Modelling Resources from First Principles

I've been providing architectural advice to a group of colleagues who are building a set of services. Without going into too much detail, they need to uniquely identify some entities. Clients of the services use these identifiers as references when they return to make related queries on these entities. They've proposed using UUIDs as the unique identifiers, and while I liked the idea, I thought it was too simplistic. There was more to the requirement than just unique identifiers.

They're actually dealing with two types of entities - widgets (say) and requests for widgets. These are different because a request can pertain to a set of widgets, so it may be necessary to model them distinctly. The service interfaces dealing with requests and widgets may need to be distinct as well.

Mind you, these services are not going to be REST services. But having been exposed to the RESTian way of thinking, I immediately thought of resource representations for the two types of entities. Rather than plain old UUIDs, I thought there should be a degree of structure around them (but not so much detail as to make the scheme brittle and inflexible).

Something like these, in other words:

http://www.mycompany.com/widgets/4f138ff2-362f-4e35-8f9e-173290fe86d7

http://www.mycompany.com/widget-requests/eabf5bdb-9800-4af5-9ad7-32c3b95fc48a

However, this suggestion proved to be a surprisingly hard sell. The cross-examination was withering.

Why all the extra information?
Why http://?
Why www.mycompany.com?

Why not a simpler scheme like these examples show:

widget:4f138ff2-362f-4e35-8f9e-173290fe86d7

widget-request:eabf5bdb-9800-4af5-9ad7-32c3b95fc48a

I found I had to retrace my steps and work through my reasoning from first principles. In the process, I learnt a great deal about naming.

My initial response was to point my colleagues to points 7 and 8 of "Common REST Mistakes", where we are admonished not to try and invent our own proprietary object identifiers, and not to try for "protocol independence" (i.e., avoid HTTP URIs). But this wasn't too convincing.

I made a bit of progress by getting agreement on the following:

1. It probably made sense to distinguish between widget identifiers and widget-request identifiers, so some sort of prefix to distinguish between them was necessary. UUIDs alone were probably not enough.
2. It also probably made sense to specify the "domain" within which these resources were being identified, so the "mycompany" string probably belonged somewhere as well.

But then, why not just these:

mycompany:widget:4f138ff2-362f-4e35-8f9e-173290fe86d7

mycompany:widget-request:eabf5bdb-9800-4af5-9ad7-32c3b95fc48a

Frankly, I hated this. My point was that such a format, even though "simple", would have to be explained to anyone looking at it. The structure wasn't immediately obvious. Worse, it was ambiguous and could be extended by later designers in ways that violated the original designers' intent. To this, the counterargument was that the knowledge of the format was only required on the server side. To the client, the whole name was just going to be an opaque string, - a reference ID.

I wrestled with this objection for a while. Then I proposed a guiding principle that given a choice between two naming conventions, a universally understood one was preferable to one that we made up ourselves, provided it wasn't unnecessarily complex.

My research led me to the definition of a URN (Universal Resource Name). What I learnt from this was that in order to name something, we first need to specify a "scheme" that then defines what the rest of the name denotes according to the predefined format for that scheme. The name of the scheme is followed by a colon, then the rest of the name is something that can only be interpreted according to the rules specified by that scheme.

In other words, a standard name (URN) looks like this:

<scheme name>:<some scheme-specific format>

A common example is

"http://www.mycompany.com/widgets/4f138ff2-362f-4e35-8f9e-173290fe86d7" (Heh!)

It's important to point out that "http" in the string above does not refer to the HTTP protocol! It's the name of a "scheme". What does this mean?

Well, in the URN "file:///home/ganesh", the string "file" is not a protocol, because more than one protocol may be used to get to the file.

Similarly, in the URN "mailto:ganesh@mycompany.com", the string "mailto" is not a protocol. SMTP is the actual mail protocol.

[For those familiar with XML namespaces, when we say "xmlns='http://www.example.com/schema'", the URN being referred to here is not necessarily a web page that one can point a browser at. It just needs to be a unique string.]

So we're not necessarily modelling our resources as web resources. All that the "http" scheme defines is that after the colon (":"), there is a scheme-specific structure that specifies a few things.

There are two slashes, then there's a dot-separated domain name, then a slash, then a "resource path" which is itself slash-separated. So that's what a URN conforming to the "http" scheme looks like:

"http" (the name of the scheme)
":" (the colon separating the name of the scheme from the scheme specific structure. This is from the basic definition of a URN)
"//" (the "http" scheme just specifies this, OK?)
"www.mycompany.com" (this is the dot-separated domain name)
"/" (this is the first slash that signifies that the domain name is terminated)
"widgets/4f138ff2-362f-4e35-8f9e-173290fe86d7" (all of this is the "resource path" , and internal slashes are possible, as we can see)

So now going back to our guiding principle (using a well-understood format is preferable to rolling our own) as well as the two points on which there was agreement (i.e., that we may need to qualify the resource's UUID with the type of resource as well as the organisational domain), it looks like the "http" scheme of the URN naming standard fits the bill. This is a well-understood way to include both a domain and a resource path to provide some structure around an already unique ID.

I concede that the "www" prefix of the domain could confuse. All we really need to identify the domain is "mycompany.com".

And so, a unique, standards-based and minimal way to name resources in this business domain would be

http://mycompany.com/widgets/4f138ff2-362f-4e35-8f9e-173290fe86d7

http://mycompany.com/widget-requests/eabf5bdb-9800-4af5-9ad7-32c3b95fc48a

Death of the Directory

The LDAP directory is a strange beast. It's a data store, but it's hierarchical in nature, rather like the old hierarchical databases most of us only read about in database textbooks. Hierarchical models, as we know, have inferior expressive power when compared to network and relational models. So shouldn't LDAP directories suffer from similar limitations?

It turns out that they do have similar limitations, and the industry as a whole has been going along with the convenient illusion that the emperor has clothes.

Talking to some old industry hands, I became gradually convinced of something that I've suspected for a while - that the LDAP directory was an invention that solved a temporary problem. The problem has gone away, but the awkward solution remains with us.

Twenty years ago, relational databases were relatively slow and cumbersome. Even reads were slow. Relational databases were therefore not a good fit for read-mostly use cases.

Enter the directory server. Directory servers were designed to be very fast at lookups. They were abysmally slow at updates, but that didn't matter. They were designed mainly for lookups, not for updates. Systems requiring on-line transaction processing needed relational databases.

Somewhere along the way, relational databases got faster. Much faster. Faster at reads as well. And somewhere there, LDAP directories lost their raison d'etre. Only the world never noticed.

Today, LDAP directories do some things well - a very small number of things. They perform authentication very well. Checking a user's credentials (an encrypted password, for example) is a directory server's bread-and-butter. Plus it can enforce password policies, lock accounts on a certain number of failed attempts, etc. These are all built-in features, whereas relational databases are too general-purpose to be able to do these out of the box.

But relational databases are excellent at modelling complex relationships. Directories suck at this. If we try and shoehorn complex structures into a hierarchical model, we will end up with highly unsatisfactory results. Not only will it be inelegant and difficult to understand, the resulting directory bloat will also slow down the system, negating the performance advantage that prompted the choice of the directory in the first place.

The bottomline is, anyone looking to implement a "directory" today would be better off with a hybrid model. They should use an LDAP directory for the limited tasks which it is good at (authentication), and should use a relational database to model and store all other information. They then gain the best of both worlds. The directory server will hold just a handful of attributes needed for authentication.

Hybrids are all very fine, but how do we bridge between a relational database and an LDAP directory? In other words, what do we use to link a record in a database with the corresponding entry in the directory? One candidate would suggest itself to anyone who has been following this blog lately - the Universally Unique ID (UUID).

Of course, most relational databases don't support a native UUID datatype. And many DBAs are used to having identity columns for tables, which are autogenerated by the DBMS. In such cases, the UUID could be another attribute of the same table with a unique constraint defined on it. In other words, the UUID is another candidate key, and this is the one that is used to link an entity within the database to corresponding attributes in other systems. It is truly universal and unique.

How do we provision databases and directories so that their records are consistent? There may be no theoretically satisfactory answer (such as a two-phase commit transaction across both), but there are a number of real-world solutions that are adequate. Organisations may find that the hybrid data store is a pragmatic approach after all.

UUIDs and 2D Barcodes

I wrote about UUIDs (Universally Unique IDs) earlier and speculated about some of their possible uses. One of them, I thought, would be the ability to link them to real-world entities through corresponding 2D barcodes, which are a cool innovation in their own right.

So this weekend, I spent some time trying to combine both technologies.

Apparently, there is a standard called PDF 417 that defines 2D barcodes. There are Open Source encoders and decoders that implement this standard.

I downloaded the Pdf417lib encoder software from SourceForge. It's just a simple Java class that you compile and run, so it's not particularly complex to use. Of course, it's not the best-documented piece of software around, but then again, I can't look an Open Source horse in the mouth. I just wish I knew what the various parameters were so I could tune them. As it was, I tried fiddling around with some of them and settled for something that sort of worked. The main() method of the class is written to generate a PostScript file corresponding to any text string that is fed to it, so all I had to do was pipe in a fresh UUID as that text string, using the java.util.UUID class and its randomUUID() method. I didn't have the appetite to do much more than prove the concept.

I wrote the following bit of code based on the main() method of the Pdf417lib class itself. This is what my test class looks like:



The critical lines here are:

Pdf417lib pd = new Pdf417lib();
pd.setText( UUID.randomUUID().toString() );

I compiled and ran the class quite simply:

$ javac TestUUIDBarcode.java
$ java TestUUIDBarcode test1.ps
$ ps2pdf test1.ps test1.pdf

The "ps2pdf" command, as can be guessed, converts PostScript files to PDF.

I ran this once more just to check that I wasn't getting the same barcode again. The UUID generation is meant to be random, so I should get a new barcode every time.

Here are two of them. I hope they look different enough.






So that's what UUIDs look like when converted into 2D barcodes. All courtesy a standard JDK function and an Open Source library. During the dot-com era, someone could have started a company based on this idea ;-).

The GUIDness of UUID

Microsoft calls it the GUID. The rest of the world calls it the UUID. But regardless of its name, the Universally Unique ID or Globally Unique ID is truly unique.

On the face of it, what's so great about a 128-bit number apart from its length?

Well, plenty. The length, humble as it may seem, crosses a tipping point of sorts, and imparts to the UUID a number of extremely useful properties.

340,282,366,920,938,463,463,374,607,431,768,211,456

That's what 2 to the power 128 is.

What's the probability of two randomly generated 128 bit numbers being the same?

2 to the power -128, or 0.0000000000000000000000000000000000000029.

That's 38 zeroes before the first significant digit. In contrast, the much-vaunted "five nines" reliability of the very best computer systems corresponds to 0.00001.

Now think about it. In the past, if we ever wanted to ensure that two entities were given IDs that had to be unique, the only way to ensure that uniqueness was through a sequence number generator, and one that was maintained at a single point.

Suddenly, the UUID provides a new way. We can randomly generate IDs of this length from any number of independent sources., and they're virtually guaranteed never to conflict! Of course, our pseudorandom number generator had better be cryptographically secure, or all bets are off...

Many languages provide libraries to generate random UUIDs. Java has the utility class java.util.UUID.

One generates a UUID in Java through the static method call UUID.randomUUID(). A toString() will generate a string representation of the UUID, which has 36 characters (32 hex characters plus 4 hyphens at defined places).

E.g., cd6b31ee-a877-41fe-a8f1-87d35d2045a6

This is more compact than the numeric representation and possibly more portable between systems.

There are any number of possible uses for UUIDs, especially when combined with other ingenious innovations like 2D barcodes. Complete identities and properties can be output in barcode format and affixed to real-world entities, providing a ready link to corresponding data in databases.

I've known of the existence of UUIDs for a while, but I'm only now waking up to their potential.

Update 10/09/2009: Here's the regular expression for a UUID:
[0-9A-Fa-f]{8}(-[0-9A-Fa-f]{4}){3}-[0-9A-Fa-f]{12}