CN103003815A - Shared data collections - Google Patents

Abstract

A data sharing mechanism may allow programs to share access to data collections. The mechanisms that implement the sharing may allow programs written in any language to read and write a shared collection. The mechanisms may make the shared nature of the collection relatively transparent to the program and to the programmer, by allowing program to operate on the data more or less as if it were purely local data. The sharing of collections may be managed by a shared object runtime on each machine on which a collection is used, and by a shared object server. The shared object server maintains the true state of the collection, and deterministically resolves collections when programs operate on the same collection without knowledge of each other's operations. The mechanisms by which collections are shared may be implemented so as to be agnostic as to the kind of data in the collection.

Description

shared data set

Background technique

A collection is a group of data items that will be manipulated together. Some examples of collections include lists, arrays, sets, bags, and various other groups of data. In the early days of programming, programs were generally monolithic entities that did not interoperate with each other. Thus, a program can manage collections internally in any way the programmer chooses. In modern programming, however, it has become a more popular practice to make different instances of the same program, or different programs, interoperate with each other by manipulating shared data sets.

While it is possible to make programs implement their own mechanisms for sharing data, doing so is generally cumbersome for the programmer. Programmers may have to implement the sharing mechanism as a cohesive part of the program. Even if the code for a known sharing mechanism is available to the programmer, the mechanism is generally specific to the program's idiosyncrasies and specific to the data types being shared. Also, when other programs want to share data with existing programs, those programs must be implemented in a way that uses the same sharing mechanism.

While various problems arise in allowing programs to share data, the sharing of collections presents additional problems. For many types of collections, the current state of the collection is defined not only by the contents of the collection, but also by the order in which those contents appear. For example, the array {1,2,3,4,5} is different from the array {2,3,1,5,4}. Even though the two arrays contain the same underlying elements (numbers from one to five), the order is different, and thus the two arrays have different states. Maintaining the state of a collection, especially the order, presents particular challenges when the state of the collection may be changed by several programs.

overview

The concept of shared collections can be implemented in such a way that the sharing mechanism is transparent to the programmer. Additionally, mechanisms to implement shared collections may provide data convergence for collections when the collection is operated by several different entities.

In one example, a shared object server manages the sharing of collections by maintaining the true state of the collection at any given time. A program that gains access to a collection can connect to a shared object runtime on the machine on which the program is running. Programs that access a shared collection register the collection as a shared collection, and this registration is communicated by the runtime to the shared object server. Other programs that want to access the collection also register the collection as a shared collection. Similarly, this registry is communicated by the runtime to the shared object server. Additionally, programs can subscribe to notifications of changes on the collection, where subscription requests are handled by the runtime. Each program maintains a local copy of the collection. When the state of a collection is changed in any way, the runtime on the machine on which the change occurred communicates this change to the shared object server. The shared object server updates the actual state of the collection and communicates this change to all programs registered with this collection through the shared object runtime on the machine on which the subscribing program is running. Each of these programs then updates its local copy of the collection based on the state changes communicated by the server. Where concurrent changes have occurred on the collection, the shared object server resolves any conflicts in those changes and arrives deterministically at the true state of the collection.

In another example, shared objects are managed in a peer-to-peer fashion rather than a client/server fashion. In a peer-to-peer implementation, each subscriber to a shared collection can communicate changes to the other subscribers. The runtime on the machine the subscriber is running on can then change their local copy while deterministically resolving any conflicts.

Collections can be implemented in almost any programming language (eg, C, C++, Java, Visual Basic, etc.). Since the concept of shared collections can be implemented in multiple programming models, programs written in different languages can operate on the same shared collection. Additionally, a programmer can write programs that will operate on shared collections in the same manner as on purely local collections. Thus, a program may be able to manipulate a shared collection without having to recognize the shared nature of the collection in any way other than issuing commands to register new collections or subscribe to changes to existing collections. In this way, the sharing of collections is effectively made transparent to the program and to the programmer. Furthermore, the sharing mechanism may be agnostic to the type of data in the collection, thereby allowing collections of any type of data to be shared.

This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Brief description of the drawings

Figure 1 is a block diagram of an example of a shared collection.

