orientechnologies / orientechnologies/orientdb

Increase speed of incremental backup by using counting bloom filter

Open
#5,149 9 comments 0 reactions 1 assignee View on GitHub

@andrii0lomakin is already working on this.

Since Nov 6, 2015.

enhancement
Dominant language
Java
Stars
5k
Forks
868
Avg merge
15h 6m
Merged PRs (30d)
18

Description

In current implementation of incremental backup we iterate over pages to find which of them were changed, but for huge databases such process may take several hours. It is not really a problem for many cases because we do not block database on writes but sometimes backup should be done in very stiff terms. To avoid given problem we are going to introduce counting bloom filter. Just to clarify.
By counting bloom filter I do not mean classic implementation of given data structure which can not be expanded in case of it reaches it's limit of capacity of registered items, but I mean family of modern algorithms with similar behaviour which allows to dynamically expand capacity of "bloom filter".

In nutshell algorithm is following:

  1. For each file we get amount of pages it contains.
  2. We do not load any page instead we merely filter indexes of pages through "bloom filter" which is matter of few binary operations for iteration.
  3. Fetch changed pages and backup them.
  4. During small "freeze" phase when we wait till ongoing atomic operations will be completed to copy database journal with changes happens to the data during backup phase we clear "bloom filter".

Actually that is almost speed limit for incremental backup because in 95% of cases we will load pages which are changed and that is action which we have to do any way.

Also as drawback part of database journal which have to be "cut" and backed up will be really small because of small period of time is needed to perform backup.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.