We show that any N-point negative-type metric space admits a bi-Lipschitz embedding into Euclidean space with distortion O(sqrt(log N)), which is sharp up to constant factors. The proof relies on a refined Arora-Rao-Vazirani chaining argument and a novel metric compression scheme, with new implications for concentration of measure and the Sparsest Cut problem. Joint work with Assaf Naor and Alan Chang.