2 is a block diagram of an example scenario in which programs may share access to a shared collection.

3 is a block diagram of an example of a peer-to-peer implementation of set sharing.

4 and 5 are block diagrams of some examples of how shared collections may be used.

6 is a flowchart of an example process in which collections may be shared.

7 is a block diagram of example components that may be used in conjunction with implementations of the subject matter described herein.

Detailed ways

In modern computing, programs often interoperate with each other by sharing access to the same underlying data. When programs share data, the programs are often implemented in a way that recognizes the fact that the data is shared. That is, programs generally must contain the implementation of mechanisms for sharing data with other programs, or with other instances of the same program. The mechanisms for sharing are often ad hoc to the nature of the data being shared, as well as programmer design choices. Therefore, when two programs want to share data, their respective programmers generally must agree on and implement a specific sharing mechanism. There are certain generalized mechanisms that allow limited forms of data sharing, but are not suitable for specific situations.

While the sharing of various data presents various implementation issues, additional issues arise when the data to be shared is a collection. A collection is a group of data items that can be manipulated together. Some examples of collections include lists, arrays, sets, bags, and various other groups of data. Some types of collections are sorted. Thus, the current state of an ordered collection is defined not only by the contents of the collection, but also by the order in which those contents appear. For example, {1,2,3,4,5} is a data set containing integers from one to five. If the set is sorted, {1,2,3,4,5} is a different state than {2,3,1,5,4} because the two states have a different order even though they both contain the same item.

When any type of data is shared among concurrently running programs, two modifications to the data may conflict - eg, one program may want to modify the data while another program is trying to delete the data. However, additional difficulties arise when such conflicts occur and the data being shared is part of a collection. A program can request that an item be inserted after the second item in the collection. Another program may request that the second item be deleted, thereby making the inserted item the second item. In order to handle these changes and arrive at the true state of the collection, it must be decided which item in the original collection is now the second. Since each program may not know that the other program is operating on the same set, two programs may refer to the "second" item in the set while having a different understanding of which item in the set is really the second item in the sequence.

Operational transformation fields involve mechanisms that allow deterministic ordering of data in calculations. Some of these mechanisms can be used to resolve conflicts in files being manipulated at the same time—eg, how to determine what edits have occurred in a text file being edited by two users at the same time. However, these types of techniques are generally not applied to generalized sharing of collections of the type described here.

The themes described here provide mechanisms for sharing collections of data. The techniques described herein can be used to provide a generalized collection sharing mechanism that allows several programs and/or several instances of the same program to share access to a collection. These techniques allow programs to be implemented in different programming languages. These techniques may allow an ordered collection of data to be manipulated concurrently by multiple programs and/or program instances in such a way that the collection deterministically reaches a particular state that can be propagated to all programs using the collection. Additionally, the techniques described herein may allow a programmer to write programs that operate on shared collections in more or less the same way that programs would operate on purely local collections. Furthermore, the sharing mechanism can be made agnostic to the underlying data type in the collection, thereby allowing the same generalized sharing mechanism to be used for any suitable kind of data. In other words, the various actions described herein can be performed without regard to the content of the data items in the collection, and without regard to the structure of the content of those items.

Programs that share data can run on a single machine, or on several machines connected by a network. To facilitate the sharing of data, each machine on which a program runs may have a shared object's runtime. A shared object runtime can facilitate the management of sharing and synchronization of shared data objects, including shared collections. In one example, the shared object's server maintains the real state of the shared collection. When a change is made to a shared collection on a machine, the runtime on the machine notifies the shared object server about the change. In response to this local change, the server may change the true state of the collection. If two programs make concurrent changes to the collection, the shared object server can resolve those changes to arrive at a true state that reflects, to the extent possible, the state of the collection that both programs intend to achieve. Thus, if two different programs each mutate the same collection without knowing about the other's changes, the server can execute one of these changes to create a new state of the collection, and then translate the other change (to the extent possible ) to reflect the change that another program would have made had it known the new state of the collection when it made the change. The server notifies the runtime on each machine of the change (or translated change, if applicable), and programs that have subscribed to the collection update their local copies of the collection according to the changes propagated by the server. In another example, collection sharing is implemented in a peer-to-peer architecture, in which each program subscribing to a shared collection notifies other subscribers about changes that the program has made, and the other subscribers (or The runtime components on the machines that are running these subscribers) synchronize their local copies to these changes without the help of the server.

