- Your web front-ends should not store data: they should be trivial to scale.
- Use a data store made to scale horizontally (otherwise, learn about sharding)
- Take advantage of the fact that "microservices" already distribute load
Firstly: Your web front-ends shouldn't really be stateful. They shouldn't store anything you can't afford to lose at any given moment. All the data should live in a dedicated database cluster. You should be able to trash a web front end or add a new one without breaking anyone's sessions or data. Scaling that should be "trivial."
That said, scaling a service's database horizontally requires some sort of sharding. But, if you opt for a document-type store, horizontal scaling through sharding is usually a baked in feature that you just have to configure. (Or, it's a detail you can completely ignore if you're using a scalable database hosting service, like DynamoDB.)
Basically, sharding requires that you identify a field used to determine how data is split across nodes. That might be a
user_id, which gets translated into a number. Which database node a particular user record is stored might depend on that ID and a hashing algorithm, for example.
A really basic example might be a modulus of some random, integer-ish user ID. You take
user_id % number_of_servers to determine where to store/retrieve the record.
With a nosql database, a lot of the details about how this happens taken care of for you -- you just hit the cluster, and it figures out what to do.
There can certainly be more sophisticated strategies, if you need ACID-like compliance.
That said, one of the benefits of a micro-service is the deferment of this scalability problem. I.e., because your user database is distinct from your product catalog and orders databases and so forth, each of these databases can already be located on different hosts: The traffic is already somewhat distributed.
Unless you're running a truly massive and unprofitable service, you can probably defer the remaining scalability work until you have the budget to address them!