Systems and methods for mutations and operational transforms in a collaborative spreadsheet environment

• US 9,460,073 B2
• Filed: 02/27/2013
• Issued: 10/04/2016
• Est. Priority Date: 02/27/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Danziger, Joshua Ari, Haldimann, Niklaus, Karve, Amod, Lloyd, Zachary Erik, Fazal, Asim
• Primary Examiner(s): Mercado, Ariel
• Application Number:
  US13/779,379
• Publication Number:
  US 20150199326A1
• Time in Patent Office: 1,315 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services

Abstract

Mutations representing spreadsheet edit operations are received at a server from client computers of collaborators and also at a collaborator'"'"'s client computer from other collaborators and the server. Different mutations may conflict, i.e., provide contradictory instructions on how a spreadsheet is to be edited. Techniques for representing sort operations, cut-and-paste operations, and operations to change cell properties as mutations, and operational transform techniques that can be used to resolve conflicts between such mutations, are disclosed herein. Further disclosed herein are techniques for identifying and processing computationally intensive types of mutations in a calculation thread which operates asynchronously with respect to a UI thread at a collaborator'"'"'s client computer. The processing may include performing an operational transform on results of the calculation thread based on results obtained in the UI thread.

Claims

1. A method for updating a spreadsheet based on user inputs, the method comprising:

receiving a first user input specifying an analytic function to be applied to data of the spreadsheet;

receiving a second user input specifying a data edit operation to be performed on the spreadsheet;

in response to determining that the first user input specifies the analytic function, assigning the first user input to a calculation thread;

in response to determining that the second user input lacks the analytic function, assigning the second user input to a UI thread;

processing the first user input in the calculation thread, the processing comprising applying the analytic function to the data of the spreadsheet to produce first mutation results;

while processing the first user input in the calculation thread, processing the second user input in the UI thread to produce second mutation results, and applying the second mutation results to the spreadsheet to update the spreadsheet;

storing the first mutation results and second mutation results in a pending queue, wherein the pending queue contains mutation results made at a client device by a user, and the pending queue includes (1) mutation results that have not been sent to a cloud computing system to be applied to other client devices and (2) mutation results that have been sent to the cloud computing system to be applied to other client devices;

in response to a determination that the processing of the first user input is complete, performing a first operational transform on the first mutation results based on the second mutation results to obtain modified first mutation results;

storing third mutation results to the spreadsheet in a collaborator queue, wherein the collaborator queue contains mutations received at the client device from the cloud computing system;

identifying a conflict between the modified first mutation results and the third mutation results;

performing a second operational transform to resolve the conflict between the modified first mutation results and the third mutation results to obtain further modified first mutation results; and

applying the further modified first mutation results to the spreadsheet.

2. The method of claim 1, wherein the data edit operation is an operation that does not include an analytic function, such that the data edit operation is assigned to the UI thread for processing.

3. The method of claim 1, wherein the data edit operation is selected from the group consisting of an insert row command, a delete row command, an insert column command, and a delete column command.

4. The method of claim 1, wherein the first user input and the second user input are each received at a server and appended to a global mutation log that stores mutations to the spreadsheet in an order that the mutations are received.

5. The method of claim 1, wherein the operational transform is performed further in response to a determination that the first mutation results conflict with the second mutation results, and the first mutation results and second mutation results are in conflict when the second mutation results are applied in view of the first mutation results before the processing of the first user input is complete.

6. The method of claim 1, wherein the calculation thread processes only analytic functions that are determined to be computationally intensive including the first user input.

7. The method of claim 1, wherein the UI thread is an initial thread used to execute a process and generates one or more secondary threads to be employed by the process for all mutations except analytic functions.

8. A computing system for updating a spreadsheet based on user inputs, the computing system comprising:

a network interface configured to;

receive a first user input specifying an analytic function to be applied to data of the spreadsheet; and

receive a second user input specifying a data edit operation to be performed on the spreadsheet;

in response to determining that the first user input specifies the analytic function, assign the first user input to a calculation thread;

in response to determining that the second user input lacks the analytic function, assign the second user input to a UI thread;

a processor configured to;

process the first user input in the calculation thread, the processing comprising applying the analytic function to the data of the spreadsheet to produce first mutation results;

while processing the first user input in the calculation thread, process the second user input in the UI thread to produce second mutation results, and apply the second mutation results to the spreadsheet to update the spreadsheet;

store the first mutation results and second mutation results in a pending queue, wherein the pending queue contains mutation results made at a client device by a user, and the pending queue includes (1) mutation results that have not been sent to a cloud computing system to be applied to other client devices and (2) mutation results that have been sent to the cloud computing system to be applied to other client devices;

in response to a determination that the processing of the first user input is complete, perform a first operational transform on the first mutation results based on the second mutation results to obtain modified first mutation results;

store third mutation results from a collaborating user to the spreadsheet in a collaborator queue, wherein the collaborator queue contains mutations received at the client device from the cloud computing system;

identify a conflict in the modified first mutation results and the third mutation results from the collaborating user;

perform a second operational transform to resolve the conflict between the modified first mutation results and the third mutation results to obtain further modified first mutation results; and

apply the further modified first mutation results to the spreadsheet.

9. The computing system of claim 8, wherein the data edit operation is an operation that does not include an analytic function, such that the data edit operation is assigned to the UI thread to be processed.

10. The computing system of claim 8, wherein the data edit operation is selected from the group consisting of an insert row command, a delete row command, an insert column command, and a delete column command.

11. The computing system of claim 8, wherein the first user input and the second user input are each received at a server and appended to a global mutation log that stores mutations to the spreadsheet in an order that the mutations are received.

12. The computing system of claim 8, wherein the processor is further configured to perform the operational transform in response to a determination that the first mutation results conflict with the second mutation results, where the first mutation results and second mutation results are in conflict when the second mutation results are applied in view of the first mutation results before the processing of the first user input is complete.

13. The system of claim 8, wherein the calculation thread processes only analytic functions that are determined to be computationally intensive including the first user input.

14. The system of claim 8, wherein the UI thread is an initial thread used to execute a process and spawns secondary threads employed by the process for all mutations except analytic functions.