When a program creates a collection, the program may issue an instruction to register the collection as a shared collection. This instruction can be received by the runtime on the machine on which the program is running, and the runtime can report the registration to the shared object server. Then, the shared object server receives a copy of the collection, which represents the initial state of the collection. From this perspective, the program that created the collection can operate on the collection in much the same way as it would if the collection were purely local, since runtime management reports changes to the shared object server (or in a peer-to-peer implementation, report to other subscribers), and receive synchronization of state changes from the shared object server.

If a program wants to use a shared collection that has been created by another program, the program issues an instruction to register the collection. This command may be received by the runtime and passed to the shared object server. The shared object server then knows to notify the runtime on the machine on which the subscribing program is running about any changes to the state of the collection. When a program subscribes to a collection, it receives a copy of the current true state of the collection, which is then stored locally as the collection. Subscribers can then operate on the shared collection in much the same way that the collection is local. In this way, the effective sharing of collections is made transparent both to programs that create and register collections, and to programs that subscribe to the collections. As noted above, the system can be agnostic to the nature of the data in the collection, so that the sharing mechanism can work on collections containing any type of underlying data.

FIG. 1 shows an example of a shared collection 102 . Shared collection 102 may include a set of data items that are related to each other in some manner and that may be accessed (eg, read and written) by multiple programs (such as programs 104, 106, and 108). Programs 104-108 may be different running instances of the same program (eg, the same application running on several different processes), or may be different programs. Additionally, programs 104-108 may all run on the same machine or on different machines. In both cases, programs 104-108 may be different programs, or separate running instances of the same program, in which sense they may be described as "distinct." Collection sharing mechanism 110 may facilitate sharing of shared collection 102 among programs 104-108. Exemplary implementations of the set sharing mechanism 110 are described below in conjunction with FIGS. 2-7 .

Shared collection 102 may have a name 112, allowing shared collection 102 to be identified by programs that share the same namespace. As an alternative to (or in addition to) name 112 , shared collection 102 may also have an identifier 114 that distinguishes shared collection 102 from other shared collections. For example, identifier 114 may be applied to collections that have not been assigned a name, so that collections can be identified before "friendly" names have been assigned to the collections.

Shared collection 102 may have multiple data items. In the example of FIG. 1, four data items 116, 118, 120, and 122 are shown, but a collection may have any number of data items. Each data item can contain any type of data. Some examples of data that may be stored in a shared collection will be described in more detail below in conjunction with FIGS. 4 and 5 . However, as general examples, some data types that can be stored in collections are elemental data types such as numbers or words, or more complex programmer-defined data types such as A structure, or element of a user interface. The mechanisms described here may be data type agnostic, such that individual data items in a collection may be (illustrated in detail) anything from elemental data types to complex user-defined data types.

In the example of FIG. 1 , shared collection 102 is an ordered collection. As mentioned above, a sorted collection is a collection in which the state of the collection is defined not only by the data items in the collection, but also by the order on those data items. Insertion or removal of data items changes the state of the sorted collection, but also changes the position between two existing data items. Thus, each data item in sorted set 102 has an ordinal position. Ordinal positions 124 , 126 , 128 , and 130 correspond to data items 116 , 118 , 120 , and 122 , respectively. Thus, data item 116 is at a first location, data item 118 is at a second location, and so on. If the sequence number of any item is to be changed, even if there is no change to the item itself, this change will result in a change in the state of the shared collection 102 .

Exemplary operations that may be performed on the shared collection 102 include transform operations 132 and delete operations 134 . A transform operation 132 swaps the sequential positions of two (or more) items in the set, and a delete operation 134 removes one of the items in the set. Also, the collection may be modified by performing an insert operation 136 to add new data items 138 to the collection. We will refer to these operations later in the discussion below.

