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
@@ -829,6 +829,13 @@
         assert len(origins) <= limit
         return PagedResult(results=origins, next_page_token=next_page_token)
 
+    def origin_count(
+        self, url_pattern: str, regexp: bool = False, with_visit: bool = False
+    ) -> int:
+        raise NotImplementedError(
+            "The Cassandra backend does not implement origin_count"
+        )
+
     def origin_add(self, origins: List[Origin]) -> Dict[str, int]:
         to_add = [ori for ori in origins if self.origin_get_one(ori.url) is None]
         self.journal_writer.origin_add(to_add)
diff --git a/swh/storage/interface.py b/swh/storage/interface.py
--- a/swh/storage/interface.py
+++ b/swh/storage/interface.py
@@ -8,7 +8,7 @@
 from enum import Enum
 from typing import Any, Dict, Iterable, List, Optional, Tuple, TypeVar, Union
 
-from typing_extensions import TypedDict
+from typing_extensions import Protocol, TypedDict, runtime_checkable
 
 from swh.core.api import remote_api_endpoint
 from swh.core.api.classes import PagedResult as CorePagedResult
@@ -67,7 +67,8 @@
     return f
 
 
-class StorageInterface:
+@runtime_checkable
+class StorageInterface(Protocol):
     @remote_api_endpoint("check_config")
     def check_config(self, *, check_write: bool) -> bool:
         """Check that the storage is configured and ready to go."""
diff --git a/swh/storage/tests/storage_tests.py b/swh/storage/tests/storage_tests.py
--- a/swh/storage/tests/storage_tests.py
+++ b/swh/storage/tests/storage_tests.py
@@ -142,6 +142,12 @@
 
         assert missing_methods == []
 
+        # If all the assertions above succeed, then this one should too.
+        # But there's no harm in double-checking.
+        # And we could replace the assertions above by this one, but unlike
+        # the assertions above, it doesn't explain what is missing.
+        assert isinstance(storage, StorageInterface)
+
     def test_check_config(self, swh_storage):
         assert swh_storage.check_config(check_write=True)
         assert swh_storage.check_config(check_write=False)
diff --git a/swh/storage/tests/test_pytest_plugin.py b/swh/storage/tests/test_pytest_plugin.py
--- a/swh/storage/tests/test_pytest_plugin.py
+++ b/swh/storage/tests/test_pytest_plugin.py
@@ -12,7 +12,7 @@
 
 
 def test_swh_storage(swh_storage: StorageInterface):
-    assert isinstance(swh_storage, StorageInterface) is not None
+    assert isinstance(swh_storage, StorageInterface)
 
 
 def test_swh_storage_backend_config(swh_storage_backend_config):