US005991771A
`
`
`
`5,991,771
`(114) Patent Number:
`United States Patent 55
`
`
`
`
`
`
`
`
`
`
`
`
`Falls et al.
`[45] Date of Patent:
`Nov. 23, 1999
`
`
`
`
`
`
`
`
`
`[54] TRANSACTION SYNCHRONIZATIONIN A
`NITWORR COMPUTER AND
`
`
`
`
`
`[75]
`
`
`
`:
`.
`:
`.
`
`
`
`
`
`Inventors: Patrick T. Falls, Newbury; Brian J.
`
`
`
`
`Collins, New Malden; Stephen P. W.
`
`
`
`
`
`Draper, Basingstoke, all of United
`
`Kingdom
`
`[86]
`
`[87]
`
`
`
`
`
`
`
`
`
`
`
`[73] Assignee: Novell, Inc., Provo, Utah
`.
`
`
`
`[21] Appl. No.:
`08/700,487
`PCT Filed:
`Jul. 18, 1996
`[22]
`
`
`
`
`
`PCT No.:
`PCT/US96/11901
`
`
`§ 371 Date:
`Jul. 3, 1997
`
`
`
`
`
`
`
`
`
`§ 102(c) Date:
`Jul. 3, 1997
`:
`
`
`
`
`PCT Pub. No; WO97/04389
`PCT Pub. Date: Feb. 6, 1997
`
`
`
`
`
`
`
`
`
`Related U.S. Application Data
`
`
`
`
`
`
`
`[60]
`Provisional application No. 60/001,261, Jul. 20, 1995.
`6
`
`
`
`
`
`[S51]
`Tint, Ce ccecceeseecneceneceneeenessenee GO06F 17/00
`
`
`
`
`
`
`[52] U.S. Ch.eee 707/202; 707/201; 395/182.1;
`
`395/182.13
`.
`
`
`
`
`
`
`[58] Field of Search 0...eee 707/8, 10, 201,
`
`
`
`
`
`
`707/203, 200, 202; 395/180, 182.1, 182.13
`
`[56]
`
`
`
`87107475
`
`92308720
`9508809
`95100255
`
`
`
`
`FOREIGN PATENT DOCUMENTS
`1/1988 European Pat. Off.
`........ GO6F 11/14
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8/1993 European Pat. Off.
`........ GOOF 15/16
`
`
`
`
`
`
`
`3/1995 European Pat. Off.
`........ GOSF 17/30
`7/1995 European Pat. Off.
`....... GO6F 17/30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`Advance Program—Second Workshop on the Management
`
`
`
`
`
`
`
`
`of Replicated Data(WMRD-I]), 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`raiversity Of California At Los Angeles, Mar. 1991, pp.
`
`“Coda: A Highly Available file System for a Distributed
`
`
`
`
`
`
`
`
`
`
`Workstation Environment”, M. Satyanarayananet al., JEEE
`Transactions On Computers, vol. 39 No. 4 Apr. 1990, pp.
`
`
`
`
`
`
`
`
`447-459.
`
`
`
`
`“Coding for Compression in Full-Text Retrieval Systems”,
`
`
`
`
`
`
`A. Moffatet al., IEEE DCC Data Compression Conference,
`
`
`
`1992, pp. 72-81.
`(List continued on next page.)
`
`
`
`Primary Examiner—Paul V. Kulik
`
`
`
`
`
`
`
`
`Attorney, Agent, or Firm—Computer Law
`
`
`ABSTRACT
`[57]
`A method and apparatus are disclosed for synchronizing
`
`
`
`
`
`
`
`transactions in a disconnectable network. Each transaction
`
`
`
`
`
`
`
`
`
`
` ‘imeludes 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-
`
`
`
`
`
`
`
`h
`the
`t
`ter
`to
`:
`i
`oth
`d
`
`
`
`
`
`
`
`Mation trom each
`computer
`the other computer an
`to
`
`
`
`
`
`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
`
`
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`ccscccccscsscsscssseeeeeeee 364200
`3/1986 Motel et al.
`4,575,793
`
`
`
`
`
`
`.. 364/200
`11/1986 Franketal. ......
`4,622,631
`
`
`
`
`
`
`
`... 364/200
`9/1988 Kollin et al.
`4,774,655
`..
`
`
`
`
`
`
`
`
`
`
`
`«364/300
`9/1988 Kumpati........
`4,774,661
`
`
`
`
`
`s- 364/200
`5/1989 Shibayama....
`4,827,399
`
`
`
`
`
`
`
`..
`«- 364/200
`4,878,167 10/1989 Kapulka et al.
`.. 439/505‘
`7/1990 Eppleyetal. ....
`4,941,845
`
`
`
`
`
`
`
`... 364/200
`3/1991 Johnsonetal....
`5,001,628
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`w.. 364/200
`5,008,814
`4/1991 Mathur .............
`w 364/200
`5/1991 Alderson etal. .
`5,019,963
`
`
`
`
`
`
`8/1991 Terry ceesccsccscsscsssssessesserserseesoeee 364/200
`5,043,876
`
`
`
`
`
`
`
`
`
`(List continued on next page.)
`
`COMPUTER
`
`
`
`
`
`
`
`
`
`
`
`
`DATABASE MANAGER
`DATABASE MANAGER
`
`
`
`
`44
`
`
`
`
`ps
`
`
`
`}/—
`AGENTS
`AGENTS }
`
`
`
`
`REPLICAMANAGER
`
`
`Ls
`
`
`
`NETWORK
`FILE
`NETWORK
`
`
`FILE
`a
`
`
`
`
`
`LINK
`SYSTEM
`SYSTEM
`LINK
`
`
`
`
`INTERFACE
`INTERFACE
`INTERFACE
`INTERFACE
`
`
`
`
`
`
`
`
`
`
`STORAGE DEVICE
`STORAGE DEVICE
`
`
`
`
`
`AND CONTROLLER
`AND CONTROLLER
`
`56
`
`
`
`
`
`56
`REPLICA
`
`REPLICA
`
`
`
`
`
`
`
`
`
`
`|
`
`
`COMPUTER
`
`
`
`
`
`
`
`
`
`REPLICA MANAGER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Starbucks Corporation,et al. - Ex. 1017
`U.S. Patent No. 9,454,748
`
`Starbucks Corporation, et al. - Ex. 1017
` U.S. Patent No. 9,454,748
`
`

