一种数据存储设备包括非易失性存储器，所述非易失性存储器包含多个块，每一个块被配置为在预定物理位置处存储多个物理页。控制器对存储在多个逻辑页中的数据进行编程和读取。易失性存储器包括逻辑到物理地址转换映射，所述映射被配置为使得能够确定存储在每一个逻辑页中的数据在一个或多个物理页中的物理位置。可以存储多个日志，每一个日志包括将一个或多个物理页与每一个逻辑页相关联的多个条目。在启动时，所述控制器可以有序读取所述多个日志中的至少一些，并且重建该映射；表明在重建映射后服务数据访问命令的预备状态；根据映射来重建表，并且基于其，在已经表明了处理所述命令的预备状态后选择块以用于垃圾收集。