  We give a Markov chain based algorithm for sampling almost uniform solutions
of constraint satisfaction problems (CSPs). Assuming a canonical setting for
the Lov\'asz local lemma, where each constraint is violated by a small number
of forbidden local configurations, our sampling algorithm is accurate in a
local lemma regime, and the running time is a fixed polynomial whose dependency
on $n$ is close to linear, where $n$ is the number of variables. Our main
approach is a new technique called state compression, which generalizes the
"mark/unmark" paradigm of Moitra (Moitra, JACM, 2019), and can give fast
local-lemma-based sampling algorithms. As concrete applications of our
technique, we give the current best almost-uniform samplers for hypergraph
colorings and for CNF solutions.
