Stateless services don't store data between requests. Any instance can handle any request. Scaling is easy: add more instances.
Stateful services remember data between requests. Specific instances handle specific users/data. Scaling requires careful coordination.
Examples:
- Stateless: Web servers, API gateways, compute workers
- Stateful: Databases, caches, WebSocket servers
The pattern: Keep your application tier stateless. Push state to dedicated stateful services (database, Redis). Then scale the stateless tier horizontally without coordination.