United States Patent (19)
`Falls et al.
`
`54
`
`(75)
`
`TRANSACTION SYNCHRONIZATION IN A
`DISCONNECTABLE COMPUTER AND
`NETWORK
`
`Inventors: Patrick T. Falls, Newbury; Brian J.
`Collins, New Malden; Stephen P. W.
`Draper, Basingstoke, all of United
`Kingdom
`
`87)
`
`Assignee: Novel, Inc., Provo, Utah
`Appl. No.:
`08/700,487
`PCT Fed:
`Jul. 18, 1996
`PCT No.:
`PCT/US96/11901
`S371 Date:
`Jul. 3, 1997
`S 102(e) Date: Jul. 3, 1997
`PCT Pub. No.: WO97/04389
`PCT Pub. Date: Feb. 6, 1997
`Related U.S. Application Data
`Provisional application No. 60/001,261, Jul. 20, 1995.
`Int. Cl. .................................................... G06F 17/00
`U.S. Cl. ....................... 707/202; 707/201; 395/182.1;
`395/182.13
`Field of Search .................................. 707/8, 10, 201,
`707/203, 200, 202; 395/180, 182.1, 182.13
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,575,793 3/1986 Morel et al. ............................ 364/200
`4,622,631 11/1986 Frank et al. ......
`... 364/200
`4,774,655 9/1988 Kollin et al...
`... 364/200
`4,774,661 9/1988 Kumpati........
`... 364/300
`4,827,399 5/1989 Shibayama ...
`... 364/200
`4,878,167 10/1989 Kapuka et al. ..
`... 364/200
`4.941,845 7/1990 Eppley et al. ...
`... 439/505
`5,001,628 3/1991 Johnson et al. ...
`... 364/200
`5,008,814 4/1991 Mathur ..............
`... 364/200
`5,019,963
`5/1991 Alderson et al. .
`... 364/200
`5,043,876 8/1991 Terry ....................................... 364/200
`(List continued on next page.)
`
`USOO5991771A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,991,771
`Nov. 23, 1999
`
`FOREIGN PATENT DOCUMENTS
`87107475 1/1988 European Pat. Off. ........ GO6F 11/14
`92308720 8/1993 European Pat. Off. ........ GO6F 15/16
`9508809 3/1995 European Pat. Off. ........ GO5F 17/30
`95100255 7/1995 European Pat. Off. ........ G06F 17/30
`
`OTHER PUBLICATIONS
`Advance Program-Second Workshop on the Management
`of Replicated Data (WMRD-II), Nov. 12–13, 1992, pp. 1-2.
`“ Application-Aware Adaptation for Mobile Computing”,
`M. Satyanarayanan et al., ACM SIGOS Operating Systems
`Review 29. 1, 1995, pp. 52-55.
`“Architecture of the Ficus Scalable Replicated File System”,
`T. Page, Jr., Computer Science Department Technical Report
`University Of California At Los Angeles, Mar. 1991, pp.
`1-18.
`“Coda: A Highly Available file System for a Distributed
`Workstation Environment, M. Satyanarayanan et al., IEEE
`Transactions. On Computers, vol. 39 No. 4 Apr. 1990, pp.
`447-459.
`“Coding for Compression in Full-Text Retrieval Systems”,
`A. Moffat et al., IEEEDCC Data Compression Conference,
`1992, pp. 72–81.
`(List continued on next page.)
`Primary Examiner Paul V. Kulik
`Attorney, Agent, or Firm-Computer Law
`57
`ABSTRACT
`A method and apparatus are disclosed for Synchronizing
`transactions in a disconnectable network. Each transaction
`includes operations that were performed on a database
`replica on one computer while that computer was discon
`nected from another computer and hence from that other
`computer's replica. Transaction Synchronization, which
`occurs after the computers are reconnected, transferS infor
`mation from each computer to the other computer and
`applies updates to both replicas as appropriate. Transaction
`logs and clash handling tools may be used with the inven
`tion.
`
`34 Claims, 4 Drawing Sheets
`
`COMPUTER
`
`DATABASE MANAGER
`44
`AGENTS ?
`
`
`
`
`
`REPLICA MANAGER
`
`
`
`
`
`28, 40
`
`COMPUTER
`
`DATABASE MANAGER
`
`AGENTS -
`
`
`
`
`
`
`
`REPLCA MANAGER
`
`FILE
`SYSTEM
`INTERFACE
`
`NETWORK
`LINK
`INTERFACE
`
`D.
`
`NETWORK
`LINK
`INTERFACE
`
`FILE
`SYSTEM
`INTERFACE
`
`52
`
`STORAGEDEVICE
`AND CONTROLLER
`REPLCA
`
`56
`
`STORAGEDEVICE
`AND CONTROLLER
`REPLCA
`
`
`
`56
`
`Instacart, Ex. 1006
`
`1
`
`

`

`5,991,771
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,113,519 5/1992 Johnson et al. ......................... 395/600
`5,142,680 8/1992 Ottman et al. ...
`... 395/700
`5,146,561 9/1992 Carey et al. ......
`... 395/200
`5,151,989 9/1992 Johnson et al. ...
`... 395/600
`5,155,847 10/1992 Kirouac et al. ...
`... 395/600
`5,159,669 10/1992 Trigg et al. .......
`... 395/159
`5,170,480 12/1992 Mohan et al. .......................... 395/600
`5,185,857 2/1993 Rozmanith et al. .................... 395/148
`5,212,789 5/1993 Rago .................
`... 395/600
`5,229,768 7/1993 Thomas ..................................... 341/51
`5,237,680 8/1993 Adams et al. ...
`... 395/600
`5,247,683 9/1993 Holmes et al. ......................... 395/700
`5,274,803 12/1993 Dubin et al. ............................ 395/600
`5,276,868
`1/1994 Poole ........
`... 395/600
`5,276.871
`1/1994 Howarth ........
`... 395/600
`5,276.876
`1/1994 Coleman et al. .
`... 395/650
`5,278.979
`1/1994 Foster et al. ......
`... 395/600
`5,278.982
`1/1994 Daniels et al.....
`... 395/600
`5,291,591
`3/1994 Kawano et al. ..
`... 395/600
`5,297.278 3/1994 Wang et al. ......
`... 395/600
`5,313,646 5/1994 Hendricks et al.
`... 395/600
`5,317,728 5/1994 Tevis et al. .......
`... 395/600
`5,321,832 6/1994 Tanaka et al. ....
`... 395/600
`5,325,524 6/1994 Black et al. ......
`... 395/600
`5,333,315
`7/1994 Saether et al. ...
`... 395/600
`5,347,653 9/1994 Flynn et al. ..
`... 395/600
`5,355,476. 10/1994 Fukumara .....
`... 395/600
`5,375,207 12/1994 Blakely et al. ...
`... 395/200
`5,377,326 12/1994 Murata et al. ...
`... 395/200
`5,388.256 2/1995 Herbert .............
`... 395/600
`5,390,335 2/1995 Stephan et al.
`... 395/800
`5,403,639 4/1995 Belsan et al. .
`... 395/600
`5,408,619 4/1995 Oran ..............
`... 395/325
`5,410,543 4/1995 Seitz et al. ........
`370/85.13
`5,410,684 4/1995 Ainsworth et al.
`... 395/575
`5,412,801 5/1995 de Remer et al. ...................... 395/575
`5,418,957 5/1995 Narayan .................................. 395/700
`5,423,034 6/1995 Cohen-Levy et al.
`... 395/600
`5,430.871
`7/1995 Jamoussi et al. .....
`... 395/600
`5,434,994 7/1995 Shaheen et al. ..
`... 395/500
`5,452,450 9/1995 Delory ..........
`... 395/600
`5,553,279 9/1996 Goldring .......
`... 395/600
`5,588,147 12/1996 Neeman et al.
`... 395/601
`5,613,113 3/1997 Goldring .......
`... 395/618
`5,666.530 9/1997 Clark et al. ...
`... 395/617
`5,684,984 11/1997 Jones et al. ............................. 395/610
`5,692,129 11/1997 Sonderegger et al.
`... 395/200.11
`5,710,922
`1/1998 Alley et al. ............................. 395/617
`5,737,600 4/1998 Geiner et al. .
`... 395/616
`5,737,601
`4/1998 Jain et al. .....
`... 395/617
`5,740,433 4/1998 Carr et al......
`... 395/618
`5,761,660 6/1998 Josten et al. ................................ 707/8
`5,774,717 6/1998 Porcaro .........
`... 707/202
`5,778,390 7/1998 Nelson et al.
`... 707/204
`5,806,075 9/1998 Jain et al. .....
`... 707/201
`5,832,518 11/1998 Mastors .........
`... 707/202
`3/1999 Draper et al. ........................
`707/202
`5,878,434
`OTHER PUBLICATIONS
`“A compact representation for file versions: a preliminary
`report", A. Black et al., 5" IEEE Conference On Data
`Engineering, 1989, pp. 321-329.
`“Concurrency Control and Consistency of Multiple Copies
`of Data in Distributed INGRES', M. Stonebraker, IEEE
`Transactions. On Software Engineering, vol. SE-5, No. 3,
`May 1979, pp. 188–194.
`“Conflict Detection Tradeoffs for Replicated Data”, M.
`Carey et al., ACM Transactions On Database Systems, vol.
`16, No. 4, Dec. 1991, pp. 703–746.
`
`
`
`“Countdown to Mobile Blast-Off", I. Brodsky, Network
`World, Feb. 19, 1996, pp. 44–46,52.
`“Data Management for Mobile Computing”, T. Imielinski et
`al., ACM SIGMOD Record, vol. 22, No. 1, Mar. 1993, pp.
`34-39.
`“Data Replicas in Distributed Information Services”, H.
`Gladney, ACM Transactions On Database Systems, vol. 14,
`No. 1, Mar. 1989, pp. 75–97.
`“Database System Issues in Nomadic Computing”, R.
`Alonso et al., ACM SIGMOD Record, 22 2, 1993, pp.
`388-392.
`“DGDBM: Programming Support for Distributed Transac
`tions Over Replicated Files”, M. Franky, ACM SIGOS
`Operating Systems Review, 293, Jul. 1995, pp. 64–74.
`“Disconnected Operation for AFS, L. Huston et al., Mobile
`and Location-Independent Computing Symposium,
`USENIX Association, 1994, pp. 1-10.
`“Disconnected Operation in the Coda File System”, J.
`Kistler et al., ACM Operating Systems Review, 255, 1991,
`pp. 213-225.
`“Disconnected Operation in a Distributed File System”, J.
`Kistler, Ph.D. thesis, Department of Computer Science,
`Carnegie Mellon University, May 1993, pp. 1-186.
`“Discord in hardwareland', T. Schmidt, Network World,
`Feb. 19. 1996, p. 47.
`“Distributed Logging for Transaction Processing”, D.
`Daniels et al., ACM, 1987, pp. 82–96.
`“Experience with Disconnected Operation in a Mobile Com
`puting Environment, M. Satyanarayanan et al., Mobile and
`LOcation-Independent Computing Symposium, 1994, pp.
`11-28.
`“Fixed Length Semiorder Preserving Code for Field Level
`Data File Compression”, M. Toyama et al., IEEE First
`International Conference on Data Engineering, 1984, pp.
`244-252.
`“Flexible and Safe Resolution of File Conflicts”, P. Kumar
`et al., 1995 UESNIX Technical Conference, Jan. 16–20,
`1995, pp. 95-106.
`“The Generalized Tree Quorum Protocol: An Efficient
`Approach for Managing Replicated Data”, D. Agrawal et al.,
`ACM Transactions on Database Systems, vol. 17, No. 4,
`Dec. 1992, pp. 689-717.
`“A Generic Multicast Transport Service to Support Discon
`nected Operation”, S. Maffeis et al., Mobile and Location
`-Independent Computing Symposium, 1995, pp. 79-89.
`“Getting Your Byte's Worth”, S. Vaughan-Nichols, Byte,
`Nov. 1990, pp. 331-336.
`“Grapevine: An Exercise in Distributed Computing Ab
`stract”, A. Birrell et al., Communications of the ACM, vol.
`25, No. 4, Apr. 1982, pp. 260-261.
`“Going Mobile”, S. Biagi, Network Var, Apr. 1996, p. 14.
`“Impact of Mobility on Distributed Computations”, B.
`Badrinath et al., ACM SIGOS Operating Systems Review, 27
`2, 1993, pp. 15–20.
`“An Introduction to Database Systems vol. II”, C. Date,
`Addison-Wesley Publidhing Company, 1993, pp. 1-33,
`291-340.
`“Isolation-Only Transactions for Mobile Computing”, Q.
`Lu et al., ACM SIGOS Operating Systems Review, 28 2,
`1994, pp. 81-87.
`“Log-Based Directory Resolution in the Coda File System”,
`P. Kumar et al., IEEE, 1993, pp. 202-213.
`“The Lotus NotesTM Storage System”, K. Moore, ACM
`SIGMOD Record, 24 2, 1995, pp. 427–428.
`
`2
`
`

`

