Wednesday, August 15, 2012

NDAP - Because User Provisioning Is Too Important To Be Left To LDAP


As I discovered during my foray into SCIM-land, the proposed user provisioning API is extremely clumsy and non-intuitive (check out these examples for yourself), and this is mainly because of multi-valued attributes. By converting multi-valued attributes (arrays) into "key-per-value" attributes (dictionaries), I argued that a much simpler and more elegant API could be developed. While some members accepted that my API was more elegant, the SCIM spec committee overall rejected my proposal as unimplementable. And this was not bloody-mindedness on their part. It is genuinely difficult for existing cloud providers to adopt a sensible and elegant API for user provisioning because they are stuck with legacy data stores that have to support multi-valued attributes, and LDAP directories are the prime culprit. Relational databases are perhaps a tad more flexible than LDAP directories, but it comes down to whether Service Providers would be willing to make changes to their relational schemas. We can pretty much guess the answer to that!

However, it seems a shame to abandon efforts to simplify and standardise the user provisioning API, which is what the SCIM effort should have been all about. Enterprise clients don't care about the legacy constraints of Service Providers. They want a simple and standard API for user provisioning. There may also be emerging Service Providers who are not encumbered by legacy constraints, and who would be willing to explore a better option than SCIM. [There are 3 Gartner people on the SCIM spec committee, but predictably enough, none of them chose to speak up on behalf of their paying customers (enterprise clients) and the one that did speak up supported the interests of incumbent service providers. That sort of behaviour is what lies behind the saying "Gartner spelt backwards is rent-rag."]

I last blogged about the need for "NoLDAP", which I described as stores of JSON documents that permitted no arrays, only dictionaries. Actually, this doesn't have to be restricted to JSON. Any data store that outlaws multi-valued attributes would do as well. In other words, all documents have to be nested dictionaries if they are to allow simple manipulation. The abbreviation "ND" then led to the initially flippant name "NDAP Directory" as an alternative to LDAP directories. But in retrospect, "NDAP Directory" isn't a bad term at all. The "access protocol" part of NDAP is just the RESTful API which includes the "Best Practice" use of PATCH that I suggested earlier.

Here's a high-level picture of how a Service Provider could configure their infrastructure to provide support to conventional authentication mechanisms as always, yet simplify the user provisioning process that has to happen behind the scenes.

The NDAP Directory is the source of truth, and the LDAP Directory is a read-only replica that is used for authentication and retrieval of common user attributes.

Perhaps such a hybrid architecture will be more practical. Will any next-generation SPs rise to the challenge? 

Monday, August 13, 2012

After NoSQL, It's Time For NoLDAP


I've been in discussions with the IETF SCIM working group (formerly Simple Cloud Identity Management and now called System for Cross-Domain Identity Management) about the three suggestions for improvement that I wrote about in my InfoQ article.

One of the things I've learnt from this discussion is that, while I sense a bit of an NIH syndrome in some of the pushback I have received, there are also some genuine technical challenges involved in implementing my ideas. In my article, I stated that the fundamental problem with manipulating resources was multi-valued attributes that lacked a unique key per value. Over the past two weeks of discussion, I'm convinced that I got that absolutely right. Multi-valued attributes are the problem. And the biggest culprit in keeping them entrenched with little hope of change is that legacy beast known as an LDAP directory.

You can see for yourself how clumsy it is in LDAP to update multi-valued attributes. When I googled "multi-valued attributes" and "LDAP" together, I found this prescient piece written by Mark Wahl in 2005. I was amazed to see how accurately he had anticipated the problem:

Unfortunately, some of the emerging protocols which also intend to represent and transfer personal identity information have perhaps taken a step backwards by not even considering these issues [problems with multi-valued attributes], perhaps sweeping them under the rug in the guise of simplicity, XMLification, or "fix in the next version", which only postpone finding interoperable solutions to allowing applications to express the identity entries they want to express.
SCIM is one of these "emerging protocols", and sure enough, the arguments that I have been facing have explicitly cited "simplicity" as the reason not to accept my solution proposal, exactly as Mark Wahl had predicted. However, the real reason for resistance is not about "simple" but about "easy".

