<commit_before>.. _transaction-protocol:

====================
Transaction Protocol
====================

NOTE: the AtlasDB transaction protocol is inspired by (but different
from) google's percolator transaction protocol. For additional reading
please see
`Percolator <http://research.google.com/pubs/pub36726.html>`__.

AtlasDB is a standard MVCC Snapshot Isolation protocol. Each transaction
has a start timestamp and a commit timestamp. You can view all rows that
have a commit timestamp less than your start timestamp. You will get a
write-write conflict for any cells that you write that were modified and
that committed at a timestamp between your start timestamp and your
commit timestamp.

Write Protocol
--------------

1. We buffer writes in memory until commit time. At commit time we grab
   row locks for all the rows we are about to write (this is to detect
   write/write conflicts). We also grab the start timestamp row lock for
   the Transaction table.

2. Now that we have our locks we check for write/write conflicts. If any
   cell has been modified by a transaction that committed after our
   startTS then we have a write conflict.

3. Write the data to the KV store with TS = startTs.

4. Now we get a fresh commit timestamp.

5. Then (this is important) we make sure our locks are still valid. If
   our locks expire after this point that is ok, but they have to be
   valid now.

6. Then we atomically do a "putUnlessExists" into the transaction table
   with our commit timestamp.

7. Unlock the locks

Read Protocol
-------------

Lets assume we are reading Cell c.

1. Read from the KV store and get the most recent data with TS <
   startTs.
2. Get a read lock on the transaction row for c.startTs (not needed if
   c.startTs is less than immutableTs). This is to wait to make sure
   the transaction that wrote it is done.
3. Read the transaction table for the commitTs.
4. One of two actions:
   
   a. If commitTs doesn't exist, try to roll back this transaction and
   start over. If it is -1 (been rolled back), delete the associated data
   and start over.
   
   b. If c.commitTs greater than your startTs, skip it and move on to the
   next highest TS for the cell.

Immutable Timestamp
-------------------

The point in time right before the oldest currently executing
transaction is referred to as the Immutable timestamp. This is because
nothing before this point in time will change. (All writes are available
to read and are either committed or pending commit.)

Any timestamp before the oldest open transaction's start timestamp may
be called the immutable timestamp, but generally it refers to the most
recent TS for which this is true.

To implement this we grab a new TS (PRE\_START\_TS) and lock that before
we begin our transaction. We have a feature in the lock server to return
the minLockedInVersion. if PRE\_START\_TS is the oldest, then lock
server will return this as the minLockedVersion. The write protocol
ensures that this lock is still held after writes are done to the
underlying store. This is the only part of the lock server that doesn't<commit_msg>Update transaction protocol documentation<commit_after>.. _transaction-protocol:

====================
Transaction Protocol
====================

NOTE: the AtlasDB transaction protocol is inspired by (but different
from) google's percolator transaction protocol. For additional reading
please see
`Percolator <http://research.google.com/pubs/pub36726.html>`__.

AtlasDB is a standard MVCC Snapshot Isolation protocol. Each transaction
has a start timestamp and a commit timestamp. You can view all rows that
have a commit timestamp less than your start timestamp. You will get a
write-write conflict for any cells that you write that were modified and
that committed at a timestamp between your start timestamp and your
commit timestamp.

Write Protocol
--------------

1. Using the transactions start timestamp, complete all reads.  This is necessary to
   determine writes required by the transaction. Buffer writes in memory
   until commit time.

2. At commit time we grab
   row locks for all the rows we are about to write (this is to detect
   write/write conflicts). We also grab the start timestamp row lock for
   the Transaction table.

3. Now that we have our locks we check for write/write conflicts. If any
   cell has been modified by a transaction that committed after our
   startTS then we have a write conflict.

4. Write the data to the KV store with TS = startTs.

5. Now we get a fresh commit timestamp.

6. Then (this is important) we make sure our locks are still valid. If
   our locks expire after this point that is ok, but they have to be
   valid now.

7. Then we atomically do a "putUnlessExists" into the transaction table
   with our commit timestamp.

8. Unlock the locks

Read Protocol
-------------

Lets assume we are reading Cell c.

1. Read from the KV store and get the most recent data with TS <
   startTs.

2. Get a read lock on the transaction row for c.startTs (not needed if
   c.startTs is less than immutableTs). This is to wait to make sure
   the transaction that wrote it is done.

3. Read the transaction table for the commitTs.

4. One of two actions:
   
   a. If commitTs doesn't exist, try to roll back this transaction and
   start over. If it is -1 (been rolled back), delete the associated data
   and start over.
   
   b. If c.commitTs greater than your startTs, skip it and move on to the
   next highest TS for the cell.

Immutable Timestamp
-------------------

The point in time right before the oldest currently executing
transaction is referred to as the Immutable timestamp. This is because
nothing before this point in time will change. (All writes are available
to read and are either committed or pending commit.)

Any timestamp before the oldest open transaction's start timestamp may
be called the immutable timestamp, but generally it refers to the most
recent TS for which this is true.

To implement this we grab a new TS (PRE\_START\_TS) and lock that before
we begin our transaction. We have a feature in the lock server to return
the minLockedInVersion. if PRE\_START\_TS is the oldest, then lock
server will return this as the minLockedVersion. The write protocol
ensures that this lock is still held after writes are done to the
underlying store. This is the only part of the lock server that doesn't
{'fraction_non_alphanumeric': 0.060369096027525805, 'fraction_numerical': 0.0054738817641538946, 'mean_word_length': 3.5290368271954673, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6338878', 'n_tokens_mistral': 1628, 'n_tokens_neox': 1558, 'n_words': 1012}