Struct tikv::server::lock_manager::deadlock::DetectTable

pub struct DetectTable {
    wait_for_map: HashMap<TimeStamp, HashMap<TimeStamp, Locks>>,
    ttl: Duration,
    last_active_expire: Instant,
    now: Instant,
}

Used to detect the deadlock of wait-for-lock in the cluster.

Fields

wait_for_map: HashMap<TimeStamp, HashMap<TimeStamp, Locks>>

Keeps the DAG of wait-for-lock. Every edge from txn_ts to lock_ts has a survival time – ttl. When checking the deadlock, if the ttl has elpased, the corresponding edge will be removed. last_detect_time is the start time of the edge. Detect requests will refresh it.

ttl: Duration

The ttl of every edge.

last_active_expire: Instant

The time of last active_expire.

now: Instant

Implementations

impl DetectTable

pub fn new(ttl: Duration) -> Self

Creates a auto-expiring detect table.

pub fn detect(
    &mut self,
    txn_ts: TimeStamp,
    lock_ts: TimeStamp,
    lock_hash: u64,
    lock_key: &[u8],
    resource_group_tag: &[u8]
) -> Option<(u64, Vec<WaitForEntry>)>

Returns the key hash which causes deadlock, and the current wait chain that forms the deadlock with txn_ts’s waiting for txn at lock_ts. Note that the current detecting edge is not included in the returned wait chain. This is intended to reduce RPC message size since the information about current detecting txn is included in a separated field.

fn do_detect(
    &mut self,
    txn_ts: TimeStamp,
    wait_for_ts: TimeStamp
) -> Option<(u64, Vec<WaitForEntry>)>

Checks if there is a path from wait_for_ts to txn_ts.

fn generate_wait_chain(
    &self,
    start: TimeStamp,
    end: TimeStamp,
    vertex_predecessors_map: HashMap<TimeStamp, TimeStamp>
) -> Vec<WaitForEntry>

Generate the wait chain after deadlock is detected. This function is part of implementation of do_detect. It assumes there’s a path from start to end in the waiting graph, and every single edge V1 -> V2 has an entry in vertex_predecessors_map so that vertex_predecessors_map[V2] == V1, and vertex_predecessors_map[V1] == 0.

fn register_if_existed(
    &mut self,
    txn_ts: TimeStamp,
    lock_ts: TimeStamp,
    lock_hash: u64,
    key: &[u8],
    resource_group_tag: &[u8]
) -> bool

Returns true and adds to the detect table if txn_ts is waiting for lock_ts. When the function returns true, key and resource_group_tag may be taken to store in the waiting graph.

fn register(
    &mut self,
    txn_ts: TimeStamp,
    lock_ts: TimeStamp,
    lock_hash: u64,
    key: &[u8],
    resource_group_tag: &[u8]
)

Adds to the detect table. The edge from txn_ts to lock_ts must not exist.

fn clean_up_wait_for(
    &mut self,
    txn_ts: TimeStamp,
    lock_ts: TimeStamp,
    lock_hash: u64
)

Removes the corresponding wait_for_entry.

fn clean_up(&mut self, txn_ts: TimeStamp)

Removes the entries of the transaction.

fn clear(&mut self)

Clears the whole detect table.

fn reset_ttl(&mut self, ttl: Duration)

Reset the ttl

const ACTIVE_EXPIRE_THRESHOLD: usize

The threshold of detect table size to trigger active_expire.

const ACTIVE_EXPIRE_INTERVAL: Duration

The interval between active_expire.

fn active_expire(&mut self)

Iterates the whole table to remove all expired entries.