God's in his heaven.
All's right with the world.

0%

IMPLEMENTING YOUR OWN TRANSACTIONS WITH MVCC（转载）

发表于 分类于

This article is part of a series. You do not have to read them in order but I will be referring to topics and explanations in previous articles:

  1. Implementing Your Own Transactions With MVCC
  2. SQL Transaction Isolation Levels Explained
  3. Implementing Repeatable Read and Serializable Transaction Isolation

MVCC (MultiVersion Concurrency Control) is a simple and effective way to implement transactional isolation with any application managing a group of things. We usually think of these things as database records by they could be anything really.

MVCC is one of the most widely implemented concurrency control algorithms because reads do not block other reads and writes do not block other reads or writes. This means that we can safely and concurrently have lots of clients reading and writing simultaneously without blocking each other. With some notable specific cases that I will explain later.

What is Isolation?

Isolation (the I from ACID) makes sure that when a client begins a transaction that the data it sees will always be the same. Event if other clients are modifying the data.

If another client (or clients);

  • Add a record: It will not be visible to you.
  • Delete a record: It will remain visible to you.
  • Modify a record: You will forever see the version before it was changed.

However, inside your transaction those three things do to take affect. So if you add a record then it will be visible to you.

Often overlooked, transactions applied to the correct applications can;

  • Alleviate blocking if you previously relied on simply locking the whole database until your modifications where finished.
  • Prevent read issues from arising if your application is affected by reading the same data twice and getting two different answers unexpectedly.
  • Provide durability. At any time you can throw away the changes if you change your mind without explicitly undoing all the changes yourself.

Terminology

A record is a single entity. This would be best explained as a database record. It could also be a file, a JSON object, anything that encapsulates something. Most importantly here is that a record cannot be simultaneously modified by two separate clients. If you have a complex data structure you will want to make sure what you define as a record does not encapsulate too much.

A collection is the set of records. This would be like a table in a database. The important thing here is that a transaction is not isolated to a single collection as long as each of the records share the same transaction IDs.

A transaction ID (also called an XID) is the unique number for the transaction. All records that have been modified under the same transaction can be saved or rolled back as one atomic operation, which is ultimately what we want.

Transaction IDs

There are three categories of transaction ID numbering systems we can use;

  1. An incrementing number. Before a transaction starts (before any changes occur is important, even if there are no changes). This is the transaction ID for all the record changes. It doesn’t matter if the changes are saved or thrown away the same transaction ID can never be used again so it must be atomic. Also important is the value must be kept when the script/server restarts to prevent transaction IDs from being reused.
  2. A timestamp. We do not need to maintain an atomic counter. This has the added benefit of allowing us to restore the collections to some point in time. There is one caveat; if the timestamp does not have a high enough resolution (lets say your using whole seconds) transactions that start very close to each other would potentially share the same transaction ID and horrible things will happen…
  3. Custom transaction ID implementations. Special cases where you are working with distributed databases or have other requirements that are not satisfied by the two types above. This may include UUID based algorithms and may not even be strictly a number.

Items 2 and 3 each deserve their own blog post so we won’t walk about it here. Just the mechanism of the most simple implementation of using an incrementing counter.

It’s Time to Dive In

I’m going to provide the code examples in Python. The full example program is available in this gist. But I will explain each piece below.

In a nutshell what we need is the next transaction ID and an array (or set) of the transactions currently active to produce new transactions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
next_xid = 1
active_xids = set()
records = []

def new_transaction():
    global next_xid
    next_xid += 1
    active_xids.add(next_xid)
    return Transaction(next_xid)

class Transaction:
    def __init__(self, xid):
        self.xid = xid
        self.rollback_actions = []

In your application you may decide that clients (if you have any) can control when transactions are opened or closed. It doesn’t affect how the transactions work and they are independent of this.

Next we need to add two discreet pieces of information attached to each record. Called the created XID and expired XID. It’s best to store these directly with the record itself. However, that is not always possible so you can maintain them somewhere external as long as you are the only one modifying the data to maintain consistency.

Row Visibility and Locking

Ultimately this is what MVCC comes down to: The visibility of a row depending on who is looking at it. Ever row has to be tested if it is visible to the client looking at it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#class Transaction:
    def record_is_visible(self, record):
        # The record was created in active transaction that is not our
        # own.
        if record['created_xid'] in active_xids and \
            record['created_xid'] != self.xid:
            return False

        # The record is expired or and no transaction holds it that is
        # our own.
        if record['expired_xid'] != 0 and \
            (record['expired_xid'] not in active_xids or \
            record['expired_xid'] == self.xid):
            return False

        return True