`

`
`5,991,771
`
`
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`5,113,519
`5/1992 Johnson et al. wv. 395/600
`
`
`
`
`
`
`8/1992 Ottmanetal. ....
`.. 395/700
`5,142,680
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9/1992 Carey etal.
`......
`.. 395/200
`5,146,561
`9/1992 Johnsonetal. ...
`.. 395/600
`5,151,989
`
`
`
`
`
`
`
`5,155,847 10/1992 Kirouacetal. ...
`.. 395/600
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10/1992 Trigg et al.
`.......
`. 395/159
`5,159,669
`5,170,480 12/1992 Mohanet al. oo... ee eeeeeeee 395/600
`
`
`
`
`
`
`5,185,857
`2/1993 Rozmanith et al. owe 395/148
`
`
`
`
`
`
`5/1993 Rago veers
`.. 395/600
`5,212,789
`
`
`
`
`
`
`
`7/1993 Thomas vaccccscssssssssesesevesseseeeeeee 341/51
`5,229,768
`
`
`
`
`
`
`5,237,680
`8/1993 Adamsetal. ....
`.. 395/600
`
`
`
`
`
`
`
`9/1993 Holmeset al. woe eceeeeee 395/700
`5,247,683
`
`
`
`
`
`
`12/1993 Dubin et al. ee eeeeeee 395/600
`5,274,803
`
`
`
`
`
`
`5,276,868
`1/1994 Poole ........
`.. 395/600
`
`
`
`
`
`
`
`1/1994 Howarth........
`.. 395/600
`5,276,871
`
`
`
`
`
`
`1/1994 Colemanetal. .
`.. 395/650
`5,276,876
`
`
`
`
`
`
`
`1/1994 Fosteret al.
`......
`.. 395/600
`5,278,979
`
`
`
`
`
`
`
`
`5,278,982
`1/1994 Danielsetal. ....
`.. 395/600
`
`
`
`
`
`
`
`3/1994 Kawanoet al.
`.. 395/600
`..
`5,291,591
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5,297,278
`3/1994 Wang et al.
`......
`.. 395/600
`5/1994 Hendricksetal.
`.. 395/600
`5,313,646
`
`
`
`
`
`
`5,317,728
`5/1994 Tevis etal. .......
`.. 395/600
`
`
`
`
`
`
`
`6/1994 Tanakaetal. ....
`.. 395/600
`5,321,832
`
`
`
`
`
`
`
`
`5,325,524
`6/1994 Black et al.
`......
`.. 395/600
`
`
`
`
`
`
`
`
`....
`7/1994 Saetheret al.
`.. 395/600
`5,333,315
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`9/1994 Flynn et al.
`..
`.. 395/600
`5,347,653
`
`10/1994 Fukumara.....
`... 395/600
`5,355,476
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5,375,207 12/1994 Blakely et al.
`.. 395/200
`..
`
`12/1994 Murata et al.
`.. 395/200
`....
`5,377,326
`
`
`
`
`
`
`
`2/1995 Herbert
`.............
`.. 395/600
`5,388,256
`
`
`
`
`
`
`
`
`
`
`
`
`
`2/1995 Stephanet al.
`.. 395/800
`5,390,335
`
`4/1995 Belsan etal. .
`.. 395/600
`5,403,639
`
`
`
`
`
`
`4/1995 Oran oe.
`ws 395/325
`5,408,619
`
`
`
`
`
`
`
`4/1995 Seitz et al...
`370/85.13
`5,410,543
`
`
`
`
`
`
`5,410,684
`4/1995 Ainsworthet al.
`.. 395/575
`
`
`
`
`
`
`
`5/1995 de Remeret al. oe 395/575
`5,412,801
`
`
`
`
`
`
`
`5,418,957
`5/1995) Narayan w..ccecesceeseseseseneee 395/700
`
`
`
`
`
`
`
`
`
`
`
`5,423,034
`6/1995 Cohen-Levyetal.
`.. 395/600
`7/1995 Jamoussietal. .....
`... 395/600
`5,430,871
`
`
`
`
`
`
`
`
`5,434,994
`7/1995 Shaheenet al.
`.. 395/500
`..
`
`
`
`
`
`
`
`9/1995) Delory w.eccccceccsesecsesesesesenees 395/600
`5,452,450
`
`
`
`
`
`
`9/1996 Goldring wee cceseeetenees 395/600
`5,553,279
`
`
`
`
`
`
`5,588,147 12/1996 Neemanetal.
`.. 395/601
`
`
`
`
`
`
`3/1997 Goldring.......
`.. 395/618
`5,613,113
`
`
`
`
`
`
`9/1997 Clark et al.
`. 395/617
`5,666,530
`...
`
`
`
`
`
`
`
`...
`5,684,984
`11/1997 Joneset al.
`.. 395/610
`
`
`
`
`
`
`
`
`
`
`
`
`11/1997 Sondereggeret al.
`. 395/200.11
`5,692,129
`5,710,922
`1/1998 Alley et al.eens 395/617
`
`
`
`
`
`
`5,737,600
`4/1998 Geineret al.
`.. 395/616
`.
`
`
`
`
`
`
`4/1998 Jain etal. .....
`w. 395/617
`5,737,601
`
`
`
`
`
`
`
`.....
`4/1998 Carret al.
`.. 395/618
`5,740,433
`
`
`
`
`
`
`5,761,660
`6/1998 Josten et al.
`ceeeeeeeeceee 707/8
`occ
`
`
`
`
`
`
`6/1998 Porcaro.........
`wee 707/202
`5,774,717
`
`
`
`
`
`707/204
`5,778,390
`7/1998 Nelsonetal.
`
`
`
`
`
`
`9/1998 Jain et al.
`.....
`«. 707/201
`5,806,075
`
`
`
`
`
`
`
`5,832,518
`11/1998 Mastors.........
`.. 707/202
`
`
`
`
`
`
`3/1999 Draperet al. occ.- 707/202
`5,878,434
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“Countdown to Mobile Blast-Off’,
`I. Brodsky, Network
`
`
`
`
`
`
`World, Feb. 19, 1996, pp. 4446,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, 29 3, Jul. 1995, pp. 64-74.
`
`
`
`
`
`
`“Disconnected Operation for AFS”, L. Hustonet al., Mobile
`
`
`
`Location—Independent Computing
`Symposium,
`and
`
`
`
`
`
`USENIX Association, 1994, pp. 1-10.
`
`
`
`
`
`
`
`“Disconnected Operation in the Coda File System”, J.
`
`
`
`
`
`
`
`
`Kistler et al.. ACM Operating Systems Review, 25 5, 1991,
`
`
`pp. 213-225.
`
`
`
`
`
`“Disconnected Operation in a Distributed File System”, J.
`
`
`
`
`
`
`
`thesis, Department of Computer Science,
`Kistler, Ph.D.
`
`
`
`
`
`
`
`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. Satyanarayananet 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.. JEEE—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. Agrawaletal.,
`
`
`
`
`
`
`
`
`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. Kumaret al., JEEE, 1993, pp. 202-213.
`
`
`
`
`
`
`
`
`“The Lotus Notes™ Storage System”, K. Moore, ACM
`
`
`
`
`
`SIGMOD Record, 24 2, 1995, pp. 427-428.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“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, JEEE
`
`
`
`
`
`
`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.
`
`
`
`
`

`