FIG. 2 illustrates an example scenario in which programs may share access to shared collection 102 . Machine 202 is the machine on which the program is executed. Machine 202 may be any type of machine having some computing capability—eg, a personal computer such as a desktop or laptop computer, a server computer, a handheld computer, a smartphone, a set-top box, and the like. In the illustrated example, two programs 204 and 206 execute on machine 202, although any number of programs may run on the machine.

Machines 202 may store data, and one type of data stored on machines 202 is a local copy of shared collection 102 . In the example of FIG. 2 , shared collection 102 is created by program 204 . The collection may be local and specific to the program 204 when the collection is created. However, program 204 may want to register the collection as a collection for sharing, to allow other programs (possibly including, programs running on other machines) to share access to collection 102 . Accordingly, the program 204 issues a register command 208 . The registration command 208 can be issued by any programming language in which the program 204 is written, and can be received by the shared object runtime 210 . For example, shared object runtime 210 may provide an application programming interface (API) that allows program 204 to issue registration instructions (and subscription requests, among other types of instructions) to shared object runtime 210 .

Upon receiving registration instruction 208 , shared object runtime 210 may register shared collection 102 with shared object server 212 . Shared object server 212 is a server that maintains the real state of shared data objects, such as shared collection 102 , and also serves as a clearinghouse for changes to shared objects. That is, when shared data changes on a machine, the shared object server 212 receives a notification and propagates the change to the state of the shared data to other machines. Shared object runtime 210 may provide a copy of shared collection 102 when shared collection 102 is registered on shared object server 212 . Once collection 102 has been registered as shared, shared object server 212 maintains the true state of collection 102 as shown in the box labeled "(real state)" in the box representing shared object server 212 in FIG. 2 . (Note that throughout this description, we refer to a program or subscriber sending an action as sending a register or subscribe request to a server or other subscriber. The action of a program sending these types of requests includes where the program communicates the request to the runtime , and the runtime communicates the request to the server, or to other subscribers or to the runtime. Similarly, as described below, a subscriber can communicate state changes to the server or to other subscribers; Actions include cases where the communication is performed at runtime on the subscriber's machine.)

When shared collection 102 is registered as shared, programs other than program 204 can access the collection by subscribing to the collection. To subscribe to a collection, the program may submit a subscription request 214 . Some collections are subject to access control restrictions specified by their creators. Such access control restrictions may limit the set of programs and/or users and/or machines that may access the shared collection. However, assuming there are no access restrictions on shared collection 102 (or there are access restrictions, but those restrictions seeking access to shared collection 102 have permission to access the collection), then subscribing to shared collection 102 allows subscribers to read and/or modify The collection.

Subscription requests can come from any program on any machine. For example, program 206 may subscribe to shared collection 102 by submitting a subscription request via shared object runtime 210 . Notably, program 206 is on the same machine 202 as the creator of shared collection 102 (ie, program 204 ). However, the subscription program can be on a different machine. For example, program 216 on machine 218 also subscribes to shared collection 102 by submitting subscription request 214 . Subscription requests from program 216 are submitted through shared object runtime 220 (the runtime of machine 218). (Each machine may have its own instance of the shared object runtime.) Additionally, subscription requests to shared collection 102 may come from programs executing on machine 222, or on any other machine.

When a program has subscribed to shared collection 102 , the program can receive a copy of the current state of truth of shared collection 102 . For example, program 216 on machine 218 receives a copy of shared collection 102, which may store a copy on machine 218 (such as the instance of shared collection 102 labeled "(local copy)" in the box of FIG. 1 representing machine 218) . Subscribers can then read and write to the local replica as if it were a purely local collection. An instance of the shared object runtime on the machine on which the program is running (e.g., in the case of program 216, shared object runtime 220) may monitor the local copy of the shared collection 102 to determine whether the program has done anything to the shared collection. Changes will be reported to the shared object server 212.

When any subscriber to shared collection 102 performs an operation that makes a change to the local copy of shared collection 102 , the shared object runtime on the subscriber's machine reports the operation to shared object server 212 . The shared object server 212 then updates the current state of the shared collection and alerts object subscribers (including the object's creator) of the state change.

