Все о двухфазной блокировке и немного MVCC

В этом блоге я опишу методы контроля параллелизма, реализованные в системах управления базами данных, и различия между ними. Я также расскажу о том, какая техника блокировки используется в  СУБРИД СУБД , о режимах блокировки и их совместимости, и, наконец, о взаимоблокировках и их решении.

обзор

Когда несколько транзакций, которые изменяют данные, выполняются одновременно, необходимо контролировать порядок обработки этих транзакций, чтобы удовлетворить свойству ACID (атомарность, согласованность, целостность, долговечность) базы данных. Выполнение нескольких транзакций одновременно должно приводить к тому же результату, что и выполнение каждой транзакции независимо , иными словами, другая транзакция не должна затрагивать одну транзакцию.

Если для каждой транзакции изменяются разные данные, между транзакциями не возникает помех, поэтому проблем не возникает. Однако, если одни и те же данные одновременно изменяются несколькими транзакциями, порядок обработки каждой транзакции должен контролироваться.

Типы управления параллелизмом

Например, транзакция T1 изменяет запись A от 1 до 2 , а затем изменяет запись B , то транзакция T2 может одновременно изменить запись A , тоже. Давайте предположим, что транзакция T2 изменяет запись A с 2 на 4 , добавляя +2 . Если две транзакции успешно завершены, проблема не возникает. Но важно, чтобы все транзакции можно было откатить. Если транзакция T1 откатывается, значение записи A должно быть возвращено к 1т.е. значение до выполнения транзакции T1 . Это должно удовлетворить свойство ACID базы данных. Однако транзакция T2 уже изменила значение записи A на 3 . Таким образом, невозможно вернуть запись A в 1 независимо от ситуации. В этом случае может быть два варианта.

1. Двухфазная блокировка (2PL)

   Первая, когда  транзакция T2  пытается изменить  запись A , она знает, что  транзакция T1  уже изменила  запись A,  и ожидает завершения  транзакции T1,  поскольку  транзакция T2  не может знать,  Транзакция T1  будет зафиксирована или отменена. Этот метод называется двухфазной блокировкой (2PL) .

2. Многоуровневое управление параллелизмом (MVCC)

   Другой способ — позволить каждой из них, транзакциям T1 и T2 , иметь свои собственные измененные версии. Даже тогда , когда транзакция T1 изменила запись A от 1 до 2 , то T1 транзакционных листьев исходного значения 1 , как это и пишет , что  версия транзакции T1  от записи A является 2 . Затем следующая транзакция T2 изменяет запись A с 1 на 3 , а не с2 до 4 , и запись о том , что  версия Т2 транзакции  от записи A является 3 .

   Когда транзакция T1 отката, это не имеет значения , если  2 ,  версия транзакции T1 , не применяется к записи A . После этого, если транзакция T2 совершена, 3 , версия Т2 транзакции , будет применена к записи A . Если транзакция T1 передана до транзакции T2 , запись Aизменяется на 2, а затем на 3 во время совершения транзакции T2 . Окончательный статус базы данных идентичен статусу выполнения каждой транзакции независимо, без какого-либо влияния на другие транзакции. Следовательно, он удовлетворяет свойству ACID. Этот метод называется многоверсионным управлением параллелизмом (MVCC) .

CUBRID внедрил метод 2PL, а также DB2 и SQL Server, в то время как Oracle, InnoDB и PostgreSQL внедрили MVCC.

Двухфазная блокировка в CUBRID

2PL, принятый CUBRID, использует блокировки для обеспечения согласованности между транзакциями, которые изменяют идентичные данные. Как буквально означает «блокировка»,  блокировка выполняется в два этапа :

1. расширение фазы (приобретение)
2. фаза усадки (отпускание)

Точнее, все транзакции должны получить блокировку для данных, к которым осуществляется доступ, и полученные блокировки снимаются только после завершения транзакции. После того, как транзакция получила блокировку для определенных данных (независимо от типа блокировки, S_LOCKдля чтения, означает общую блокировку или X_LOCKдля записи, означает эксклюзивную блокировку ), когда другая транзакция пытается получить новую блокировку для данных, Новая блокировка разрешена или отложена в зависимости от  правила совместимости блокировки . Поэтому успех или неудача предыдущей транзакции не влияет на следующие транзакции, поэтому согласованность данных сохраняется.

