Optimistic Concurrency Control
Unlike most high-end transactional database engines, YottaDB uses Optimistic Concurrency Control (OCC) to implement ACID transactions. Since transactions do not typically collide, optimistic techniques scale up better than other techniques. OCC and the daemonless architecture reinforce each other to provide the extreme level of scalability that YottaDB users have come to expect.
How YottaDB OCC Works
Every database records a transaction number in its file header. Each database block header records the database transaction number when that block was last updated. When a process is inside a transaction:
- The database engine tracks the file and block number of each database block read, and the transaction number of that block. Since a block to be updated must first be read, this list includes blocks to be updated.
- When application logic updates the database, the update is retained in process-private memory and does not update the database. The update is visible to subsequently application logic within the process, but is not visible to any other process until the transaction commits.
- When the application logic signals that it is ready to commit the transaction, the database engine checks whether any block read within the transaction has a higher transaction number than that it has recorded. If none has — the typical case — the engine commits the transaction.
- If even one block has been updated since the process read it, the database engine discards its work and restarts the transaction logic. This restart is transparent to the application logic, which does not need to be coded to be aware of YottaDB transaction processing. This simplifies application code and improves maintainability. In the most common case, where a collision results from a random overlapping update by a concurrent process, it is able to commit on the second attempt.
- If the second attempt also fails to commit, the engine makes a third attempt, and if that fails, the engine concludes that pathological application logic is causing the collisions, and makes a fourth and final attempt during which updates by other processes are blocked, allowing the transaction to commit. [Applications should be written to avoid pathological colliding concurrent transactions; YottaDB provides tools and support services for application developers to identify such pathology should it occur.]
OCC Enables Scalable ACID Transaction Processing
YottaDB implements transactions with strong Atomic, Consistent, Isolated, Durable (ACID) properties. Consider application logic to move $100 from a savings account to a checking account, which conceptually consists of the following steps:
- Validate that the accounts exist, that the requested transfer is permitted, that there is sufficient balance, that the transfer request is authenticated, etc.
- Subtract $100 from the savings account.
- Add $100 to the checking account.
- Compute and debit any applicable service charges.
- Create a record to log the transaction.
Consider that application logic executing concurrently with an update to business rules affecting minimum balances and service charges, and a balance inquiry. Each of the three is implemented as an ACID transaction.
Atomicity is the property that the entire transaction happens or none of it happens. For example, in the event of a system malfunction, it should not recover to an intermediate state such as between the withdrawal from savings and the deposit to checking.
Consistency is the property that the database should never be observable in a state that is inconsistent (the process of course sees its own data that it is manipulating in a transient state).
Isolation is the property that each transaction execute and commit as if it were the only transaction active on the system. For example, if the money transfer transaction commits before the transaction that updates business rules,
There is a duality between Consistency and Isolation – as a practical matter, it is not possible to provide strong Consistency without strong Isolation and vice versa. YottaDB provides strong Consistency and Isolation. Strict Serializability implies strong Consistency and Isolation, and vice versa.
Durability is the property that once a transaction is committed, the database state change it represents is permanent, even if the computer crashes. YottaDB implements Durability by logging each transaction to a journal file, and “hardening” that journal file to non-volatile storage as part of the logic that commits a transaction.
Published on May 01, 2023