Re: Newbie question about db normalization theory: redundant keys OK?

On 2007-12-26, David BL wrote:

> But can you provide a realistic example, and offer a "proof" that
> message queues are inadequate?

I've given an example where the transaction both can be bounced by the target system because it violates a local integrity constraint, and also cannot be rolled back because acceptance of the effects of the transaction on the source system carries irreversible external effects. In such a situation you have no alternative but to obtain agreement from the target system *before* you return with success, which implies the use of a distributed agreement protocol. To me that's proof enough.

> When you say "Y is cancelled" do you mean an account on machine Y is
> being closed?

Yes.

> 2. Given that peers only find out asynchronously that the account is
> being closed there will be some period of time for which deposits
> continue to be made into the account. Y must continue pumping messages
> from its peers. [...]

Then the "close account" transaction cannot return with success until you have a guarantee that no message queue in the system contains a deposit message aimed at the account. In order to have that guarantee, you either have to obtain distributed agreement using some explicit commit protocol, or to have an implicit acknowledgement from all of the peers, say by lower bounding the submission time of the transaction they're now processing above the time your deposit message would have arrived. Unfortunately the latter option forces much tighter coupling on the systems than the former, because you have to have communication with all of the peers, not just those which actually participate in a transaction with the account. (Commit protocols communicate the participation information lazily and selectively by contacting peers when the transaction arrives. The second option would seem to dictate eager broadcasting of the information.) You'll also have to deal with distributed clock synchronization, which is a nasty problem in its own right.

> 3. It is assumed that each peer (in a local transaction) eventually
> reads the message that the account is being closed. This stops it from
> performing any further deposits into the account. [...]

If that is the case, then the peers have to remember which accounts on the other machines have been closed. That is, at worst all of them have to maintain state for all of the accounts in the system. That is obviously not a good idea in a distributed system.

> There should be a concept of a claim that is not currently allocated
> to a handler, and the claim is passed around the network until it is
> assigned to a handler. Allocation of a claim to a handler is a local
> decision using a local transaction allowing the legal obligation to be
> enforced.

If you allocate the claim to a handler, it might be that there is a reassignment message in one of the remote queues already destined for that handler. If that second claim then pushes the number of claims for this handler past ten, one of the allocations was an irreversible mistake. Hence, you cannot allocate and/or reallocate a claim before you have a guarantee that this won't happen in the future. You'll again need distributed agreement. Of course you *could* wait until you can be sure that the allocation can no longer bounce, but then you'll again have the issues with clock synchronization, excessive coupling and so on, and in an online system you can't really have guarantees about the future unless you actually quiesce everything but this one transaction. You can't seriously be thinking of anything like that, can you?

> A 100% guarantee of global consistency is provably not possible and
> multiphase commit protocols can get it wrong under certain (perhaps
> unlikely) failure conditions.

Of course. You can't get something for nothing, so you usually have to make some assumptions about how the underlying system behaves. But then, under the usual assumptions like nonpartition of the network etc., you *can* guarantee quite a lot using just 2PC.

> It is far from clear to me that message queues cannot provide similar
> statistical guarantees.

Perhaps, but thus far you haven't been able to show how they would accomplish even the kind of guarantees the usual commit protocols do in my example case, with lower latency, more permissive assumptions about the lower level system, or whathaveyou.

> How many programmers properly understand how 3PC avoids most but not
> all blocking that can occur in 2PC?

Application programmers are not *supposed* to understand that sort of thing. The very reason there is such a thing as a transaction abstraction, with its usual ACID properties, is that you can hide the complex implementation details behind it, and let the presumably more knowledgeable database implementers take care of them, once and for all.

> The recovery mechanisms for these protocols are horribly complicated.

Well, just considering cascading aborts, message queues can behave terribly badly in that sense as well.

> There are a number of papers about the impossibility of properly
> defining global properties of a distributed system.

Yes, but that sort of trouble can be cut through by making assumptions. At least in that case you can get conditional certainty, and solid grounds for probabilistic reasoning based on those conditions.

> Paradoxically, the asynchronous approach is so much more efficient it
> will reach quiescence far more quickly than any 2PC approach could
> hope for.

I don't think quiescence is the aim in an online environment. And as I said, when you can do with less, you should have the option; there is nothing wrong with your approach where it *does* apply. It's just that it's not general enough.

>> Even this is not really true: the new state of the queue still needs to
>> be forced into stable storage before the transaction can safely return.
>> Otherwise a crash before the message insertion is made persistent would
>> cause an inconsistency between the states the client and the DBMS see.
>
> No the queue is part of the local DB state. Local transactions ensure
> atomicity across all local DB state irrespective of durability.

Precisely my point. The local transaction needs to cover the durable update of the message queue, so it also needs to force the update into stable storage before it can return. As a matter of fact, it probably shouldn't return before the system is certain that the transfer can no longer bounce from the target system.

> The need to force the log relates to a requirement of durability on
> local messages in a queue that are asynchronously posted to a peer.

But it also relates to durability as the user initiating the transaction sees it. Either your terminal says the transaction was aborted or it says it committed. The client/terminal/user is part of the transaction, and returning with success means the effects must have been made durable. Otherwise the user/client is in an inconsistent state with respect to the rest of the system.

> This provides a lot of freedom for forcing the log much less often
> than the ingestion rate.

Sure. But that precise latitude is already exploited widely even in DBMSs that do not utilize message queues. After all, there is a considerable literature on logging policy alone.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2