Re: Concurrency in an RDB

From: NENASHI, Tegiri <tnmail42_at_gmail.com>
Date: Mon, 18 Dec 2006 17:30:40 +0100 (CET)
Message-ID: <Xns989D75458D6BAasdgba@194.177.96.26>

"David" <davidbl_at_iinet.net.au> wrote in
news:1166446464.885673.257380_at_f1g2000cwa.googlegroups.com:

>
> Sampo Syreeni wrote:

>> On 2006-12-17, David wrote:
>>
>> > In OT there is never a need to report failure. Transactions are
>> > guaranteed to succeed! A user makes a local modification on local
>> > state without any risk of a dirty read w.r.t the local database.
>>
>> Yes, but in the general case there is a risk of dirty reads to remote
>> state. It's being hidden under a symmetry assumption, which
>> effectively says that whatever the protocol can produce under such
>> circumstances must be a valid state of the distributed DB, but the
>> restriction is still there. It shows up in that OT isn't generally
>> applicable, and in that (the corrected version of) dOPT annuls some
>> transactions, i.e. reduces to an OCC protocol which can only
>> guarantee durability after it's completed a kind of validation round.

>
> Although OT behaves like the ultimate OCC protocol there is no direct
> concept of dirty reads, validation or conflict resolution. However
> it certainly behaves like that is the case.
>

>> > I agree that with some effort it may be possible to increase
>> > performance. Note that if errors are common then this approach may
>> > not help much.
>>
>> By parallelization, adaptive choice of the coding algorithm you use
>> to trace faulty transactions (i.e. you try independent sets of
>> compatible updates so that the probability of success is
>> approximately 1/2) and temporal interleaving, I think you can get
>> pretty much arbitrary throughput, with latency dominated by batch
>> buildup.

>
> Consider that 50% of the individual transactions break the constraint.
> Then batching won't help. Eg try a batch of size 2. Expectation
> value of number of compiles per batch = 0.25*1 + 0.25*2 + 0.5*3 =
> 2.25, which is actually worse than not batching at all.
>

How it is possible that the expectation is 2.25 ? It is 0.25*1 + 0.25*1 + 0.25*2 = 1 -- one is incorrect two times and two are incorect one time. It is the same like with individual arrival and it is not surprising because the model of probability is the same.

--
Tegi



> 

> Cheers,

> David

> 

>

Received on Mon Dec 18 2006 - 10:30:40 CST