`
`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-70.
`
`
`
`
`
`
`
`“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., JEEE 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. Heidemannet al., JEEE, 1992, pp. 2-5.
`
`
`
`
`“Replicated Data in a Distributed Environment”, M. Colton,
`
`
`
`
`
`
`
`ACM SIGMODRecord, 22 2, 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.
`
`
`
`
`
`
`
`
`Liskovet al., ACM SIGOS Operating Systems Review, 25 1,
`
`
`
`1991, pp. 60-64.
`
`
`
`
`
`
`
`“Replication in the Harp File System”, B. Liskov, ACM
`
`
`
`
`
`
`
`Operating Systems Review, 25 5, 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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“RES 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. Kumaret al., JEEE, 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, JEEE—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. Neumanet 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, p p. 50, 52.
`
`
`
`
`
`Summary ofFitler et al. Invention, 1992.
`
`
`
`
`
`
`
`Mobile NetWare Lite Specification, Version 1.0, Aug. 20,
`
`
`
`
`1992 (best available copy).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

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

`

`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
`
`
`
`

`

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

`

`U.S. Patent
`
`
`
`
`Nov. 23, 1999
`
`
`
`
`
`Sheet 4 of 4
`
`
`5,991,771
`
`
`
`OBTAIN NETWORK CONNECTION
`
`
`
`
`
`RECORDPATTIi
`
`
`
`
`
`
`
`IDENTIFY FIRST TRANSACTION
`
`
`
`LOCATE REPLICA TO SYNCHRONIZE
`
`
`
`
`
`
`
`
`
`TRANSFER UPDATE FROM FIRST
`
`
`COMPUTER TO SECOND COMPUTER
`
`
`
`DETECTMISSEDPOREiy
`
`
`
`
`
`
`
`
`
`APPLY UPDATE TO REPLICA ON
`SECOND COMPUTER
`
`
`
`
`
`
`
`
`
`IDENTIFY SECOND TRANSACTION
`
`
`
`
`
`
`
`TRANSFER UPDATE FROM SECOND
`
`
`
`COMPUTER TO FIRST COMPUTER
`
`
`
`
`
`DETECT MISSED UPDATE
`
`
`
`
`
`APPLY UPDATE TO REPLICA ON
`FIRST COMPUTER
`
`
`
`
`
`
`FIG. 4
`
`
`100
`
`102
`
`104
`
`
`
`
`106
`
`108
`
`
`110
`
`
`112
`
`
`
`114
`
`
`
`

