Design time-versioned KV without timestamp argument

Design a time-versioned key-value store that does not accept a timestamp argument on writes. Support set(key, value) which stores the value with an internally assigned, monotonically increasing timestamp, getLatest(key) which returns the most recent value, and getAtOrBefore(key, wallTime) which returns the value that was current at or before the given wall-clock time. Describe your data structures, how you ensure monotonicity despite clock issues, and the time/space complexity of operations.