Concurrency Control & NoSQL Systems – Key Vocabulary

A comprehensive set of vocabulary flashcards covering key terms in database concurrency control techniques and modern NOSQL data-management concepts.

Concurrency Control

Techniques that manage simultaneous transaction execution to preserve isolation and consistency.

Isolation

ACID property ensuring each transaction appears to run alone despite concurrent execution.

Consistency (DB)

State in which all database integrity constraints are satisfied before and after a transaction.

Read–Write Conflict

Situation where one transaction reads a data item that another concurrently writes.

Write–Write Conflict

Situation where two transactions concurrently attempt to write the same data item.

Binary Lock

Lock with two states—locked (1) or unlocked (0)—enforcing mutual exclusion on a data item.

Shared (Read) Lock

Lock mode allowing multiple transactions to read a data item but not write it.

Exclusive (Write) Lock

Lock mode that grants a single transaction both read and write access to a data item.

Lock Table

System structure that stores the lock status and waiting queues for each data item.

lock_item(X)

Operation that requests a lock on data item X; the transaction may wait if X is already locked.

unlock_item(X)

Operation that releases a lock on data item X and wakes one waiting transaction.

Two-Phase Locking (2PL)

Protocol in which all lock requests precede the first unlock, producing serializable schedules.

Growing Phase

First phase of 2PL where a transaction may obtain new locks but cannot release any.

Shrinking Phase

Second phase of 2PL where a transaction releases locks but cannot obtain new ones.

Lock Conversion

Process of upgrading a shared lock to exclusive or downgrading exclusive to shared under rules.

Basic 2PL

Standard two-phase locking without extra restrictions; guarantees serializability but not recoverability.

Conservative (Static) 2PL

Variant where a transaction locks all required items before execution, preventing deadlocks.

Strict 2PL

Variant that holds exclusive locks until commit or abort, yielding strict (recoverable) schedules.

Rigorous 2PL

Stronger form keeping both shared and exclusive locks until commit/abort; easy to implement.

Deadlock

Condition where each transaction in a set waits indefinitely for locks held by others in the set.

Starvation

Indefinite delay of a transaction because it never gains the needed locks while others proceed.

Wait-For Graph

Directed graph whose nodes are transactions and edges show waiting; cycles indicate deadlock.

Deadlock Prevention

Protocols that order resource acquisition or use timestamps to avoid cyclic waits.

Deadlock Detection

Technique that periodically checks the wait-for graph for cycles and aborts a victim.

Wait-Die Protocol

Timestamp scheme where an older transaction waits; younger conflicting one aborts (dies).

Wound-Wait Protocol

Timestamp scheme where an older transaction aborts (wounds) a younger holder; otherwise waits.

No Waiting (NW)

Deadlock-free protocol that immediately aborts a transaction if its lock request cannot be granted.

Cautious Waiting (CW)

Protocol allowing waiting only if the lock-holder is not itself blocked; else aborts requester.

Timeout (Deadlock)

Simple scheme that aborts a transaction if it waits longer than a preset period.

Timestamp

Unique, usually increasing, identifier representing a transaction’s start time.

Timestamp Ordering (TO)

Concurrency control that orders conflicting operations by transaction timestamps to ensure serializability without locks.

read_TS(X)

Largest timestamp of any transaction that successfully read item X.

write_TS(X)

Largest timestamp of any transaction that successfully wrote item X.

Strict Timestamp Ordering

TO variant delaying a read/write on X until the transaction that last wrote X commits or aborts, yielding strict schedules.

Cascading Rollback

Series of transaction aborts triggered when a transaction that wrote data later read by others is aborted.

Multiversion Concurrency Control (MVCC)

Techniques that keep multiple committed versions of data items, letting readers access old versions to increase concurrency.

Version

Distinct stored value of a data item, each tagged with readTS and writeTS.

Certify Lock

Special lock mode in multiversion 2PL used to finalize writes during commit (certification).

Optimistic (Validation) Control

Method that defers conflict checking until transaction end; uses read, validation, and write phases.

Validation Phase

Stage in optimistic control that tests whether a transaction can commit without violating serializability.

Granularity

Size of data items chosen for locking, ranging from field to whole database.

Fine Granularity

Locking on small items (e.g., records) allowing high concurrency but many locks.

Coarse Granularity

Locking on large items (e.g., files) reducing lock overhead but limiting concurrency.

Intention Lock

Lock type (IS, IX, SIX) placed at higher-level nodes to declare forthcoming lower-level locks in multiple-granularity schemes.

IS (Intention Shared)

Intent lock indicating forthcoming shared locks on descendants.

IX (Intention Exclusive)

Intent lock indicating forthcoming exclusive locks on descendants.

SIX (Shared-Intention Exclusive)

Lock holding shared access on a node while permitting exclusive locks below it.

Multiple Granularity Locking (MGL)

Protocol that coordinates IS, IX, SIX, S, X locks along a hierarchy of data items.

Replication

Storing copies of data on multiple nodes to improve availability and read performance.

Master-Slave Replication

Model where all writes occur at the master copy and propagate to read-only slave copies.

Master-Master Replication

Model permitting writes at any replica, requiring conflict resolution to reconcile versions.

Horizontal Scalability

Ability to increase system capacity by adding more nodes (scale-out).

Vertical Scalability

Increasing capacity by upgrading existing hardware resources (scale-up).

Shard

Horizontal partition of a dataset distributed across nodes for load balancing.

Shard Key

Field whose value determines the shard on which a document or record is stored.

Eventual Consistency

Weak consistency model where replicas converge to the same state if no new updates occur.

CAP Theorem

Principle stating a distributed system cannot simultaneously guarantee Consistency, Availability, and Partition tolerance.

Consistency (CAP)

All nodes see the same data at the same time after a write completes.

Availability (CAP)

Every request receives a response—success or failure—without guarantee of latest data.

Partition Tolerance

System continues to operate despite network partitions separating nodes.

Document Store

NOSQL database that stores self-describing documents (e.g., JSON) accessed by document id.

Key-Value Store

NOSQL model storing (key, value) pairs for fast lookup by unique key.

Column-Family (Wide Column) Store

NOSQL system that groups columns into families and stores them separately; supports sparse rows and versioning.

Graph Database

Database that represents data as nodes and relationships, enabling graph traversal queries.

MongoDB

Popular open-source document store using BSON, replica sets, and sharding.

DynamoDB

Amazon cloud key-value store offering hash and range keys, auto-scaling, and eventual consistency.

BigTable

Google’s proprietary wide-column store underpinning services like Gmail and Maps.

HBase

Apache open-source wide-column store modeled after BigTable and built on Hadoop HDFS.

Cassandra

Distributed NOSQL database blending key-value and column-family features with tunable consistency.

Redis

In-memory key-value database supporting persistence, replication, and rich data structures.

Voldemort

Open-source key-value store using consistent hashing, versioning with vector clocks, and eventual consistency.

Replica Set (MongoDB)

Group of MongoDB nodes with one primary and multiple secondary copies for high availability.

Consistent Hashing

Data distribution technique that evenly maps keys to nodes and minimizes reallocation when nodes join or leave.

Vector Clock

Metadata list tracking causality among versions in distributed version control.

JSON

Lightweight text format for structured data, widely used in NOSQL document stores.

BSON

Binary JSON format used internally by MongoDB to store documents efficiently.