Repository: borgbackup/borgstore

Issue:
get rid of ad-hoc mkdir usage
We have ad-hoc `mkdir` at quite some places that makes sure base and nesting directories are either present or created.

With a local fs, this is no big thing, but with a slow remote sftp repo, it means quite some useless (because the directory already exists) mkdir calls being repeated over and over again.

So, guess it is better to create all needed base and nesting directories once when the store is created.

Example (locks):

```
[chan 0] stat(b'/Volumes/USB_APFS/borg2-test-fc/locks/cc22550fcd2df7fc')
[chan 0] mkdir(b'/Volumes/USB_APFS/borg2-test-fc/.', 511)
[chan 0] mkdir(b'/Volumes/USB_APFS/borg2-test-fc/locks', 511)
[chan 0] open(b'/Volumes/USB_APFS/borg2-test-fc/locks/xnbnxkfe.tmp', 'w')
[chan 0] open(b'/Volumes/USB_APFS/borg2-test-fc/locks/xnbnxkfe.tmp', 'w') -> 00000000
[chan 0] close(00000000)
[chan 0] posix_rename(b'/Volumes/USB_APFS/borg2-test-fc/locks/xnbnxkfe.tmp', b'/Volumes/USB_APFS/borg2-test-fc/locks/cc22550fcd2df7fc')
```

Discussion:
@ThomasWaldmann: See some remarks about how some cloud storages deal with (empty) directories: #46@ThomasWaldmann: Issues encountered:
- `nesting.nest` can deal with arbitrary names, not just all-hex hash-like names. if we would keep it that way, we would not know what directories to generate in advance.
- levels config can be incomplete currently and level with default to 0 for missing namespaces - if we want to create every dir in advance, levels has to be complete and have all namespaces and related levels.
- `Store` does not have `mkdir`, this is only available in the backends
@ThomasWaldmann: Fixed by #67.

Code assumes that nesting with level > 0 uses all-hex hash-like names.@ThomasWaldmann: Looks now like this:
```
[chan 0] stat(b'/tmp/b2-repo/data/58/45/584528941ebf8fae1d203b5bb0aa3713dadf7e8bf6995d35a8820d7f0a6edc5e')
[chan 0] open(b'/tmp/b2-repo/data/58/45/azytxkwy.tmp', 'w')
[chan 0] open(b'/tmp/b2-repo/data/58/45/azytxkwy.tmp', 'w') -> 00000000
[chan 0] close(00000000)
[chan 0] posix_rename(b'/tmp/b2-repo/data/58/45/azytxkwy.tmp', b'/tmp/b2-repo/data/58/45/584528941ebf8fae1d203b5bb0aa3713dadf7e8bf6995d35a8820d7f0a6edc5e')
[
```

Solution patch:
diff --git a/src/borgstore/backends/_base.py b/src/borgstore/backends/_base.py
index 0709eff..645d2b9 100644
--- a/src/borgstore/backends/_base.py
+++ b/src/borgstore/backends/_base.py
@@ -41,6 +41,13 @@ def validate_name(name):
 
 
 class BackendBase(ABC):
+    # a backend can request all directories to be pre-created once at backend creation (initialization) time.
+    # for some backends this will optimize the performance of store and move operation, because they won't
+    # have to care for ad-hoc directory creation for every store or move call. of course, create will take
+    # significantly longer, especially if nesting on levels > 1 is used.
+    # otoh, for some backends this might be completely pointless, e.g. if mkdir is a NOP (is ignored).
+    precreate_dirs: bool = False
+
     @abstractmethod
     def create(self):
         """create (initialize) a backend storage"""
diff --git a/src/borgstore/backends/posixfs.py b/src/borgstore/backends/posixfs.py
index 8c5cfa5..ddd85ea 100644
--- a/src/borgstore/backends/posixfs.py
+++ b/src/borgstore/backends/posixfs.py
@@ -35,6 +35,11 @@ def get_file_backend(url):
 
 
 class PosixFS(BackendBase):
