Constant time updates after memory deduplication
Systems and methods are described for resource-efficient memory deduplication and write-protection. In an example, a method includes receiving, by a computing device having a processor, a request to assess deduplication for a plurality of candidate files. The computing device may perform one or more iterative steps for deduplication. The iterative steps may include: receiving, from the plurality of candidate files, a candidate file that is not write-protected; determining, based on a predetermined Bernoulli distribution, a decision to write-protect the candidate file; rendering the candidate file as a write-protected candidate file; determining, based on a review of other candidate files from the plurality of candidate files, that the write-protected candidate file can be deduplicated; and deduplicating the write-protected candidate file.
1. A method comprising:
receiving, by a computing device having a processor, a request to assess deduplication for a plurality of candidate files;
performing one or more iterations of:
receiving, from the plurality of candidate files, a candidate file that is not write-protected;
determining, based on a predetermined Bernoulli distribution, a decision to write-protect the candidate file;
rendering the candidate file as a write-protected candidate file;
determining, based on a review of other candidate files from the plurality of candidate files, that the write-protected candidate file can be deduplicated; and
deduplicating the write-protected candidate file.
2. The method of claim 1 , wherein the Bernoulli distribution is based on a probability generated by a random number generation (RAN) function.
3. The method of claim 1 , wherein the Bernoulli distribution is based on a network bandwidth of the computing device.
4. The method of claim 1 , wherein the rendering the candidate file as the write-protected candidate file comprises:
saving a copy of the candidate file;
identifying, based on a comparison with the copy, a change to the candidate file; and
reversing the change to the candidate file to cause the candidate file to satisfy a similarity threshold with the copy.
5. The method of claim 1 , wherein the deduplicating the write-protected candidate file comprises:
searching, within a memory associated with the computing device, a duplicate file comprising at least a predetermined threshold of data found in the candidate file; and
deleting the duplicate file.
6. The method of claim 1 , wherein the deduplicating the write-protected candidate file comprises:
identifying, for the candidate file, a first location in a memory associated with the computing device, wherein the candidate file is stored in the first location;
searching, within the memory, a duplicate file comprising at least a predetermined threshold of data found in the candidate file; and
identifying, for the duplicate file, a second location in the memory, wherein the duplicate file is stored in the second location.
7. The method of claim 6 , further comprising:
deleting contents of the duplicate file from the second location; and
storing, at the second location, a pointer to the first location.
8. The method of claim 6 , further comprising:
deleting contents of the candidate file from the first location; and
storing, at the first location, a pointer to the second location.
9. The method of claim 1 , further comprising, prior to receiving the candidate file that is not write-protected,
identifying a candidate file as not yet write-protected.
10. The method of claim 9 , wherein the identifying the candidate file as not yet write-protected comprises:
detecting that the candidate file has been modified within a threshold number of passes.
11. A system comprising:
a processor; and
memory storing instructions that, when executed by the processor, cause the processor to:
receive a plurality of candidate files to assess for write-protection and deduplication;
perform one or more iterations of:
determining whether a given candidate file of the plurality of candidate files is write-protected;
after determining that the given candidate file is not write-protected, determining, based on a predetermined Bernoulli distribution, whether to write-protect the given candidate file;
rendering, based on the Bernoulli distribution, the given candidate file as a write-protected candidate file;
determining, based on a review of other candidate files from the plurality of candidate files, that the write-protected candidate file can be deduplicated; and
deduplicating the write-protected candidate file.
12. The system of claim 11 , wherein the Bernoulli distribution is based on a probability generated by a random number generation (RAN) function.
13. The system of claim 11 , wherein the Bernoulli distribution is based on a network bandwidth of the computing device.
14. The system of claim 11 , wherein the instructions, when executed, cause the processor to deduplicate the write-protected candidate file by:
searching, within a memory associated with the computing device, a duplicate file comprising at least a predetermined threshold of data found in the given candidate file; and
deleting the duplicate file.
15. The system of claim 11 , wherein the instructions, when executed, cause the processor to:
identify a second candidate file of the plurality of candidate files as write-protected;
determine, based on a review of other candidate files, that the second candidate file can be deduplicated; and
deduplicate the second candidate file.
16. A method comprising:
receiving, by a computing device having a processor, a plurality of candidate files to assess for write-protection and deduplication;
generating, based on a review of other candidate files, a first list of candidate files that can be deduplicated, and a second list of candidate files that cannot be deduplicated;
for each of a plurality of candidate files in the first list,
determining, based on a predetermined first Bernoulli distribution, a first decision to either assess or deny permission to assess the candidate file in the first list for write-protection;
identifying, based on a permission to assess, the candidate file in the first list as a write-protected candidate file; and
deduplicate the write-protected candidate file; and
for each of a plurality of candidate files in the second list,
determining, based on a predetermined first Bernoulli distribution, a second decision to either assess or deny permission to assess the candidate file in the second list for write-protection; and
if a given candidate file in the second list is not write-protected, rendering, based on the second decision, the candidate file as a write-protected candidate file.
17. The method of claim 16 , further comprising, prior to the identifying the candidate file in the first list as a write-protected candidate file:
identifying the candidate file in the first list as not write-protected; and
rendering, based on the first decision, the candidate file as a write-protected candidate file.
18. The method of claim 17 , wherein the identifying the candidate file in the first list as not yet write-protected comprises:
detecting that the candidate file has been modified within a threshold number of passes.
19. The method of claim 16 , wherein the first Bernoulli distribution is greater than the second Bernoulli distribution, such that a greater proportion of candidate files in the first list to be assessed for write-protection than candidate files in the second list to be assessed for write-protection.
20. The method of claim 16 , wherein the first Bernoulli distribution is based on a first probability generated by a random number generation (RAN) function, wherein the second Bernoulli distribution is based on a second probability generated by the random number generation (RAN) function, wherein the first probability is greater than the second probability.