Про раскидывание по директориям — само собой. Мне хватало одного уровня вложенности, ключ кеша строился как md5(от чего-то), и в итоге в директории с кешем было 16 каталогов по последним буквам имен файлов 0-9a-f. Когда дело пойдет на миллионы — стоит вложенность увеличить до двух.