> wait until all its key-value pairs have timed out and then just shut it down

you can do it that way but it often winds up making the server's shutdown dependent on a client behavior. For example, the liveness of a key is determined by the client in most applications, not the server. Any sort of naive TTL system where a read on a key extends its lifetime means that the server cannot shut down without permission from the clients, because the client can just keep reading the same key over and over, extending its lifetime until the client shuts down. I have a system that works this way now, I'm working on removing that behavior. When I want to take a server offline, I have no idea if it will take ten minutes or four hours to drain. It's very annoying.

> have each client send everything to both of the session state servers

generally a client would write to just one server (server A), and that server would write to the other server (server B). If server A applies the change locally and then confirms it with the client, then syncs the change to server B independently of the client request, that's asynchronous replication. If server A waits until server B has applied the change locally before confirming the write with the client, that's synchronous replication. If the client can only send writes to one of the servers, but can send reads to either server, that's master-replica replication. The easiest thing to reason about is synchronous master-replica systems: client sends a request to A, A applies it to A's storage, A sends it to B, B applies it to B's storage, B confirms it with A, A confirms it with the client. If a client can send a write to either server, that's master-master replication. Master-master replication is harder to implement; what if two different clients write the same key on two different servers at the same time? A conflict arises.

Concurrency issues are unavoidable in web systems. Uncoordinated users are using the system simultaneously; "everybody wait in line" is not a realistic option in practice.

> What do people do about that, say, at high end sites?

that varies pretty widely. Depends a lot on what you're building, how much money you have, how much time you have, how many users you have, how many engineers you have, how easy it is for you to hire, what skills your current engineering team has, what clients will be accessing the data, etc. The permutations of concerns are innumerable. Lots of people buy hosted redis from redislabs.com or AWS Elasticache because they are either unwilling or unable to run a redis server themselves. That's a great solution for most people most of the time; it works great for a lot of use cases, it's relatively inexpensive, and the providers give you useful tools that you would otherwise have to build yourself.

> Maybe I should think about implementing more.

Are you selling a key-value store? What is your startup?

Maybe you should think about implementing less, and focusing on building the things that actually matter to users. Key-value stores are nice engineering problems, but they're implementation details: users don't know about and don't care about their existence, and their existence does not drive revenue. And that's why most people just buy hosted redis, download a redis client library, and call it a day. It's not technically the best solution, but it's often times the most economical solution.