It is not easy for SCIM to move to a simple model, and that is the problem. It is more expedient to maintain complexity.

The irony is that the SCIM spec is anything but simple, thanks to multi-valued attributes. This is how the spec proposes to deal with multi-valued attributes:

Multi-valued attributes: An attribute value in the PATCH request body is added to the value collection if the value does not exist and merged if a matching value is present. Values are matched by comparing the value Sub-Attribute from the PATCH request body to the value Sub-Attribute of the Resource. Attributes that do not have a value Sub-Attribute; e.g., addresses, or do not have unique value Sub-Attributes cannot be matched and must instead be deleted then added. Specific values can be removed from a Resource by adding an "operation" Sub-Attribute with the value "delete" to the attribute in the PATCH request body. As with adding/updating attribute value collections, the value to delete is determined by comparing the value Sub-Attribute from the PATCH request body to the value Sub-Attribute of the Resource. Attributes that do not have a value Sub-Attribute or that have a non-unique value Sub- Attribute are matched by comparing all Sub-Attribute values from the PATCH request body to the Sub-Attribute values of the Resource. A delete operation is ignored if the attribute's name is in the meta.attributes list. If the requested value to delete does not match a unique value on the Resource the server MAY return a HTTP 400 error.

Sounds like quite the dog's breakfast, doesn't it?

To be fair, that's the implementation, which is usually hidden from sight. Let's see if the visible API looks any better.

Here's how to delete a single member from a Group, as per the current spec:

   PATCH /Groups/acbf3ae7-8463-4692-b4fd-9b4da3f908ce
   Host: example.com
   Accept: application/json
   Authorization: Bearer h480djs93hd8
   ETag: W/"a330bc54f0671c9"

   {
     "schemas": ["urn:scim:schemas:core:1.0"],
     "members": [
       {
         "display": "Babs Jensen",
         "value": "2819c223-7f76-453a-919d-413861904646"
         "operation": "delete"
       }
     ]
   }

Here's how to delete ALL members from a group according to the current spec:

   PATCH /Groups/acbf3ae7-8463-4692-b4fd-9b4da3f908ce
   Host: example.com
   Accept: application/json
   Authorization: Bearer h480djs93hd8
   ETag: W/"a330bc54f0671c9"

   {
     "schemas": ["urn:scim:schemas:core:1.0"],
     "meta": {
       "attributes": [
         "members"
       ]
     }
   }

For two functions that do very similar things, the syntax is wildly different. It's hardly what one would call simple. But these represent the easy way out from an implementation perspective, and so the SCIM Working Group is extremely reluctant to tamper with this implementation.

With my suggestion (based on "best practice" around the use of PATCH), here's how to delete a single member from a group:

   PATCH /Groups/acbf3ae7-8463-4692-b4fd-9b4da3f908ce
   Host: example.com
   Accept: application/json
   Authorization: Bearer h480djs93hd8
   ETag: W/"a330bc54f0671c9"

   {
     "operations" : [
       {
         "RETIRE" : {
           "key" : "members.2819c223-7f76-453a-919d-413861904646"
         }
       }
     ]
   }

Here's how I suggest deleting ALL members from a group:

   PATCH /Groups/acbf3ae7-8463-4692-b4fd-9b4da3f908ce
   Host: example.com
   Accept: application/json
   Authorization: Bearer h480djs93hd8
   ETag: W/"a330bc54f0671c9"

   {
     "operations" : [
       {
         "RETIRE" : {
           "key" : "members"
         }
       }
     ]
   }

That's a darn sight more elegant, if I may say so myself. In both cases, a reader can tell exactly what is being attempted. What's more, the syntax for both "delete" functions is identical.

This is arguably simple as an API. But I'm told it cannot be implemented, because it's not simple easy. I'm told that cloud service providers will not be willing to make the changes required to make this work, and this will hinder adoption of the spec. And what do incumbent cloud providers use to store identity information? Why, LDAP of course!