+    # PosixFS implementation supports precreate = True as well as = False,
+    # but be careful: if backend creation was with precreate_dirs = False,
+    # backend usage must not be with precreate_dirs = True.
+    precreate_dirs: bool = True
+
     def __init__(self, path, *, do_fsync=False):
         self.base_path = Path(path)
         if not self.base_path.is_absolute():
@@ -124,7 +129,9 @@ def store(self, name, value):
             raise BackendMustBeOpen()
         path = self._validate_join(name)
         tmp_dir = path.parent
-        tmp_dir.mkdir(parents=True, exist_ok=True)
+        if not self.precreate_dirs:
+            # note: tmp_dir already exists, if it was pre-created by Store.create_levels.
+            tmp_dir.mkdir(parents=True, exist_ok=True)
         # write to a differently named temp file in same directory first,
         # so the store never sees partially written data.
         with tempfile.NamedTemporaryFile(suffix=TMP_SUFFIX, dir=tmp_dir, delete=False) as f:
@@ -155,7 +162,9 @@ def move(self, curr_name, new_name):
         curr_path = self._validate_join(curr_name)
         new_path = self._validate_join(new_name)
         try:
-            new_path.parent.mkdir(parents=True, exist_ok=True)
+            if not self.precreate_dirs:
+                # note: new_path.parent dir already exists, if it was pre-created by Store.create_levels.
+                new_path.parent.mkdir(parents=True, exist_ok=True)
             curr_path.replace(new_path)
         except FileNotFoundError:
             raise ObjectNotFound(curr_name) from None
diff --git a/src/borgstore/backends/rclone.py b/src/borgstore/backends/rclone.py
index 3a564fb..9a952a6 100644
--- a/src/borgstore/backends/rclone.py
+++ b/src/borgstore/backends/rclone.py
@@ -65,8 +65,9 @@ class Rclone(BackendBase):
     This uses the rclone rc API to control an rclone rcd process.
     """
 
+    precreate_dirs: bool = False
     HOST = "localhost"
-    TRIES = 3                   # try failed load/store operations this many times
+    TRIES = 3  # try failed load/store operations this many times
 
     def __init__(self, path, *, do_fsync=False):
         if not path.endswith(":") and not path.endswith("/"):
diff --git a/src/borgstore/backends/sftp.py b/src/borgstore/backends/sftp.py
index 4cf580a..2ff4807 100644
--- a/src/borgstore/backends/sftp.py
+++ b/src/borgstore/backends/sftp.py
@@ -35,6 +35,11 @@ def get_sftp_backend(url):
 
 
 class Sftp(BackendBase):
+    # Sftp implementation supports precreate = True as well as = False,
+    # but be careful: if backend creation was with precreate_dirs = False,
+    # backend usage must not be with precreate_dirs = True.
+    precreate_dirs: bool = True
+
     def __init__(self, hostname: str, path: str, port: int = 0, username: Optional[str] = None):
         self.username = username
         self.hostname = hostname
@@ -214,7 +219,9 @@ def store(self, name, value):
             raise BackendMustBeOpen()
         validate_name(name)
         tmp_dir = Path(name).parent
-        self._mkdir(str(tmp_dir), parents=True, exist_ok=True)
+        if not self.precreate_dirs:
+            # note: tmp_dir already exists, if it was pre-created by Store.create_levels.
+            self._mkdir(str(tmp_dir), parents=True, exist_ok=True)
         # write to a differently named temp file in same directory first,
         # so the store never sees partially written data.
         tmp_name = str(tmp_dir / ("".join(random.choices("abcdefghijklmnopqrstuvwxyz", k=8)) + TMP_SUFFIX))
@@ -242,12 +249,14 @@ def move(self, curr_name, new_name):
             raise BackendMustBeOpen()
         validate_name(curr_name)
         validate_name(new_name)
-        try:
-            parent_dir = Path(new_name).parent
-            self._mkdir(str(parent_dir), parents=True, exist_ok=True)
-        except OSError:
-            # exists already?
-            pass
+        if not self.precreate_dirs:
+            # note: the parent dir of new_name already exists, if it was pre-created by Store.create_levels.
+            try:
+                parent_dir = Path(new_name).parent
+                self._mkdir(str(parent_dir), parents=True, exist_ok=True)
+            except OSError:
+                # exists already?
+                pass
         try:
             self.client.posix_rename(curr_name, new_name)
         except FileNotFoundError:
diff --git a/src/borgstore/store.py b/src/borgstore/store.py
index 2406d9c..f988099 100644
--- a/src/borgstore/store.py
+++ b/src/borgstore/store.py
@@ -8,7 +8,7 @@
 - recursive .list method
 - soft deletion
 """
