Skip to content

Reuse RID of deleted records #1391

Description

@lvca

Discussed in #1203

Originally posted by lvca August 12, 2023
ArcadeDB does not reuse the assigned RIDs. Never. Even when the record is deleted. This has the advantage of determining if a link is broken (the RID points to a non-existent record), useful in case of unidirectional edges.

In other cases reusing the RIDs allows reusing all the space in pages. In some use cases that are heavily based on deletes, this feature can save a lot of space and improve overall performance.

I'd like to make this configurable, so the user can decide per bucket/type if the RIDs are reusable.

Phase 1 (scheduled for 24.1.1):

  • After a record delete, the page should be compressed by shifting the records to the left making space for new records
  • Delete records should have pointers = 0 and not valid pointers with zero length buffers. This would save precious bytes and would make the page 100% reusable
  • Update the total record in the page counter when the last record is deleted: cycle left the pointers while the pointers are 0. Then update the total records on the page
  • Consider calling compressPage() at commit time only if a page has been updated or deleted (insert does not create holes)
  • More random stress tests with heavy multi-threads load to check for bugs on reclaimed space (Unknown issue with using unique index + loading multi-page records under heavy load #1402)

Phase 2 (it will be separated into a new issue):

  • When an insert/update needs a new page, scan the previous pages to find a hole to reuse. This allows to execute this scan only at new pages, so in the best case 1 time every 2048 inserted records
  • Consider saving holes on a different structure to be quickly reused without a scan
  • To properly recover the space occupied by shrunk multi-page records (a record spans over multiple pages and then shrinks in size)
  • Deleted empty segments in edge linked list

Metadata

Metadata

Assignees

Labels

enhancementNew feature or request

Fields

No fields configured for Feature.

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions