text:
The invention relates to the use of history information as an aid to synchronization in a peer-to-peer system. In particular, node trees are used to represent portions of files systems designated for synchronization. The nodes in the node tree embody history information regarding associated objects. The history information includes version vectors that are used to simplify synchronization-related comparisons and create job lists that may be used to bring participating peers into synchronization.
1. A first peer system for synchronizing data elements in a group of synchronizing peer systems, said first peer system comprising,
A sync software module for managing synchronization directly with a second peer system and directly with a third peer system;
A memory for storing a first node tree representing a first sync point in said first peer system, a second node tree representing a second sync point in said second peer system, and a third node tree representing a third sync point in said third peer system;
A microprocessor resource for running said sync software module while said sync software module interacts with metadata; said running activity producing a first job list for said first peer, a second job list for said second peer and a third job list for said third peer;
Said metadata derived from a set of corresponding nodes, said set of corresponding nodes comprising one node from each of said first node tree, said second node tree and said third node tree;
Said second job list comprising instructions to synchronize objects in said second sync point with corresponding objects in said first sync point and said second sync point;
Said first job list comprising instructions to synchronize objects in said first sync point with corresponding objects in said second sync point and said first sync point;
An i/o system for connecting with said second peer system and said third peer system for transferring said second job list and said third job list respectively.
2. The system of
3. The system of
4. The system of
5. The system of
6. The system of
7. The system of
8. The system of
9. The system of
10. The system of
11. The system of
12. The system of
13. The system of
14. The system of
15. The system of
16. A method of synchronizing a first peer system with a second peer system and a third peer system, the method comprising the steps of:
Generating a first node tree, said first node tree corresponding to a first sync point existing in a store of said first peer system;
Generating a second node tree, said second node tree corresponding to a second sync point existing in a store of said second peer system;
Generating a third node tree, said third node tree corresponding to a third sync point existing in a store of said third peer system;
Storing said node trees in a store of said first peer system;
Analyzing metadata to produce a first job list for said first peer, a second job list for said second peer and a third job list for said third peer;
Said metadata derived from a set of corresponding nodes, said set of corresponding nodes comprising one node from each of said first node tree, said second node tree and said third node tree;
Said second job list comprising instructions to synchronize objects in said second sync point with corresponding objects in said first sync point and said second sync point;
Said first job list comprising instructions to synchronize objects in said first sync point with corresponding objects in said second sync point and said first sync point;
Enacting said first job list on said first peer system;
Enacting said second job list on said second peer system; and
Enacting said third job list on said third peer system.
17. The method of
18. The method of
19. The method of
20. The method of
21. The method of
22. The method of
23. The method of
24. The method of
25. The method of
26. The method of
27. The method of
28. The method of
29. An apparatus for synchronizing datums between a first peer system, a second peer system and a third peer system, said apparatus comprising:
A memory for storing a first node tree representing a first sync point in said first peer system, a second node tree representing a second sync point in said second peer system, and a third node tree representing a third sync point in said third peer system;
A microprocessor resource for running a client software program, a service software module and a sync software module, said service software module providing a program interface for indicating a sync point, and said sync software module for interacting with metadata and thereby producing a first job list for said first peer system, a second job list for said second peer system and a third job list for said third peer system;
Said metadata derived from a set of corresponding nodes, said set of corresponding nodes comprising one node from each of said first node tree, said second node tree and said third node tree;
Said second job list comprising instructions to synchronize objects in said second sync point with corresponding objects in said first sync point and said second sync point;
Said first job list comprising instructions to synchronize objects in said first sync point with corresponding objects in said second sync point and said first sync point.
30. The apparatus of
31. The apparatus of
32. The apparatus of
33. The apparatus of
34. The apparatus of
35. The apparatus of
36. The apparatus of
37. The apparatus of
38. The apparatus of
39. A media encoding program instructions for performing the method of
Synchronization is a function that provides or maintains consistency between data sets. For example, a desktop computer may have desktop data sets regarding personal information management ("PIM"). A user of that desktop computer may desire to use that PIM data when she is away from her desktop computer. Therefore, she may desire access to the PIM data while using a laptop computer or a personal digital assistant ("PDA") such as a phone or other device like a miniature device. In order to accommodate that desire, her laptop computer and PDA may each carry PIM data sets that correspond to the PIM data sets on the desktop computer. The role of the synchronization function is to give the user a common view of her data on each device. This role is generally accomplished by synchronization events when two or more of the devices synchronize.
A common technique for synchronizing devices is by using snapshots of data at a point in time and comparing current data to the snapshot to determine what has changed. For illustration purposes, refer to
A problem occurs in the described synchronization process when corresponding data is changed on both the desktop and the portable. For example, suppose that sometime prior to synchronization, Jane Doe's phone number was changed to 877-555-5555 on the Desktop and 800-555-5555 on the portable. During the compare operation (or at another time) the synchronizing system will notice this discrepancy and identify a conflict. In the current commercial art, there is generally no elegant way to resolve this conflict with certainty. Some solutions present an interface to the user and ask her to choose between the two options. Unfortunately, even the user may not remember which piece of data is correct. Other commercial solutions simply create duplicate entries in each database (one with each of the possible data items).
The problem is exacerbated if there are more than two devices carrying the corresponding data sets. For example, referring to
Finally, the problem may be generalized for peer-to-peer systems with 3 or more peers. That generalization is that, if peers may synchronize with each other 2 at a time, and a conflict arises there is no way to know if one of the peers carries a more up-to-date data. It is noteworthy, that a time stamp can not resolve the conflict with certainty. This is because as a matter of practical human usage, if two corresponding data items have been changed over the past days or months, that doesn't necessarily mean that the second change is correct. This is especially true if the second change occurred as the result of synchronization with another peer (such "another peer" may have received its data change long ago). Therefore, in the peer-to-peer situation, we would be unable to determine if a detected conflict is, on the one hand, a true conflict, or on the other hand, an apparent conflict that could be correctly resolved (e.g. per user intent) if we understood the history of the data.
Some of the related prior art techniques for synchronization may be found in the following U.S. Pat. No. 5,710,922 "Method for synchronizing and archiving information between computer systems," which is incorporated herein by reference. In addition, the following pending patent applications offer similarly interesting information and are hereby incorporated by reference: "A Method of Synchronizing Between Three or More Devices" by Toby Paterson and Jerome Lebel, having application Ser. No. 10/853,306 and filed May 24, 2004; "A Method of Synchronizing" by Toby Patterson and Jerome Lebel, having application Ser. No. 10/852,926 and filed May 24, 2004; and "Apparatus And Method For Peer-To-Peer N-Way Synchronization In A Decentralized Environment," having application Ser. No. 11/157,647 and filed Jun. 21, 2005.
In view of the discussion herein as well as the other problems existing in the prior art, certain embodiments of the invention propose a synchronization system that employs datum history information in a process to provide synchronization services either as an API layer in an operating system or as directly employed by software and systems requiring synchronization.
The embodiments described herein relate to the use of history information as an aid to synchronization in a peer-to-peer system. In some embodiments, there is a group of syncing peers. Each peer in the group has a designated sync point in its storage area. Each sync point indicates a hierarchy in the file system and the group of sync points correspond to each other in that they indicate storage areas that are kept in synchronization with each other.
In some embodiments of the invention, the file system hierarchy indicated by the sync point is scanned to acquire metadata regarding all the objects in the hierarchy. The metadata is organized in a node tree that mimics the hierarchy of the sync point of each peer. In particular, each node in the tree corresponds to an object in the file system. In some embodiments, the nodes may be data structures that comprise a great deal of information about the object and the history of the object in terms of adds, deletes and modifications. In some embodiments, one special kind of history metadata retained is information regarding prior conflict resolutions regarding the node.
Some embodiments of the invention employ a data structure called a version vector. A version vector indicates synchronization metadata for each node in the node trees. A software engine is used to compare corresponding nodes of the syncing group of node trees. As the comparison takes place, the engine may generate job lists for the peers corresponding to the node trees under comparison. The job lists comprise instructions indicating actions (such as adds, deletes and modifications) for each peer to become synchronized with the others.
Some embodiments of the invention provide other synchronization and user interface techniques. In particular, there is discussion and teaching regarding peer discovery, synchronization infrastructure building, and multi-touch user interface
I. Sample Hardware and Software Structures
While the techniques described herein may be embodied in virtually any structural context, we shall describe some example structural embodiments for illustrative purposes. Referring to
Referring now to
Transitioning from sample hardware, we shall now discuss general software background. In particular, referring to
With those caveats, we see in
II. Vocabulary and Non-Limitation
Throughout this disclosure, we shall use certain vocabulary to discuss synchronization techniques and examples. Most of the illustrations discussed relate to collections of files, where individual files are the datum being synchronized. Generally, we discuss a "datum" as the data or collection of data that is being synchronized and thus treated indivisibly for the purpose of the synchronization function. However, many embodiments of the invention are expressly intended to apply to virtually any kind of data. Some examples of data that may be synchronized using the techniques taught herein are the following: PIM data such as contacts, calendar entries, notes, to-do items, etc.; text files; word processing files; package-type files; files from a file system, media files such as jpegs, mp3, mpeg2, mpeg4, or wav files; records from a database; or any other data file type, whether or not associated with a specific applications.
Retreating then to the language of most of our illustrative embodiments, we shall primarily discuss the invention in terms of "peers" that synchronize with each other or in a group. Referring now to
Referring again to
Referring again to
The topic of synchronization implies multiple peers and indeed, some embodiments are described in term of a "sync set," which is merely a collection of peers that all sync a common group of data such as a hierarchy of files. Of course, a single peer may be a member of a plurality of sync sets simply by having a different common group of data with each set.
Furthermore, many embodiments of the inventions discuss data organization in terms of a hierarchy such as a tree. Referring to
Referring now to
Thus, in
As suggested above, we may also view the trees of
In addition, with respect to the metadata node trees, some embodiments of the invention employ a special node called a tombstone. A tombstone node is in a state tree to represent history in that spot of the state tree. Unlike other metadata nodes, a tombstone node does not have a directly corresponding object in the file system. Rather, in some embodiments, a tombstone node implies that there was once an object at a designated location in the file system (sync point). In these embodiments, tombstone nodes exist as a way to hold node history in the state tree. This history may be employed to provide synchronization features that are discussed later.
A concept related to the tombstone node is that of node history. A node history is a tag attached to a node in the state tree which tracks the location of old file system objects. In some embodiments, a node history is attached to a node whenever a file system object is moved or deleted. In some embodiments, the node history contains a location version vector for the underlying object at the time of the object was moved, and a reference to the state tree node representing the new location of the object. If the object is moved outside of the sync point or deleted, this reference is undefined (i.e., "nil") and represents a deleted object. This means that in some embodiments, a "delete" operation is just a special case on move, i.e. moved to an undefined space (or nowhere).
III. History Information
a. Using History
When comparing a set of datum to determine the most current, some embodiments of the invention involve the use of history information as part of the assessment. For example, each datum may be associated with a meta-data set that comprises information regarding every change to that datum. The following is a list of some of the information that is desirable to track: the date and time of a datum change; the identity of the local store and/or peer before the datum change; the identity of the store and/or peer after the datum change; the location of the datum in a store at before the datum change; the location of the datum in the store after the datum change; user information regarding the datum change; account information regarding the datum change; the mechanism that cause the datum change (e.g. a user, a sync, etc.); whether a change was the result of a conflict resolution such as a user resolving a conflict; and the history of datums that "lose" (i.e. are updated/modified) by virtue of synchronization with conflict resolution.
b. History in the Form of Version Histories
In some particular embodiments, version histories are maintained for each datum of interest. In practice, there are beneficial uses for maintaining this relatively rich indication of history. For example, in many embodiments of the invention, detailed historical data is maintained. Referring to
Referring then to
Therefore, the history may be exploited to make intelligent decisions about the data. One example of such a decision is, in the situation of an apparent conflict, the devices may determine whether one version of the data item is an ancestor of another. This can be very useful in many cases, such as that of truncated data. Truncated data may occur when a fat device such as a desktop computer synchronizes with a thin device such a phone. If the phone is not capable enough to carry all of a data item (or all of a set such as a record), the data from the desktop computer is truncated for inclusion in the phone database. Later, the phone may synchronize with another device, such as a PDA, and convey the truncated data. If the PDA and desktop attempt to subsequently synchronize, they will encounter a conflict that only specific history data can resolve. Thus, one or more preferred embodiments of the invention call for the maintenance of history information per datum.
Furthermore, if it is not obvious from the discussion above, to be very clear, many embodiments of the invention comprise history information in addition to time stamps because time stamps do not solve some complex synchronization problems. This is true even if all synchronizing machines somehow have perfectly synchronized clocks. For example, suppose a file "cron.log" is created at exactly midnight on both machine A and machine B, which are machines perfectly synchronized with respect to time. If we synchronized A and B using timestamps alone, we may believe that the two cron.log files are actually the same file (having be independently created, they are not the same file). So even for this trivial example it is clear that other information is useful; namely, in this example, the identity of the machine that made the modification. So, some embodiments will carry the following history information: on machine A, "A @00:00," indicating machine A at midnight; on machine B, "B @00:00". Now, comparing these ever-so-slightly richer histories will correctly show that the files were different form one and other.
Some embodiments of the invention call for associating datum with a type of history information called version histories. The notion of version histories according to the invention may comprise one or more of several concepts.
First, one point that may be evident from the discussion above is that perfect accuracy and synchronization of heterogeneous system clocks is an unrealistic expectation in the real world. Thus, many embodiments of the invention do not rely on such perfection. Rather, with the aid of other history information, these embodiments only expect that each peer have access to a system clock that is monotonically increasing per each event. For example, the clock could simply increment each time an "event" occurs. Thus, some embodiments may simply use a generation count rather than a clock of any kind. Furthermore, a preferred embodiment may use a clock or generation count that never repeats a value (e.g. a full time and date stamp or analogous count).
Next, some embodiments of the invention call for incrementing the clock or generation count for every event. Thus, the count might be incremented for every data modification and perhaps even for related issues like software or hardware failures that have the possibility to impact the status of the data. However, other embodiments employ a more parsimonious incrementing scheme where the clock/count is incremented only once for each synchronization. These embodiments recognize that repetitive increments of the clock/count have little benefit during a period where the data is only accessed locally to the peer. Moreover, a simple dirty bit system may be employed to track the datum that have changed, then prior to synchronization the clock/count may be incremented (in practice of some embodiments, either a count will be incremented or a time stamp applied).
When a plurality of datums are ready for synchronization, one approach to progressing is to compare version histories of corresponding datum to determine whether one datum is an ancestor of another. In making such determination, version history X is an ancestor of version history Y if-and-only-if version history X appears as a prefix in version history Y. For example, {A@7:21, B@8:35} is an ancestor of {A7:21, B@8:35, C@8:34} because "A@7:21, B@8:35" appears as a prefix in "A@7:21, B@8:35, C@8:34" meaning that the latter history incorporates all of the former in addition to something new (by comparison). As another example, {A@7:21, B@8:35} is also an ancestor of {A@7:21, B@8:35, D@8:36} for the same reason. However, when we compare our two descendant version histories, we encounter a different situation: {A@7:21, B@8:35, C@8:34}; {A@7:21, B@8:35, D@8:36}. In comparing these version histories we see that they both have a common ancestor in "A@7:21, B@8:35" but they have each descended differently (C@8:34 and D@8:36 respectively). Thus, in terms of synchronization, there is a conflict situation because the same ancestor was edited in two different places at two different times (in some embodiments, the fact that the times are different does not impact the decision to declare a conflict). The conflict occurs in certain embodiments because we assume the worst, i.e., different modifications were made on peers C and D. After declaring the conflict, in some embodiments, a part of the conflict resolution is to look inside the datum for direct comparison.
To summarize, with respect to version history, if the versions for two datums are the same, then the contents of the datums are guaranteed to be the same; but if the versions are different, the contents of the datums may or may not be the same. To determine if a conflict is a true conflict or a false conflict, a comparison of the datums may be undertaken. Further, it should be noted that in terms of computing, the expense of such a comparison varies depending upon the type of data. For example, comparing phone numbers is magnitudes cheaper than comparing 4 MB MP3 files.
c. Slimming Version Histories: Version Vectors
As we have discussed, version histories can be very useful in the synchronization task. However, as discussed so far, this history data may grow forever. Thus we introduce the concept of the version vector for some embodiments where it is preferable to use a slimmer version of history.
One mechanism for slimming version history is to use generation counts rather than time stamps. Thus rather than {A@01,15,2007,7:21, B@01,15,2007,8:35}, we simply use {A@1, B@2}, which provides the same useful meaning that: data originated on A, A syncs with B: B modified data.
Another mechanism for slimming version history is to remove multiple references to activity in the same store. For example {A@1, B@2, C@2, A@3} means: data originates on A: A syncs with B; B modifies; B syncs with C; C modifies; C syncs with A). However, for purposes of some embodiments, it is not important to see the history of the datum having been in store A twice. Rather, for those embodiments, it is only important to know the most recent activity on store A. Thus, we can slim version history by only retaining the most up-to-date (latest generation count) of each store. Applying that concept, the history above may become {B@2,C@2, A@3}. This mechanism is effective because the clock/count of each peer provides constantly ascending counts that do not repeat. Furthermore, in some embodiments, we can even omit the B@2, C@2 elements and then interrogate store A each time a synchronization encounters an A variable such as A@3 (this assumes we require the stores to maintain a more complete history).
Yet another mechanism to slim the histories is to simply remove unnecessary syntax such as the @ sign. Thus, {B@2, C@2, A@3} becomes {B2, C2, A3}. Furthermore, given the positive sequential nature of the clock/count, there is no need to maintain any particular sequence among components of these version vectors (e.g. A3 is always more recent than A1 or A2).
After applying these slimming principles, we can once again visit the matter of comparing vectors. In particular, a version vector X is an ancestor of version history Y if-and-only-if for every store x entry in the X vector, the clock/count value of x entry in the Y vector is greater or equal. For example: {A7, B8} is an ancestor of {A7, B8, C8}, and also of {A7, B8, D8}. Looking closely, however at the latter two vectors, you should notice a conflict because they were the same file when they left B, but then they were modified independently on C and D. For illustration, other examples are as follows:
In addition to the foregoing, some embodiments treat non-existent entries in a version vector as having zero as their local clock/count value. This preserves the correct behavior with respect to comparisons, e.g., {A7, B8} works the same way as {A7, B8, C0}. However, omitting these "0" dimensions permits for peers to join the system at any time without revising any existing version vectors.
Referring now to
Referring again to
For more information on similar vectors, we refer to the contemporary literature on vector clocks such as: "Distributed Systems: Principles and Paradigms", Andrew Tanenbaum et. al., section 5.2.2; "Vector timestamps"—"Database System Concepts" (3rd ed.), Abraham Silberschatz et. al., section 21.7.4; "Disconnectivity and Consistency"—"Concurrent and Distributed Computing in Java", Vijay Garg, section 7.5 "Vector clocks."
d. Loser Vectors
Some embodiments of the invention employ a concept called loser vectors. In these embodiments, loser vectors are used to preserve information about conflict resolution. In particular, in some embodiments, the loser vector is employed to preserve a user decision regarding conflict resolution. The general idea is to preserve the resolution so that it may be employed without re-expending the effort of conflict resolution again (e.g. asking the user twice about the same conflict). An added benefit of the loser vector is consistency; once a conflict resolution is made there need not be risk that the same conflict is resolved a different way next time (creating even more confusion). Furthermore, the use of loser vectors may be deployed through options or preference settings to provide flexibility.
Of course, the loser vector can be used to preserve any conflict resolution and may be desirable when conflict resolution requires user involvement or some extraordinary or increased effort. For example, if conflict resolution requires detailed comparison of MP3 files, or even worse MPEG2 movies, some embodiments may preserve loser vectors so that the comparison needn't be repeated.
In concept, a version/loser vector is constructed in the style of a header and an argument. The header provides the version vector regarding the datum and the argument provides the identity of the losing vector. For example, we interpret the loser vector A1B2[A1C2] as header A1B2 reflecting the state of the datum and [A1C2] reflecting a potential state of the datum that a conflict resolution process (e.g. ask the user) has eliminated.
Referring now to
Finally, with respect to certain embodiments employing loser vectors, there are a few edge cases to be considered. First, when two loser/version vectors have equal headers, they may also have different loser vector portions. In this case, some embodiments will merge (and prune, if applicable) the loser vectors and write them back to their respective stores. Thus, in these embodiments, the version for a datum may change even though the datum itself doesn't change.
In some embodiments, you can create a highly unusual case where two versions include each others' header in their loser vector portion (i.e., they are both a loser to the other). For caution, these embodiments should treat this case as a conflict.
In some embodiments, there is another highly unusual case where the user or system tries to add a "loser" to a loser vector that is strictly newer than the header of the version. In these embodiments, there may be several solutions including simply declaring a conflict. In some embodiments, when this case is detected, the headers are merged and incremented. A related question concerns the prescribed course of action when the user elects an older version during a conflict resolution. In this case, some embodiments assign a new version to the older datum thus eliminating the possibility that the older version vector loses in a future sync and thereby overwrites the user's express wishes.
IV. Synchronizing
a. Discovering Sync Peers
The inventions herein contemplate that peers (or nodes) in a peer-to-peer syncing system may have several alternative mechanisms and/or processes to discover other peers. As a primary mechanism, users may designate other peers for synchronization grouping. Such user designation may be performed through a user interface (e.g. by forms, menus or by prompting the user) and by indicating the identity of one or more of the following: peers, users, accounts, user groups or associations, account associations, user attributes or criteria, peer attributes or criteria, account attributes or criteria.
As a complement or supplement to peer discovery by user entry, peers may arrange to find each other through a network or conjoined networks. In this respect, there are many known techniques in the art providing for peers to discover each other and embodiments of the invention contemplate use of any of these techniques. For example, varying embodiments may employ Bonjour network discovery or Gnutella-type discovery.
Furthermore, software systems may arrange to search for and retrieve peer IDs or node IDs that meet any specified or suggested criteria. Thus, in some embodiments, peer discovery may be partially or totally automatic via one or more software modules that aid with the discovery process.
One technique for effecting software-aided discovery is to designate one or more software modules for keeping track of information about peers and/or groups of peers. For example, a sync server module or other software module may maintain a table, database or other data structure of information regarding peers or groups of peers. Thus, some peers (or software within those peers) may discover other peers by communicating with the module having the table or database. This module having the table or database may be analogized to an instant messaging server such as AIM or ICQ, which are well known in the art. Further, the well-known techniques applicable to instant messaging servers may be applied to embodiments of the invention.
b. Building the Infrastructure
Referring to
Once the sync point 501 is ascertained, either in response to an API call or for another reason, software in the file sync module 508 arranges to scan the store 506. In some embodiments, the scan of store 506 yields a data structure comprising every decipherable datum in the sync point's 501 area of the store 501. Having that information, the file sync module may build state tree 509, which may be done in response to an API call. The step of building a state tree is shown in
According to a preferred embodiment, every peer in the sync set will perform similar operations resulting in a fully constructed state tree for each peer; each state tree associated with a sync point in the peer's store and all the sync points related by common association to the sync set.
c. Initiating Synchronization
Some embodiments employ an initial control flow that may be described through the metaphor of instigator peers and collaborator peers. An instigator peer is such due to its role in instigating syncing activity. Once an instigator fully initiates a sync session, all other peers are collaborators in that session. Through use of file sync software or other appropriate software, a peer may become an instigator peer by initiating syncing activity; leaving the role of collaborator other peers in the sync set. Since some embodiments allow any peer to be an instigator for some sync sessions and/or collaborator for other sync sessions, the controlling software modules for a peer may be configured to embody either role.
Varying embodiments of the invention contemplate appointment of the instigator through various mechanisms. Some basic embodiments involve the following mechanisms for determining an instigator: the instigator may be pre-ordained by programming; the instigator may be determined by collective decision and action of the sync set once and forever; the instigator may be determined by collective decision and action of the sync set some time before every sync event or at intervals between syncing events: the instigator may be appointed by the sync set every time there is a change to group membership; or the instigator may be determined by the designation of one or more users or administrators.
In other embodiments, the instigator may be self-appointed or somewhat self-appointed. In these embodiments, a peer may decide to instigate a sync event for any reason at any time, but without limitation, for any one or more of the following reasons: upon an event related to a sync client such as a PIM function or file addition or modification; upon addition of peers or clients of any type; upon another system event such as start up or shut down; upon an indication of impending component or system failure; upon initiation of a backup power supply; upon user initiation; upon expiration of a timer; upon a set schedule.
In addition to determining the identity of instigators and collaborators, some embodiments comprise notions relating to the timing of sync sessions. In particular, in some embodiments, once an instigator makes a decision to sync, the sync may be initiated either immediately or upon a schedule or timed delay. Some embodiments impose a timed delay so as to employ minimal system resources during the delay. For example, at system start up, a prospective instigator may delay sync initiation for a designated amount of time or until system start up events have quieted. Alternatively, the delay may allow resources for the system to handle whatever event precipitated the desire to perform synchronization. In some of these embodiments the delay will be for a fixed period of time, while in other embodiments the length of delay will change and/or be randomly decided for each event.
In certain embodiments as described, it may be possible for two peers to essentially simultaneously elect to be instigators. Thus, such two peers would essentially simultaneously initiate synchronization between all peers and their synchronization efforts would "collide." In some embodiments, the invention comprises rules and procedures to prevent the "collision" or any simultaneous operation of two instigators. In particular, if a first peer detects a collision (e.g. that another peer is/has initiated a sync), then the detecting peer should discontinue its efforts to initiate a sync. In some embodiments, after discontinuing such efforts, the detecting peer schedules or otherwise arranges to instigate a future sync. The timing of this future sync may be after a random or predetermined delay. A benefit of a random delay is to re-initiate a sync event with a low probability of "colliding" with another instigator again. In addition, varying embodiments of the invention contemplate the use of any of the anti-collision type techniques well-known and used in the networking area.
d. Basic Synchronization
In order to begin synchronization, aided by the file sync module, an instigating peer establishes communication with each other (collaborator) peer and requests a copy of their state trees (
Referring to
Furthermore, this is an appropriate time to note that, for some embodiments, the nature of comparison is for the sync engine to walk corresponding state tree structures. In walking these tree structures, the general process is to begin at the root nodes and compare respective version vectors for the root trees under consideration. If the root node is in sync, then no further action is required on those trees. If the root node is not in sync, then the engine walks down in the tree. We can generalize the tree walk process by stating that if a node other than the root node is under consideration, then a comparison result of "in sync" causes the engine to move up in the tree; and a comparison result of clear winner causes the engine to walk down the tree. In the case of a conflict, the resolution may determine whether to go forward as "in sync" or "clear winner."
In a more particular embodiment, when considering a version vector comparison, if the node is in sync, then no action is required and the process can walk up the tree to find the next node to analyze. If the comparison determines that there is a clear winner, and the node represents datum (as opposed to a container), then the datum should be updated or a job list entry created to do the same. In addition, the version vectors for associated containers (up the tree) should be updated to reflect the synchronization result. If the comparison determines that there is a clear winner, and the node represents a container (as opposed to a datum), then the process walks down the tree to make further node comparisons. As suggested above, the container nodes may be updated when a determination is made with respect to datum or leaf nodes. In particular, in some embodiments the process updates version vectors as it recursively walks up the tree. Of course, other embodiments may chose to update containers as the tree walk progresses. If a node other than the root node is under consideration, then a finding of nodes in sync causes the engine to move up in the tree; and a finding of nodes not-in-sync causes the engine to move down the tree.
Referring again to
Finally, referring to
As discussed above, in some embodiments, as each peer is contacted (e.g.
In OS X, peers may use a change tracking system (such as file system events) to determine which portions of the sync point's hierarchy contain modifications. These changes are used to tag directory nodes in the state tree as "isChildModified" (because FSEvents does not provide file-level change notifications; an implementation of the file sync software only uses change tracking data to indicate which directories have modifications). After the deltas have been processed, an implementation of the file sync software queries the database comprising the state tree nodes (hereinafter "node database") for all the directories with the "modified children" flag set and scans those individually. If no change tracking system is available, or if the change tracking fails or generates results which don't make sense, the peer employs a full scan. Furthermore, before a directory is scanned, all of its existing child nodes are tagged with an "isRemoved" flag. As the contents of the directory are scanned, the name of each object reported by the file system is checked against the existing child nodes of the directory in the state tree. If a node is found with the current object's name, its "isRemoved" flag is cleared and its store node info is updated from the catalog information reported by the file system.
Continuing discussion of the OS X implementation, for each new object discovered a new node is created as a child of the directory node being scanned, and its store node info is set to correspond to the catalog information reported by the file system. These new nodes are also tagged with an "isNew" flag. Note that a new node has undefined (i.e., nil) version vectors until later in sync process. When a node's store node info is updated, it is also potentially given up to three new version vectors. If the node is a file and the contents of its data fork have changed, it receives an updated "contentsVersionVector." If the object's attributes (any metadata synced by an implementation of the file sync software) have changed, it receives an updated "attributesVersionVector." Finally, if the location of the object has changed (see "Move Tracking," below) it receives an updated "locationVersionVector." For directories, the "contentsVersionVector" is updated whenever any child object has been modified in any way (attributes, location, new, or deleted). This applies to any deep children, too, so if a single file is changed deep within the sync point's hierarchy, each parent directory (up to and including the root of the sync point) receives an updated "contentsVersionVector." This lets an implementation of the file sync software quickly determine if it needs to descend down any branch of the state trees when generating sync jobs. Thus, if all peers have the same "contentsVersionVector" for any given directory node, it is guaranteed that all descendent nodes are already in sync.
Still continuing discussion of the OS X implementation, once the file system reports that no more child objects are available for the current directory, any child node with its "isRemoved" flag still set is given a "deleted" node history and converted into a tombstone node. Since tombstone nodes cannot contain children of their own, if the deleted object was a directory the children of the directory are simply deleted from the state tree—only the top-most directory which was deleted will remain in the state tree.
Continuing discussion of the OS X implementation, after each directory with its "isChildModified" flag has been scanned (and the flag cleared), any directory nodes with their "isNew" flag set are scanned as above. This process is repeated until there are no new directories found. Note that the above process is somewhat optimized for scanning the remote iDisk as it supports returning catalog information for up to five levels of hierarchy (iDisk is Apple Computer's virtual disk space or server disk space that is available to computer users anywhere via a connection to the internet). This "deep" scan is used for all new directories, while the "isChildModified" directories are just scanned for their immediate children. If any peer is unable to successfully update its state tree, or if the machine driving the sync loses contact with any peer, it is simply removed from the set of available peers. If this leaves fewer than two available peers, the sync is aborted. Otherwise, the sync proceeds to the "Sync Job Generation" stage.
In order to facilitate synchronization, some embodiments of the file sync module track file/datum moves (from one place in the store to another). In addition, some embodiments of file sync treat delete operations as moves by indicating that a file or datum is moved to a nil space (moved to nowhere). In general, the engine may find a move by comparing temporally different versions of the same state tree. For example, upon a synchronization event, a peer may update its state tree to current. Assuming that a copy of the pre-updated state tree has been preserved, the updated state tree may be compared to old version. Such comparison will reveal moved nodes. Moreover, in some embodiments, an indication such as a tombstone or a tombstone node may be inserted in the updated tree to preserve the history of the prior node location and any other desirable metadata. For example, the tombstone or tombstone node may record identifying information for the object that previously occupied the space and the location to which it moved.
Apple Computer's OS X software may allow a move tracking implementation as follows for stores which support nodeIDs. In some embodiments, the nodeID is a fixed-length integer number that uniquely names a file/datum throughout its lifetime, regardless of its name or path location within the host file system. This means that even if a file is renamed or moved, its nodeID remains the same. In some of the nodeID embodiments, the nodeID should not be reused when a file is deleted (or, at least, not for a period of time that obviates risk of duplication). In the implementation under discussion, the nodeID of each object reported by the file system is compared to the nodeID last seen for the object (recorded in the node's store node info). If the nodeID has changed, we ask the file system to locate the object with the previous nodeID. If the previous object is found and it exists within the sync point's hierarchy, we record a "move" node history on the old location before updating the node with the information from the current scan. If the previous object is found but is outside the sync point's hierarchy, the old object is given a "deleted" node history before updating the node with the information from the current scan. If the previous object is not found, no node history is added as we assume the new object is just an updated version of the old object. Additionally, at the end of the directory scan, any child node with its "isRemoved" flag still set is first checked by asking the file system to locate the object referred to by the child node's nodeID. If an object is found and it is within the sync point's hierarchy, a "move" node history is added to the child node, which indicates the new location of the object. If necessary, new nodes are added to create the necessary path within the state tree for this new location. If an object is not found for the nodeID, or if the object found is not within the sync point's hierarchy, the node is given a "deleted" node history as before.
As discussed above, many embodiments call for vector comparison during the synchronization process. Since these embodiments incorporate the notion of simultaneously synchronizing 3 or more peers, we may refer to the associated vector comparison as "N-way" where N represents the number of vectors under consideration.
During an N-way comparison and as indicated in
Losers vectors are those that are direct ancestors of any winner(s) (i.e., strictly older than a winning version). Winner vectors are those that are neither ancestors to any other vector under consideration, nor equivalent to any other winner vector under consideration. Tied winner vectors are simply vectors that equivalent to any winner vector. When we consider together the concepts of winners and tied winners, we can make some illustrative observations. The first observation is that the difference between a winner and its equivalent tied winners may simply be random choice or the sequence in which the engine reached the vector for consideration. Once a vector is declared a winner (by virtue of the programmatic rules), any equivalent vectors found must be tied-winners because they will fail to satisfy one condition of being a winner (i.e. non equivalence to a winner). A second observation is that if two winners are declared after comparison, a conflict is implied. This is because we are comparing vectors that represent corresponding datum from a plurality of peers; for example Jane Doe's phone number. If we examine the vector and determine that it is not an ancestor of any other vector in the set under comparison, then we may declare that vector a winner (we have no other winners yet so the second winner criteria is met). Suppose we then examine a second vector and determine that it is neither equivalent to the winner nor an ancestor of the winner (e.g. it may be relative of the winner that diverged in by virtue an apparently independent modification of the datum). Since the second vector is not equivalent to or an ancestor of the winner vector, we generally must assume that this second vector represents datum different than the first (so we have two different phone numbers for Jane Doe). Thus, the second vector is also declared a winner, and as such, there is a conflict.
This breakdown of versions into winners, losers and tied winners simplifies synchronization analysis because: (i) any n-way version vector comparison which results in more than one "winner "is an indication of a conflict; (ii) a result of one winner and one or more losers indicates a clear winner and the identity of the peers requiring update; (iii) a result of one winner and the remainder of all tied winners indicates that the node is in sync; and (iv) tied winners indicate possible additional sources for the same data so a peer can potentially copy the data from the "best" peer or even from all winning peers. To maintain this simplicity, in many embodiments, the resulting vector from each comparison operation may only be a member of one of the three output sets (winners, losers OR tied winners).
In some embodiments, once the sync engine determines it does not have a conflict at any given node, the winner and tied winners are grouped to provide a comprehensive set of peers which contain the desired data. This set may be employed later to help update peers.
One aspect of the n-way version vector comparison is that, in certain embodiments, undefined (i.e., nil) version vectors are always "winners." This is because a null is not an ancestor of anything nor equal to anything (much the same as NaNs are never equal in floating point comparisons). An undefined version vector implies that the engine does not know anything about the history of the object, which is the case for newly-discovered objects. Since, in these embodiments, undefined version vectors are always winners, the engine will always detect a conflict when there are new objects present unless the only object present is a single new object (i.e. the only winner is the new object because it is the only object). Thus, in many embodiments, when the engine first examines a new state tree, there may be no version vectors (they may all be null); and as such, in these embodiments, a null may be defined as a winner. A process may be employed to detect objects with undefined version vectors and compare the contents of the objects (datum) to see if any are equal. Furthermore, in the case of undefined or null version vectors, they may be given the version vector of any object that is equivalent to the object associated with the null version vector. If all the objects have undefined version vectors, one version vector may be assigned to all objects that are equivalent to one and other.
Later on in the process, some embodiments may employ a conflict resolution process, which may use conflict resolution software code. As an initial effort in conflict resolution, such embodiments may examine the nature of the underlying data (e.g. a container like a directory or folder, or a datum like a file). If the node under examination is a container type, the conflict resolution moves to the next level of the tree and orderly begins examination of the nodes. The process will continue through nodes and levels until a datum type node (such as one representing a file) is found. Once the datum type nodes are found, in some embodiments, the engine may examine and compare any available metadata to attempt to make a determination regarding the relationship of the respective datum (i.e. equivalent or not). If no decision can be made from the metadata, the substantive datum may be examined and compared for a definitive determination on the status of the relationships between corresponding datums. Regardless of whether the relationship is determined with meta or datum comparison, if the datum are equivalent, then the system may automatically update the version vectors and make any other necessary adjustments to the state tree (e.g. to any relevant container nodes). If the datums are not equal, then the conflict must be resolved by some more sophisticated process, such as a user inquiry through a user interface, artificial intelligence or predictive logic.
Referring generally to the process of
As implied above, the general operation of copy and move may be broken down into smaller operations. In particular, some embodiments make use the following job tasks, which may be accomplished through API calls from an application program or high-level software to file sync or other system service software:
Additionally, in some embodiments, there are two "meta jobs" that the engine may generate:
In some embodiments, job generation may be divided into two passes of the engine through the metadata; the first pass for moves (and thus deletes); and a second pass for all other sync jobs. In these embodiments, moves are generated first because it is possible for a file to be both moved and modified in the same sync. It is also possible for a file to be moved and then for a new file to take its original place (e.g. a rolled log files). To properly handle the moved-and-modified case, some embodiments should first generate a move job (and track that pending move so that subsequent checks for the other job types target the correct destination). The program logic for determining which directories need to be checked for sync jobs is the same for both passes, although the actual program logic to determine job generation is obviously different.
The following details describe an implementation for Apple Computer's OS X software, and are intended as illustrative for this disclosure and are expressly not intended to be limiting in any way. Each of the two job generation passes starts by creating a work-set of directories to be checked and initializing that set to contain the root path ("/"). Then the engine repeatedly pulls a path from that set and requests the node at this path from each peer. To determine if it should check the children of this directory it compares the "contentsVersionVector" of these directory nodes from each peer. This is a simple "all or nothing" comparison (if-and-only-if all of the nodes' version vectors compare as equal—so 0 "losers", 1 "winner", n−1 "tied winners"), the directories contain identical objects down to their deepest leaf nodes and can be skipped. Otherwise the children of this node need to be checked for sync jobs.
For illustrative purposes, the following details are provided regarding child job generation in Apple's OS X software. Since it is quite possible for each peer to have children with non-intersecting names, it may be necessary to iterate the child nodes for each peer's directory. To eliminate redundant checks, a list of the child names checked already is used while iterating the children for earlier peers. In pseudo code:
For each unique child name, the engine first checks to see if all peers' nodes are directories (but not package directories). If all the nodes are directories, the path to this location in the tree is added to the set of directories to be checked (as mentioned above). Then move job generation looks for node histories which might apply to the other peers' nodes. If any are found, a MOVE job is generated and the source and destination paths are remembered for the second job generation pass, where they will be used to remap moved nodes so that subsequent jobs are generated based on the results of the moves.
For the second pass of job generation, all non-MOVE types of jobs are generated. To begin, the engine performs an n-way version vector compare on the "contentsVersionVector" for the peers' nodes. If this compare results in their being more than one "winner" the nodes are declared in conflict. As an implementation detail, the nodes are also always declared in conflict if all the nodes are not of the same type (i.e. file, directory, package), regardless of version vectors. When a conflict arises at this point, an attempt is made to "auto-resolve" the conflict. If the conflict is able to be immediately resolved, the n-way version vector compare output sets are adjusted to reflect the results of the conflict resolution (so "winners" will contain only one object) and job generation continues. If the conflict can not be resolved, the conflicting nodes are noted and added to the list of conflicts to be presented to the user for resolution. The engine may skip generating jobs for conflicting nodes and the sync will proceed. This means that conflicts do not block the sync operation.
As mentioned just above, when a conflict is detected during sync job generation, file sync is first given a chance to resolve the conflict (e.g. through auto resolution). The filesync module may check a few simple rules to decide if it can determine an appropriate winner. In a particular OS X embodiment, the only rule applied to all sync sets is for conflicts on .DS_Store files, and in the case of conflicts on .DS_Store files, the file that is "apparently" newest (e.g. based upon the last-modified date in the catalog information) may be chosen as the winner. Other types of automatic conflict resolution rules may also be implemented, such as Portable Home Directories (PHD). Certain PHD syncs may be given a flag which specifies whether the local or remote object should win in a conflict (to avoid conflicts during login and logout syncs).
For the OS X embodiments under discussion, at this point in job generation, it is guaranteed that there is either a clear winning node or all nodes are equal. Thus, ADD and MODIFY jobs can now be generated. Any peer that did not have an object present at the current location (either no node at all, or a tombstone node) receives an ADD job. These peers are a special case as they are not included in the n-way version vector compare because there is nothing to compare. Any peer which has a node in the "losers" set receives a MODIFY job. When any ADD job is generated, a "pending" node is inserted into the peer's state tree at the location of the ADD. This gives the engine something to work with for subsequent job generation. This also allows the engine to easily determine dependencies on jobs (remember, the state tree may be scanned in an indeterminate order—both because the node database may return objects in an indeterminate order and because the "directories to be scanned" set may return paths to be scanned in an indeterminate order). Sync jobs that require a specific order are flagged as dependent. For example jobs that require certain other jobs be performed first are flagged as depending on those other jobs. In order for such flagging to be useful, a sync job may not be eligible to be performed until all of its dependent jobs have been completed. For example, if we add a directory of files, the directory must first be created on the destination peer before the files can be added. Therefore, the ADD jobs for each file will be dependent on the ADD job for their parent directory.
Note, that in the embodiments under discussion, as jobs are generated, the job records are given an indication of the set of peers that contain the winning object. This may be set simply as the union of the winners and tied winners. When the jobs are sent to their respective peers to be executed, the peer processing the job can examine this set of winning peers and decide from which winning peer to copy the needed data. If there is only one winner, there is no choice, but for n-way syncs it is possible that some peers are on the local LAN while others are on the WAN and therefore more expensive to access. It is also possible for peers to drop out of the sync at any time (most likely due to a dropped connection) so by the time a peer gets around to processing any given job some of the winning peers might not be available at all. By having the full set of winning peers available, the engine can offer syncs that are both faster and more robust.
Package files are actually bundles of objects that are presented in a file browser as a single file. In some embodiments, a package is a Mac OS X specific concept whereby a directory in the file system can be tagged as a package to denote that it should be treated atomically, like a file. Due to their uniqueness, some embodiments of the invention handle packages as a special case. Specifically, since packages comprise a bundle of object within themselves, some embodiments provide for state trees and/or tree walking to compare the insides of packages. When walking the package insides, the engine may determine the relationship between a set of corresponding packages, for example, whether the packages are equivalent.
The following discussion describes illustrative implementation details of Apple's OS X software. During the second job generation pass, the engine may discover that packages have been added or modified. For these cases, the sync engine may generate special PACKAGE ADD or PACKAGE MODIFY jobs. The normal sync job generation logic is not used because packages should be treated as atomic units. These package jobs allow for "sub-jobs," and the sub-jobs are all processed as part of processing the main PACKAGE ADD or PACKAGE MODIFY job. Furthermore, in some embodiments, it is considered unsafe to modify the contents of a package directly because a crash or loss of network connectivity could leave the package in an inconsistent state. Therefore, new packages may be constructed in a temporary directory and then swapped into place once they are complete. Because of this, the sync engine must generate a different set of jobs for the objects inside of packages than it otherwise would for the same objects inside a normal directory. For example, files which have not been modified still need to be copied into the temporary directory; while files which are deleted don't need any job because they won't already exist in the temporary directory. Therefore, there are only three types of sub jobs for packages: ADD, MODIFY, and UNCHANGED.
To allow for optimizing package updating, the job generation for packages will note files in the destination package which are identical to their counterpart in the winning package. This allows the peer to make its own local copy (or even hard-link) these unchanged files, eliminating the need to copy the data across the network. Such unchanged files are represented by PACKAGE CHILD UNCHANGED jobs.
Since the files inside the winning package are always the winning files, there is no need to perform n-way version vector comparisons when generating package sub-jobs. The engine simply compares the version vector for the winning package's file nodes to the node for the losing peer(s). If the version vectors compare as equal, a PACKAGE CHILD UNCHANGED job is generated for that node. If the version vectors are not equal, a MODIFY job is generated. If the losing peer did not have a node at this location, an ADD job is generated.
Regarding the OS X embodiments under illustrative discussion, at the end of the second job generation pass, all the syncing peers may be notified that job generation is complete and they may begin syncing. In these embodiments, it is the responsibility of each peer to perform its own sync jobs. This means that all copying is "pull" rather than "push." For remote peers, the sync jobs are sent to the peer over the network and are processed independently of the jobs for all other peers. The jobs for each peer must be processed in a certain order: for instance, all MOVE (including delete) jobs are performed first, followed by ADDs on directories, ADDs on files and packages, MODIFYs on files and packages, and finally UPDATE VERSIONS. Jobs which are dependent upon other jobs may only be executed once all its dependent jobs have completed successfully. If any sync job fails in its processing, all jobs which depend on that job are cancelled.
Since it is possible that not all remote peers will have the appropriate file sync software running on them, it may be necessary for the machine driving the sync to perform the jobs for these "dumb" remote peers. This means fewer optimizations can be made, although some remote peers may have services available which can compensate.
Regarding the OS X embodiments under illustrative discussion, all jobs which are not inherently atomic (everything except moving or deleting a file) use temporary objects. For example, when a file is added or modified, the new data is always copied to a temporary file. When the temporary file is completely updated, it is swapped with the file it is replacing. This is desirable even for ADD jobs where there isn't a file to replace because otherwise there would be a possibility that a partially copied file may be left where only a fully-copied file should exist. When deleting a directory (including a package), the directory is first renamed to a temporary name so that the directory appears to have been deleted in one operation. Then the contents of the directory and the renamed directory itself are deleted. This way, if something should interrupt the delete operation, the engine hasn't left behind a partially deleted directory or a partially deleted package.
In the OS X embodiments under discussion, the engine uses a special format for the names of all temporary objects it creates. A temporary name starts with the prefix ".fstemp." and then appends a unique set of characters to prevent collisions with possible other temporary objects. This prefix starts with a dot (".") so that these temporary objects are normally invisible, and the static prefix lets the sync engine know that such files should never themselves be synced (and in fact should be cleaned up once it is known that such files have been orphaned due to a crash or loss of network connectivity).
In some embodiments, such as the illustrative OS X embodiment under discussion, "update version jobs" are used to update the version vectors on nodes as the sync progresses. For instance, the version vector for a directory may be updated once all the sync jobs for its children have been completed. Thus, we may update the "contentsVersionVector" only after everything below it is in sync so that subsequent syncs will not skip checking this directory's children should the sync be cancelled or fail and children of the directory not be updated. Once all child jobs have completed successfully, the "contentsVersionVector" may be updated to a pre-determined (during sync job generation) version vector. This way, when all peers have a given directory in sync, they will also have equal "contentsVersionVectors." "Update version jobs" are sorted last and depend upon all the child jobs of the directory on which they will operate.
One skilled in the art will understand that the concepts disclosed herein may be employed in embodiments and technical areas that vary from the disclosed embodiments. Those embodiments are intended only as illustrative and without limitation.
V. NAT Traversal
The description herein makes repetitive mention of networks and connectivity for communication betweens peers, nodes and/or way stations (generally called "nodes" for purposes of this discussion). In practice, these nodes may be deployed either individually or on separate LANs or networks presenting security and credentials problems for traffic between nodes. The inventions herein fully appreciate and contemplate the use of techniques for traversing heterogeneous networks; such techniques being well known in the literature of the current day. Furthermore, with respect to NAT traversal and related areas, this application specifically incorporates by reference the currently pending patent application entitled NAT Traversal For Media Conferencing, by Joe Abuan, Joshua Graessley, Hyeonkuk Jeong and Berkat Tung, assigned to Apple Computer and having the Ser. No. 10/769,841. One skilled in the art will understand the application of the techniques described therein to the current invention. Thus, the inventions herein fully contemplate the use of NAT traversal techniques and the like for facilitating commutation between nodes in the disclosed systems.
VI. Multi-Touch User Interface
Where the embodiments of this invention call for user interface and user input, the invention contemplates the use of any known manner of such input. However, one manner of input interesting for controlling synchronization or designating synchronization preferences and function is a manner involving touch sensitive systems. Thus, any embodiment of the invention calling for user interaction contemplates the potential use of touch sensing of one or multiple finger signals or gestures. Further, such gestures (whether effected with one or multiple fingers) may be augmented in meaning through the use of fusion concepts where sound or other input mechanisms are interpreted along with such gestures. For purpose of further disclosure of gestures that may be used in connection with disclosed embodiments, reference is made to U.S. patent application Ser. No. 11/232,299, entitled System and Method For Processing Raw Data Of Track Pad Device, filed Sep. 21, 2005 and incorporated by reference herein.
One skilled in the art will understand that the concepts disclosed herein may be employed in embodiments and technical areas that vary from those disclosed.
Patent Citations
Non-Patent Citations
Referenced by
Legal Events
Original Image


text:
HOW CAN I PICK ONE? I don't regret anything! I fully believe I opened myself up to every opportunity that presented itself. I dived into the culture and respected it at the same time. I immersed myself into the people and their lifestyle because I believe it's important to have an understanding of their country.
- Attempted to speak Spanish
- Drank several Pisco Sours and got to make one
- Reached the highest altitude point of 4800m where it snowed
- Ate not enough churros
- Visited several cathedrals and visited an underground tomb
- Ran free with the alpacas and llamas
- Saw Condors flying free in the Colca Canyons
- Zip lined in Colca Canyon
- Dressed in traditional Inca clothing
- Ate Guinea Pig
- Visited children in Lake Titicaca and gave them gifts
- Walked on floating villages
- Learnt Peruvian card games
- Saw two 7 Wonders of the World (Machu Picchu and Iguassu Falls)
- Climbed Machu Picchu Mountain
- Stayed in the Amazon Jungle
- Went under a waterfall in Iguassu Falls
- Took selfies with Christ the Redeemer
- Walked through a Favela
- Met AMAZING people that I will be friends with for a long time
- Went on a Contiki by myself
I just want to finish this by shouting out to all the solo/independent people out there. I went on this Contiki tour by myself and am so proud of my courage and independence that lead me to do it. After traveling by myself, I've realized several things. First, you're pushed into an unknown culture where you HAVE to do things for yourself. You have to trust your instincts and ideas and your ability to navigate yourself through this journey. Two, you learn more about yourself everyday because at the end of the day you're traveling with yourself. Three, you can be selfish in a selfless way, it's your holiday, you aren't attached to another friend/family member, you can choose to do what you want, WHEN you want without feeling pressured. Four, you're forced to open up yourself to other people with communicating.
Traveling alone can be an overwhelming experience especially if you haven't done it yet. But don't think about it, JUST DO IT. Now is the time, while you're young. I promise you'll come back a richer person in knowledge and you'll always take away precious memories that will last a lifetime. I know I have.
One of my favourite quotes is, "I always wonder why birds choose to stay in the same place when they can fly anywhere on the earth, then I ask myself the same question."- Harun Yahya.
Alice "The Wanderer" x
All photography courtesy of Alice Pye
Want to start your own Latin American adventure? Click here to see more about The Adventure.

subset: commoncrawl


text:
Nearing the Finish Line- The NFL season has reached the final two weeks of regular season with two weeks remaining. For 20 teams, they are playing their last two games for the season before getting ready for the 2014 draft and their offseason plans. For 12 other teams, the second season starts two weekends from now. The playoff picture is somewhat more cut and dried than it was a week ago. It's possible Week 17 next weekend could even see more than the usual share of meaningless games, however it is just as likely that there will be more than enough games which will be in essence "de-facto playoff games" in their own right. Week 16 will certainly not be lacking in suspense as a number of meaningful games are on tap. The New Orleans Saints visit Charlotte, NC to take on the division rival Carolina Panthers. The winner of this game has the inside track to the NFC South title while the losing team is likely either the 5th or 6th seed in the NFC's post season bracket. In the AFC bracket the defending champion Baltimore Ravens host the New England Patriots in a game the Ravens need to win to maintain the sixth seed in the AFC. The Miami Dolphins are on the road in frigid Buffalo, NY to take on the Bills. The Dolphins with a win and a Ravens loss will take over the sixth and final seed in the AFC bracket. The San Diego Chargers are even mathematically still alive but need to win their last two games while getting help with both Baltimore and Miami. A win by both the Ravens and Miami eliminates the Chargers. A win by the Ravens alone finally puts the New York Jets out of their misery. Things even get more interesting as far as Baltimore is concerned. If the Ravens win their final two games while Cincinnati drops their last two (that would include a Week 17 showdown between these two teams in Cincinnati) this combination actually gives the Ravens the AFC North title while the Bengals fall into a tie for the sixth seed. That would leave Cincy at 9-7, and they would actually lose a tie breaker with Miami if the Dolphins finish 9-7. The scenario with the Bengals is unlikely though as their final two regular season games are at home.
Looking at the NFC bracket aside from New Orleans and Carolina, the NFC North is up for grabs after the Lions home loss to the Ravens last Monday night. The Lions fell to 7-7 with the loss and no longer control their destiny. If Chicago can win in Philly while the Lions and Packers drop their games this Sunday, the Bears win the NFC North. The Lions and Packers must win out while the Bears lose out. However if the Lions finish the season tied with the Bears for the top spot in the division, the tie breaker favors Detroit. The Lions will need more help though than the Packers who stunned the NFL with a huge comeback against Dallas last Sunday. In the NFC East, it's between the Philadelphia Eagles and Dallas Cowboys with the Eagles leading the division by a game. The two teams meet at Jerryworld in Week 17 in a game that could decide the division winner and which team will miss the post season entirely. The Eagles play host the Chicago Bears Sunday night while the Cowboys renew their rivalry with the Redskins in DC. Out west the Arizona Cardinals will try to keep their playoff hopes alive as they are on the outside looking in. The Cardinals however have the unenviable task of having to take on the Seahawks in Seattle.
Kingshark Line- The KSL endured a rough weekend in Week 15 going 9-7. The overall mark through 15 weeks is 150-76 for a .663 winning percentage. Tough weeks are all a part of the deal when trying to accurately forecast NFL games. Who knew Tony Romo would keep passing the ball when he didn't need to? Who knew the Bengals really weren't ready for prime time afterall? Who knew the Saints would lay such a big egg after a big win over the Panthers the week before? Who knew the Lions would lose on a 60 plus yard field goal in the last seconds of the game for the second time in franchise history? Who knew the Vikings without Adrian Peterson and a number of starters would boat-race the Eagles? This is why games are hard to pick. At the same time, half of the fun is the thrill of the chase. As we enter Week 16, gone are the Thursday night games (which really do more harm than good for the teams who have to participate in them). It's all Sunday affairs from now until the post season with the season's final Monday night game being played this week as well. If there is one thing that is for certain, this Sunday will have a lot of drama around the league. With that in mind here is how the Kingshark Line sees Week 16 playing out:
New Orleans@Carolina (FOX)- Could be the day's most interesting game as the Saints try to regain control of the NFC South against the rival Panthers. Two weeks ago the Saints routed the Panthers in New Orleans 31-13. However the Panthers rebounded with a solid win over the Jets while the Saints laid an egg in St Louis. The Saints have had two bad games in their last three and will need to be very focused going into this game. The Panthers know with a win they take control of the NFC's #2 seeding as well as their division. The Panthers clearly ran into a buzz saw two weeks ago but should have learned a lot about the Saints. New Orleans like so many other teams just seems to play a little different on the road than at home. The Panthers are at home and can hold serve with the best. This will be a closer game than two weeks ago, but at home Cam Newton outduels Drew Brees. Panthers 24 Saints 21.
Miami@Buffalo (CBS)- The Dolphins are looking to keep their post season hopes alive but must travel to Buffalo where if anything it will be much colder than it was two weeks ago in Pittsburgh. Miami on the last road game in the cold handled the Steelers, and last week pulled off the upset of the week in a four point home win over New England. Buffalo also was on the road in Florida where they had spent the past two weekends themselves. Last week the Bills outlasted the Jaguars 27-20 after having lost 27-6 in Tampa the week before. The Bills are a team that can play well at times but can never maintain any level of consistency. Miami knows that their road in the playoffs if they get there will feature nothing but cold weather games. The Dolphins also have a payback factor as they lost at home to the Bills earlier this season. The Bills have nothing to lose here while Miami has plenty to lose, but maybe a lot more to gain too. The gain should be motivating enough even in frigid weather (all bets are off however if there is a blizzard). Dolphins 19 Bills 16.
Minnesota@Cincinnati (FOX)- The Bengals with a huge opportunity to show the nation last Sunday that they were ready for prime time instead got spanked by a Pittsburgh Steelers team who is playing out the string. The Vikings offense has been hot the last two weeks in giving the Ravens all they could handle two weeks ago, then spanking the Eagles at home last week. The Bengals have been very good at home this season and have plenty of reasons to win this weekend as they can still wrap up the AFC North division. QB Andy Dalton needs to have a good game, and if anything has the right opponent to accomplish that goal. Cincinnati wants to atone for a bad loss before a national television audience last weekend. The Bengals should be able hold their own against the Vikings but should expect at least some challenge as well. Again elements could be a factor here too. Bengals 27 Vikings 17.
Denver@Houston (CBS)- The Broncos have had 10 days to think about a shocking loss in their regular season home finale to San Diego. The Broncos were ambushed a week ago Thursday by a Chargers team which played their best game of the season. The Broncos obviously want to rebound and find themselves playing a team that has lost their last dozen. What the Broncos need to do is not take the Texans for granted and execute their offense. The Broncos defense has a lot of question marks and will need a good game here more than the offense. The Texans meanwhile look to have the first pick in this spings' NFL Draft all but locked up. Look for Peyton Manning & Company to do what they need to get the job done here. Broncos 37 Texans 23.
Indianapolis@Kansas City (CBS)- The Chiefs come into this game with a lock on a post season birth and an outside shot at the AFC West title. The Colts have already won the AFC South with very little competition for their division. If the Chiefs somehow win the AFC West this game could actually serve as a playoff preview. Kansas City is coming off two games scoring 45 and 56 points respectively albeit against much weaker competition, the Colts on the other hand beat the Texans at home. Right now the Chiefs are playing much better than the Colts who have struggled in hostile environments this season. The Chiefs fire power especially at home just seems to be superior. Could be a fun game to watch too. Chiefs 31 Colts 24.
Dallas@Washington (FOX)- The Cowboys are looking to rebound after a mind numbing loss at home to Green Bay. The Redskins in Atlanta last weekend actually played one of their better games of the season despite the one-point loss. If the Redskins have only one reason to be motivated here it's because it's "Dallas Week." The Cowboys may not lack in desire but seem at times to lack in brains. You simply have to know when to stop throwing the ball around the yard sometimes. A 23-point lead is usually enough reason to keep the ball on the ground. Dallas needs this game to keep their playoff hopes alive. The Redskins would love to spoil all of that. Kirk Cousins at least gives a the Skins a better shot here than an injured RGIII. Tony Romo might throw another pick in this game but if he limits it to one or none it will give Dallas a good chance. This should be close and the Redskins with nothing else to play for should give a solid effort here. Cowboys take this one...just barely. Cowboys 20 Redskins 19.
Tennessee@Jacksonville (CBS)- The Titans season was probably sunk when they allowed the Jaguars to gain their first win of the season Nov. 9th in Nashville. Jacksonville lost at home to the Bills last weekend however have at least saved some face having won four of their last six. The Titans gave their all in an overtime loss to Arizona. This game is simply a toss-up. Titans Head Coach Mike Munchak is likely a goner of the Titans get swept by the Jags. Neither team has much to lose here as this game will probably be decided by whichever team can make the fewest mistakes. Flipped a coin, heads the home team; tails the road team. It came up tails. Titans 20 Jaguars 17.
Cleveland@NY Jets (CBS)- If Joe Namath and Jim Brown were in the prime's of their careers this would be a fun game to watch. It still could be if the teams just decide to entertain the fans and play a sandlot game. Otherwise this could be a snoozer of epic proportions. When you hear Browns vs Jets, the excitement just isn't really there and it has a lot to do with both teams being perennially poor with some on and off years by the Jets thrown in. The Browns in their last two games have at least shown up and battled. The Browns should have won the game in New England two weeks ago but got hosed by the officials. Cleveland also gave Chicago all they could handle a week ago. The Jets got hammered last weekend by the Carolina Panthers. Cleveland has played the better football over the last two weeks but that really matters little. Geno Smith vs Jason Campbell is a wash, with Smith getting the slight edge only because they are home. Jets 16 Browns 13.
Tampa Bay@St Louis (FOX)- Just two teams playing out the string here. St Louis played a solid game last weekend in an upset of the Saints while the Buccaneers just could not keep up with the 49ers. If nothing else the Rams of late have been tough at home late this season. Tampa has won four of their last seven. Another coin flip game. This time the coin landed on heads. Rams 24 Buccaneers 20.
NY Giants@Detroit (FOX)- The Lions have lost control of their destiny in a gut wrenching home loss to Baltimore last Monday night. The Giants are out of the playoff picture and have reverted to just being awful again. With both Matthew Stafford and Eli Manning's propensity to throw interceptions as well as Tony Romo does, this could be a "pick fest". For the Lions this is a "Must Win" if they want to be mathematically alive come Week 17. The Giants are out of gas and are just trying to get through the final two games without further injuries. Lions 20 Giants 13.
New England@Baltimore (CBS)- This will be a good one. The defending champion Ravens need this game to keep their sixth seeding in the AFC playoff hunt. The Patriots are looking to rebound from a tough loss in Miami last weekend. The Ravens have been tough at home this season and still have enough of a defense to get the job done against most anyone. The Patriots finally fell in Miami last week after back to back last second wins in their previous two games. If the Patriots are to win here they cannot afford to have the game go to the wire, but may not have a choice against the Ravens defense. Baltimore has won their last four games and though not exactly art they are finding ways to win. A win here combined with a Miami loss will give the Ravens the 6th seed and eliminate San Diego too. The Patriots are "in" already are one of the few teams that isn't all that concerned about where they seed. The Ravens if they've shown anything over the last four games is that they have the heart of a champion and they could be tough to deny here. In one of those rare days, Joe Flaco and the Ravens defense finds a way to out-duel Tom Brady & Co. Ravens 24 Patriots 17.
Pittsburgh@Green Bay (CBS)- Aaron Rogers for the 7th straight week will be on the sidelines as a defacto offensive coordinator, putting the ball into the hands of back-up QB Matt Flynn. Last week Flynn led the Packers to an improbable comeback over the Cowboys at Jerryworld. The Packers despite their shortcomings in Rogers' absence still have a shot at the NFC North Title. The Steelers had a huge win over the rival Bengals last week but are no longer in playoff contention. Green Bay will be very hard pressed to build on what they did a week ago but if they can keep that momentum they should be handle a team on the road playing out the string. Ben Roethlisberger and the Steelers offense has found their game in recent weeks while the defense still struggles from time to time. The elements could play a factor here but this should still be an entertaining game. Packers 26 Steelers 21.
Arizona@Seattle (FOX)- The Arizona Cardinals have before them the NFL's version of "Mission: Impossible" as they take on the Seahawks at Century Link Field (aka the NFL's version of Devils Island). Are the Cardinals up for the task? They have no choice but to be. Last week the Cardinals edged the Titans in overtime while Seattle buried the hapless Giants at the Meadowlands. If the Cards pull the upset here it would be a gargantuan. However we just have this feeling that the Seahawks are not about to let this happen. Seattle with a win clinches the NFC West Division and will likely lock down the top seed in the NFC playoff bracket. Arizona stays with Seattle for at least the first half, but may not have enough gas in the tank to keep up with the Seahawks for four quarters. They would not be the first opposing team to experience this at Century Link either. Good Luck, Cardinals (Trust me, you'll need it). Seahawks 38 Cardinals 24.
Oakland@San Diego (CBS)- The Chargers are also mathematically alive for a post season birth in the AFC bracket but will need to win out and get lots of help. The Chargers could actually even be eliminated from the post season before this game kicks off, or even before it ends. As for the game San Diego is coming off a huge road win in Denver 10 days earlier while the Raiders got boat-raced at home by the Chiefs last Sunday. The Raiders won the earlier season meeting between the two teams in Oakland. Since that game the Raiders have only won once in seven games. The Chargers have had a rough go if it this season but have won their last two games against the NY Giants and Broncos in rather impressive fashion. The Chargers are at least well rested here and this could make a difference. The Raiders are clearly playing out the string, but would at least love to cancel out the Chargers playoff hopes of they could. A rivalry game will give the Raiders a good deal of motivation, but the Chargers have perhaps a little more to play for here. Chargers 28 Raiders 20.
Chicago@Philadelphia (NBC)- NBC's Sunday Night Football flexed into this game which could be interesting for a number of reasons concerning both teams' post season aspirations. Last weekend Jay Cutler returned to the QB's helm for the Bears and was rusty but still made big plays when most needed (this despite the Bears giving up two touchdowns on turnovers). The Eagles saw their five game winning streak sapped in Minnesota last weekend. The Eagles over the long haul have played the better football however now must find a way to rebound after a bad loss. The Bears with a win combined with losses by the Lions and Packers take the NFC North. The Eagles with a win can actually capture the NFC East if the Redskins can upset the Cowboys (not out of the question). The Eagles have started to win at home again and seem to be having fun out there which is a big edge. The Bears cannot make the same mistakes they made in Cleveland last Sunday and expect a win. Since both teams defenses rank in the lower third of the NFL it will be which offense can make the most of their chances. Nick Foles bests Jay Cutler in a shootout. Eagles 30 Bears 27.
Atlanta@San Francisco (ESPN)- The 49ers and Falcons, two former division rivals get the honors of closing out Candlestick Park in what is likely the final event ever in the 53 year old stadium this Monday night. The 49ers are coming off a business like win in Tampa last weekend while the Falcons edged the Redskins for only their fourth win this season in a year that has just gone completely wrong for them. The 49ers need to keep building on their current three game winning streak if they want to climb higher than the NFC's sixth and final seed. For the Falcons it's about pride and jobs in 2014, but they can still give any team a tough game. The 49ers need to treat the game the same way they took care of business in Tampa last weekend. Focus at the task at hand and build on the things that got them to this point. The 49ers should be able to move the ball on a Falcons defense that is in the lower third of the NFL. The 49ers defense needs to have a strong game and not let the Falcons hang around for too long. The 49ers should be able to handle their business as they bid farewell to their home of 42 years. 49ers 27 Falcons 16. For more information on this game please go to this link: http://goldengatereport.com/articles/49ers-close-out-candlestick-vs-falcons-on-mnf
The Kingshark
Follow me on Twitter @Kingshark49
PS: Have a Very Merry Christmas!!!
*Mandatory Disclaimer: The Kingshark Line is stickily for entertainment purposes only. I have the same exact information that anyone else has and do not claim to know any more or less than the next guy. This is not to promote or encourage gambling on football or any other sport. No point spreads are played here or implied in any way. Scores are for entertainment purposes only and are only based on team trends, team reports, etc. There is no inside information given here or implied. This is just for your information and entertainment. Enjoy the games.


text:
Thursday December 02 2010
KS 2010 LE Deer Opener
Is deer meat good to eat?
Venison can be excellent table fare, and it is lower in calories and saturated fat than beef or chicken. Steps you take in the field play a significant role in how your meat will taste. A clean kill and prompt field dressing are critical. (Make sure you tag the carcass before you move it from the kill site.) Cool the meat quickly and keep it clean, and you'll enjoy many tasty venison meals. Watch the video "How To Field Dress A Deer" to learn some excellent field care techniques.
<object width="444" height="358"><param name="movie" value="http://www.youtube.com/v/Yrc9tO5_KFo?fs=1&hl=en_US&rel=0"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/Yrc9tO5_KFo?fs=1&hl=en_US&rel=0" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="444" height="358"></embed></object>
Ride along with KDWP Game Warden Marvin Peterson on the opening day of the 2010 Kansas Firearm deer season.
There are no options.


text:
El Salvador: Not Just a Haven for Surfers
With 190 miles of coast, replete with warm, sandy beaches that are considered amongst the best in the world by surfers, San Salvador ought to be more renowned. Beachfront property here is inexpensive…you can buy villas just a few steps from the blue Pacific Ocean for less than $100,000.
But El Salvador has more to offer than just its stunning coast-line. With the cosmopolitan capital San Salvador, and an interior that includes volcanoes, hot springs, lakes and waterfalls—this little country has plenty to offer those in search of unspoiled natural beauty.
Get Your Free El Salvador Report Now
Learn more about El Salvador and other countries in our daily postcard e-letter.
Simply enter your email address below and we'll also send you a FREE Report—Unexpected Beauty in El Salvador.
Get Your Free Report Here
Fast Facts About El-Salvador
- Population: 6,108,590
- Capital City: San Salvador
- Climate: Tropical on coast, temperate in uplands
- Time Zone: GMT-6
- Language: Spanish (official)
- Country Code: 503
- Location: Central America, bordering the North Pacific, between Honduras and Guatema
Help rebuild the Great Wall of China: Volunteer adventures in the natural world
Protect the "Land of Fire and Ice" Glaciers, hot springs, volcanoes, midnight sun…hiking, whale-watching, skiing, kayaking…it's no surprise that Iceland has become one of Europe's most popular vacation destinations. Sadly, this increase in mass tourism is taking its toll on the country's fragile ecological environment. British company BTCV offers packages to volunteers interested in conservation […]
Help rebuild the Great Wall of China…and other volunteer adventures in the natural world
The world's longest man-made structure—stretching more than 4,000 miles—China's Great Wall also ranks among the World's 100 Most Endangered Sites. Beyond its restored areas—those that are most-visited by tourists—hundreds of miles lie in disrepair. Volunteer vacationers are sought to help clean and rebuild sections of the wall where restoration projects are already underway.
Clarification Causes Confusion
In May it was announced that visitors to Panama entering on a tourist visa would no longer be granted a 90-day stay (extendable for another 90 days). Instead, immigration officials said, those entering on a tourist visa would be granted just 30 days-extendable up to 60 additional days. This month, rumors began circulating that the […]
Year-round balmy temperatures, exceptional surf, and a beachfront property boom fed by years of peace in El Salvador
A surfers paradise with some of the world's best waves and 190 miles of sandy beaches, warm weather, and water temperatures in the 80s throughout the year, many will find El Salvador's beachfront property market a very attractive proposition.
Can You Turn a Sorpresa From El Salvador Into a Multimillion-dollar Business?
I was driving through the hills just north of San Salvador, enjoying El Salvador's great highway system, when I noticed a sign indicating the turnoff for the village of Ilobasco [ee loh BAHS ko]. I didn't have a strict itinerary to keep, so I took the exit…and discovered a pleasant town of 23,000, which was a center for the production of ceramics as far back as pre-Columbian times, primarily due to the quality of the clay in the area. Today, Ilobasco is the village for the most renowned craft item in El Salvador–the sorpresa, meaning "surprise."
Gastronomical: El Salvador's Sunday Food Festival in Juayúa
The smell of freshly roasted coffee beans wafted through the air as I made my way to El Salvador's famous Sunday food festival which takes place in the small town of Juayúa.
Your Man in El Salvador
I'm looking to retire in Central America. I still haven't pinned down a destination yet, but I wanted to tell you about a contact I made during a recent research trip to El Salvador.
The Best Welcome in El Salvador
Señor Gonzales is a judge in San Salvador, and his wife, Rebeca, is an international lawyer. Usually they live and work in the city, but open up their house to paying guests on the weekends. The hospitality is superb, including some extras like free pancakes and coffee at breakfast, and they invited all their guests to dinner on Sunday. I can't remember ever having been treated so kindly.


text:
XR650R electricity
View Single Post
Studly Adventurer
Joined: Aug 2005
Location: oakland, ca
Oddometer: 919
Originally Posted by
I am in the process of setting up the xr for a large HID. I talked to ricky stator and he informed me that for the size of HID I am planning on using I would need a decent battery to help it start. So I purchased his 200w stator and rectifier/regulator.
Today I looked all over the bike and could not find any place to mount the crf 450 battery that I had just bought. It was the smallest that I could find here in the small town of Camp Verde. I finally decided on putting at the back of the bike behind the airbox. I fabbed up a battery box and mounted it. I wish the battery was a little slimmer but I think it will work ok. Anyone else try this?
Here are some pics of the box I made.
I now need to make a small plastic cover to put over the terminals. I tried the battery the other way but the positive terminal was too close to the mounting bolts, didn't want to short out the battery.
I will install the stator and regulator later this week. I am still waiting on some parts so I can fab the front light. I think I will use a trailtech cage to mount my reflector and ballast.
What do you guys think? Does it look ok or should I start over?
i have a similar battery mounted on my bike using a tray sold by Baja Designs. the tray goes mounted above the engine behind the stator. the way yours is set up looks good but it will take a pounding, i wonder if it will hold in the long run. this is the best picture i have right now of my set up, the battery is right behind the e-start (previous owner install) i'd like to get rid of but love when i'm too hot and tired to kick
it's a great location for the battery, well protected and solidly mounted to the engine.
When the facts change, I change my mind. What do you do, sir?
John Maynard Keynes
Faced with the choice between changing one's mind and proving that there is no need to do so, almost everyone gets busy on the proof."
John Kenneth Galbraith
The object of life is not to be on the side of the majority, but to escape finding oneself in the ranks of the insane.
Marcus Aurelius
View Public Profile
Find More Posts by haggeo