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
@@ -32,6 +32,7 @@
     MetadataFetcher,
     MetadataTargetType,
     RawExtrinsicMetadata,
+    Sha1Git,
 )
 from swh.storage.interface import ListOrder, PagedResult, VISIT_STATUSES
 from swh.storage.objstorage import ObjStorage
@@ -260,7 +261,7 @@
             [{"sha1_git": c for c in contents}], key_hash="sha1_git"
         )
 
-    def content_get_random(self):
+    def content_get_random(self) -> Sha1Git:
         return self._cql_runner.content_get_random().sha1_git
 
     def _skipped_content_get_from_hash(self, algo, hash_) -> Iterable:
@@ -416,7 +417,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) -> Sha1Git:
         return self._cql_runner.directory_get_random().id
 
     def revision_add(self, revisions: List[Revision]) -> Dict:
@@ -505,7 +506,7 @@
         seen = set()
         yield from self._get_parent_revs(revisions, seen, limit, True)
 
-    def revision_get_random(self):
+    def revision_get_random(self) -> Sha1Git:
         return self._cql_runner.revision_get_random().id
 
     def release_add(self, releases: List[Release]) -> Dict:
@@ -537,7 +538,7 @@
         for rel_id in releases:
             yield rels.get(rel_id)
 
-    def release_get_random(self):
+    def release_get_random(self) -> Sha1Git:
         return self._cql_runner.release_get_random().id
 
     def snapshot_add(self, snapshots: List[Snapshot]) -> Dict:
@@ -652,7 +653,7 @@
             "next_branch": last_branch,
         }
 
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> Sha1Git:
         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
@@ -50,6 +50,7 @@
     MetadataFetcher,
     MetadataTargetType,
     RawExtrinsicMetadata,
+    Sha1Git,
 )
 from swh.model.hashutil import DEFAULT_ALGORITHMS, hash_to_bytes, hash_to_hex
 from swh.storage.interface import ListOrder, PagedResult, VISIT_STATUSES
@@ -361,7 +362,7 @@
             if content not in self._content_indexes["sha1_git"]:
                 yield content
 
-    def content_get_random(self):
+    def content_get_random(self) -> Sha1Git:
         return random.choice(list(self._content_indexes["sha1_git"]))
 
     def _skipped_content_add(self, contents: List[SkippedContent]) -> Dict:
@@ -454,9 +455,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) -> Sha1Git:
         return random.choice(list(self._directories))
 
     def _directory_entry_get_by_path(self, directory, paths, prefix):
@@ -536,7 +535,7 @@
             (rev["id"], rev["parents"]) for rev in self.revision_log(revisions, limit)
         )
 
-    def revision_get_random(self):
+    def revision_get_random(self) -> Sha1Git:
         return random.choice(list(self._revisions))
 
     def release_add(self, releases: List[Release]) -> Dict:
@@ -564,7 +563,7 @@
             else:
                 yield None
 
-    def release_get_random(self):
+    def release_get_random(self) -> Sha1Git:
         return random.choice(list(self._releases))
 
     def snapshot_add(self, snapshots: List[Snapshot]) -> Dict:
@@ -655,7 +654,7 @@
             "next_branch": next_branch,
         }
 
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> Sha1Git:
         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
@@ -27,6 +27,7 @@
     MetadataFetcher,
     MetadataTargetType,
     RawExtrinsicMetadata,
+    Sha1Git,
 )
 
 
@@ -310,7 +311,7 @@
         ...
 
     @remote_api_endpoint("content/get_random")
-    def content_get_random(self):
+    def content_get_random(self) -> Sha1Git:
         """Finds a random content id.
 
         Returns:
@@ -443,7 +444,7 @@
         ...
 
     @remote_api_endpoint("directory/get_random")
-    def directory_get_random(self):
+    def directory_get_random(self) -> Sha1Git:
         """Finds a random directory id.
 
         Returns:
@@ -547,7 +548,7 @@
         ...
 
     @remote_api_endpoint("revision/get_random")
-    def revision_get_random(self):
+    def revision_get_random(self) -> Sha1Git:
         """Finds a random revision id.
 
         Returns:
@@ -612,7 +613,7 @@
         ...
 
     @remote_api_endpoint("release/get_random")
-    def release_get_random(self):
+    def release_get_random(self) -> Sha1Git:
         """Finds a random release id.
 
         Returns:
@@ -764,7 +765,7 @@
         ...
 
     @remote_api_endpoint("snapshot/get_random")
-    def snapshot_get_random(self):
+    def snapshot_get_random(self) -> Sha1Git:
         """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
@@ -36,6 +36,7 @@
     Revision,
     Release,
     SkippedContent,
+    Sha1Git,
     Snapshot,
     SHA1_SIZE,
     MetadataAuthority,
@@ -376,7 +377,7 @@
 
     @timed
     @db_transaction()
-    def content_get_random(self, db=None, cur=None):
+    def content_get_random(self, db=None, cur=None) -> Sha1Git:
         return db.content_get_random(cur)
 
     @staticmethod
@@ -529,7 +530,7 @@
 
     @timed
     @db_transaction()
-    def directory_get_random(self, db=None, cur=None):
+    def directory_get_random(self, db=None, cur=None) -> Sha1Git:
         return db.directory_get_random(cur)
 
     @timed
@@ -616,7 +617,7 @@
 
     @timed
     @db_transaction()
-    def revision_get_random(self, db=None, cur=None):
+    def revision_get_random(self, db=None, cur=None) -> Sha1Git:
         return db.revision_get_random(cur)
 
     @timed
@@ -666,7 +667,7 @@
 
     @timed
     @db_transaction()
-    def release_get_random(self, db=None, cur=None):
+    def release_get_random(self, db=None, cur=None) -> Sha1Git:
         return db.release_get_random(cur)
 
     @timed
@@ -786,7 +787,7 @@
 
     @timed
     @db_transaction()
-    def snapshot_get_random(self, db=None, cur=None):
+    def snapshot_get_random(self, db=None, cur=None) -> Sha1Git:
         return db.snapshot_get_random(cur)
 
     @timed
diff --git a/swh/storage/tests/test_retry.py b/swh/storage/tests/test_retry.py
--- a/swh/storage/tests/test_retry.py
+++ b/swh/storage/tests/test_retry.py
@@ -561,9 +561,6 @@
     """
     sample_dir = sample_data.directory
 
-    directory = swh_storage.directory_get_random()  # no directory
-    assert not directory
-
     s = swh_storage.directory_add([sample_dir])
     assert s == {
         "directory:add": 1,
@@ -591,9 +588,6 @@
 
     sample_dir = sample_data.directories[1]
 
-    directory_id = swh_storage.directory_get_random()  # no directory
-    assert not directory_id
-
     s = swh_storage.directory_add([sample_dir])
     assert s == {
         "directory:add": 1,
@@ -617,9 +611,6 @@
 
     sample_dir = sample_data.directory
 
-    directory_id = swh_storage.directory_get_random()  # no directory
-    assert not directory_id
-
     with pytest.raises(StorageArgumentException, match="Refuse to add"):
         swh_storage.directory_add([sample_dir])