Ayende @ Rahien

Refunds available at head office

Designing a document database: Authorization

This is actually a topic that I haven’t considered upfront. Now that I do, it looks like it is a bit of a hornet nest.

In order to have authorization we must first support authentication. And that bring a whole bunch of questions on its own. For example, which auth mechanism to support? Windows auth? Custom auth? If we have auth, don’t we need to also support sessions? But sessions are expansive to create, so do we really want that?

For that matter, would we need to support SSL?

I am not sure how to implement this, so for now I am going to assume that magic happened and it got done. Because once we have authorization, the rest is very easy.

By default, we assume that any user can access any document. We also support only two operations: Read & Write.

Therefore, we have two pre-defined attributes on the document, read & write. Those attributes may contain a list of users that may read/write to the document. If either read/write permission is set, then only the authorized users may view it.

The owner of the document (the creator) is the only one allowed to set permissions on a document. Note that write permission implies read permission.

In addition to that, an administrator may not view/write to documents that they do not own, but he is allowed to change the owner of a document to the administrator account, at which point he can change the permissions. Note that there is no facility to assign ownership away from a user, only to take ownership if you are the admin.

There is a somewhat interesting problem here related to views. What sort of permissions should we apply there? What about views which are aggregated over multiple documents with different security requirements? I am not sure how to handle this yet, and I would appreciate any comments you have in the matter.

Designing a document database: Concurrency

In my previous post, I asked about designing a document DB, and brought up the issue of concurrency, along with a set of questions that effect the design of the system:

  • What concurrency alternatives do we choose?

We have several options. Optimistic and pessimistic concurrency are the most obvious ones. Merge concurrency, such as the one implemented by Rhino DHT, is another. Note that we also have to handle the case where we have a conflict as a result of replication.

I think that it would make a lot of sense to support optimistic concurrency only. Pessimistic concurrency is a scalability killer in most system. As for conflicts as a result of concurrency, Couch DB handles this using merge concurrency, which may be a good idea after all. We can probably support both of them pretty easily.

It does cause problems with the API, however. A better approach might be to fail reads of documents with multiple versions, and force the user to resolve them using a different API. I am not sure if this is a good idea or a time bomb. Maybe returning the latest as well as a flag that indicate that there is a conflict? That would allow you to ignore the issue.

  • What about versioning?

In addition to the Document ID, each document will have an associated version. The Document Id is a UUID, which means that it can be generated at the client side. Each document is also versioned by the server accepting it. The version syntax follow the following format: [server guid]/[increasing numeric id]/[time].

That will ensure global uniqueness, as well as giving us all the information that we need for the document version.

Designing a document database: Scale

In my previous post, I asked about designing a document DB, and brought up the issue of scale, along with a set of questions that effect the design of the system:

  • Do we start from the get go as a distributed DB?

Yes and no. I think that we should start from the get go assuming that a database is not alone, but we shouldn’t burden it with the costs that are associated with this. I think that simply building replication should be a pretty good task, which mean that we can push more smarts regarding the distribution into the client library. Simpler server side code usually means goodness, so I think we should go with that.

  • Do we allow relations?
    • Joins?
    • Who resolves them?

Joins are usually not used in a document DB. They are very useful, however. The problem is how do we resolve them, and by whom. This is especially true when we consider that a joined document may reside on a completely different server. I think that I am going to stick closely to the actual convention in other document databases, that is, joins are not supported. There is another idea that I am toying with, the notion of document attributes, which may be used to record this, but that is another aspect all together. See the discussion about attachments for more details.

  • Do we assume data may reside on several nodes?

Yes and no. The database only care about data that is stored locally, while it may reference data on other nodes, we don’t care about that.

  • Do we allow partial updates to a document?

That is a tricky question. The initial answer is yes, I want this feature. The complete answer is that while I want this feature, I am not sure how I can implement this.

Basically, this is desirable since we can use this to reduce the amount of data we send over the network. The problem is that we run into an interesting issue of how to express that partial update. My current thinking is that we can apply a diff to the initial Json version vs. the updated Json version, and send that. That is problematic since there is no standard way of actually diffing Json. We can just throw it into a string and compare that, of course, but that expose us to json format differences that may cause problems.

I think that I am going to put this issue as: postphoned.

Designing a document database: Storage

In a previous post, I asked about designing a document DB, and brought up the issue of storage, along with a set of questions that needs to be handled:

  • How do we physically store things?

There are several options, from building our own persistent format, to using an RDMBS. I think that the most effective option would be to use Esent. It is small, highly efficient, require no installation and very simple to use. It also neatly resolve a lot of the questions that we have to ask in addition to that.

  • How do we do backups?

Esent already has the facilities to do that, so we have very little to worry about it here.

  • How do we handle corrupted state?

See above, Esent is also pretty good in doing auto recovery, which is a nice plus.

  • Where do we store the views?
    • Should we store them in the same file as the actual data? 

I think not, I think that the best alternative is to have a file per view. That should make things such backing up just the DB easier, not to mention that it will reduce contention internally. Esent is built to handle that, but it is better to make it this way than not. All the data (include logs & temp dirs) should reside inside the same directory.