That's why I'm coming around to the view that no incremental change is possible. Human society progresses in its views not because people gradually change their minds, but because generations die, and new generations with different ideas take their place. Ideas only die when people die. People never change their minds. It's the people who have to be replaced. A cynical observation, but probably true. The Augean stables can only be cleaned with a flood. 

So we need a new spec, a new set of cloud service providers and a new type of directory, if we are to simplify cross-domain identity management.

It's the last of these that I want to talk about here.

I want a directory that has the advantage of LDAP (fast reads) without the disadvantages (a rigid tree structure and awful treatment of multi-valued attributes). I think one of the NoSQL document databases that can hold JSON documents may fit the bill, -- with one important constraint. JSON supports two types of data structures, the dictionary and the array. The dictionary forces every value to have a unique key. That's goodness. The array allows multiple values per key. As we now know, that's the root of all evil. Therefore, our document database must only allow dictionaries and not arrays. Clients are still free to upload data to the directory in array form, but the directory will only store these arrays after converting them into dictionaries. It will generate its own random keys for them. (If the order of elements is to be preserved, the generated keys can be in sequence, with sufficient gaps between them to permit insertions of other values later.)

Every element of such a directory can be addressed in a fully-qualified way through "dot notation". Take this example of part of a Telecom company's customer database. The logical customer record shown has two addresses, and different telecom "carriage" services are available at the two addresses. The first address has carriage services "cable" and "ADSL", while the second has "ADSL2+" and "Wi-fi". As we can see, that's two nested arrays. The outer array holds addresses, and within each address, there's an inner array holding available services.

{
  ...
  addresses: [
    {
      "type" : "home",
      "street_number" : "35",
      "street_name" : "High Road",
      ...
      "country" : "Australia",
      "available_services" : ["cable", "ADSL"]
    },
    {
      "type" : "office",
      "street_number" : "213",
      "street_name" : "Main Street",
      ...
      "country" : "Australia",
      "available_services: ["ADSL2+", "Wi-fi"]
    }
  ]
}

Let's say we need to update the customer record, because the first address now has "Wi-fi" too, and it no longer has "cable". How do we do this?

We want to delete
"customerX.addresses[0].available_services[0]"

and insert "Wi-fi" into the array
"customerX.addresses[0].available_services".

However, we can't reliably use positional indexes because these can change with every operation. We need stable identifiers. (I will not even attempt to formulate the SCIM syntax required for these operations!)

Here's how I suggest it should be done:

PATCH /Users/2819c223-7f76-453a-919d-413861904646

{
  "operations" : [
    {
      "INCLUDE" : {
        "key" : "addresses.d6ea365462f5.available_services",
        "value" : "Wi-fi"
      },
      "RETIRE" : {
        "key" : "addresses.d6ea365462f5.available_services.9be6378dc303"
      }
    }
  ]
}

Again, if may say so myself, this is elegance. And that's only possible because my directory has converted these two arrays into dictionaries, like this:

{
  ...
  addresses: {
    "d6ea365462f5" :
    {
      "type" : "home",
      "street-number" : "35",
      "street-name" : "High Road",
      ...
      "country" : "Australia",
      "available_services" : {
        "9be6378dc303" : "cable", 
        "6aa1429eba34" : "ADSL"
      }
    },
    "3cbaaff8e84e" :
    {
      "type" : "office",
      "street-number" : "213",
      "street-name" : "Main Street",
      ...
      "country" : "Australia",
      "available_services: {
        "2beca1fdf3e5" : "ADSL2+", 
        "8c3dcc204a33" : "Wi-fi"
      }
    }
  }
}

