Data storage system conflict management

Abstract

Data storage system conflict management techniques are described. In one example, data is sent by client devices to both a repository system and a search index system of a data storage system. Each of the client devices maintains, locally, records of changes to data of the repository system, e.g., through use of an invertible Bloom lookup table. The records are used as a basis by the client devices to send reports to an arbiter system and used to detect conflicts When detected, a conflict request is communicated to client devices involved in the conflict as well as to the repository system and responses used to generate a correction that is communicated to update the repository system and search index system.

What is claimed is: 
     
       1. A method comprising:
 communicating, by a client device, a report to an arbiter system describing records of changes to data of a repository system that is searchable using a search index of a search index system, the records maintained locally by the client device; 
 receiving, by the client device, a conflict request from the arbiter system responsive to the communicating of the report, the conflict request generated to request response data to resolve a conflict detected between the data of the repository system and the search index based on comparing the records of changes to data of the repository system described in the report and at least one other report communicated to the arbiter system; 
 communicating, by the client device, the response data to the arbiter system responsive to the receiving of the conflict request; 
 receiving, by the client device, a correction from the arbiter system, the correction generated based on the response data communicated by the client device and response data communicated to the arbiter system by the repository system; and 
 resolving, by the client device, the conflict based on the correction received from the arbiter system to correct data maintained locally at the client device. 
 
     
     
       2. The method as described in  claim 1 , wherein the at least one other report communicated to the arbiter system is by the repository system. 
     
     
       3. The method as described in  claim 1 , wherein the at least one other report communicated to the arbiter system is by another client device. 
     
     
       4. The method as described in  claim 1 , wherein the report and the at least one other report communicated to the arbiter system include at least a portion of a hash of a key and a portion of a hash of a corresponding value of a respective said record. 
     
     
       5. The method as described in  claim 4 , wherein the portion of the hash of the key or the portion of the hash of the corresponding value of the respective said record is specified in a report request received by the client device from the arbiter system. 
     
     
       6. The method as described in  claim 1 , wherein the report and the at least one other report describe changes initiated to both the data of the repository system and the search index of the search index system. 
     
     
       7. The method as described in  claim 1 , wherein the conflict request specifies a number of records to be obtained describing changes to the data involved in the conflict and an amount of data to be included, respectively, in a hash of the number of records. 
     
     
       8. The method as described in  claim 7 , wherein the amount of data to be included, respectively, in the hash of the number of records is based on criteria including a number of active said client devices, heuristic data describing past conflicts, or a probability of encountering the conflict. 
     
     
       9. The method as described in  claim 7 , wherein the amount of data to be included specifies a portion of a hash of a key and a portion of a hash of a corresponding value of a respective said record. 
     
     
       10. The method as described in  claim 1 , wherein the correction is generated using an XOR operation based on response data received from the repository system and the response data received from the client device. 
     
     
       11. A computing device comprising:
 a processing device; and 
 a computer-readable storage medium implementing a repository system and storing instructions that, responsive to execution by the processing device, causes the processing device to perform operations including:
 maintaining data by the repository system that is received from a plurality of client devices and searchable using a search index of a search index system; 
 receiving a conflict request from an arbiter system, the conflict request generated to request response data to resolve a conflict detected between the data of the repository system and the search index based on comparing records of changes to the data of the repository system described in reports received by the arbiter system from the plurality of client devices; 
 communicating the response data to the arbiter system responsive to the receiving of the conflict request; 
 receiving a correction from the arbiter system, the correction generated based on the response data communicated by the repository system and response data communicated to the arbiter system by at least one of the plurality of client devices; and 
 resolving the conflict based on the correction received from the arbiter system to correct the data in the repository system. 
 
 
     
     
       12. The computing device as described in  claim 11 , wherein the comparing of the records is performed based on a plurality of reports received by the arbiter system from the plurality of client devices. 
     
     
       13. The computing device as described in  claim 12 , wherein the plurality of reports includes at least a portion of a hash of a key and a portion of a hash of a corresponding value of a respective said record. 
     
     
       14. The computing device as described in  claim 13 , wherein the portion of the hash of the key or the portion of the hash of the corresponding value of the respective said record is specified in a report request received by a respective said client device. 
     
     
       15. The computing device as described in  claim 12 , wherein the plurality of reports describes changes initiated to both the data of the repository system and the search index system. 
     
     
       16. The computing device as described in  claim 11 , wherein the conflict request specifies a number of records to be obtained describing changes to the data involved in the conflict and an amount of data to be included, respectively, in a hash of the number of records. 
     
     
       17. The computing device as described in  claim 16 , wherein the amount of data to be included, respectively, in the hash of the number of records is based on criteria including a number of active said client devices, heuristic data describing past conflicts, or a probability of encountering the conflict. 
     
     
       18. The computing device as described in  claim 16 , wherein the amount of data to be included specifies a portion of a hash of a key and a portion of a hash of a corresponding value of a respective said record. 
     
     
       19. A data storage system comprising:
 a repository system configured to maintain data received from a plurality of client devices; 
 a search index system configured to maintain a search index supporting a search of the data in the repository system; and 
 an arbiter system configured to:
 detect a conflict between the data of the repository system and the search index by comparing records of changes to the data of the repository system described in a plurality of reports, one to another, received from the plurality of client devices; 
 generate a conflict request for transmission to the repository system and a client device of the plurality of client devices to request response data to resolve in the conflict; 
 generate a correction to the data of the repository system and the search index based on the response data received from the repository system and the client device responsive to the conflict request; and 
 resolve the conflict by communicating the correction to the repository system and the search index system to be used, respectively, to correct the data of the repository system and the search index of the search index system. 
 
 
     
     
       20. The data storage system as described in  claim 19 , where the comparing of the records is performed based further on records of changes to the data of the repository system described in at least one other report communicated by the repository system.