DDJ: Could you, maybe talk a little bit about this mathematical. . . transaction theory. It seems like transactions are such an implementation plumbing type of work.
JG: There are a couple of ideas. One of them is (the basic theorem for concurrency control) as follows: You want the system to have no concurrency anomalies. You want a system that, if you run the transactions in parallel, nothing bad happens. So, what is the definition of nothing bad happens? It is as though you ran the transactions one at a time. If something happens when you run the transactions in parallel, that is different than if you ran them one at a time, then that's going to be a surprising behavior. That is the first observation. How can you get the affect that the transactions ran one at a time and still run them in parallel? Well, it is not completely obvious, but the answer is the following: If you structure your program, so that before you access any piece of data, you lock it, and you prevent anybody else from changing it. Then, you hold the locks until the end of the transaction. Then, if you do those two things, any execution which obeys the locking protocol will be equivalent to some serial execution.
The actual theorem gets stated if all transactions are well formed, which is to say that all operations are covered by a lock; and, are two phase. This is to say there is a growing phase (where locks are acquired) and there is a shrinking phase where locks are being released. Then, every legal execution is equivalent to a serial execution. That result has been proven many times, stated many different ways. The interesting thing about this is that now, if we have this theorem, we can take a program that you write and we can mechanically go through it and introduce locking at various steps along the way in a completely automatic way. Your program can run in parallel with all the other programs and never see any concurrency anomalies. This theorem gives us a mechanical way to provide both concurrency and safety. That is a mathematical body which is really quite elegant. Then, it has this other dual side of it which is extremely relevant. That is to say you can take it and apply it to build automatic concurrency control. Literally, this meant that programmers never had to learn about locking ever again. That is to say, the locks are inserted for them automatically by the database system. That is the "I" of ACID. To some extent the "A", or atomicity. It is both all or nothing and isolated. The durability we developed largely inspired by the Interlisp work of Warren Teitelman who had kept an undo log for people who were using Interlisp so that as you were programming along, you could say "undo" and it would undo previous statements. To this day, if you use word processors, you see a little "undo" and you have, more or less, unlimited undo backwards. What is going on there is that a journal is being kept of all the changes that you are making. The old values are being preserved. We developed a theory about how transactions could be redone and undone that would allow you to, basically, scroll forward and backwards in time.
DDJ: This works because, ultimately, all these actions, even if they are initiated by several users, do happen sequentially.
JG: It works for a couple of reasons. That is one of the reasons. Another reason is that it requires that actions be reversible. So, if you drill a hole in a piece of metal, it is really hard to undo that. If you fire a missile, it is really hard to undo that. This theory has a notion of real actions which cannot be undone and can only be so called "compensated". If I pull out a dollar bill and hand it to you, you have got it and there is no easy way for me to undo that, except to come back to you and say, "Please give me the dollar bill back." That is really another action. There are certain actions which you can completely mask from the outside world. We call them "real actions" which go off and affect the real world. You have to have compensation actions associated with them. There is a, I think, not so elegant, but very useful, or relevant, mathematical theory that goes around recovery. The whole mechanism of undoing and redoing and a structure which allows you to plug in new resource managers into this world that allow you to have automatic undo and redo.
We then got into the whole world of distributed databases. In the world of distributed databases, life gets quite a bit more complicated because you now find that you need to get multiple databases to all agree yes or no to the commitment of a transaction. It turns out that there is a variety of algorithms for doing this. Again, the progress that we made in this area was first to come up with a mathematical model of what it meant for the nodes of a distributed database to all agree or disagree. Also, a model of how things fail. Then, algorithms, which are tolerant to those kinds of failures. An example -- If you have got two computers and one of the computers fails and the other computer can tell that the first has failed then it is actually pretty easy to do these agreement protocols. If you have a world in which the computers can fail and the communication links can fail, so the network can fail, then you can't distinguish between this computer failed and this phone line to the computer failed. Both computers are still working. Why is that an issue? Well, if they are both still working and the phone line is broken, they both think the other guy is down. They might, then, continue operating and delivering service. They could let their databases diverge. The one guy could say, "Oh, yeah, I can give you $10 because I am in charge, Jim is down." Jim says, "Yeah, I'll give you $10 because Phillip is down. I'm in charge." We developed a mathematical model that showed that you had to have three or more nodes in order to provide a reliable system and, then, algorithms that are independent of the number of nodes that allow you to come to agreement, eventually. Those algorithms are generally called the two faced commit protocol. You will hear about two-phased commit in various discussions in the database world. This was all by way of talking about the theory that went into the transaction mechanism.
DDJ: We talked about distributed databases and distributive transactions. A lot of this work is still in process. This is far away from the early '70s.
JG: People are still coming up with better algorithms and coming to understand the issues with much more sophistication.
DDJ: It seems like the algorithms are there. You can go to a bookstore and get a book on concurrent algorithms this thick. Real world solutions have been slow to appear. Is that a correct perception on my part?
JG: Yeah. The reason that they have been slow to appear is that it is difficult to remember. The bandwidth has been very, very hard to come by until quite recently. The price of T1 lines has been extraordinary. The T1 line is merely 1.5 megabytes a second.
DDJ: Is there a limitation in the algorithms though that they depend on network speed. . .
JG: I don't think so. That is to say people operate with a certain clock, i.e., a second. If it is MTV, I think the attention span is about 3 seconds. They want things to happen right now. If you've got a system in which you've got 56 kilobit bandwidth, which was the norm at the beginning of this decade, then there is really a limit to how much you can do in a second in terms of doing a remote procedure call tour, remote node, getting back a response, or exchange messages a few times. We are on the threshold now. . . In fact, I think all of us are using web browsers all the time (every day) where we are using networks, and network bandwidth in a way that was inconceivable a decade ago. When the technology actually arrives, then the algorithms start getting used. I think, if there had been a way of using much lower bandwidth to achieve these tasks, people would have figured it out 10 years ago. That was the time when it really mattered. Now, the old algorithms (the algorithms of 10 years ago) are perfectly appropriate to the networks of today. There is much less pressure to optimize for bandwidth today. Ten years ago there was a big push to do more efficient protocols. Frankly, nobody found any.