Менеджер блокировки в CUBRID

Таким образом, ключевой момент 2PL , принятый CUBRID, является то , что замок должен быть обработан через две фазы :  расширение фазы и сокращение фазы . Затем [рисунок 1]  освобождает все блокировки, полученные при выполнении транзакции, только после завершения транзакции (фиксация или откат) .

Рисунок 1: Двухфазная блокировка.

Метод управления параллелизмом 2PL естественным образом контролирует доступ к идентичным данным из транзакций, заставляя все транзакции соблюдать протокол 2PL. На следующем рисунке 2 ниже показан пример трех транзакций, использующих 2PL: транзакция 1 выполняет операцию B = B + A , транзакция 2 выполняет операцию C = A + B , а транзакция 3 выполняет операцию печати C. Поскольку все три транзакции обращаются к данным A, B и C, требуется контроль параллелизма. В этом случае каждая транзакция выполняется в соответствии с протоколом 2PL, поэтому нет конфликта данных.

Рисунок 2: Управление параллелизмом с использованием 2PL.

Режимы блокировки

Для того, чтобы понять управление параллелизмом нескольких сделок более глубоко, давайте поговорим о  режимах блокировки , преобразовании блокировки и уровне изоляции транзакций . На приведенном выше рисунке вы можете увидеть , что S-lock, разделяемую блокировку для A был приобретен первый сделки 1 , но он также приобрел  Транзакции 2 тоже. Наоборот, запрашиваемая транзакция X-lockблокируется до тех пор, пока не S-lockбудет освобождена. В этом случае различные режимы блокировки используются, чтобы минимизировать конфликты со стороны шкафчиков. Основные типы замков, используемых в СУБД.

• Shared (S) Lock : Используется для операции чтения. Обычно он задается в целевой записи при выполнении SELECTоператора. Он блокирует транзакцию от изменения данных, которые уже были прочитаны другими транзакциями.
• Исключительный (Х) Замок : Используется для записи-операций , таких как INSERT, UPDATE, DELETE. Он блокирует изменение данных несколькими транзакциями.
• Update (U) Lock : используется для определения того, что целевой ресурс будет изменен. Он используется для минимизации взаимоблокировки, которая может возникнуть, когда несколько транзакций выполняют как чтение, так и запись.
• Intent Shared (IS) Lock: Set on the upper resource (e.g. tables) to set the S-lock on some lower resources (e.g. records or pages). It is to prevent other transactions from setting X-lock on the upper resource. Intent lock will soon be described.
• Intent Exclusive (IX) Lock: Set on the upper resource to set X-lock on some lower resources.
• Shared with Intent Exclusive (SIX) Lock: Set on the upper resource to set S-lock and X-lock on some lower resources.

Lock mode compatibility

Among the lock modes above, intent locks are used to improve the transaction concurrency and to prevent deadlock between the upper resources and the lower resources. For example, when Transaction A tries to read Record R on Table T, it sets IS_LOCK on Table T before setting S_LOCK on Record R. Then, Transaction B is prevented from setting X_LOCK on Table T to change the structure of Table T. If Transaction A has not set IS_LOCK on Table T, Transaction B would change the structure of Table T. Then, Transaction A would perform a wrong read operation. This way Transaction B has no need to check all records in Table T to check whether there is any lock set by other transactions for setting X_LOCK on Table T. The following lock mode compatibility table will clearly show the effect of intent locks:

Table 1: The lock mode compatibility table of CUBRID.

From the lock mode compatibility table, you can see that X_LOCK cannot be set on a table if IS_LOCK is set on the table. And only IS_LOCK can be compatible with SIX_LOCK. This means that SIX_LOCK intends to set S_LOCK and X_LOCK on the record and it will not allow any lock but IS_LOCK for S_LOCK on other non-conflicting records. From the table, you can see that IX_LOCK and IX_LOCK can be compatible with each other. IX_LOCK intends to set X_LOCK for some records. So, the compatibility is available. If there are two transactions that try to change an identical record, IX_LOCK for the table is allowed. However, there is no problem in concurrency control since only the transaction that has acquired X_LOCK for the record first can change the record (X_LOCK and X_LOCK are not compatible).

