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".