Record deletes only remove the in-memory index entry which allows the defrag process to reclaim the disk space for future writes. When restarting Aerospike, deletes that haven’t been overwritten can return. This and potential workarounds have been discussed in much more detail here: Expired/Deleted data reappears after server is restarted - #27 by maxim_ky.