For a large array of Constraint Satisfaction Problems the following phenomenon has been observed: all known polynomial-time algorithms stop finding solutions of random instances at constraint densities much smaller than those for which solutions provably exist. We study this phenomenon by examining how the set of solutions of different problems evolve as constraints are added. We prove in a precise mathematical sense that, in each case, the barrier faced by algorithms corresponds to a phase transition in solution-space geometry. Roughly speaking, at some problem-specific, critical density, the set of solutions shatters going from a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms appear to stop exactly as soon as the shattering occurs. Besides giving a geometric view of the solution space of random CSPs our results provide novel constructions of one-way functions. Joint work with Amin Coja-Oghlan.