`5,991,771
`Page 3
`
`“Low Cost Management of Replicated Data in Fault-Tol
`erant Distributed Systems”, T. Joseph et al., ACM Transac
`tions on Computer Systems, vol. 4, No. 1, Feb. 1986, pp.
`54-7O.
`“Maintaining Availability in Partitioned Replicated Data
`bases”, A. Abbadi et al., ACM Transactions on Computer
`Systems, vol. 14, No. 2, Jun. 1989, pp. 264-290.
`“Model Based Concordance Compression”, A. Bookstein et
`al., IEEE DCC Data Compression Conference, 1992, pp.
`82-91.
`“The Multicast Policy and Its Relationship to Replicated
`Data Placement’, O. Wolfson et al., ACM Transactions On
`Database Systems, vol. 16, No. 1, Mar. 1991, pp. 181-205.
`“A Multi-Group Technique for Data Compression', K.
`Hazboun et al., ACM SIGMOD Conference, 1982, pp.
`284-292.
`“NetWare 4 for Professionals', D. Bierer et al., New Riders
`Publishing, 1993, pp. 359-374.
`“A Non-Blocking Transaction Data Flow Graph Based
`Approach For Replicated Data”, P. Krishna Reddy et al.,
`Operating Systems Review (SIGOPS) 27 No. 3, Jul. 1993,
`pp. 46-54.
`“Partially Connected Operation’, L. Huston et al., Mobile
`and Location-Independent Computing Symposium, 1995,
`pp. 91-97.
`“Peephole Log Optimization’, L. Huston et al., IEEE Work
`Shop On Mobile Computing Systems and Applications, Dec.
`1994, pp. 1-8.
`“Performing Remote Operations Efficiently on a Local
`Computer Network”, A. Spector, Communications of the
`ACM, vol. 25, No. 4, Apr. 1982, pp. 246-259.
`“Primarily Disconnected Operation: Experiences with
`Ficus”, J. Heidemann et al., IEEE, 1992, pp. 2-5.
`“Replicated Data in a Distributed Environment, M. Colton,
`ACM SIGMOD Record, 222, 1993, pp. 464–466.
`“Remote access can't slow down', H. Allard, Network
`World, Feb. 19, 1996, p. 53.
`“A Replicated UNIX File System (Extended Abstract)", B.
`Liskov et al., ACM SIGOS Operating Systems Review, 251,
`1991, pp. 60–64.
`“Replication in the Harp File System”, B. Liskov, ACM
`Operating Systems Review, 255, 1991, pp. 226-238.
`“Resolving File Conflicts. In The Ficus File System”, P.
`Reiher et al., 1994 Summer Usenix, Jun. 6-10, 1994, pp.
`183-195.
`
`“RFS Architectural Overview', A. Rifkin et al., Jun. 1986,
`pp. 248-259.
`“Scalable, Secure, and Highly Available Distributed File
`Access”.M. Satyanarayanan, Computer 23 No.5, May 1990,
`pp. 9-20.
`“A Snapshot Differential Refresh Algorithm, B. Lindsay et
`al., ACM SIGMOD Record, 15 2, 1986, pp. 53–60.
`“Software spins wheels in niche markets’, K. Scherberger,
`Network World, Feb. 19, 1996, p. 49.
`Space and Time Savings Through Large Data Base Com
`pression and Dynamic Restructuring, P. Alsberg, Proceed
`ings of the IEEE, Vol. 63, No. 8, Aug. 1975, pp. 1114-1122.
`“Sun-3 Architecture” Anon., Aug. 1986, pp. 8-9, 49–57.
`“Supporting Application-Specific Resolution in an Optimis
`tically Replicated File System”, P. Kumar et al., IEEE, 1993,
`pp. 66-70.
`“System Isolation and Network Fast-Fail Capability in
`Solaris', G. Montenegro et al., Mobile and Location-Inde
`pendent Computing Symposium, 1995, pp. 67-78.
`“Transaction Support in a Log-Structured File System”, M.
`Seltzer, IEEE Ninth International Conference On Data
`Engineering, 1993, pp. 503–510.
`“The Transparent Remote File System”, R. Hughes, Date
`Unknown.
`“Two Levels of Filesystem Hierarchy on One Disk', V. Cate,
`Department of Computer Science, Carnegie Mellon Univer
`sity, May 1990, pp. 1-20.
`“Using Prospero to Support Integrated Location-Indepen
`dent Computing, B. Neuman et al., Mobile and Location
`Independent Computing Symposium, 1994, pp. 29–34.
`“Wireless IR lets mobile devices get personal” (partial
`article).J. Edney, Electronic Engineering Times, Feb. 19,
`1996, p. 44.
`“Wireless LANs roaming for standards” (partial article),
`unknown, Electronic Engineering Times, Feb. 19, 1996, p.
`65.
`“Wireless nets come of age”, I. Gillott, Network World, Feb.
`19, 1996, pp. 50, 52.
`Summary of Fitler et al. Invention, 1992.
`Mobile NetWare Lite Specification, Version 1.0, Aug. 20,
`1992 (best available copy).
`
`3
`
`

`

`U.S. Patent
`U.S. Patent
`
`Nov. 23, 1999
`Nov. 23, 1999
`
`Sheet 1 of 4
`Sheet 1 of 4
`
`5,991,771
`5,991,771
`
`oy
`
`is,
`4) ae
`
`N
`
`20,24,28
`
`”
`
`s
`FIG.1
`
`Zz
`OTHER
`DS20,28,36we|) ]
`°oo EI2ol(JOl
`STORAGE
`OS O N
`716,28GSSC]
`
`MEDIA
`
`a
`
`
`
`14
`
`/
`IDE
`
`2
`
`CO
`N4
`O
`s
`H
`u
`2
`
`e oO=-L
`
`nx
`
`
`
`S5
`34
`
`16,28,38
`
`4
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 2 of 4
`
`5,991,771
`
`
`
`YAOVNVWVOINIdSsdy
`
`dls
`
`WALSAS
`
`AOVAYALNI
`
`MHOMLAN
`
`ANIM
`
`AOVAYSALNI
`
`9S
`
`VOMd3u
`
`
`
`ADIAAGADVHOLS
`
`
`
`YATIOWLNOOGNV
`
`vv
`
`ySLNADV
`
`
`
`HAOVNVWASVEVLVG
`
`YHALNdNOO
`
`COLA
`
`ASVaEVLVd
`
`AOVAYALNIAOVAYALNI
`MHOMLANAls
`
`ANI]WALSAS
`
`
`
`YAOVNVWVOlIdSY
`
`rr
`
`{SiNa9Vv|
`
`HAOVNVW
`
`9S
`
`VOMd4Y
`
`
`
`AOIAACADVYOLS
`
`
`
`YATIOWLNOOCNV
`
`5
`
`
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 3 of 4
`
`5,991,771
`
`REPLICA MANAGER
`
`
`
`REPLICA DISTRIBUTOR
`
`
`
`46
`
`CONSISTENCY DISTRIBUTOR
`
`70
`
`LOCATION DISTRIBUTOR
`
`OBJECT DISTRIBUTOR
`
`OBJECT SCHEMA
`
`FILE DISTRIBUTOR
`
`REPLICA PROCESSOR
`
`CONSISTENCY PROCESSOR
`
`72
`
`LOCATION STATE PROCESSOR
`
`OBJECT PROCESSOR
`
`TRANSACTION LOGGER
`
`FILE PROCESSOR
`
`
`
`TRIGGER FUNCTION REGISTRATIONS
`
`94
`
`FIG. 3
`
`6
`
`

`

