Foreign key constraints in DynamoDB

What are foreign keys

A foreign key is a property in a table that references items in another table. That's why they are called "foreign": they are keys in a different table.

For example, let's have two tables, one for users and one for groups. A user can belong to a group and this association is stored as a foreign key in the users table:

The constraint required here needs to ensure that the referenced item exists. That means it needs to guarantee two things:

• The group exists when adding a user
• The group can not be deleted when a user is in it

SQL databases usually support foreign key constraints out of the box. When you create a table you can define that a column is a reference to another table and the database engine makes sure that the above two conditions are always enforced.

For example, a user - group association can be defined in SQL as:

CREATE TABLE user_groups (
  id VARCHAR(100) PRIMARY KEY
);

CREATE TABLE users (
  id VARCHAR(100) PRIMARY KEY,
  name VARCHAR(100) NOT NULL,
  user_group VARCHAR(100),
  FOREIGN KEY (user_group) REFERENCES user_groups(id)
);

Adding a user to a group that does not exist fails:

INSERT INTO users (id, name, user_group) VALUES ("user1", "User 1", "group1");

-- Query Error: Error: ER_NO_REFERENCED_ROW_2:
-- Cannot add or update a child row: a foreign key constraint fails
-- (`test`.`users`, CONSTRAINT `users_ibfk_1` FOREIGN KEY (`user_group`) REFERENCES `user_groups` (`id`))

Creating a group first and then adding the user runs just fine:

INSERT INTO user_groups (id) VALUES ("group1");
INSERT INTO users (id, name, user_group) VALUES ("user1", "User 1", "group1");

Deleting a group when users are still associated with it fails:

DELETE FROM user_groups;

-- Query Error: Error: ER_ROW_IS_REFERENCED_2:
-- Cannot delete or update a parent row: a foreign key constraint fails
-- (`test`.`users`, CONSTRAINT `users_ibfk_1` FOREIGN KEY (`user_group`) REFERENCES `user_groups` (`id`))

But deleting the users first and then delete the group works:

DELETE FROM users;
DELETE FROM user_groups;

Constraints in DynamoDB

But DynamoDB does not support foreign key constraints natively. It's a key-value store and all operations it supports involve individual items. You can check that the values in a single item are correct, such as a user has a username and it's not an empty string, but by default a Put operation can not check outside what is included in the item.

Transactions are a relatively new additions to the database and they solve some of these problems. They are still a lot simpler than SQL transactions, but at least they provide all-or-nothing guarantees across multiple items.

Using a transaction, you can make sure that the group exists when adding a user:

TransactItems: [
	{
		Put: {
			TableName: USER_TABLE,
			ConditionExpression: "attribute_not_exists(#pk)",
			ExpressionAttributeNames: {
				"#pk": "ID",
			},
			Item: {
				ID: {S: id},
				group: {S: group},
				name: {S: name},
			}
		},
	},
	{
		ConditionCheck: {
			TableName: GROUP_TABLE,
			ConditionExpression: "attribute_exists(#pk)",
			Key: {
				ID: {S: group},
			},
			ExpressionAttributeNames: {
				"#pk": "ID",
			},
		},
	}
]

