Normal
0
false
false
false
EN-US
X-NONE
X-NONE
Almost two decades ago, I was a member of a database
development team that introduced adaptive locking. Locking, the most popular concurrency control
technique in database systems, is pessimistic. Locking ensures that two or more conflicting operations on the same data
item don’t “trample” on each other’s toes, resulting in data corruption. In a
nutshell, here’s the issue we were trying to address. In everyday life, traffic lights serve the
same purpose. They ensure that traffic
flows smoothly and when everyone follows the rules, there are no accidents at
intersections.
As I mentioned earlier, the problem with typical locking
protocols is that they are pessimistic. Regardless of whether there is another conflicting operation in the
system or not, you have to hold a lock! Acquiring and releasing locks can be quite expensive, depending on how
many objects the transaction touches. Every transaction has to pay this penalty. To use the earlier traffic light analogy, if
you have ever waited at a red light in the middle of nowhere with no one on the
road, wondering why you need to wait when there’s clearly no danger of a
collision, you know what I mean.
The adaptive locking scheme that we invented was able to
minimize the number of locks that a transaction held, by detecting whether there were one or more transactions
that needed conflicting eyou could get by without holding any lock at all. In many “well-behaved” workloads, there are few
conflicts, so this optimization is a huge win. If, on the other hand, there are many concurrent, conflicting requests,
the algorithm gracefully degrades to the “normal” behavior with minimal cost.
We were able to reduce the number of lock requests per TPC-B
transaction from 178 requests down to 2! Wow! This is a dramatic improvement in concurrency as well as transaction
latency.
The lesson from this exercise was that if you can identify
the common scenario and optimize for that case so that only the uncommon
scenarios are more expensive, you can make dramatic improvements in performance
without sacrificing correctness.
So how does this relate to the architecture and design of
some of the modern NoSQL systems? NoSQL
systems can be broadly classified as master-slave sharded, or peer-to-peer
sharded systems. NoSQL systems with a
peer-to-peer architecture have an interesting way of handling changes. Whenever an item is changed, the client (or
an intermediary) propagates the changes synchronously or asynchronously to
multiple copies (for availability) of the data. Since the change can be propagated asynchronously, during some interval
in time, it will be the case that some copies have received the update, and
others haven’t.
What happens if someone tries to read the item during this
interval? The client in a peer-to-peer system will fetch the same item from
multiple copies and compare them to each other. If they’re all the same, then every copy that was queried has the same
(and up-to-date) value of the data item, so all’s good. If not, then the system provides a mechanism to
reconcile the discrepancy and to update stale copies.
So what’s the problem with this? There are two major issues:
First, IT’S HORRIBLY
PESSIMISTIC because, in the common case, it is unlikely that the same data item
will be updated and read from different locations at around the same time! For every read operation, you have to read
from multiple copies. That’s a pretty
expensive, especially if the data are stored in multiple geographically
separate locations and network latencies are high.
Second, if the copies are not all the same, the application
has to reconcile the differences and propagate the correct value to the
out-dated copies. This means that the application program has to handle
discrepancies in the different versions of the data item and resolve the issue
(which can further add to cost and operation latency).
Resolving discrepancies is only one part of the problem.
What if the same data item was updated independently on two different nodes
(copies)? In that case, due to the
asynchronous nature of change propagation, you might land up with different
versions of the data item in different copies. In this case, the application program also has to resolve conflicts and
then propagate the correct value to the copies that are out-dated or have
incorrect versions. This can get really
complicated. My hunch is that there are many
peer-to-peer-based applications that don’t handle this correctly, and worse,
don’t even know it. Imagine have 100s of
millions of records in your database – how can you tell whether a particular
data item is incorrect or out of date? And what price are you willing to pay
for ensuring that the data can be trusted? Multiple network messages per read
request? Discrepancy and conflict
resolution logic in the application, and potentially, additional messages? All this overhead, when all you were trying
to do was to read a data item.
Wouldn’t it be simpler to avoid this problem in the first
place? Master-slave architectures like
the Oracle NoSQL Database handles this very elegantly. A change to a data item is always sent to the
master copy. Consequently, the master
copy always has the most current and authoritative version of the data
item. The master is also responsible for
propagating the change to the other copies (for availability and read
scalability). Client drivers are aware
of master copies and replicas, and client drivers are also aware of the
“currency” of a replica. In other
words, each NoSQL Database client knows
how stale a replica is.
This vastly simplifies the job of the application
developer. If the application needs the
most current version of the data item, the client driver will automatically
route the request to the master copy. If
the application is willing to tolerate some staleness of data (e.g. a version that is no more than 1 second out
of date), the client can easily determine which replica (or set of replicas)
can satisfy the request, and route the request to the most efficient copy. This results in a dramatic simplification in
application logic and also minimizes network requests (the driver will only
send the request to exactl the right replica, not many).
So, back to my original point. A well designed and well architected system
minimizes or eliminates unnecessary overhead and avoids pessimistic algorithms
wherever possible in order to deliver a highly efficient and high performance
system. If you’ve every programmed an Oracle
NoSQL Database application, you’ll know the difference!
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:"";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin-top:0in;
mso-para-margin-right:0in;
mso-para-margin-bottom:10.0pt;
mso-para-margin-left:0in;
line-height:115%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:"Times New Roman";
mso-fareast-theme-font:minor-fareast;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;}
