diff --git a/requirements-swh.txt b/requirements-swh.txt
--- a/requirements-swh.txt
+++ b/requirements-swh.txt
@@ -1,4 +1,4 @@
-swh.core[db,http] >= 2.10
+swh.core[db,http] >= 2.14
 swh.counters >= v0.8.0
 swh.model >= 6.3.0
 swh.objstorage >= 0.2.2
diff --git a/swh/storage/api/server.py b/swh/storage/api/server.py
--- a/swh/storage/api/server.py
+++ b/swh/storage/api/server.py
@@ -7,7 +7,7 @@
 import os
 from typing import Any, Dict, Optional
 
-from psycopg2.errors import QueryCanceled
+from psycopg2.errors import OperationalError, QueryCanceled
 
 from swh.core import config
 from swh.core.api import RPCServerApp
@@ -100,11 +100,21 @@
     return error_handler(exception, encode_data, status_code=400)
 
 
-@app.errorhandler(QueryCanceled)
-def querycanceled_error_handler(exception):
+@app.errorhandler(OperationalError)
+def operationalerror_exception_handler(exception):
     # Same as error_handler(exception, encode_data); but does not log or send to Sentry.
     # These errors are noisy, and are better logged on the caller's side after it
-    # retried a few times
+    # retried a few times.
+    # Additionally, we return 503 instead of 500, telling clients they should retry.
+    response = encode_data(serializers.exception_to_dict(exception))
+    response.status_code = 503
+    return response
+
+
+@app.errorhandler(QueryCanceled)
+def querycancelled_exception_handler(exception):
+    # Ditto, but 500 instead of 503, because this is usually caused by the query
+    # size instead of a transient failure
     response = encode_data(serializers.exception_to_dict(exception))
     response.status_code = 500
     return response
diff --git a/swh/storage/tests/test_api_client.py b/swh/storage/tests/test_api_client.py
--- a/swh/storage/tests/test_api_client.py
+++ b/swh/storage/tests/test_api_client.py
@@ -1,10 +1,12 @@
-# Copyright (C) 2015-2020  The Software Heritage developers
+# Copyright (C) 2015-2022  The Software Heritage developers
 # See the AUTHORS file at the top-level directory of this distribution
 # License: GNU General Public License version 3, or any later version
 # See top-level LICENSE file for more information
 
+import psycopg2.errors
 import pytest
 
+from swh.core.api import RemoteException, TransientRemoteException
 import swh.storage
 from swh.storage import get_storage
 import swh.storage.api.server as server
@@ -79,6 +81,46 @@
     def test_origin_count(self):
         pass
 
+    def test_exception(self, app_server, swh_storage, mocker):
+        """Checks the client re-raises unknown exceptions as a :exc:`RemoteException`"""
+        assert swh_storage.revision_get(["\x01" * 20]) == [None]
+        mocker.patch.object(
+            app_server.storage._cql_runner,
+            "revision_get",
+            side_effect=ValueError("crash"),
+        )
+        with pytest.raises(RemoteException) as e:
+            swh_storage.revision_get(["\x01" * 20])
+        assert not isinstance(e, TransientRemoteException)
+
+    def test_operationalerror_exception(self, app_server, swh_storage, mocker):
+        """Checks the client re-raises as a :exc:`TransientRemoteException`
+        rather than the base :exc:`RemoteException`; so the retrying proxy
+        retries for longer."""
+        assert swh_storage.revision_get(["\x01" * 20]) == [None]
+        mocker.patch.object(
+            app_server.storage._cql_runner,
+            "revision_get",
+            side_effect=psycopg2.errors.AdminShutdown("cluster is shutting down"),
+        )
+        with pytest.raises(RemoteException) as excinfo:
+            swh_storage.revision_get(["\x01" * 20])
+        assert isinstance(excinfo.value, TransientRemoteException)
+
+    def test_querycancelled_exception(self, app_server, swh_storage, mocker):
+        """Checks the client re-raises as a :exc:`TransientRemoteException`
+        rather than the base :exc:`RemoteException`; so the retrying proxy
+        retries for longer."""
+        assert swh_storage.revision_get(["\x01" * 20]) == [None]
+        mocker.patch.object(
+            app_server.storage._cql_runner,
+            "revision_get",
+            side_effect=psycopg2.errors.QueryCanceled("too big!"),
+        )
+        with pytest.raises(RemoteException) as excinfo:
+            swh_storage.revision_get(["\x01" * 20])
+        assert not isinstance(excinfo.value, TransientRemoteException)
+
 
 class TestStorageApiGeneratedData(_TestStorageGeneratedData):
     @pytest.mark.skip("Not supported by Cassandra")