Shared object server 212 may include a synchronization component 226 that facilitates the collection and dissemination of state information among subscribers of shared collection 102 . The manner in which synchronization component 226 operates may be implementation dependent. In one example, the synchronization component maintains a master copy of the shared collection 102 in its true state, and only propagates a new copy of the shared collection 102 whenever the state of this collection changes. In another example, the synchronization component 226 maintains a list of changes relative to the current version of the shared collection 102 and propagates these changes to clients. The runtime on each client can then compute the true state of the shared collection 102 based on the local state of the shared collection 102 and the changes received from the shared object server 212 . Even if the shared object server 212 does not propagate a complete copy of the shared collection 102 in response to every state change, the shared object server 212 can determine how to resolve simultaneous changes to the shared collection 102 so that - when the client-side runtime receives notification of the change - It can compute the new state of the shared set 102 from the old state. As described below, if desired, the synchronization component 226 can translate changes so that changes made by a first subscriber can be sent to the first subscriber without knowledge of the second subscriber's synchronized changes, and can is applied in a way that makes sense and causes the results of all subscribers to converge on the same state of the shared set 102 .

One function performed by the synchronization component 226 may be to determine how changes made by two clients are applied to the collection, where neither client is aware of the other's changes. This situation may occur if two clients make changes involving the same item in the collection at about the same time, so that each client makes the change before the other receives notification of the change. For example, suppose the first two items in the set are alpha and beta. Two clients—call them A and B—make changes to the collection at about the same time. A wants to add a new term after alpha, gamma, and B wants to remove beta. So A performs an operation that adds a new item at sequence position two, and B performs an operation that deletes an item at sequence position two. If the operation of A is performed first, the final state after the two operations is that alpha and beta occupy positions one and two, respectively. If the operation of B is performed first, the final state after the two operations is that alpha and gamma occupy positions one and two respectively. Synchronization component 226 can resolve this apparent conflict as follows.

For the purposes of this example, call server S and clients A and B. S, A, and B all start in state 0 with A performing operation X and B performing operation Y. Since neither A nor B knows that the other operation has been performed, A and B each report to S in state 0 - i.e., A and B each report that they have performed an operation on the set while the set exists in state 0 . An operation has been performed, now A and B each increment their state to 1. One of these operations, however, will reach S first. For this example, assume that X arrives first. Since operation X operates in state 0 (which matches the current state of S), it is executed on S and sent to B without being transitioned. Additionally, an acknowledgment is sent to A. S is now in state 1. At this point, B receives operation X from S. Since operation Y has not been confirmed by S, operation X is transformed relative to Y and then applied to the collection. B is now in state 2. When operation Y reaches S, the operation indicates that it was executed in state 0. Since 0 is no longer the current state of S, S determines that it does not know about operation X when B performs Y. Thus, operation Y is transformed relative to operation X and passed to A. Confirmation is sent to B. S is now in state 2. At this point, A receives the transformed version of operation Y. Since A has no proxy operations, the transformed Y is applied without further transformation of the transformed Y. (That is, a transitioned Y indicates that it was executed relative to state 1. Since A is already in state 1, there is no basis for further transitioning Y.) A is now in state 2. Also, the replicas in A and B's collections now display the same data in the same order.

Figure 2 shows an exemplary client/server-type implementation, where the server manages the sharing of collections. However, peer-to-peer implementations may also be used. Figure 3 shows an example of a peer-to-peer implementation of set sharing.

In the example of FIG. 3, machines 202, 218, and 222 participate in the sharing of set 102 (as they did in FIG. 2). For example, each machine may have one or more programs that are subscribers to the shared collection 102 (where creators of the shared collection are included in the notion of "subscriber"). Each machine has an instance of the shared object runtime—that is, shared object runtimes 210, 220, and 302 run on machines 202, 218, and 222, respectively. In a peer-to-peer implementation, the shared object runtimes communicate directly with each other rather than with the server. Additionally, the shared object runtime may be responsible for translating incoming changes rather than having the server perform those changes. Thus, as long as the different runtimes implement the same algorithm for resolving conflicting changes to the collection, the current state of the collection can be known deterministically.

