How does Redis handle multiple threads (from different clients) updating the same data structure in Redis?

Redis is actually single-threaded, which is how every command is guaranteed to be atomic. While one command is executing, no other command will run.

A single-threaded program can definitely provide concurrency at the I/O level by using an I/O (de)multiplexing mechanism and an event loop (which is what Redis does). The fact that Redis operations are atomic is simply a consequence of the single-threaded event loop. The interesting point is atomicity is provided at no extra cost (it does not require synchronization between threads).