Despite interest in structured peer-to-peer overlays and their scalability to millions of nodes, few, if any, overlays operate at that scale. This paper considers the distributed hash table extensions supported by modern BitTorrent clients, which implement a Kademlia-style structured overlay network among millions of BitTorrent users. As there are two disjoint Kademlia-based DHTs in use, we collected two weeks of traces from each DHT. We examine churn, reachability, latency, and liveness of nodes in these overlays, and identify a variety of problems, such as median lookup times of over a minute. We show that Kademlia’s choice of iterative routing and its lack of a preferential refresh of its local neighborhood cause correctness problems and poor performance. We also identify implementation bugs, design issues, and security concerns that limit the effectiveness of these DHTs and we offer possible solutions for their improvement.