diff --git a/swh/indexer/tests/storage/test_init.py b/swh/indexer/tests/storage/test_init.py
--- a/swh/indexer/tests/storage/test_init.py
+++ b/swh/indexer/tests/storage/test_init.py
@@ -3,6 +3,8 @@
 # License: GNU General Public License version 3, or any later version
 # See top-level LICENSE file for more information
 
+import inspect
+
 import pytest
 
 from swh.indexer.storage import IndexerStorage, get_indexer_storage
@@ -50,3 +52,41 @@
     with pytest.warns(DeprecationWarning):
         concrete_idx_storage = get_indexer_storage(class_name, args=kwargs)
     assert isinstance(concrete_idx_storage, expected_class)
+
+
+@pytest.mark.parametrize("class_name,expected_class,kwargs", SERVER_IMPLEMENTATIONS)
+def test_init_types(class_name, expected_class, kwargs, mock_psycopg2):
+    """Checks all methods of SearchInterface are implemented by this
+    backend, and that they have the same signature.
+
+    """
+    if kwargs:
+        concrete_idx_storage = get_indexer_storage(class_name, **kwargs)
+    else:
+        concrete_idx_storage = get_indexer_storage(class_name)
+
+    # Create an instance of the protocol (which cannot be instantiated
+    # directly, so this creates a subclass, then instantiates it)
+    interface = type("_", (IndexerStorageInterface,), {})()
+
+    for meth_name in dir(interface):
+        if meth_name.startswith("_"):
+            continue
+        interface_meth = getattr(interface, meth_name)
+
+        missing_methods = []
+
+        try:
+            concrete_meth = getattr(concrete_idx_storage, meth_name)
+        except AttributeError:
+            if not getattr(interface_meth, "deprecated_endpoint", False):
+                # The backend is missing a (non-deprecated) endpoint
+                missing_methods.append(meth_name)
+                continue
+
+        expected_signature = inspect.signature(interface_meth)
+        actual_signature = inspect.signature(concrete_meth)
+
+        assert actual_signature == expected_signature, meth_name
+
+        assert missing_methods == []