The lock mode compatibility table is expressed as a global variable lock_Comp[][] in the lock_table.c file in CUBRID source code. Among CUBRID sources, most codes related to lock modes are implemented in lock_manager.c file. To set lock on a data object, the lock_object() function is used which receives three parameters: the OID of an object where the lock mode will be set, the OID of the class where the object belongs, and the desired lock mode. In the source code of the function, you can see that the function is executed in several ways based on the target of the lock mode, the lock mode for an instance object or for a class object.

Take note of this: in CUBRID, a class object is also an object. Keep it in mind that a class object has an OID and all class objects are the instances of a root class, so it uses ROOTOID, the OID of the root object, as its class OID.

From the code, you can see that the required intent lock is set on a class object when a lock mode is required for an instance object. And there is a concept of lock waiting time in the lock mode request. To retrieve the lock timeout value set on the current transaction, the logtb_find_wait_secs() function is called. CUBRID supports the SET TRANSACTION LOCK TIMEOUT SQL command and the setLockTimeout() method in JDBC. The command is to specify the lock timeout of the current transaction. Lock waiting time means the time for a transaction, which has made a request for lock mode, to wait when a lock mode is set on an object by a transaction and the requested lock is not compatible with the already-set lock mode. As you have seen before, the 2PL concurrency control method does not allow lock from other transactions until the existing lock is released. For the following two reasons, lock timeout should be set by a transaction:

1. When a user does not want to wait too long because of the lock mode.
2. To lower the frequency of deadlock.

Deadlocks

A deadlock occurs when two or more transactions request resources locked by each of them, so all transactions cannot be progressed. Figure 8 below shows an example of a deadlock.

Figure 2: Transaction Deadlock.

First, Transaction 1 executes UPDATE participant SET gold=10 WHERE host_year=2004 AND nation_code=’KOR’ statement and sets X_LOCK on the ‘KOR’ record. Transaction 2 sets X_LOCK on the ‘JPN’ record. Transaction 3 sets X_LOCK on the ‘CHN’ record.

After that, Transaction 1 requests X_LOCK on the ‘JPN’ record for executing UPDATE for that record. However, the ‘JPN’ record is already locked with X_LOCK by Transaction 2. So, Transaction 1 should wait until Transaction 2 ends. Based on the 2PL protocol, the X_LOCK is released when the transaction ends. Transaction 2 requests X_LOCK on the ‘CHN’record and waits for Transaction 3. Finally, Transaction 3 waits for Transaction 1 to acquire the 'KOR' record of Transaction 1 as it has X_LOCK on the ‘CHN’ record. As a result,Transaction 1 waits for Transaction 2 to end, Transaction 2 waits for Transaction 3 to end, and Transaction 3 waits for Transaction 1 to end. So, no transaction can be progressed. This is called a deadlock.

Most DBMSs which use the 2PL method, including CUBRID, use the deadlock detection method to solve the deadlock problem. It periodically checks whether the cycle illustrated in the above figure occurs by drawing a Lock Wait Graph for the transactions being executed.

In CUBRID, the thread for detecting deadlock checks the Lock Wait Graph every second. When a deadlock is detected, one transaction among the transactions is randomly selected and aborted by force. This is called unilateral abort. When a transaction is selected as a victim to be sacrificed to solve the deadlock and unilaterally aborted, the corresponding SQL statement returns an error code. The error message is «The transaction has timed out due to deadlock while waiting for X_LOCK for an object. It waited until User 2 ended.” When an error is returned and the application aborts the transaction, the locks of the transaction are released and other transactions can be continuously processed.

To see how the deadlock is detected, see the lock_detect_local_deadlock() function in the source code. This function is called with the intervals (in seconds) specified by the PRM_LK_RUN_DEADLOCK_INTERVAL variable (the deadlock_detection_interval_in_secs parameter in cubrid.conf file) on the background thread which executes thread_deadlock_detect_thread().

Even if a deadlock does not occur, when the execution time of a transaction is too long, other transactions should wait for too long as well. For a certain application, it is wiser to give up rather than wait. In particular, when a web server has called DB tasks and the wait time is too long, all threads of the web server are used to process the DB, so they cannot be used to process external HTTP requests any more, causing service failures. Therefore, for a web application, the threads should be returned without waiting an unlimited amount of time for DB processing even if an error occurs. Two methods are used for that:

