Granted Patent B2

US 12,293,076 · App. 17/871,972 · Granted May 6, 2025

Inventors: Luke A. Higgins (Silver Spring, MD); Robert R. Bruno (Columbia, MD)

Assignee: MORGAN STANLEY SERVICES GROUP INC.

G06F3/0608G06F3/0641G06F3/0673G06F12/084G06F2212/62

Abstract

Claims (57)

1. A system for caching and deduplicating a plurality of segments of data, comprising:

at least one server having one or more processors;

at least one database; and

non-transitory memory comprising instructions that, when executed by the one or more processors, cause the one or more processors to:

receive, at the server, a first segment of data from the plurality of segments of data;

identify a value of a first data field in the first segment of data, the value of the first data field comprising a unique source identifier;

perform a transformation on the value of the first data field to obtain a transformed source identifier;

identify a value of a second data field in the first segment of data, the second data field being densely populated by values in the plurality of received segments of data;

partition the value of the second data field into a first partition comprising more significant bits and a second partition comprising less significant bits;

generate a first key based on the transformed source identifier and the first partition comprising more significant bits;

store, in the at least one database, an entry associating the first key with a bitmap, the bitmap having a maximum length equal to a maximum number of possible values a bitmap of equal length to the second partition could validly take;

set a single bit of the bitmap, corresponding to a value of the second partition, to true;

receive, at the server, a second segment of data from the plurality of segments of data;

likewise generate a second key based on a transformed source identifier in the second segment of data and a value of a first partition of the second data field in the second segment of data;

retrieve a bitmap associated with the second key; and

based on a set bit in the retrieved bitmap corresponding to a value of the second partition of the second data field of the second segment of data, determine that the second segment of data had previously been received by the server.

2. The system of claim 1 , wherein the non-transitory memory comprises instructions that, when executed by the one or more processors, further cause the one or more processors to:

receive, at the server, a third segment of data from the plurality of segments of data;

generate a third key;

retrieve a bitmap associated with the third key; and

based on an unset bit in the retrieved bitmap corresponding to a value of the second partition of the second data field of the third segment of data, determine that the third segment of data had not previously been received by the server.

3. The system of claim 1 , wherein the non-transitory memory comprises instructions that, when executed by the one or more processors, further cause the one or more processors to:

identify a portion of entries stored in the at least one database having an age greater than a predetermined threshold; and

drop the identified portion of entries from the at least one database.

4. The system of claim 3 , wherein the portion of entries is identified based on at least a portion of a timestamp included in the key of each entry in the portion of entries.

5. The system of claim 1 , wherein the second data field comprises values generated by an incrementing counter.

6. The system of claim 1 , wherein the first and second keys further comprise at least a portion of a timestamp.

7. The system of claim 1 , wherein the first and second keys comprise a concatenation of strings, the strings comprising at least transformed source identifier and the first partition of the second data field.

8. The system of claim 7 , wherein the strings further comprise at least a portion of a timestamp.

9. The system of claim 1 , wherein the bitmap has an adaptive length depending on values previously encountered for the second partition.

10. A computer-implemented method for caching and deduplicating a plurality of segments of data, comprising:

receiving a first segment of data from the plurality of segments of data;

identifying a value of a first data field in the first segment of data, the value of the first data field comprising a unique source identifier;

performing a transformation on the value of the first data field to obtain a transformed source identifier;

identifying a value of a second data field in the first segment of data, the second data field being densely populated by values in the plurality of received segments of data;

partitioning the value of the second data field into a first partition comprising more significant bits and a second partition comprising less significant bits;

generating a first key based on the transformed source identifier and the first partition comprising more significant bits;

storing, in a database, an entry associating the first key with a bitmap, the bitmap having a maximum length equal to a maximum number of possible values a bitmap of equal length to the second partition could validly take;

setting a single bit of the bitmap, corresponding to a value of the second partition, to true;

receiving a second segment of data from the plurality of segments of data;

likewise generating a second key based on a transformed source identifier from the first data field in the second segment of data and a value of a first partition of the second data field in the second segment of data;

retrieving a bitmap associated with the second key; and

based on a set bit in the retrieved bitmap corresponding to a value of the second partition of the second data field of the second segment of data, determining that the second segment of data had previously been received.

11. The method of claim 10 , wherein the non-transitory memory comprises instructions that, when executed by the one or more processors, further cause the one or more processors to:

receive, at the server, a third segment of data from the plurality of segments of data;

generate a third key;

retrieve a bitmap associated with the third key; and

based on an unset bit in the retrieved bitmap corresponding to a value of the second partition of the second data field of the third segment of data, determine that the third segment of data had not previously been received by the server.

12. The method of claim 10 , wherein the non-transitory memory comprises instructions that, when executed by the one or more processors, further cause the one or more processors to:

identify a portion of entries stored in the at least one database having an age greater than a predetermined threshold; and

drop the identified portion of entries from the at least one database.

13. The method of claim 12 , wherein the portion of entries is identified based on at least a portion of a timestamp included in the key of each entry in the portion of entries.

14. The method of claim 10 , wherein the second data field comprises values generated by an incrementing counter.

15. The method of claim 10 , wherein the first and second keys further comprise at least a portion of a timestamp.

16. The method of claim 10 , wherein the first and second keys comprise a concatenation of strings, the strings comprising at least a transformed source identifier and a first partition of the second data field.

17. The method of claim 16 , wherein the strings further comprise at least a portion of a timestamp.

18. The method of claim 10 , wherein the bitmap has an adaptive length depending on values previously encountered for the second partition.

Assignments (1)

Continuity (2)

References Cited (34)