A method is provided for space-efficient bookkeeping using bit-level locking. Each row of a bookkeeping table stores binary data comprising a plurality of bits. Each bit of the plurality of bits corresponds to a particular message and a particular consumer of the message, and indicates whether the particular message has been dequeued by the particular consumer. The bookkeeping table is stored on-disk and data corresponding to the bookkeeping table is stored in volatile memory. When a message is dequeued the in-memory bookkeeping data is updated, and the bookkeeping table is updated based on the in-memory bookkeeping data when the dequeue is committed.