# US 11,442,911 B2 · Moving window data deduplication in distributed storage > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,911 B2 - Document ID: US11442911B2 - Status: Granted - Kind: B2 - Application number: 17/007,495 - Filed: 2020-08-31 - Published: 2022-03-03 - Granted: 2022-09-13 - Earliest claimed: 2020-08-31 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Pavlo Padinker; Pavan Edara; Bigang Li - Web page: https://patentgrep.com/patent/US11442911B2 ## CPC - G06F 3/0641: {De-duplication techniques} - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/0671: {In-line storage system} - G06F 12/0804: with main memory updating (G06F12/0806 takes precedence) - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/2322: {using timestamps} - G06F 16/235: {Update request formulation} - G06F 3/0608: {Saving storage space on storage systems} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The present disclosure describes a service which provides primary in-line deduplication. A streaming application program interface (API) may allow for streaming records into a storage system with high throughput and low latency. As part of this process, the API allows user to add identifiers as a field used for data deduplication. The deduplication service keeps a moving window of the identifiers in memory and does in-line deduplication by quickly determining whether data is a duplicate. Keeping only deduplication keys in memory reduces the cost of running the service. Moreover, the real-time nature of the moving window approach allows for storing deduplication information alongside the data and accessing it immediately on read. In this regard, read after write consistency is supported, and costs are reduced. ## Claims ### Claim 1 A method for deduplication, comprising: receiving, with one or more processors, a request to write data to a table, the request including an insert identifier uniquely identifying the data; processing, with the one or more processors, the insert identifier for the request by comparing the received insert identifier with other insert identifiers that have been stored in the table within a time window of predetermined duration moving relative to a current time; determining, with the one or more processors, whether the write data corresponding to the insert identifier is duplicate data; storing, with the one or more processors, the insert identifier in the table and adding the write data to the table when the data is not duplicate; flagging the duplicate data by maintaining an identifier indicating that the data is a duplicate when the data is a duplicate; and updating the table to remove insert identifiers added before the time window of predetermined duration based on a timestamp associated with each insert identifier. ### Claim 2 (depends on 1) The method of claim 1, wherein: updating the table to remove insert identifiers comprises removing insert identifiers associated with timestamps that no longer fall within the time window of predetermined duration. ### Claim 3 (depends on 1) The method of claim 1, wherein flagging the duplicate data comprises marking the duplicate data in the table. ### Claim 4 (depends on 1) The method of claim 1, wherein flagging the duplicate data comprises storing an indication of the duplicate data in a component used to read the data from the table. ### Claim 5 (depends on 1) The method of claim 1, further comprising not writing the data in the request to the table when the data is determined to be duplicate. ### Claim 6 (depends on 1) The method of claim 1, wherein determining whether table data corresponding to the insert identifier is duplicate comprises determining whether the received insert identifier is already stored in memory. ### Claim 7 A system for deduplication, comprising: memory storing one or more insert identifiers, each insert identifier being attached to data written to a table within a time window of predetermined duration moving relative to a current time; one or more processors in communication with the memory and the table, the one or more processors configured to: receive a request to write data to a table, the request including an insert identifier uniquely identifying the data; process the received insert identifier for the request by comparing the received insert identifier with other insert identifiers that have been stored in the table within the time window of predetermined duration; determine whether the write data corresponding to the received insert identifier is duplicate data; store the received insert identifier in the table and add the write data to the table when the data is not duplicate; flag the duplicate data by maintaining an identifier indicating that the data is a duplicate when the data is a duplicate; and update the table to remove insert identifiers added before the time window of predetermined duration based on a timestamp associated with each insert identifier. ### Claim 8 (depends on 7) The system of claim 7, wherein: updating the table to remove insert identifiers comprises removing insert identifiers associated with timestamps that no longer fall within the time window of predetermined duration. ### Claim 9 (depends on 7) The system of claim 7, wherein flagging the duplicate data comprises marking the duplicate data in the table. ### Claim 10 (depends on 7) The system of claim 7, wherein flagging the duplicate data comprises storing an indication of the duplicate data in a component used to read the data from the table. ### Claim 11 (depends on 7) The system of claim 7, wherein the one or more processors are further configured to not write the data in the request to the table when the data is determined to be duplicate. ### Claim 12 (depends on 7) The system of claim 7, wherein determining whether table data corresponding to the insert identifier is duplicate comprises determining whether the received insert identifier is already stored in memory. ### Claim 13 A non-transitory computer-readable medium storing instructions executable by one or more processors for performing a method of deduplication, the method comprising: receiving a request to write data to a table, the request including an insert identifier uniquely identifying the data; processing the received insert identifier for the request by comparing the received insert identifier with other insert identifiers that have been stored in the table within the time window of predetermined duration moving relative to the current time; determining whether the write data corresponding to the received insert identifier is duplicate data; storing the received insert identifier in the table and adding the write data to the table when the data is not duplicate; flagging the duplicate data by maintaining an identifier indicating that the data is a duplicate when the data is a duplicate; and updating the table to remove insert identifiers added before the time window of predetermined duration based on a timestamp associated with each insert identifier. ### Claim 14 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein: updating the table to remove insert identifiers comprises removing insert identifiers associated with timestamps that no longer fall within the time window of predetermined duration. ### Claim 15 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein flagging the duplicate data comprises marking the duplicate data in the table or storing an indication of the duplicate data in a component used to read the data from the table. ### Claim 16 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein determining whether table data corresponding to the insert identifier is duplicate comprises determining whether the received insert identifier is already stored in memory.