orientechnologies / orientechnologies/orientdb
Increase speed of incremental backup by using counting bloom filter
@andrii0lomakin is already working on this.
Since Nov 6, 2015.
- 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:
- For each file we get amount of pages it contains.
- 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.
- Fetch changed pages and backup them.
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.