-
+from binascii import hexlify
 from collections import Counter
 from contextlib import contextmanager
 import os
@@ -42,8 +42,6 @@ def get_backend(url):
 class Store:
     def __init__(self, url: Optional[str] = None, backend: Optional[BackendBase] = None, levels: Optional[dict] = None):
         self.url = url
-        levels = levels if levels else {}
-        self.set_levels(levels)
         if backend is None and url is not None:
             backend = get_backend(url)
             if backend is None:
@@ -51,6 +49,7 @@ def __init__(self, url: Optional[str] = None, backend: Optional[BackendBase] = N
         if backend is None:
             raise NoBackendGiven("You need to give a backend instance or a backend url.")
         self.backend = backend
+        self.set_levels(levels)
         self._stats: Counter = Counter()
         # this is to emulate additional latency to what the backend actually offers:
         self.latency = float(os.environ.get("BORGSTORE_LATENCY", "0")) / 1e6  # [us] -> [s]
@@ -60,12 +59,41 @@ def __init__(self, url: Optional[str] = None, backend: Optional[BackendBase] = N
     def __repr__(self):
         return f"<Store(url={self.url!r}, levels={self.levels!r})>"
 
-    def set_levels(self, levels: dict) -> None:
+    def set_levels(self, levels: dict, create: bool = False) -> None:
+        if not levels or not isinstance(levels, dict):
+            raise ValueError("No or invalid levels configuration given.")
         # we accept levels as a dict, but we rather want a list of (namespace, levels) tuples, longest namespace first:
         self.levels = [entry for entry in sorted(levels.items(), key=lambda item: len(item[0]), reverse=True)]
+        if create:
+            self.create_levels()
+
+    def create_levels(self):
+        """creating any needed namespaces / directory in advance"""
+        # doing that saves a lot of ad-hoc mkdir calls, which is especially important
+        # for backends with high latency or other noticeable costs of mkdir.
+        with self:
+            for namespace, levels in self.levels:
+                namespace = namespace.rstrip("/")
+                level = max(levels)
+                if level == 0:
+                    # flat, we just need to create the namespace directory:
+                    self.backend.mkdir(namespace)
+                elif level > 0:
+                    # nested, we only need to create the deepest nesting dir layer,
+                    # any missing parent dirs will be created as needed by backend.mkdir.
+                    limit = 2 ** (level * 8)
+                    for i in range(limit):
+                        dir = hexlify(i.to_bytes(length=level, byteorder="big")).decode("ascii")
+                        name = f"{namespace}/{dir}" if namespace else dir
+                        nested_name = nest(name, level)
+                        self.backend.mkdir(nested_name[: -2 * level - 1])
+                else:
+                    raise ValueError(f"Invalid levels: {namespace}: {levels}")
 
     def create(self) -> None:
         self.backend.create()
+        if self.backend.precreate_dirs:
+            self.create_levels()
 
     def destroy(self) -> None:
         self.backend.destroy()
@@ -139,7 +167,8 @@ def _get_levels(self, name):
         for namespace, levels in self.levels:
             if name.startswith(namespace):
                 return levels
-        return [0]  # "no nesting" is the default, if no namespace matched
+        # Store.create_levels requires all namespaces to be configured in self.levels.
+        raise KeyError(f"no matching namespace found for: {name}")
 
     def find(self, name: str, *, deleted=False) -> str:
         """


Test patch:
diff --git a/tests/test_backends.py b/tests/test_backends.py
index 99b8bd3..0cf1ebc 100644
--- a/tests/test_backends.py
+++ b/tests/test_backends.py
@@ -25,7 +25,9 @@
 
 
 def get_posixfs_test_backend(tmp_path):
-    return PosixFS(tmp_path / "store")
+    be = PosixFS(tmp_path / "store")
+    be.precreate_dirs = False  # True (default) makes tests super slow.
+    return be
 
 
 @pytest.fixture()
@@ -43,7 +45,10 @@ def get_sftp_test_backend():
     # needs an authorized key loaded into the ssh agent. pytest works, tox doesn't.
     url = os.environ.get("BORGSTORE_TEST_SFTP_URL")
     if url:
-        return get_sftp_backend(url)
+        be = get_sftp_backend(url)
+        if be is not None:
+            be.precreate_dirs = False  # True (default) makes tests super slow.
+        return be
 
 
 def check_sftp_available():
diff --git a/tests/test_store.py b/tests/test_store.py
index 611d765..76cdcfb 100644
--- a/tests/test_store.py
+++ b/tests/test_store.py
@@ -124,7 +124,7 @@ def test_upgrade_levels(posixfs_store_created):
     ii1 = ItemInfo(k1, True, len(v0), False)
 
     # start using the backend storage with nesting level 0:
-    posixfs_store_created.set_levels({ROOTNS: [0]})
+    posixfs_store_created.set_levels({ROOTNS: [0]}, create=True)
     with posixfs_store_created as store:
         # store k0 on level 0:
         store.store(k0, v0)
@@ -133,7 +133,7 @@ def test_upgrade_levels(posixfs_store_created):
         assert list_store_names(store, ROOTNS) == [k0]
 
     # now upgrade to nesting level 1 (while keeping support for level 0), using the same backend storage:
-    posixfs_store_created.set_levels({ROOTNS: [0, 1]})
+    posixfs_store_created.set_levels({ROOTNS: [0, 1]}, create=True)
     with posixfs_store_created as store:
         # does k0 still work?
         assert store.find(k0) == "" + k0  # found on level 0
@@ -164,7 +164,7 @@ def test_downgrade_levels(posixfs_store_created):
     ii1 = ItemInfo(k1, True, len(v0), False)
 
     # start using the backend storage with nesting level 1:
-    posixfs_store_created.set_levels({ROOTNS: [1]})
+    posixfs_store_created.set_levels({ROOTNS: [1]}, create=True)
     with posixfs_store_created as store:
         # store k1 on level 1:
         store.store(k1, v1)
@@ -173,7 +173,7 @@ def test_downgrade_levels(posixfs_store_created):
         assert list_store_names(store, ROOTNS) == [k1]
 
     # now downgrade to nesting level 0 (while keeping support for level 1), using the same backend storage:
-    posixfs_store_created.set_levels({ROOTNS: [1, 0]})
+    posixfs_store_created.set_levels({ROOTNS: [1, 0]}, create=True)
     with posixfs_store_created as store:
         # does k1 still work?
         assert store.find(k1) == "00/" + k1  # found on level 1
@@ -218,11 +218,11 @@ def test_move_delete_undelete(posixfs_store_created):
 
 def test_move_change_level(posixfs_store_created):
     k0, v0 = key(0), b"value0"
-    posixfs_store_created.set_levels({ROOTNS: [0]})
+    posixfs_store_created.set_levels({ROOTNS: [0]}, create=True)
     with posixfs_store_created as store:
         store.store(k0, v0)  # store on level 0
         assert store.find(k0) == "" + k0  # now on level 0
-    posixfs_store_created.set_levels({ROOTNS: [0, 1]})
+    posixfs_store_created.set_levels({ROOTNS: [0, 1]}, create=True)
     with posixfs_store_created as store:
         store.move(k0, change_level=True)
         assert store.find(k0) == "00/" + k0  # now on level 1