`

`5,991,771
`
`
`
`
`1
`TRANSACTION SYNCHRONIZATIONIN A
`
`
`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.
`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.
`
`
`TECHNICAL BACKGROUND OF THE
`
`
`INVENTION
`
`
`
`
`
`
`
`
`
`
`
`It is often convenient, and sometimesessential, 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
`
`
`
`
`
`
`
`wavesor infrared light as carriers. Mobile-link computers
`can be used in a walk-alone modeif the network connection
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is lost. However, mobile-link systems provide few or no
`
`
`
`
`
`
`automaticfacilities 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 changesto 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 cachedfile exist:
`
`
`
`
`
`
`
`
`the original stored on the server, and a duplicate stored in the
`
`
`
`10
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`2
`
`
`
`
`
`
`
`
`disconnected client’s cache. The user mayalter 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®
`
`
`
`
`
`
`4.1 (LOTUS NOTESis a trademark of International Busi-
`
`
`
`
`
`
`
`ness Machines, Inc. and NETWAREisa registered trade-
`
`
`
`mark of Novell, Inc.).
`
`
`
`
`
`
`
`However, some of these approachesto replication are not
`
`
`
`
`
`
`transactional. A transaction is a sequence of one or more
`
`
`
`
`
`operations whichare appliedto 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 offiles, directories, or other
`
`
`
`
`
`
`
`
`objects in the replica. This seriously degrades the perfor-
`
`
`
`
`
`
`
`mance of such approaches when the network connection
`
`
`
`
`
`
`
`used for synchronization1s relatively slow, as many modem
`or WAN linksare.
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`
`
`
`approachestoreplication is the requirement they imposethat
`
`
`
`
`
`
`
`
`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 whenit 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 advancementin theart 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 advancementto 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 advancementto 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.
`
`
`
`
`
`
`
`
`
`

`

`5,991,771
`
`
`3
`
`
`
`
`
`
`It would be an additional advancementto provide such a
`
`
`
`
`
`
`
`system and method which do not require a synchronization
`
`
`
`
`
`
`
`
`time period that depends directly on the total numberoffiles,
`
`
`
`
`
`
`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 advancementto 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.
`
`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 duringthat 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
`40
`
`
`
`
`
`
`
`
`
`
`course, the network may also include more than one com-
`
`
`
`
`
`
`
`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-
`
`
`
`
`
`
`
`
`least a portion of a target database. The target
`tains at
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`
`Eachreplica 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 changesin 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