diff --git a/swh/provenance/provenance.py b/swh/provenance/provenance.py
--- a/swh/provenance/provenance.py
+++ b/swh/provenance/provenance.py
@@ -10,6 +10,7 @@
 
 from typing_extensions import Literal, TypedDict
 
+from swh.core.statsd import statsd
 from swh.model.model import Sha1Git
 
 from .interface import (
@@ -23,6 +24,8 @@
 
 LOGGER = logging.getLogger(__name__)
 
+BACKEND_DURATION_METRIC = "swh_provenance_backend_duration_seconds"
+
 
 class DatetimeCache(TypedDict):
     data: Dict[Sha1Git, Optional[datetime]]
@@ -80,11 +83,15 @@
     def close(self) -> None:
         self.storage.close()
 
+    @statsd.timed(metric=BACKEND_DURATION_METRIC, tags={"method": "flush"})
     def flush(self) -> None:
         self.flush_revision_content_layer()
         self.flush_origin_revision_layer()
         self.clear_caches()
 
+    @statsd.timed(
+        metric=BACKEND_DURATION_METRIC, tags={"method": "flush_origin_revision"}
+    )
     def flush_origin_revision_layer(self) -> None:
         # Origins and revisions should be inserted first so that internal ids'
         # resolution works properly.
@@ -145,6 +152,9 @@
                     RelationType.REV_IN_ORG,
                 )
 
+    @statsd.timed(
+        metric=BACKEND_DURATION_METRIC, tags={"method": "flush_revision_content"}
+    )
     def flush_revision_content_layer(self) -> None:
         # Register in the storage all content, directories and revisions that are
         # involved in this layer's associated relations.