1. One is lock timeout supported by CUBRID.
2. The other is query cancel. JDBC is defined with an API which can cancel the SQL statement being executed.

The key data structure of the lock manager is defined in the lock_manager.c file.

typedef struct lk_entry LK_ENTRY;
struct lk_entry
{
#if defined(SERVER_MODE)
  struct lk_res *res_head;      /* back to resource entry           */
  THREAD_ENTRY *thrd_entry;     /* thread entry pointer             */
  int tran_index;               /* transaction table index          */
  LOCK granted_mode;            /* granted lock mode                */
  LOCK blocked_mode;            /* blocked lock mode                */
  int count;                    /* number of lock requests          */
  struct lk_entry *next;        /* next entry                       */
  struct lk_entry *tran_next;   /* list of locks that trans. holds  */
  struct lk_entry *class_entry; /* ptr. to class lk_entry           */
  LK_ACQUISITION_HISTORY *history;      /* lock acquisition history         */
  LK_ACQUISITION_HISTORY *recent;       /* last node of history list        */
  int ngranules;                /* number of finer granules         */
  int mlk_count;                /* number of instant lock requests  */
  unsigned char scanid_bitset[1];       /* PRM_LK_MAX_SCANID_BIT/8];       */
#else                           /* not SERVER_MODE */
  int dummy;
#endif                          /* not SERVER_MODE */
};
 
typedef struct lk_res LK_RES;
struct lk_res
{
  MUTEX_T res_mutex;            /* resource mutex */
  LOCK_RESOURCE_TYPE type;      /* type of resource: class,instance */
  OID oid;
  OID class_oid;
  LOCK total_holders_mode;      /* total mode of the holders */
  LOCK total_waiters_mode;      /* total mode of the waiters */
  LK_ENTRY *holder;             /* lock holder list */
  LK_ENTRY *waiter;             /* lock waiter list */
  LK_ENTRY *non2pl;             /* non2pl list */
  LK_RES *hash_next;            /* for hash chain */
};

From the file, the lk_Gl global variable of LK_GLOBAL_DATA type is the core. The LK_ENTRY structure stands for the lock itself. For example, when the Transaction T1 has requested a lock, one LK_ENTRY is created. LK_RES is a structure that shows to which resource the lock belongs. In CUBRID, all resources are objects (instance objects and class objects), so they are shaped as OIDs. In the LK_RES structure, you can see the list of holders with LK_ENTRY type and the list of waiters. The list of holders is a list of transactions that hold the lock for the resource now. For example, when Transaction T1 and Transaction T2 have acquired S_LOCK for the data record with OID1, LK_ENTRY that corresponds to the S_LOCK of T1 and T2 will be registered in the list of holders. When Transaction T3 requests X_LOCK on the OID1 record, T3 should wait because of the existing S_LOCK. So, the LK_ENTRY corresponding to X_LOCK of T3 will be registered to the list of waiters. Which lock is held by which transaction is maintained in the tran_lock_table variable which has the LK_TRAN_LOCK structure as a table.

The Wait For Graph for detecting a deadlock is expressed as TWFG_node and TWFG_edge of the LK_WFG_NODE structure and the LK_WFG_EDGE structure. The lock_detect_local_deadlock() function creates a Wait For Graph and detects whether there is a cycle on the graph. When a cycle is detected, the lock_select_deadlock_victim() function selects a victim transaction to be sacrificed for solving the deadlock. For reference, transactions are continuously executed while a Wait For Graph is drawn up and checked, the information of the ended transaction is removed from the graph. The victim transaction is selected based on the following criteria:

• If a transaction is not a holder, it cannot be a victim.
• When a transaction is in the commit phase or the rollback phase, it cannot be selected as a victim.
• Select a transaction of which lock timeout is not set to -1 (unlimited waiting) first.
• Select the latest transaction rather than the older one. (The transaction ID is an incremental number. A transaction with smaller transaction number is the older one.)

Conclusion

This concludes the talk about Two-Phase Locking in CUBRID. I briefly covered the types of concurrency control, the difference between 2PL and MVCC, about what locking technique is used in CUBRID RDBMS, about locking modes and their compatibility, and finally, the deadlocks and the solution for them.

In this article I have mentioned about OID (Object Identifiers) which are used to identify instance objects as well as class objects. In the next article I will continue this talk and explain what Object, Class, and OID are.