Cloud computing systems today, whether open-source or used inside companies, are built using a common set of core techniques, algorithms, and design philosophies – all centered around distributed systems. Learn about such fundamental distributed computing "concepts" for cloud computing. Some of these concepts include: clouds, MapReduce, key-value/NoSQL stores, classical distributed algorithms, widely-used distributed algorithms, scalability, trending areas, and much, much more! Know how these systems work from the inside out. Get your hands dirty using these concepts with provided homework exercises. In the programming assignments, implement some of these concepts in template code (programs) provided in the C++ programming language. Prior experience with C++ is required. The course also features interviews with leading researchers and managers, from both industry and academia. This course builds on the material covered in the Cloud Computing Concepts, Part 1 course.
1.5. Optimistic Concurrency Control
Loading...
来自 University of Illinois at Urbana-Champaign 的课程
Cloud Computing Concepts: Part 2
168 个评分
从本节课中
Week 2: Concurrency and Replication Control
Lesson 1: Transactions are an important component of many cloud systems today. This module presents building blocks to ensure transactions work as intended, from Remote Procedure Calls (RPCs), to serial equivalence for transactions, to optimistic and pessimistic approaches to concurrency control, to deadlock avoidance/prevention. Lesson 2: This module covers how replication – maintaining copies of the same data at different locations – is used to provide many nines of availability in distributed systems, as well as different techniques for replication and for ensuring transactions commit correctly in spite of replication.
与讲师见面
Indranil GuptaProfessor
Department of Computer Science
[MUSIC]
In this lecture, we're going to discuss optimistic concurrency control,
which tries to increase the level of concurrency or
transactions per second compared to pessimistic concurrency control.
And this is important because it improves revenue.
It improves the operations per second and it lowers latency.
And these are important in non-transactions systems.
So systems like Dropbox, Google Apps, Wikipedia,
Key-value Stores yh, Amazon's Dynamo.
All of these even though they don't support transactions necessarily they
prefer optimistic concurrency control approaches, because it reduces latency and
increased concurrency.
Meaning it, it improves operations per second.
Optimistic concurrency control in general is preferable over pessimistic
concurrency control when conflicts are expected to be rare.
But when conflicts do occur, you need to make sure that
they are caught and resolved if necessary.
So the most basic approach to optimistic concurrency control is to just allow
transactions.
Were are going to be discussing the transaction
version of optimistic concurrency control.
You just allow transactions and clients to read and write objects at will.
When the transaction tries to comment, you check for serial equivalence.
If it's violated, then you abort the transaction and
roll back in the updates that it made.
Now an abort by transaction may result in other transactions
that dread dirty data from this transaction also being aborted,
because that data was never ever reflected based on a.
Those were the transactions that read the dirty data by an aborted transaction you
also need to abort.
But those transactions may have written data, which may have been read by other
transactions and those transactions now transitively also need to be aborted.
As a result transaction aborts are a little bit tricky,
because one transaction abort might lead to a series of other
cascading aborts of other transactions as well.
So a second approach that tries to improve on this is known as timestamp ordering.
This is used by several databases.
Each transaction is assigned an id that's called the transaction ID.
The transaction id determines that,
that transaction's position in the serialization order.
So you want to make sure that you have a serial equivalents order that obeys
a transaction id ordering.
When a transaction t is used in operation,
you need to make sure that two conditions are true.
T's write to an object O is allowed, only if transactions that
have previously read or written that object O had lower id's than T.
Okay? That's the first
condition that needs to be satisfied.
Second condition is that if T is trying to read an object O,
that is allowed only if O was last written by a transaction with a lower id than T.
Okay. So, if these two conditions are,
are satisfied, then you can ensure that the transactions, even though they
interweave their operations follow the serialization order and then the resulting
is serially equal aligned and the ordering is the serialization order.
Typically, timestamp ordering is implemented by maintaining read and
write time stamps for the object.
And whenever any of these two rules is violated for a transactions operation,
then that transaction is aborted.
So this works with serial equivalence, but still you're resulting,
you're still causing transactions to abort over here.
Right?
You don't have cascading aborts anymore here necessarily because the transaction
only aborts and that's it.
Or at least the trans the cascading aborts are minimized over here,
because the transaction can still abort and
other transactions can can be customized abort because of it.
But the, the aborts are minimized compared to the previous approach that
we discussed in the previous slide.
But essentially, what I'm saying here is that you still have abort and
you might want to do better than this.
So third approach is known as multi-version concurrency control.
This is used in several systems, including some key-value store systems like the.
Here, for each object you maintain a per transaction version of the object.
Right.
And so each transaction maintains its own tentative version of that object.
You also have a committed version, which is meeting on the server side,
on the database side.
Each tentative version has a timestamp of its own and
the committed version also has a timestamp.
Some variance some systems implement both read and
write timestamp for the tentative version.
Whether a transaction wants to do a read or a write,
you need to find the correct tentative version to read or write from.
And this correctness which is the correct version to choose from is based on
the transaction id, so you want to make sure
that you read only from transactions that were immediately previous writers.
And so you choose your point in the transaction in, among the versions
of that object and you choose the right version to read and write from.
Okay.
So this is only the sort of high level overview of multi-version
concurrency control.
We are not discussing its all its gory details over here.
Now eventual consistency that we have seen in key-value stores
is in fact a form of optimistic concurrency control.
Cassandra key value store we have seen, in DynamoDB key-value store and
also in the VF key-value store.
But these systems are, not transaction systems.
So the optimistic approach looks different.
In fact, it looks slightly simpler in some ways.
So, in Cassandra and DynamoDB,
there's only one version of each data item, each key-value pair.
That's what we would call an object.
And you have a last-write-wins or last-writer-wins policy, which is LWW.
Essentially, the timestamp, typically based on physical time is used to
determine whether to overwrite the older value.
If the new write's timestamp is higher, then the current object's timestamp,
you overwrite.
Otherwise, you do nothing and you ignore the that write.
So ensures eventual consistency, which means that eventually you end write stop
all, all the replicas will reflect the same value,
which is the latest timestamp write.
But you could have situations where a slightly older write with a fresher time
stamp, because of unsynchronized clocks in a disable system.
A slightly older write with a fresher timestamp might in fact win and so
the last-writer-wins really is based on the notion as physical time and
some notion of time synchronization across clients.
A different approach used in the Riak key-value store uses vector clocks.
And you should be familiar with vector clocks, because you've studied
them in the first half of the course when we discussed lampo time stamps and
then vector clocks.
This notion implements causal ordering and these vector clocks are used
to detect whether a new write is strictly newer than the current value.
If the vector clock value is strictly greater than.
Or if it's not compatible,
then the new write might conflict with the old existing value.
If there's a conflict, then you create a sibling value.
Meaning you, you maintain for that key two values.
Saying that these are two possible values for this key.
These are sibling values.
These are results, these need to be resolved at some point of time,
they could be resolved by the user.
You could bubble them up to the client or the user, which then picks one value and
then does it right using that value and overwrites the existing values
with a newer time stamp or it could result automatically by the application.
So in any case, these are not resolved by the react system itself.
They are pushed out to the client either by the user or by the application itself.
The Riak uses vector clocks and the vector clocks might get very large,
because the number of entries in the vector clock is
potentially the same as the number of clients.
And to do prevent a vector clock from getting too many entries,
you you use sideways pruning, you typically prune the number of entries,
the maximum number of entries that can be there in the vector clock.
Also vector clocks might get very old,
some entries might have very old items vector clock values in them.
And so to prevent that from happening, you prune out
you remove entries that have very old time stamps in them.
So to wrap up our discussion of concurrency control we first discuss RPCs
and RMIs, remote procedure calls and remote method invocations,
which are important building blocks in understanding what transactions are.
Transactions are one of the most important concepts in database systems
that have been used for many decades.
For transactions, you need to maintain asset properties and
to maintain asset properties serial equivalence is a very important technique.
And typically, this is detected and enforced by a conflicting operations.
And there is two ways or two approaches in which you can do concurrency control, so
that serial equivalence is still maintained.
The first is pessimistic concurrency control such as locking
which limits concurrency, but is always correct.
Optimistic concurrency control lets transactions to
proceed with their reads and writes under certain conditions.
But checks later on or enforces checks at some point of time so
that the asset properties and serial equivalence are in fact always obeyed.
[MUSIC]