(But how does the client know these generated keys? They're returned as part of the record creation response, and also provided as part of the resource representation returned with every GET request.)

This model is easy to support if a service provider implements its identity store as a database of JSON documents rather than in LDAP. One can have both "simple" and "easy", without compromises. But for that, LDAP has to go. "NoLDAP" is what we need in its place.

My definition of a "NoLDAP Directory" is simply this:
A document database that holds dictionary-only JSON documents.

I think the next generation of cloud service providers will emerge based on this architecture, offering a simple API that is also easy for them to implement.

As for LDAP and SCIM, I guess the best TLA is RIP.

Don't SCIM Over Your Data Model

My article critiquing the SCIM (System for Cross-Domain Identity Management, formerly Simple Cloud Identity Management) is now published on InfoQ.

I had sent the suggestions to the SCIM mailing list a week earlier, but the discussion there only started after the InfoQ article came out...

Thursday, August 02, 2012

Best Practice For The Use of PATCH in RESTful API Design


This topic deserves standalone treatment. I wrote before in the context of SCIM that PATCH is a relatively recent HTTP verb that is being recommended for use in situations where a resource is to be partially modified. In comparison, PUT is a bit of a sledgehammer, because it requires the entire resource to be replaced in toto using a fresh representation.

So the advent of PATCH is a welcome development no doubt, but one immediate problem is posed by current web infrastructure. Not all infrastructure components understand PATCH. Firewalls are suspicious, proxies could mangle or drop messages containing the unfamiliar verb, not all web servers are geared to handle it, and so on. Heck, even the ultramodern HTML 5 spec has no support for the PUT and DELETE verbs, so asking for PATCH support is a bit ambitious at this point.

However, I'm not too worried about those problems because Time is a great infrastructure deployer. (Besides, there's nothing I can do to help on that front.)

The bigger problem I see is that we as API designers don't really know how to use PATCH. There is no guidance around its use other than to "use it for partial updates". Everyone agrees that we need more fine-grained control over updating resources, but this level of granularity needs detailed specification. We simply don't have that anywhere.

Well, we've got it now, and remember that you read it here first :-).

First off, let's take a JSON model of a resource because it's the most popular and everyone understands it. (Yes, I know, I'm one of the SOFEA authors, but I don't like XML either.)

You should know that the JSON family actually comprises two siblings, one good and one evil. Abel and Cain. Thor and Loki. Edwin Booth and John Wilkes Booth. Take your pick.

I'm going to call them JSON the Argonaut and JSON Voorhees (of Friday the Thirteenth notoriety).

JSON the Argonaut is the good sibling. He buys a ticket for every member of his family when he goes to see a show.

JSON Voorhees is the bad one. He buys a single ticket for himself, and gets all his kids to slip under the turnstile.

And you wonder why it's so hard to get good seats at the show.

You have no idea what I'm talking about, do you?

Check out the JSON website:

JSON is built on two structures:
  • A collection of name/value pairs. In various languages, this is realized as an object, record, struct, dictionary, hash table, keyed list, or associative array.
  • An ordered list of values. In most languages, this is realized as an array, vector, list, or sequence.

See the connection? The first structure describes JSON the Argonaut, who ensures that every member of his family has a ticket (a label or key). The second structure describes JSON Voorhees, who gets away with a single ticket (a label or key) for his entire family. The first thing we need to do therefore, before we even start looking at PATCH, is to fix JSON Voorhees. By which I mean, get him to buy tickets for all his kids.

This is what JSON Voorhees's family looks like when he slips them past with a single ticket:

This is what we want his family to look like when he buys all the tickets he needs to:


You see? One label per value.

In other words, when working with JSON objects, convert all arrays to dictionaries.

