A stateless service keeps request state outside the instance (e.g., in a DB/Redis), so any instance can handle any request. A stateful service keeps state in memory on a specific instance, which makes scaling and failover harder (you need sticky sessions or state replication).