Design a snapshotable key-value store

Design and implement a snapshotable key–value map supporting the following APIs:

• S(key, value): set the current value of a string key to a string value.
• G(key): get the current value for key (or null if absent).
• Snapshot(): capture the current state and return a snapshotId (opaque string).
• GS(snapshotId, key): get the value of key as of the given snapshot. Requirements:
• Support arbitrarily many snapshots; later writes must not affect earlier snapshots.
• Be space‑efficient across snapshots (avoid full copies; consider copy‑on‑write or per‑key versioned logs).
• Target time complexity around O(log u) per operation where u is updates per key (justify alternatives).
• Define behavior for overwrites, deletions, unknown keys, and consecutive snapshots without intervening writes.
• Specify snapshotId generation and ordering guarantees.
• Discuss how to extend to concurrency (reads during writes) and persistence/durability (optional). Example scenario to satisfy: S("a", "a-foo"); S("b", "b-foo"); id = Snapshot(); S("a", "a-foo-prime"); G("a") -> "a-foo-prime" GS(id, "a") -> "a-foo" G("b") -> "b-foo" GS(id, "b") -> "b-foo".