citusdata / citusdata/citus

Foreign keys: Updating co-located placements in different order could cause deadlock

Open
#861 6 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
12.8k
Forks
794
Avg merge
2d 14h
Merged PRs (30d)
31

Description

If shard placements have foreign keys and the replication factor is >1, then we need to make sure we always perform commands in the same order across _all co-located placements_. Otherwise, a write to the referenced table could take locks that will block the writes on the referring table and create a deadlock.

A way to simulate the deadlock in PostgreSQL below.

```
CREATE TABLE main_1 (x int, y int);
CREATE TABLE main_2 (x int, y int);
CREATE TABLE reference_1 (a int unique, b int);
CREATE TABLE reference_2 (a int unique, b int);
ALTER TABLE main_1 ADD CONSTRAINT main_1_cs FOREIGN KEY (x) REFERENCES reference_2 (a);
ALTER TABLE main_2 ADD CONSTRAINT main_2_cs FOREIGN KEY (x) REFERENCES reference_2 (a);
INSERT INTO reference_1 VALUES (1,1);
INSERT INTO reference_2 VALUES (1,1);
```

In session 1, write to first shard placement of main table:

```
BEGIN;
INSERT INTO main_1 VALUES (1,1);
```

In session 2, write to second shard placement of referenced table:

```
BEGIN;
DELETE FROM reference_2 WHERE a = 1;
```

In session 1, write to second shard placement of main table.

```
INSERT INTO main_2 VALUES (1,1);
...blocks waiting on DELETE to finish ...
```

In session 2, write to first shard placement of referenced table.

```
DELETE FROM reference_1 WHERE a = 1;
ERROR: deadlock detected
DETAIL: Process 11755 waits for ShareLock on transaction 2677; blocked by process 11751.
Process 11751 waits for ShareLock on transaction 2678; blocked by process 11755.
HINT: See server log for query details.
CONTEXT: while deleting tuple (0,1) in relation "reference_1"
```

In the Citus case, the deadlock wouldn't actually be detected since it's happening across 2 machines. To solve this, we need to always write to nodes (rather than placements) in the same order.

I think this may be partially solved by ensuring placement IDs that are always generated in the same order as the node IDs (might already be the case). We also need to evaluate whether this property is preserved across copy and move operations and pg_dist_node changes.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.