Crash recovery on startup should be enabled. Transactions should probably avoid crossing file boundaries.It is important the the files will include a version table, which will allow to detect invalid versions (caused a whole bunch of problems with RDHT until we fixed it).

  • Are we transactional?

Yes, we are transactional. But only for document writes. We are not transactional for document + views, for example, since view generation is done as a background service.

  • Do we allow multi document operation to be transactional?

Yes, depending on the operation. We allow submittal of several document writes / deletes at the same time, and they would succeed or fail as a single unit. Beyond that, no.

Designing a document database

A while ago I started experimenting with building my own document DB, based on the concepts that Couch DB have. As it turn out, there isn’t really much to it, at a conceptual level. A document DB requires the following features:

  • Store a document
  • Retrieve document by id
  • Add attachment to document
  • Replicate to a backup server
  • Create views on top of documents

The first two requirements are easily handled, and should generally take less than a day to develop. Indeed, after learning about the Esent database, it took me very little time to create this. I should mention that as an interesting limitation to the DB, I made the decision to accept only documents in Json format. That makes some things very simple, specifically views and partial updates.

There are several topics here that are worth discussion, because they represent non trivial issues. I am going to raise them here as questions, and answer them in future posts.

Storage:

  • How do we physically store things?
  • How do we do backups?
  • How do we handle corrupted state?
  • Where do we store the views?
    • Should we store them in the same file as the actual data? 
  • Are we transactional?
  • Do we allow multi document operation to be transactional?

Scale:

  • Do we start from the get go as a distributed DB?
  • Do we allow relations?
    • Joins?
    • Who resolves them?
  • Do we assume data may reside on several nodes?
  • Do we allow partial updates to a document?

Concurrency:

  • What concurrency alternatives do we choose?
  • What about versioning?

Attachments:

  • Do we allow them at all?
  • How are they stored?
    • In the DB?
    • Outside the DB?
  • Are they replicated?
  • Should we even care about them at all? Can we apply SoC and say that this is the task of some other part of the system?

Replication:

  • How often should we replicate?
    • As part of the transaction?
    • Backend process?
    • Every X amount of time?
    • Manual?
  • Should we replicate only the documents?
    • What about attachments?
    • What about the generated view data?
  • Should we replicate to all machines?
    • To specified set of machines for all documents?
    • Should we use some sharding algorithm?

Views:

  • How do we define views?
  • How do we define the conversion process from a document to a view item?
  • Does views have fixed schema?
  • How often do we update views?
  • How do we remove view items from the DB when the origin document has been removed?

There are some very interesting challenges relating to doing the views. Again, I am interested in your opinions about this.

There are several other posts, detailing my current design, which will be posted spaced about a day apart from one another. I’ll post a summary post with all the relevant feedback as well.

Schema-less databases

This post about how Friend Feed is using schema-less storage for most of their work is fascinating. In the ALT.Net Seattle there was a session about that, which generated a lot of interest.

My next post will have more details about the actual implementation details of doing something like that in a manner easily accessible in .Net, but just reading the post is very interesting. Another item that I found that was an interesting read, although it is far harder to read is: http://highscalability.com/how-i-learned-stop-worrying-and-love-using-lot-disk-space-scale

Application structure: Concepts & Features

I spoke about this topic quite a bit in ALT.Net Seattle. This is mostly relating to application architecture and how you structure your application. This is the logical result of applying the Open Closed and Single Responsibility Principles.

Feature may not be as overloaded a term in our industry as a service, but it still important to define exactly what I mean. A feature, in my eyes, is a discrete part of the application that perform some operation. That is pretty vague, I know, but I hope that the examples I am going to go through later would make it clearer. So far, it is pretty much the standard fare, but I have a few rules about a feature, the most important of them is:

A feature creation may not involve any design activity.

That is probably something that would raise a few eyebrows, but the idea is very simple. In any application, we tend to have very small number of concepts, and a far larger number of features, each applying to a concept. All design activity occur at the concept level. As a matter of fact, most of the work is getting the concepts right, after that, it is pretty much  boring, following a very clear checklist about what we should do to get something working.

Let us take NH Prof as a good example. We have very few concepts in the application:

  • Session & statements
  • Stack trace
  • Loaded entities
  • Reports
  • Alerts
  • Filtering

That is it.

As for features? We have several dozens of them. Each alert is a feature, being able to see query duration is a feature, returned row count is a feature, every report is a feature.

Remember that a feature involves no design? In order to facilitate that, we have to create an environment in which building a feature is a very predictable operation. This is done at the concept building phase, where we try to figure out what all the different parts of a feature is, and smooth them out. Building a feature is easy, all the hard work was already done, and now you need to fill in the details.

We can get to this situation by paying attention to friction points, applying the Open Close Principle and utilizing conventions. The end result is a very structured approach to building each feature.

A real world example would be NH Prof’s alerts. Adding a new alert is composed of several stages, the first is, of course, determining what we want to alert on. The second is figuring out how we can actually detect this, and finally actually generating the alert. That is all a bunch of fast talk, so let me drill down even further.