`U.S. Patent
`
`Nov. 23, 1999
`
`Sheet 4 of 4
`
`5,991,771
`
`OBTAIN NETWORK CONNECTION
`
`1 OO
`
`RECORD TRANSACTION
`
`IDENTIFY FIRST TRANSACTION
`
`LOCATE REPLICA TO SYNCHRONIZE
`
`TRANSFER UPDATE FROM FIRST
`COMPUTER TO SECOND COMPUTER
`
`DETECT MISSED UPDATE
`
`APPLY UPDATE TO REPLICAON
`SECOND COMPUTER
`
`RECORD TRANSACTION
`
`IDENTIFY SECONDTRANSACTION
`
`TRANSFER UPDATE FROM SECOND
`COMPUTER TO FIRST COMPUTER
`
`DETECT MISSED UPDATE
`
`APPLY UPDATE TO REPLICAON
`FIRST COMPUTER
`
`FIG. 4
`
`1 O2
`
`104
`
`1 O6
`
`1 O8
`
`11 O
`
`112
`
`14
`
`7
`
`

`

`1
`TRANSACTION SYNCHRONIZATION INA
`DISCONNECTABLE COMPUTER AND
`NETWORK
`
`This application is a 371 of PCT/US96/11901 filed Jul.
`18, 1996. This case claims benefit of provisional application
`Ser. No. 60/001261 filed Jul. 20, 1995.
`
`5
`
`FIELD OF THE INVENTION
`The present invention relates to the Synchronization of
`transactions performed on Separated disconnectable
`computers, Such as transactions performed on a mobile
`computer and on a computer network while the mobile
`computer and the network are disconnected, or transactions
`performed on Separate Server computers in a network. More
`particularly, the present invention relates to the Synchroni
`Zation of transactions when the Separate computers are
`reconnected.
`
`15
`
`TECHNICAL BACKGROUND OF THE
`INVENTION
`It is often convenient, and Sometimes essential, to carry a
`computer and Selected data while traveling. It may also be
`convenient or essential to access a computer network using
`a “mobile computer Such as a laptop, palmtop, notebook, or
`personal digital assistant. However, different types of mobile
`computing make very different assumptions about the use
`and availability of computer networkS.
`Some mobile computers are not ordinarily connected to a
`computer network. Like their non-traveling "Stand-alone”
`counterparts, Such “walk-alone” computers cannot be con
`nected to a network unless significant hardware or software
`modifications are made to them or to the network.
`“Mobile-link' portable computers are typically connected
`to a computer network and attempt (with varying degrees of
`Success) to maintain that network connection during mobile
`use through a wireleSS link. Typical wireleSS links use radio
`waves or infrared light as carriers. Mobile-link computers
`can be used in a walk-alone mode if the network connection
`is lost. However, mobile-link systems provide few or no
`automatic facilities to Synchronize the mobile-link computer
`with the network when the connection is re-established.
`“Disconnectable' computers include portable computers
`that operate in either a walk-alone or a mobile-link mode and
`provide Significant automated facilities for Synchronizing
`operations performed on the mobile computer with opera
`tions performed on the network. Disconnectable computers
`need not be portable. For instance, Separate Server comput
`ers in a wide-area network (WAN) or other network that are
`connected to one another only sporadically or at intervals
`may be disconnectable computers.
`Unfortunately, conventional disconnectable computers
`Still rely routinely on manually directed file copying to Select
`the data that will be used in the field. Moreover, conven
`tional disconnectable computer Systems are not easily
`extended to Support a variety of database formats, and they
`do not properly handle the Situation in which changes to the
`“Same' data are made on both the portable computer and on
`a network computer during disconnected operation.
`For instance, the Coda File System (“Coda") is a client
`Server System that provides limited Support for disconnect
`able operation. To prepare for disconnection, a user may
`hoard data in a client cache by providing a prioritized list of
`files. On disconnection, two copies of each cached file exist:
`the original Stored on the Server, and a duplicate Stored in the
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,991,771
`
`2
`disconnected client's cache. The user may alter the duplicate
`file, making it inconsistent with the Server copy. Upon
`reconnection, this inconsistency may be detected by com
`paring timestamps.
`However, the inconsistency is detected only if an attempt
`is made to access one of the copies of the file. The Coda
`System also assumes that the version Stored in the client's
`cache is the correct version, So Situations in which both the
`original and the duplicate were altered are not properly
`handled. Moreover, the Coda Synchronization mechanism is
`Specifically tailored, not merely to file Systems, but to a
`particular file System (a descendant of the Andrew File
`System). Coda provides no Solution to the more general
`problem of Synchronizing transactions in a distributed data
`base that can include objects other than file and directory
`descriptors.
`Some approaches to distributed database replication are
`not directed to mobile computing per Se but do attempt to
`ensure consistency between widely Separated replicas that
`collectively form the database. Examples include, without
`limitation, the replication Subsystem in Lotus Notes and the
`partition synchronization Subsystem in Novell NetWare(R)
`4.1 (LOTUS NOTES is a trademark of International Busi
`ness Machines, Inc. and NETWARE is a registered trade
`mark of Novell, Inc.).
`However, Some of these approaches to replication are not
`transactional. A transaction is a Sequence of one or more
`operations which are applied to a replica on an all-or-nothing
`basis. Non-transactional approaches may allow partially
`completed update operations to create inconsistent internal
`States in network nodes. Non-transactional approaches may
`also require a Synchronization time period that depends
`directly on the total number of files, directories, or other
`objects in the replica. This Seriously degrades the perfor
`mance of Such approaches when the network connection
`used for Synchronization is relatively slow, as many modem
`or WAN links are.
`Moreover, in Some conventional approaches potentially
`conflicting changes to a given Set of data are handled by
`Simply applying the most recent change and discarding the
`others. Another drawback of Several conventional
`approaches to replication is the requirement they impose that
`either or both computer systems be locked out of use while
`the replicas are being Synchronized.
`Another drawback of conventional disconnected comput
`ing approaches is that the location of data on the mobile
`computer does not always correspond to its location on the
`network computer. Files may be located in one Subdirectory
`or on one drive during connected operation and in another
`Subdirectory or on another drive during disconnected opera
`tion. Thus, the mobile computer does not present the same
`view of the network when it is disconnected as it does when
`connected to the network. In addition to creating a risk of
`confusion and conflicting file versions, these conventional
`approaches require users to repeatedly reconfigure applica
`tion programs to look for data in different locations.
`Thus, it would be an advancement in the art to provide a
`System and method for properly Synchronizing transactions
`when a disconnectable computer is reconnected to a net
`work.
`It would be an additional advancement to provide Such a
`System and method which identify potentially conflicting
`database changes and allow their resolution by either auto
`matic or manual means.
`It would also be an advancement to provide Such a System
`and method which are not limited to file System operations
`but can instead be extended to Support a variety of database
`objects.
`
`8
`
`

`

`5,991,771
`
`3
`It would be an additional advancement to provide Such a
`System and method which do not require a Synchronization
`time period that depends directly on the total number of files,
`directories, or other objects in the replica.
`It would be a further advancement to provide such a
`system and method which do not lock either the mobile
`computer or the network computers during Synchronization.
`It would be an additional advancement to provide Such a
`System and method which present consistent file locations
`regardless of whether the mobile computer is connected to
`the network.
`Such a System and method are disclosed and claimed
`herein.
`
`15
`
`4
`prior to disconnection as a basis for the mobile computer's
`Virtual network. Copying is accomplished using a device
`controller in each computer, a replica manager on each
`computer, and the network link. The device controller on
`each computer communicates with that computer's Storage
`device to control data transferS.
`Each computer's replica manager communicates with the
`device controller of that computer and with the network link.
`Each replica manager also communicates with a database
`manager on its computer. The database manager can Send
`database transactions to the device controller only through
`the replica manager, allowing the replica managers to log
`transactions and to Synchronize the transactions after the
`network connection is re-established.
`Each replica manager includes a replica distributor and a
`replica processor. The replica distributor insulates the data
`base manager from the complexities caused by having target
`database entries Stored in replicas on multiple computers,
`while Still allowing the database manager to efficiently
`acceSS and manipulate individual target database objects,
`variables, and/or records. The replica processor maintains
`information about the location and Status of each replica and
`ensures that the replicas tend to converge.
`The network link Supports a remote procedure call
`(“RPC"), distributed memory, or similar mechanism to
`allow replica distributors to call procedures in the replica
`processors on or more network computers. The network link
`also tracks connectivity information Such as which network
`computers are currently accessible and what State those
`computers are in.
`Each replica distributor includes at least a consistency
`distributor and a location distributor, and each replica pro
`ceSSor includes at least a consistency processor and a
`location State processor. The consistency distributors and
`consistency processors maintain convergent consistency of
`the target database replicas. The location distributors and the
`location State processors are used to determine the Storage
`locations of database entries.
`The replica distributor may also include an object dis
`tributor and an object Schema, in which case the correspond
`ing replica processor includes an object processor. The
`object distributor provides an interface to target database
`objects, making operations Such as "add object”, “modify
`object', and “read object' available. The objects are defined
`using a compile-time Schema definition language. The data
`base manager and various Subsystems of the replica manager
`can all query the object Schema to obtain information
`regarding the format and Storage requirements of objects,
`but Semantic interpretation of object values is generally
`restricted to the database manager.
`One embodiment of the replica processor also includes a
`transaction logger which maintains a log of recent updates
`for each object in the target database. This log allows
`recovery of local transactions after power losses or other
`unexpected interruptions. The transaction log at a given
`location also provides an efficient Source of the updates
`needed to bring other locations up to date. Transaction logs
`are further, described in a commonly owned copending
`application Ser. No. 08/700,490, entitled TRANSACTION
`LOG MANAGEMENT IN ADISCONNECTABLE COM
`PUTER AND NETWORK, filed the same day and having
`the same inventors as the present application.
`In one embodiment, the replica distributor and replica
`processor contain a file distributor and a file processor,
`respectively. These file Subsystems provide access to file
`contents for operations such as “read” and “write” on file
`
`25
`
`BRIEF SUMMARY OF THE INVENTION
`The present invention provides a System and method
`which facilitate disconnected mobile computing in Several
`wayS. Prior to disconnection, the invention allows network
`administrators or users to readily Select data that should be
`copied from a network to a mobile computer by Simply
`identifying one or more target database Subtrees. During
`disconnected operation of the mobile computer, the inven
`tion presents the user with a “virtual network” environment
`that is consistent in use and appearance with the Selected
`portion of the actual network.
`Finally, upon reconnection of the mobile computer to the
`network, the invention Synchronizes operations performed
`on the mobile computer during the disconnected interval
`with operations performed on the network during that inter
`val. Synchronization is both Substantially automatic and
`transactional, So minimal user intervention is needed and
`inconsistent internal States are avoided. Moreover, Synchro
`nization does not routinely discard any of the changes made
`on either the network or the mobile computer.
`One embodiment of a System according to the present
`invention includes at least two computers capable of being
`connected by a network link. One computer will act as the
`mobile computer, while the other acts as the network. Of
`course, the network may also include more than one com
`40
`puter after the mobile computer is disconnected. Suitable
`mobile computers include laptops, palmtops, notebooks, and
`personal digital assistants. Suitable network computers
`include additional mobile computers as well as desktop,
`tower, WorkStation, micro-, mini-, and mainframe comput
`erS. Suitable network links include packet-based, Serial,
`internet-compatible, local area, metropolitan area, wide
`area, and wireleSS network linkS.
`Each of the computers includes a non-volatile Storage
`device Such as a magnetic or optical disk or disk array.
`Initially, the Storage device on the network computer con
`tains at least a portion of a target database. The target
`database includes file descriptors, directory descriptors,
`directory Services objects, printer jobs, or other objects. The
`target database is a distributed database whose entries may
`be kept in one or more replicas on different computers.
`Each replica of the target database contains at least Some
`of the same variables or records as the other replicas, but
`different replicas may temporarily contain different values
`for the same variable or record. Such inconsistencies are
`temporary because changes in value are propagated through
`out the replicas by the invention. Thus, if the changes to a
`particular variable or record are infrequent relative to the
`propagation delay, then all replicas will converge until they
`contain the same value for that variable or record.
`Selected portions of the database may be copied from the
`network computer to the mobile computer's Storage device
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`9
`
`

`

`5,991,771
`
`15
`
`35
`
`40
`
`25
`
`S
`objects. The file distributor and processor insulate the data
`base manager from complexities caused by the distributed
`nature of the target database files. More generally, the replica
`managers intercept any file System or operating System call
`that directly accesses replicated files or database entries, So
`that consistent convergent replicas are maintained.
`One embodiment of the replica manager contains trigger
`function registrations. Each registration associates a trigger
`function with a target database operation Such that the
`registered trigger function will be invoked on each replica,
`once the computers are connected, if the associated opera
`tion is requested of the database manager. The trigger
`function is invoked on each replica after the associated
`operation request is transmitted from the database manager
`to the replica manager. Trigger functions can be used to
`handle taskS Such as file replication, where the file contents
`are not directly accessed by the database manager, while
`ensuring that files converge in a manner consistent with the
`database operation.
`In operation, the replica managerS Synchronize transac
`tions upon reconnection in the following manner. Using the
`network link, a network connection is created between the
`mobile computer and a network computer. The network
`computer need not be the network computer from which the
`mobile computer was disconnected. The replica manager on
`the mobile computer identifies a transaction that targets an
`object in a replica on the mobile computer, and locates a
`corresponding replica that resides on the network computer.
`The mobile computer then transfers an update based on the
`transaction over the network connection to the network
`computer.
`Meanwhile, the replica manager on the network computer
`performs similar Steps, determining whether another trans
`action targeted an entry in the network computer replica and
`transferring an update based on any Such transaction to the
`mobile computer's replica manager over the same network
`connection. The respective replica managers then apply the
`transaction updates to their respective replicas. The proceSS
`is repeated for any other replicas in the network, with pairs
`of replica managers propagating the updates from the mobile
`computer throughout the network.