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
@@ -775,6 +775,9 @@
         strategies.lists(hypothesis_strategies.directories(), min_size=1, max_size=10)
     )
     def test_directory_add_get_arbitrary(self, swh_storage, directories):
+        # Deduplicate based on ids
+        directories = list({d.id: d for d in directories}.values())
+
         swh_storage.directory_add(directories)
 
         for directory in directories:
@@ -1199,6 +1202,9 @@
         )
     )
     def test_revision_add_get_arbitrary(self, swh_storage, revisions):
+        # Deduplicate based on ids
+        revisions = list({rev.id: rev for rev in revisions}.values())
+
         # remove non-intrinsic data, so releases inserted with different hypothesis
         # data can't clash with each other
         revisions = [
@@ -1748,6 +1754,9 @@
         )
     )
     def test_release_add_get_arbitrary(self, swh_storage, releases):
+        # Deduplicate based on ids
+        releases = list({rel.id: rel for rel in releases}.values())
+
         # remove non-intrinsic data, so releases inserted with different hypothesis
         # data can't clash with each other
         releases = [
@@ -3993,6 +4002,9 @@
     )
     @given(strategies.lists(hypothesis_strategies.snapshots(), min_size=1, max_size=10))
     def test_snapshot_add_get_arbitrary(self, swh_storage, snapshots):
+        # Deduplicate based on ids
+        snapshots = list({snp.id: snp for snp in snapshots}.values())
+
         swh_storage.snapshot_add(snapshots)
 
         for snapshot in snapshots:
@@ -5612,6 +5624,12 @@
         strategies.lists(hypothesis_strategies.objects(split_content=True), max_size=2)
     )
     def test_add_arbitrary(self, swh_storage, objects):
+        # Deduplicate based on ids if any
+        objects = list(
+            {obj.id: obj for obj in objects if hasattr(obj, "id")}.values()
+        ) + [obj for obj in objects if not hasattr(obj, "id")]
+        random.shuffle(objects)
+
         for (obj_type, obj) in objects:
             if obj.object_type == "origin_visit":
                 swh_storage.origin_add([Origin(url=obj.origin)])