If shared collection 102 is changed, eg, on machine 202 , shared object runtime 202 on machine 202 transmits a notification of state change 304 to shared object runtimes 220 and 302 on machines 218 and 222 . Each shared object runtime applies a state change 304 to the current state of the shared collection 102 to arrive at the new state of the collection 102 . In the event that two different state changes come from two different machines at the same time, the shared object runtime can apply a conflict resolution algorithm (eg, the algorithm described above in connection with synchronization component 226) to determine what state change to apply. As described above, the algorithm can be made deterministic so that any two runtimes receiving the same set of conflicting changes can resolve conflicts in the same way, thereby causing the sets to be changed to the same state on each different machine.

Figures 4 and 5 show some examples of how shared collections may be used. The examples in Figures 4 and 5 are schematic and do not limit the subject matter here. It is provided only to give some specific examples of how the shared collection may be used, but it is understood that there are numerous other contexts in which the shared collection may be used.

Figure 4 illustrates an exemplary task list, which may be implemented as a shared collection. Each task in the task list may be a task to be performed. The illustrated task list includes four exemplary items, 402, 404, 406, and 408, and may be tasks to be performed by a workgroup developing a new product for a company. A task list may be implemented as a set, where each task to be performed is an item in the set, and where the order defined by the items represents the order in which the items are to be performed. Members of the workgroup may all have control over the task list. For example, the task list can be accessed through e-mail and calendar programs where each team member is running an instance. Thus, different team members can add or delete items on the list, or can rearrange existing items. Thus, each instance of a program can be a subscriber to a collection representing a task list. When any team member uses his or her instance of the program to make a change to the task list, that change can be propagated to other instances of the program in the manner described above. So, a worker can use a first instance of the program to switch the order of the first and second tasks (as indicated by numeral 410), and another worker can use a second instance of the program to delete the third task (as indicated by numeral 412). These changes can be processed and a new state of the collection can be reached.

Figure 5 illustrates an exemplary user interface, which may be implemented as a collection. The user interface may, for example, be a desktop toolbar in which the data items shown in FIG. The vertical sequence diagram is a widget in the toolbar. A list of widgets can be implemented as a collection, and different programs can share access to the collection. For example, the user may determine that he wants the clock to be on top of the new feed, and thus may switch the order of the first two elements in the set (shown as numeral 512). The user can then report errors in the toolbar to the information technology manager. The manager can then use the manager to connect to the toolbar. The manager can identify, for example, that the photo viewer has a bug, and can therefore remove the widget from the toolbar (shown as numeral 514). In this way, two people use two different applications to modify a user interface implemented as a collection.

