diff --git a/keyserver/src/database/migration-config.js b/keyserver/src/database/migration-config.js
--- a/keyserver/src/database/migration-config.js
+++ b/keyserver/src/database/migration-config.js
@@ -2,6 +2,8 @@
 
 import fs from 'fs';
 
+import { SQL, dbQuery } from './database';
+
 const migrations: $ReadOnlyMap<number, () => Promise<void>> = new Map([
   [
     0,
@@ -25,6 +27,14 @@
       await fixBaseRoutePathForLocalhost('facts/squadcal_url.json');
     },
   ],
+  [
+    3,
+    async () => {
+      await addUUIDColumnToIdsTable();
+      await setUUIDsInIdsTable();
+      await addTriggerBeforeIdInsert();
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
@@ -83,4 +93,46 @@
   await writeFile.close();
 }
 
+async function addUUIDColumnToIdsTable(): Promise<void> {
+  const show_query = SQL`
+    SHOW COLUMNS FROM ids
+    LIKE 'uuid_id'
+  `;
+  const [result] = await dbQuery(show_query);
+  if (result !== undefined && result.length > 0) {
+    return;
+  }
+  const alter_query = SQL`
+    ALTER TABLE ids
+    ADD COLUMN uuid_id CHAR(36)
+  `;
+  await dbQuery(alter_query);
+}
+
+async function setUUIDsInIdsTable(): Promise<void> {
+  const update_query = SQL`
+    UPDATE ids
+    SET uuid_id = UUID()
+    WHERE uuid_id IS NULL
+  `;
+  await dbQuery(update_query);
+}
+
+async function addTriggerBeforeIdInsert(): Promise<void> {
+  const show_query = SQL`
+    SHOW TRIGGERS LIKE 'ids'
+  `;
+  const [result] = await dbQuery(show_query);
+  if (result !== undefined && result.length > 0) {
+    return;
+  }
+  const trigger = SQL`
+    CREATE TRIGGER ids_before_insert
+    BEFORE INSERT ON ids
+    FOR EACH ROW
+    SET new.uuid_id = UUID()
+  `;
+  await dbQuery(trigger);
+}
+
 export { migrations, newDatabaseVersion };
diff --git a/keyserver/src/database/setup-db.js b/keyserver/src/database/setup-db.js
--- a/keyserver/src/database/setup-db.js
+++ b/keyserver/src/database/setup-db.js
@@ -62,7 +62,8 @@
 
       CREATE TABLE ids (
         id bigint(20) NOT NULL,
-        table_name varchar(255) NOT NULL
+        table_name varchar(255) NOT NULL,
+        uuid_id CHAR(36)
       ) ENGINE=InnoDB DEFAULT CHARSET=latin1;
 
       CREATE TABLE memberships (
@@ -340,6 +341,11 @@
 
       ALTER TABLE metadata
         ADD PRIMARY KEY (name);
+
+      CREATE TRIGGER ids_before_insert
+        BEFORE INSERT ON ids
+        FOR EACH ROW
+        SET new.uuid_id = UUID();
     `,
     { multipleStatements: true },
   );