Thread-safe key-value store with atomic batch writes

Design and implement an in-memory string key-value store used by many threads at once, with get, put, delete and write_batch. A batch is an ordered list of puts and deletes (the same key may appear twice; apply them in order). Validate the whole batch first and reject it if it is empty or holds an invalid key. A valid batch must be atomic: no reader or writer ever sees only part of it. Explain your locking scheme, how you avoid deadlocks, how reads stay fast, and how you would test the concurrency.