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
@@ -732,6 +732,17 @@
     },
   ],
   [57, synchronizeInviteLinksWithBlobs],
+  [
+    58,
+    async () => {
+      await dbQuery(
+        SQL`
+          ALTER TABLE updates
+            MODIFY \`key\` varchar(255) CHARSET latin1 COLLATE latin1_bin
+        `,
+      );
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
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
@@ -4,7 +4,7 @@
 import bots from 'lib/facts/bots.js';
 import genesis from 'lib/facts/genesis.js';
 import { usernameMaxLength } from 'lib/shared/account-utils.js';
-import { sortIDs } from 'lib/shared/relationship-utils.js';
+import { sortUserIDs } from 'lib/shared/relationship-utils.js';
 import { undirectedStatus } from 'lib/types/relationship-types.js';
 import { threadTypes } from 'lib/types/thread-types-enum.js';
 
@@ -171,7 +171,7 @@
         id bigint(20) NOT NULL,
         user varchar(255) CHARSET latin1 COLLATE latin1_bin NOT NULL,
         type tinyint(3) UNSIGNED NOT NULL,
-        \`key\` bigint(20) DEFAULT NULL,
+        \`key\` varchar(255) CHARSET latin1 COLLATE latin1_bin DEFAULT NULL,
         updater bigint(20) DEFAULT NULL,
         target bigint(20) DEFAULT NULL,
         content mediumtext CHARACTER SET utf8mb4 COLLATE utf8mb4_bin,
@@ -423,7 +423,7 @@
 }
 
 async function createUsers() {
-  const [user1, user2] = sortIDs(bots.commbot.userID, ashoat.id);
+  const [user1, user2] = sortUserIDs(bots.commbot.userID, ashoat.id);
   await dbQuery(
     SQL`
       INSERT INTO ids (id, table_name)
diff --git a/keyserver/src/updaters/relationship-updaters.js b/keyserver/src/updaters/relationship-updaters.js
--- a/keyserver/src/updaters/relationship-updaters.js
+++ b/keyserver/src/updaters/relationship-updaters.js
@@ -2,7 +2,7 @@
 
 import invariant from 'invariant';
 
-import { sortIDs } from 'lib/shared/relationship-utils.js';
+import { sortUserIDs } from 'lib/shared/relationship-utils.js';
 import { messageTypes } from 'lib/types/message-types-enum.js';
 import {
   type RelationshipRequest,
@@ -74,7 +74,7 @@
     const now = Date.now();
     for (const userID in userRelationshipOperations) {
       const operations = userRelationshipOperations[userID];
-      const ids = sortIDs(viewer.userID, userID);
+      const ids = sortUserIDs(viewer.userID, userID);
 
       if (operations.length) {
         updateIDs.push(userID);
@@ -146,7 +146,7 @@
     updateIDs.push(...userIDs);
 
     const updateRows = userIDs.map(userID => {
-      const [user1, user2] = sortIDs(viewer.userID, userID);
+      const [user1, user2] = sortUserIDs(viewer.userID, userID);
       return { user1, user2, status: undirectedStatus.KNOW_OF };
     });
 
@@ -169,7 +169,7 @@
     const undirectedRows = [];
     for (const userID of userIDs) {
       directedRows.push([viewer.userID, userID, directedStatus.BLOCKED]);
-      const [user1, user2] = sortIDs(viewer.userID, userID);
+      const [user1, user2] = sortUserIDs(viewer.userID, userID);
       undirectedRows.push({ user1, user2, status: undirectedStatus.KNOW_OF });
     }
 
diff --git a/keyserver/src/utils/relationship-changeset.js b/keyserver/src/utils/relationship-changeset.js
--- a/keyserver/src/utils/relationship-changeset.js
+++ b/keyserver/src/utils/relationship-changeset.js
@@ -2,7 +2,7 @@
 
 import invariant from 'invariant';
 
-import { sortIDs } from 'lib/shared/relationship-utils.js';
+import { sortUserIDs } from 'lib/shared/relationship-utils.js';
 import {
   type UndirectedRelationshipRow,
   undirectedStatus,
@@ -15,7 +15,7 @@
   finalized: boolean = false;
 
   static _getKey(userA: string, userB: string): string {
-    const [user1, user2] = sortIDs(userA, userB);
+    const [user1, user2] = sortUserIDs(userA, userB);
     return `${user1}|${user2}`;
   }
 
diff --git a/lib/shared/relationship-utils.js b/lib/shared/relationship-utils.js
--- a/lib/shared/relationship-utils.js
+++ b/lib/shared/relationship-utils.js
@@ -12,10 +12,18 @@
 } from '../types/relationship-types.js';
 import type { UserInfo } from '../types/user-types.js';
 
-function sortIDs(firstId: string, secondId: string): string[] {
-  return [Number(firstId), Number(secondId)]
-    .sort((a, b) => a - b)
-    .map(num => num.toString());
+function sortUserIDs(firstId: string, secondId: string): string[] {
+  if (!isNaN(Number(firstId)) && !isNaN(Number(secondId))) {
+    return [Number(firstId), Number(secondId)]
+      .sort((a, b) => a - b)
+      .map(num => num.toString());
+  } else if (!isNaN(Number(firstId))) {
+    return [firstId, secondId];
+  } else if (!isNaN(Number(secondId))) {
+    return [secondId, firstId];
+  }
+
+  return [firstId, secondId].sort();
 }
 
 function getAvailableRelationshipButtons(
@@ -106,7 +114,7 @@
 }
 
 export {
-  sortIDs,
+  sortUserIDs,
   getAvailableRelationshipButtons,
   relationshipBlockedInEitherDirection,
   getRelationshipDispatchAction,
diff --git a/lib/shared/relationship-utils.test.js b/lib/shared/relationship-utils.test.js
new file mode 100644
--- /dev/null
+++ b/lib/shared/relationship-utils.test.js
@@ -0,0 +1,17 @@
+// @flow
+
+import { sortUserIDs } from './relationship-utils.js';
+
+describe('sortUserIDs', () => {
+  it('should sort id that are numbers, as numbers', () => {
+    expect(sortUserIDs('100', '99')).toEqual(['99', '100']);
+  });
+  it('should always sort uuid after id that is a number', () => {
+    expect(sortUserIDs('100A', '99')).toEqual(['99', '100A']);
+    expect(sortUserIDs('100', '99A')).toEqual(['100', '99A']);
+  });
+  it('should sort uuid lexicographically', () => {
+    expect(sortUserIDs('100A', '99A')).toEqual(['100A', '99A']);
+    expect(sortUserIDs('DEF', 'abc')).toEqual(['DEF', 'abc']);
+  });
+});