route53-infima

Yes! we do recursive, nested, shuffle sharding in these cases. Our Open Source infima library doesn't quite include direct support for this, but you can get a sense of how we put it all together: https://github.com/awslabs/route53-infima

Clickable: https://github.com/awslabs/route53-infima#shuffleshard http://git.io/332VLA

People often think that the N-queens problem is just an abstract exercise, good sample work that stretches the mind. But when we were building Route 53, we actually use the N-queens problem, it's part of how we assign Shuffle Shards; https://github.com/awslabs/route53-infima#shuffleshard The solution we included in Infima is a recursive search with backtracking because of some other needs; http://git.io/332VLA but it's the N-queens problem, in a real practical setting.

Full-disclosure: I'm an engineer at Amazon Web Services. "Mr. Hamilton later said privately that Amazon had developed original statistical methods to limit damage from catastrophic failures." I don't think it's what James is referring to (as it's just the tip of the iceberg), but at Re:Invent we also released Infima - a library for service-level fault isolation and fault tolerance using Route 53 for endpoint discovery; https://github.com/awslabs/route53-infima The techniques in Infima give some insight into how we think about multi-tenancy and availability, as well as provide a framework for building other services on top of EC2, Route 53 and so on.