1. A method comprising: under control of one or more configured computing systems of a content delivery network (CDN) service, obtaining a Domain Name System (DNS) query from a client computing device at a first DNS server, wherein the DNS query corresponds to a requested resource and wherein the first DNS server corresponds to the CDN service; associating the client computing device with a cluster of other client computing devices; determining routing information for the associated cluster of the client computing device; and selecting a cache component of the CDN service for providing the requested resource based on the determined routing information, wherein the determined routing information includes a frequency defined by probabilities of selection for each cache component identified in the determined routing information for the associated cluster.