The second part (ConditionCheck) makes sure that an item with the given ID exists (attribute_exists(#pk)) and the first part adds a user. If the second part fails the first part is cancelled.

This takes care of the first criterion of foreign keys. But what about the second ("The group can not be deleted when a user is in it")? Unfortunately, DynamoDB transactions can not ensure that no item with a specific attribute exists that is not the key of the item. To solve this, we need denormalization.

Denormalization

Denormalization means adding information to the database that is already there in some form. In the SQL world it's a best practice to store every piece of information only once (called normalization) as the database supports complex queries and transactions that span multiple read and write operations.

But because NoSQL databases (and DynamoDB in particular) support only simple queries and the transactions are equally limited, adding extra data to work around these limitations is a best practice. But doing that requires great care.

Denormalization brings the risk of inconsistencies. Since the same information is contained multiple times what happens if they don't agree? Usually, one is the source of truth and the others are derived information, but when a mechanism builds on the latter (such as a transaction check as we'll see) any inconsistency leads to errors.

So, how to use denormalization to make sure a group can not be deleted when it has users?

To implement this, add a counter to the groups that keeps track of the current amount of users the group has.

The denormalized information here is the number of users in a group as querying and counting the users should yield the same result. That means, every operation that changes the result of that query must also change the num_users attribute.

With this attribute, we can write a transaction that only allows deleting a group when there are no users associated with it:

TransactItems: [
	{
		Delete: {
			TableName: GROUP_TABLE,
			ConditionExpression: "attribute_exists(#pk) AND #num_users = :zero",
			ExpressionAttributeNames: {
				"#pk": "ID",
				"#num_users": "num_users",
			},
			ExpressionAttributeValues: {
				":zero": {N: "0"}
			},
			Key: {
				ID: {S: id}
			},
		},
	},
]

The ConditionExpression checks that the num_users equals 0. If it's not then the transaction fails. This implements the second requirement of foreign keys.

But that also means we have to make sure that these counters are kept up-to-date at all times. The guarantees of the above transaction holds only when the counter for the group is accurate. And if even a single operation does not update it and it goes out-of-sync then either the transaction will fail or the constraint does not hold.

For a simple implementation, that means we need to implement it in 4 operations:

• Creating a group
• Creating a user
• Deleting a user
• Moving a user to a new group

Related

How to keep accurate counts in DynamoDB

Use transactions to atomically update items and keep a record of their numbers

Implementation

Create group

This part is simple, as we just need to initialize the num_users to 0:

Put: {
	TableName: GROUP_TABLE,
	ConditionExpression: "attribute_not_exists(#pk)",
	ExpressionAttributeNames: {
		"#pk": "ID",
	},
	Item: {
		ID: {S: id},
		num_users: {N: "0"},
	}
},

Create user

When we create a user, we need to also increment the group's num_users by 1:

TransactItems: [
	{
		// add user
		Put: {
			TableName: USER_TABLE,
			ConditionExpression: "attribute_not_exists(#pk)",
			ExpressionAttributeNames: {
				"#pk": "ID",
			},
			Item: {
				ID: {S: id},
				group: {S: group},
				name: {S: name},
			}
		},
	},
	{
		// increment group
		Update: {
			TableName: GROUP_TABLE,
			UpdateExpression: "ADD #num_users :one",
			ConditionExpression: "attribute_exists(#pk)",
			Key: {
				ID: {S: group},
			},
			ExpressionAttributeNames: {
				"#pk": "ID",
				"#num_users": "num_users",
			},
			ExpressionAttributeValues: {
				":one": {N: "1"},
			}
		},
	}
]

Delete user

This is a more interesting operation. Deleting a user usually gets only its ID, so first we need to fetch the whole user object to find out its group membership:

const currentUser = unmarshall((await client.send(new GetItemCommand({
	TableName: USER_TABLE,
	Key: {
		ID: {S: id}
	}
}))).Item);

With the user object, we have everything to delete the user. Like in other DynamoDB operations, add a condition to match the previously fetched item (#group = :group) as another process might have changed the object between the two calls. Remember that while DynamoDB transactions are atomic, a read before the transaction is a different operation.

Then decrease the num_users by 1 for the group:

TransactItems: [
	{
		Delete: {
			TableName: USER_TABLE,
			// user exists and in the expected group
			ConditionExpression: "attribute_exists(#pk) AND #group = :group",
			ExpressionAttributeNames: {
				"#pk": "ID",
				"#group": "group",
			},
			ExpressionAttributeValues: {
				":group": {S: currentUser.group},
			},
			Key: {
				ID: {S: id}
			},
		},
	},
	{
		// decrease num_users by 1
		Update: {
			TableName: GROUP_TABLE,
			UpdateExpression: "ADD #num_users :minusone",
			ConditionExpression: "attribute_exists(#pk) AND #num_users > :zero",
			Key: {
				ID: {S: currentUser.group},
			},
			ExpressionAttributeNames: {
				"#pk": "ID",
				"#num_users": "num_users",
			},
			ExpressionAttributeValues: {
				":minusone": {N: "-1"},
				":zero": {N: "0"}
			}
		},
	}
]

Delete group

During delete, check that there are no users in the group:

{
	Delete: {
		TableName: GROUP_TABLE,
		ConditionExpression: "attribute_exists(#pk) AND #num_users = :zero",
		ExpressionAttributeNames: {
			"#pk": "ID",
			"#num_users": "num_users",
		},
		ExpressionAttributeValues: {
			":zero": {N: "0"}
		},
		Key: {
			ID: {S: id}
		},
	},
},

Update user

When an operation modifies a user make sure to handle the case where it affects its group membership. If it does, the transaction needs to decrease the num_users for the old group by 1, and increase it for the new group by 1.

To know the current membership, get the user object:

const currentUser = unmarshall((await client.send(new GetItemCommand({
	TableName: USER_TABLE,
	Key: {
		ID: {S: id}
	}
}))).Item);

Then to change it:

TransactItems: [
	{
		Put: {
			TableName: USER_TABLE,
			// check that the group is what we expect and the user exists
			ConditionExpression: "attribute_exists(#pk) AND #group = :group",
			ExpressionAttributeNames: {
				"#pk": "ID",
				"#group": "group",
			},
			ExpressionAttributeValues: {
				":group": {S: currentUser.group},
			},
			Item: {
				ID: {S: id},
				group: {S: group},
				name: {S: name},
			}
		},
	},
	...(currentUser.group !== group ? [
		// moving between groups
		{
			// add 1 to the new group
			Update: {
				TableName: GROUP_TABLE,
				UpdateExpression: "ADD #num_users :one",
				ConditionExpression: "attribute_exists(#pk)",
				Key: {
					ID: {S: group},
				},
				ExpressionAttributeNames: {
					"#pk": "ID",
					"#num_users": "num_users",
				},
				ExpressionAttributeValues: {
					":one": {N: "1"},
				}
			},
		},
		{
			// subtract 1 from the old group
			Update: {
				TableName: GROUP_TABLE,
				UpdateExpression: "ADD #num_users :minusone",
				ConditionExpression: "attribute_exists(#pk) AND #num_users > :zero",
				Key: {
					ID: {S: currentUser.group},
				},
				ExpressionAttributeNames: {
					"#pk": "ID",
					"#num_users": "num_users",
				},
				ExpressionAttributeValues: {
					":minusone": {N: "-1"},
					":zero": {N: "0"},
				}
			},
		},
	] : [])
]

Conclusion

DynamoDB can support foreign keys, but it requires great care to keep the count up-to-date.