(xnerv: created_id is the transaction ID which created this row. expired_id is the transaction ID which deleted this row.)

Furthermore, we discussed before that simultaneous transactions cannot make a modification to the same record. If this happens there are two ways to handle this:

  1. Abort (rollback) the transaction that tried to make the most recent changes and propagate the error back to the original client.
  2. Wait (block) the second transaction until that record becomes available. This has some special challenges with performance and potential reread errors.

The safest and easiest one is the first choice - so that’s what we’re going to use in this tutorial. When we do need to modify a record we need to check if it is locked by another transaction with this:

1
2
3
4
5
#class Transaction:
    def row_is_locked(self, record):
        return record['expired_xid'] != 0 and \
            record['expired_xid'] in active_xids

Adding a Record

This is an easy one. We set the created_xid to the current transaction ID and expired_xid to 0 :

1
2
3
4
5
6
7
#class Transaction:
    def add_record(self, record):
        record['created_xid'] = self.xid
        record['expired_xid'] = 0
        self.rollback_actions.append(["delete", len(records)])
        records.append(record)

The rollback_actions will be explained later.

Deleting a Record

There are two possibilities:

  1. The expired_xid is 0 meaning the record has never been deleted by anyone. So by setting expired_xid to the current transaction ID we are marking it as deleted.
  2. The expired_xid it not 0 and expired_xid is an active transaction. The record has been deleted by another active transaction and so we cannot touch it.

The third scenario where expired_xid is not an active transaction is not possible due to the normal visibility constraints.

1
2
3
4
5
6
7
8
9
10
#class Transaction:
    def delete_record(self, id):
        for i, record in enumerate(records):
            if self.record_is_visible(record) and record['id'] == id:
                if self.row_is_locked(record):
                    raise Error("Row locked by another transaction.")
                else:
                    record['expired_xid'] = self.xid
                    self.rollback_actions.append(["add", i])

The rollback_actions will be explained later.

Updating a Record

Updating is a combination of deleting the old one and adding a new one. This allows the existing record to still be viewed by other transactions. If the delete_record fails then the exception raised would cause the subsequent add_record not to happen which is what we want.

(xnerv: Absolutely this implementation is different from popular DBMS like MySQL.)

1
2
3
4
5
#class Transaction:
    def update_record(self, id, name):
        self.delete_record(id)
        self.add_record({"id": id, "name": name})

Committing Changes

Once all the modifications have been made we need to commit all the changes so that future clients can see these new changes. Very easy, we simply remove our transaction ID from the active list of transactions:

1
2
3
4
#class Transaction:
    def commit(self):
        active_xids.discard(self.xid)

Rollback Changes

Rolling back can be done several ways, one way is to replay the changes in reverse:

1
2
3
4
5
6
7
8
9
10
#class Transaction:
    def rollback(self):
        for action in reversed(self.rollback_actions):
            if action[0] == 'add':
                records[action[1]]['expired_xid'] = 0
            elif action[0] == 'delete':
                records[action[1]]['expired_xid'] = self.xid

        active_xids.discard(self.xid)

Note: This is fine for an environment where the server can guarantee that the all rollback actions will be replayed and that when the server is shut down forcefully that all the active transactions will have rollback() invoked on them.

If you want higher durability that can recover from a server randomly crashing you will need to keep the transaction ID stored somewhere atomically and have extra code on the server start up that checks to see if it was shutdown safely, and manually repairs the records if need be. I will not go into this as this article is already long enough, but it may be explained in a future article.

Vacuuming or Reclaiming Space

You have probably noticed with this algorithm is that it does not ever actually delete data, only mark it as deleted. This makes it fantastic for keeping lots of records on disk by only appending to the file for modifications.

Overtime you will likely want to gain back all that dead space. If it’s in a memory database you could simply iterate through the records and permanently delete the records that are now fully dead.

If your using a medium like the disk this isn’t so easy. If your application isn’t too complicated you may be able to rewrite all of the non-dead rows out to a new file and switch it underneath your server. There are tons of solutions for this that aren’t specific to how MVCC works so I’ll leave that up to you.

In any case we need to be sensitive to row visibility here as well. Records that have an expired_xid that is not 0 and it does not appear in the active transactions are fully dead rows.

本文地址：http://xnerv.wang/implementing-your-own-transactions-with-mvcc/
转载自：IMPLEMENTING YOUR OWN TRANSACTIONS WITH MVCC