diff --git a/swh/storage/cassandra/storage.py b/swh/storage/cassandra/storage.py
--- a/swh/storage/cassandra/storage.py
+++ b/swh/storage/cassandra/storage.py
@@ -260,7 +260,7 @@
             [{"sha1_git": c for c in contents}], key_hash="sha1_git"
         )
 
-    def content_get_random(self):
+    def content_get_random(self) -> bytes:
         return self._cql_runner.content_get_random().sha1_git
 
     def _skipped_content_get_from_hash(self, algo, hash_) -> Iterable:
@@ -416,7 +416,7 @@
     def directory_ls(self, directory, recursive=False):
         yield from self._directory_ls(directory, recursive)
 
-    def directory_get_random(self):
+    def directory_get_random(self) -> bytes:
         return self._cql_runner.directory_get_random().id
 
     def revision_add(self, revisions: List[Revision]) -> Dict:
@@ -505,7 +505,7 @@
         seen = set()
         yield from self._get_parent_revs(revisions, seen, limit, True)
 
-    def revision_get_random(self):
+    def revision_get_random(self) -> bytes:
         return self._cql_runner.revision_get_random().id
 
     def release_add(self, releases: List[Release]) -> Dict:
@@ -537,7 +537,7 @@
         for rel_id in releases:
             yield rels.get(rel_id)
 
-    def release_get_random(self):
+    def release_get_random(self) -> bytes:
         return self._cql_runner.release_get_random().id
 
     def snapshot_add(self, snapshots: List[Snapshot]) -> Dict:
@@ -652,7 +652,7 @@
             "next_branch": last_branch,
         }
 
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> bytes:
         return self._cql_runner.snapshot_get_random().id
 
     def object_find_by_sha1_git(self, ids):
diff --git a/swh/storage/in_memory.py b/swh/storage/in_memory.py
--- a/swh/storage/in_memory.py
+++ b/swh/storage/in_memory.py
@@ -361,7 +361,7 @@
             if content not in self._content_indexes["sha1_git"]:
                 yield content
 
-    def content_get_random(self):
+    def content_get_random(self) -> bytes:
         return random.choice(list(self._content_indexes["sha1_git"]))
 
     def _skipped_content_add(self, contents: List[SkippedContent]) -> Dict:
@@ -454,9 +454,7 @@
     def directory_entry_get_by_path(self, directory, paths):
         return self._directory_entry_get_by_path(directory, paths, b"")
 
-    def directory_get_random(self):
-        if not self._directories:
-            return None
+    def directory_get_random(self) -> bytes:
         return random.choice(list(self._directories))
 
     def _directory_entry_get_by_path(self, directory, paths, prefix):
@@ -536,7 +534,7 @@
             (rev["id"], rev["parents"]) for rev in self.revision_log(revisions, limit)
         )
 
-    def revision_get_random(self):
+    def revision_get_random(self) -> bytes:
         return random.choice(list(self._revisions))
 
     def release_add(self, releases: List[Release]) -> Dict:
@@ -564,7 +562,7 @@
             else:
                 yield None
 
-    def release_get_random(self):
+    def release_get_random(self) -> bytes:
         return random.choice(list(self._releases))
 
     def snapshot_add(self, snapshots: List[Snapshot]) -> Dict:
@@ -655,7 +653,7 @@
             "next_branch": next_branch,
         }
 
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> bytes:
         return random.choice(list(self._snapshots))
 
     def object_find_by_sha1_git(self, ids):
diff --git a/swh/storage/interface.py b/swh/storage/interface.py
--- a/swh/storage/interface.py
+++ b/swh/storage/interface.py
@@ -310,7 +310,7 @@
         ...
 
     @remote_api_endpoint("content/get_random")
-    def content_get_random(self):
+    def content_get_random(self) -> bytes:
         """Finds a random content id.
 
         Returns:
@@ -443,7 +443,7 @@
         ...
 
     @remote_api_endpoint("directory/get_random")
-    def directory_get_random(self):
+    def directory_get_random(self) -> bytes:
         """Finds a random directory id.
 
         Returns:
@@ -547,7 +547,7 @@
         ...
 
     @remote_api_endpoint("revision/get_random")
-    def revision_get_random(self):
+    def revision_get_random(self) -> bytes:
         """Finds a random revision id.
 
         Returns:
@@ -612,7 +612,7 @@
         ...
 
     @remote_api_endpoint("release/get_random")
-    def release_get_random(self):
+    def release_get_random(self) -> bytes:
         """Finds a random release id.
 
         Returns:
@@ -764,7 +764,7 @@
         ...
 
     @remote_api_endpoint("snapshot/get_random")
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> bytes:
         """Finds a random snapshot id.
 
         Returns:
diff --git a/swh/storage/storage.py b/swh/storage/storage.py
--- a/swh/storage/storage.py
+++ b/swh/storage/storage.py
@@ -376,7 +376,7 @@
 
     @timed
     @db_transaction()
-    def content_get_random(self, db=None, cur=None):
+    def content_get_random(self, db=None, cur=None) -> bytes:
         return db.content_get_random(cur)
 
     @staticmethod
@@ -529,7 +529,7 @@
 
     @timed
     @db_transaction()
-    def directory_get_random(self, db=None, cur=None):
+    def directory_get_random(self, db=None, cur=None) -> bytes:
         return db.directory_get_random(cur)
 
     @timed
@@ -616,7 +616,7 @@
 
     @timed
     @db_transaction()
-    def revision_get_random(self, db=None, cur=None):
+    def revision_get_random(self, db=None, cur=None) -> bytes:
         return db.revision_get_random(cur)
 
     @timed
@@ -666,7 +666,7 @@
 
     @timed
     @db_transaction()
-    def release_get_random(self, db=None, cur=None):
+    def release_get_random(self, db=None, cur=None) -> bytes:
         return db.release_get_random(cur)
 
     @timed
@@ -786,7 +786,7 @@
 
     @timed
     @db_transaction()
-    def snapshot_get_random(self, db=None, cur=None):
+    def snapshot_get_random(self, db=None, cur=None) -> bytes:
         return db.snapshot_get_random(cur)
 
     @timed