[If the sequence of items in the array is important and you don't want to lose that when turning it into a dictionary, generate keys that are in sequence, only taking care to see that there are enough "gaps" between keys so that new items can be inserted between them later, if required. Something like a B-Tree algorithm will be useful, I think.]

When we POST a resource containing arrays to a server, the server should convert them into dictionaries and return the new representation of the resource to us. All the generated keys should be in the new representation. And this is Goodness with a capital G, because now, all of a sudden, PATCH has a much easier job to do.

[Why can't we just use positional indexes, e.g., email-addrs[i]? Think about what will happen when one client does a GET and decides it needs to delete email-addrs[1]. In the meantime, another client deletes email-addrs[1], resulting in email-addrs[2] becoming the new email-addrs[1]. Then the first client will end up deleting the wrong attribute. Yes, you can check the Etags and the if-not-modified headers before an update to stop this from happening, but you will then end up with a large number of failed updates under high concurrency, which can be avoided with unique and stable identifiers.]

Now PATCH has a unique handle on every attribute value within a resource, no matter how complex or how deeply nested it is. Every value has a unique key that can be expressed as

first.second.third.fourth.fifth

if it's (say) five levels down from the top level resource URI.

Now we can use the same REST concepts that we had before PATCH, to operate on each of these. The coarse-grained verbs used to operate on resources can now be used to operate on parts of a resource as well.

POST to add a new attribute to a collection
PUT to replace the value of an attribute
DELETE to make an attribute inaccessible (and not necessarily delete it physically, of course)

In place of a URI, we specify the key of the attribute within the resource, using the dot-separated notation we just showed.

There's just one small detail. Actually two.

1. PATCH is turning out to be an operation container rather than an operation in itself. This means we're going to have to nest other verbs within it to operate on different parts of a resource. There's nothing to stop us from bundling operations to add, modify and delete various parts of a resource whose top-level URI the PATCH request targets. In fact, that's probably the kind of elegance we're after. But then we wouldn't want any confusion between these nested operations and the coarse-grained HTTP verbs used to operate on resources, so we should perhaps look for equivalent verbs to POST, PUT and DELETE to use inside of PATCH.

2. When we think about it, the semantics of the HTTP PUT verb are a bit unclear (at least to me). Do we intend to replace a resource that is already there, or do we intend to create a new resource with a URI of our own choosing (as opposed to a server-decided URI)? And what constitutes an error in either case (because they're the exact opposite conditions)? We probably need to split PUT into its subtypes to reflect these separate "create" and "update" semantics, and for good measure define a third subtype to cover the "create-or-update" case, which is also very likely to be required. While we're at it, we may want to narrow the scope of POST to only mean "add to a collection", because POST as it's used today is a bit of a catch-all command in REST when none of the others quite applies.

So with these two drivers in mind, let's look at what new verbs we could use as nested operations within a PATCH request.
  1. INCLUDE (equivalent to POST): Add the given attribute value to a collection and return the unique key generated for it.
  2. PLACE (equivalent to one form of PUT): Add the given attribute key-value pair at the location implied by the key. (If there’s already an attribute with this key, return an error status.)
  3. REPLACE (equivalent to another form of PUT): Replace the current value of the given key with this new value. (If there’s no such key, return an error status.)
  4. FORCE (equivalent to a third form of PUT): This means PLACE or REPLACE. (At the end of this operation, we want the specified key to refer to the given value whether the key already existed or not.)
  5. RETIRE (equivalent to DELETE): Delete, deactivate or otherwise render inaccessible the attribute with the given key.
  6. AMEND (equivalent to PATCH): (This verb is just listed for completeness. We probably don’t need a nested PATCH since PATCH cascades to every level of the tree.)
And here's a picture that illustrates far more effectively than a thousand words how PATCH will then work. Click to see the enlarged version. (There's a minor syntax error in the PATCH command. Each element in the "operations" array needs to be surrounded with curly braces.)


The final piece of the puzzle is the PATCH response.

If PATCH is to be used as an operation container with multiple nested operations, then the most appropriate status code is the WebDAV-defined "207 Multi-Status". Each nested operation must have its own status code, because some may succeed while others fail. Even with successful operations, there is a difference between "200 OK" and "201 Created", because with "201 Created", we expect to find the server-generated key accompanying the response.

Here's what the response to the above PATCH command could look like.


(Like with the PATCH request, there's a minor syntax error in the PATCH response. Each element in the "results" array needs to be surrounded with curly braces.)

To sum up,

  1. Ensure that when resources are created, all their array-type elements are replaced by dictionaries. Every value should be independently addressable using its own unique key.
  2. Use one of 5 different operations (INCLUDE, PLACE, REPLACE, FORCE and RETIRE) within PATCH to refer to various keys and specify new values. There is no possible confusion between the scope of these verbs and those of the HTTP verbs POST, PUT and DELETE, and their meanings are also unambiguous.
  3. Use the "207 Multi-Status" code in the response to the PATCH itself, and nest the status codes for each individual operation inside the response.
And that, in a nutshell, is what I hope will be considered Best Practice around the use of PATCH!