Let us say that we want to give an alert about too many joins. That seems like a good alert, doesn’t it? Let us see, how can we detect this?

Well, simply counting the number of occurrences of the string “join” in the statement would give us good results, so we will go with that. The architecture of NH Prof is set up to make this easy, all we really have to do is add this class:

public class TooManyJoins : AbstractStatementProcessor
{
    private readonly Regex joinFinder = new Regex("join", RegexOptions.Compiled | RegexOptions.IgnoreCase);
 
    public override void BeforeAttachingToSession(SessionInformation sessionInformation, FormattedStatement statement)
    {
    }
 
    public override void AfterAttachingToSession(SessionInformation sessionInformation, FormattedStatement statement, OnNewAction newAction)
    {
        if(joinFinder.Matches(statement.RawSql).Count<7)
            return;
 
        newAction(new ActionInformation
        {
            HelpTopic = "TooManyJoins",
            Severity = Severity.Warning,
            Title = "Too many joins in query"
        });
    }
 
    public override void ProcessTransactionStatement(TransactionMessageBase tx)
    {
    }
}

To be frank, I am not sure that I like this, because we still have two empty methods, and there are other things there that reflect some historic choices that I made, but it works for now, and it is not too painful.

Adding this class means that NH Prof will:

  • Pick it up and instantiate it
  • Invoke it at the appropriate times
  • When an alert is generated, it will show it in the UI

That is almost it. We probably need to add configuration (the configuration object is injected to the base class and is accessible to us, so there is no work there, but we still need to worry about adding this to the configuration UI, and of course we must document the alert.

All in all, there is very little actual thought involved in adding a new feature for NH Prof. That is explicitly and by design. This flows to the UI side as well, since we want to maintain the same level of velocity for backend and frontend changes. Adding something new to the UI is pretty easy, and there is a whole bunch of infrastructure to help you ( I mean, I can do this, so it is very easy).

Now, adding a concept, however, is a much more complex scenario. NH Prof’s filtering story, for example, is a concept that we had to add (you can’t see it yet, but it will be there soon). But the filtering story is built by applying a pipeline to the application model. Adding a new filtering operation is very easy, because all the work was already done.

I put up a non conclusive list of things that I believe are part of this design principle. Those are not hard and fast rules, but they are good guidelines.

  • All design work is done in the concept level.
  • Building a feature doesn’t involve any meaningful design work.
  • Work should be structured on repeated addition of features.
  • A feature is a testing boundary.
  • Adding a feature is easy, fast and painless.
  • A feature is complete, that means UI, documentation, configuration and schema are all part of a feature.
  • Building a feature is a structured operation.
  • Testing a feature is a structured operation.
  • All the work required for a feature should be directly and closely related to that feature.

The funny part about NH Prof that Christopher, Rob and me has reached pretty much the same approach, even while working in graphically disparate manner and without a lot of tight communication between us. Well, it is not really funny, because that is the only way we could actually get things to work. Anything else would be ridiculously complicated and require too much synchronization between us.

There are other things that are related to this, mostly about reducing friction and identifying pain points and removing them. It is something that can be applied in isolation, but it usually preferable to deal with it at both project and architecture level.

Alt.net: Alienation by adoption

Last week I participated in ALT.Net Seattle, which was quite interesting. It used the same open spaces format as most ALT.Net conference, and I can honestly say that it was a good experience to most of the attendees.

It did not, however, had the same style of interaction. One of the things that I really enjoyed in the previous ALT.Net conferences is the level of interaction and participation. In this instance, I think that a majority of the people arrived mostly to soak in the information. That changed the dynamics of the conference, and it was quite visible in all the sessions that I was part of.

Just to be clear, I am not saying that it was bad, or that you must participate, I am pointing out a difference between the current conference and the previous ones.

I think that something like that is inevitable as the community grows, because at this stage in the game we are moving from the early adopters to the pragmatists. The problem is that we are currently in that gap, where the ideas only begin to go through:

image

It is my hope that when we finish cross this chasm, we will be able to return back to the same style of interaction that we have had in the past. The problem is, as I see it, that currently too many of the attendees felt uncomfortable to speak. Once again it was the case of the best conversations happening in the hallways and at dinners, when people could relax.

I think that as we see the people in the wider community gain experience and confidence, we will go back into the same vibrant discussions and learning. In the meanwhile, I intend to do my best to push the community forward toward that time.

It was a good conference, even if the highlight for me was the air hockey table talk.

Closed source?

image

Some interesting observations about my experience in shipping commercial software. It seems like the notion of closed source isn’t really working.

Torkel has developed an application using the NH Prof architecture, peeked via reflector. And no, I don’t really mind.

The part that really blew me away was when I started getting patches for NH Prof. No, they didn’t have the code, but they were able to:

  • Follow a pretty complex internal interaction
  • Isolate the actual part that caused their problem
  • Provide a solution and send it to me

From my part, I was able to just take their solution, apply it and commit, resulting in a build that they could download in a very short time.

So far, it seems to be working.