Most of the algorithms on Apache Mahout scale way beyond 20M records, even with high-dimensional data. If you only need to build a prediction model, there are specific tools like Vowpal Wabbit (http://hunch.net/~vw/) that can easily scale to billions of records on a single machine.