Note that in the examples of Figures 4 and 5, the illustrated collections may involve complex data types. For example, the data item in Figure 4 is a task (which may contain fields for overview, long description, due date, reminder date, etc.). And the data item in FIG. 5 may be an application handle (which may contain fields such as the application's name, location on disk, runtime parameters, etc.). In other words, these examples show that any type of data can be used in a shared collection, and that the collection sharing mechanism can handle various types of data in the same way, regardless of the nature or structure of the data.

Figure 6 illustrates an exemplary process in which collections may be shared. Before turning to the description of FIG. 6, note that the flowchart contained in FIG. 6 is described by way of example with reference to the components shown in FIGS. 1-5, although the process of FIG. 6 may be implemented in any system and is not limited to Scenarios shown in 1-5. Additionally, the flowchart in FIG. 6 shows an example where the stages of the process are implemented in a particular order, as shown by the lines connecting the blocks, but the various stages shown in this diagram can be in any order , or in any combination or subcombination.

At 602, a collection is created. For example, a program can create collections by using mechanisms that would normally be used to create local collections. The collection can be any type of collection—for example, a list, an array, and so on. At 604, a collection can be registered for sharing. For example, a program that creates an assembly can issue instructions, which can be received by the shared object runtime on the machine on which the program is running. In one example, the runtime exposes an API that allows a program to issue check-in instructions, although check-in instructions could be issued in other ways.

After the collection is registered as shared, a subscription request for the collection can be received (at 606). For example, other programs that share the same namespace as the program that created the collection can issue subscription requests to that collection. These subscription requests may be issued to the shared object runtime on the machine on which the subscribing program is running. In one example, a subscription request can be made through an API exposed by the runtime. For the purposes of topics here, the creator is considered one of the subscribers. (Even if the creator issues a registration request rather than a subscription request, the creator of the shared object is a subscriber in the sense that the subscribers are those programs that have access to the collection.) The subscriber can receive the current state of the collection (at 608 ), and they store a local copy of the collection.

At some point, the subscriber makes a change to the collection (at 610). Exemplary changes include insertion 652 , deletion 654 , and movement 656 . Insertion 652 adds a new item to the collection at a specific position in the collection order. DELETE 654 removes the existing item from the collection. Moving 656 reorders the order of two or more items in the collection.

When the shared object runtime on the subscriber machine detects a change, the shared object runtime notifies the applicable entity(s) of the change (at 612), and the changes are received by the entity(s) (at 614). Which entities are "applicable entities" may be implementation dependent. As noted above, there are, for example, client/server and peer-to-peer implementations for implementations of the subject matter described herein. In a client/server implementation, the runtime detecting changes may notify the shared object server managing the real state of the collection. In a peer-to-peer implementation, each runtime notifies the other runtimes directly.

When changes to the collection are received, any conflicting changes (eg, changes indicating that two clients are already performing operations on the same state of the collection) are resolved in a deterministic manner (at 616 ). For example, if two subscribers have made changes that affect the "second" item in the collection (eg, one entity switches the positions of the first and second entities, and the other entity, simultaneously, deletes the second entity) , these conflicting changes can be resolved to arrive at the true state of the collection—eg, using the algorithm described above in connection with synchronization component 226 (shown in FIG. 2 ). The conflict is resolved in a manner that may or may not achieve the intent of the subscriber who made the change, but unambiguously determines the resulting state.

In a client/server implementation, the resolved changes may be communicated to subscribers (at 618). In a peer-to-peer implementation, subscribers and/or runtimes on subscriber machines receive change information from other subscribers and/or runtimes, and resolve conflicts themselves without assistance from the server. Deterministic conflict resolution processing allows each client to resolve changes in the same way so that subscribers can converge on the same result on the true state of the collection. (Again, the resulting state can be resolved explicitly, but the resulting state may or may not fulfill the intent of the Subscriber who made the change.)

When any existing conflicts have been resolved (and in the case of a client/server implementation, when the results of the conflict resolution have been communicated from the server to the subscriber), changes to the local copy of the collection can be made (in 620) to make these local copies consistent with the real state. Subscribers then continue to read and write to the collection.

Figure 7 illustrates an example environment in which aspects of the invention described herein may be deployed.

Computer 700 includes one or more processors 702 and one or more data memory components 704 . Processor(s) 702 are typically microprocessors, such as those contained in a personal desktop or laptop computer, server, handheld computer, or another type of computing device. Data memory component(s) 704 are components capable of short-term or long-term storage of data. Examples of data memory component(s) 704 include hard disks, removable disks (including optical disks and magnetic disks), volatile and nonvolatile random access memory (RAM), read only memory (ROM), flash memory, magnetic tape, etc. . The data memory component(s) are examples of computer readable storage media. Computer 700 may include or be associated with display 712, which may be a cathode ray tube (CRT) monitor, a liquid crystal display (LCD) monitor, or any other type of monitor.

Software may be stored in data memory component(s) 704 and may run on one or more processor(s) 702 . One example of such software is collective shareware 706 that may implement some or all of the functionality described above in connection with Figures 1-6, although any type of software may be used. Software 706 may be implemented, for example, by one or more components, which may be components in a distributed system, separate files, separate functions, separate objects, separate lines of code, and so on. A computer (e.g., a personal computer, a server computer, a handheld computer, etc.) in which a program is stored on a hard disk, loaded into RAM, and executed on a computer processor(s) represents the scenario depicted in FIG. The subject matter described herein is not limited to this example.

The subject matter described herein may be implemented as software stored within one or more of data memory components 704 and executed on one or more processors 702 . As another example, the subject matter can be implemented as instructions stored on one or more computer-readable storage media. Tangible media such as optical or magnetic disks are examples of storage media. Instructions may exist on non-transitory media. Such instructions, when executed by a computer or other machine, may cause the computer or other machine to perform one or more acts of a method. Instructions to perform actions may be stored on one medium, or may be distributed across multiple media such that the instructions co-occur on one or more computer-readable storage media regardless of whether all the instructions happen to be on the same medium .

Additionally, any acts described herein (whether shown in figures or not) can be performed by a processor (eg, processor(s) 702 ) as part of a method. Thus, if actions A, B, and C are described herein, a method including actions A, B, and C can be performed. Furthermore, if actions A, B, and C are described herein, a method comprising performing actions A, B, and C using a processor can be performed.

In one example environment, computer 700 may be communicatively connected to one or more other devices via network 708 . Computer 710, which may be similar in structure to computer 700, is an example of a device that may be connected to computer 700, but other types of devices may be so connected.

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.

Claims (15)

1. A method of facilitating data collection sharing, the method comprising: receiving a registration of the data set created by a first program, wherein the registration is received from an object runtime on a machine on which the first program executes; receiving a subscription to the collection of data from a second program different from the first program, wherein there is a set of subscribers to the collection of data, and wherein the set of subscribers includes the first program and said second procedure; receiving a first notification that a first one of said subscribers has performed a first operation on said data collection, making a change to the state of said data collection; and The change in state is propagated to the set of subscribers. 2. The method of claim 1, further comprising: receiving a second notification that a second of said subscribers has performed a second operation on said collection of data, said second operation being different from said first operation; and A conflict between the first operation and the second operation is resolved by inverting the second operation relative to the first operation. 3. The method of claim 2, wherein the second notification describes the second operation using an ordinal position of an item of the data set depending on whether it was performed before or after the second operation The first operation is performed after the second operation, and the ordinal position refers to a different item. 4. The method of claim 1, further comprising: maintaining a copy of the data set in a true state of the data set; and wherein the propagating includes: The true state is communicated to the subscriber. 5. The method of claim 1, wherein said propagating comprises: A description of a change relative to the subscriber's version of the state of the data set is communicated to the subscriber, the change resulting from performing the first operation. 6. The method of claim 1, wherein the method is performed regardless of the structure of the content of the items in the data set. 7. The method of claim 1, wherein the first notification includes the type of operation being performed on the data collection, the position of the item being operated on in the data collection, and the The state of the data collection. 8. A computer readable medium comprising computer executable instructions for performing the method of any one of claims 1-7. 9. A system for facilitating the sharing of data collections, the system comprising: processor; storage; and a collection sharing component stored in the memory and executing on the processor, wherein the collection sharing component receives a registration request from a first program that created the data collection on a first machine, the first A program receives a subscription request for said collection of data from a second program executing on a second machine, said first machine being different from said second machine, wherein said collection sharing component receives from a first set of subscribers a at a member, receiving a first notification that a first operation changing the state of the data collection has been performed by the first member, and wherein the collection sharing component propagates a second notification that the state has been changed to all The set of subscribers, wherein the set of subscribers includes the first program and the second program. 10. The system of claim 9, wherein the collection sharing component receives from a second member of the set of subscribers that the second member has executed on the data collection A third notification of a second operation, and resolves conflicts between the first operation and the second operation by translating the second operation relative to the first operation, the first operation being different from the The second operation, and the first member is different from the second member. 11. The system of claim 10, wherein the second notification describes the second operation using an ordinal position of an item of the data set, wherein depending on whether the second operation is performed before or after The first operation is performed after the second operation, and the ordinal position refers to a different item. 12. The system of claim 9, wherein the collection sharing component maintains a copy of the data collection in a true state of the data collection, and wherein the second notification includes the true state. 13. The system of claim 9, wherein the second notification includes a description of a change in the subscriber version relative to the state of the data collection, the change resulting from execution of the first operate. 14. The system of claim 9, wherein the collection sharing component propagates the second notification regardless of the content structure of items in the data collection. 15. The system of claim 9, wherein the first notification includes the type of operation performed on the data collection, the position of the item being operated on in the data collection, and the The state of the data collection.

Images