`
`[19]
`5,991,771
`[11] Patent Number:
`United States Patent
`
`
`
`
`
`
`
`
`
`
`
`
`
`Falls et al.
`[45] Date of Patent:
`Nov. 23, 1999
`
`
`
`
`
`U5005991771A
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`
`
`1/1988 European Pat. Off.
`87107475
`........ G06F 11/14
`
`
`
`
`
`
`8/1993 European Pat. Off.
`92308720
`........ G06F 15/16
`
`
`
`
`
`
`3/1995 European Pat. Off.
`9508809
`........ G05F 17/30
`
`
`
`
`
`
`7/1995 European Pat. Off.
`........ GO6F 17/30
`95100255
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`[54] TRANSACTION SYNCHRONIZATION IN A
`
`
`
`
`
`
`BgfgggIECTABLE COMPUTER AND
`
`.
`,
`.
`,
`
`
`
`
`
`InVemorS Patfild‘ T- Falls> NeWbury> Brlan J-
`
`
`
`
`Colllns, New Malden; Stephen P. W.
`
`
`
`
`
`Draper, Basingstoke, all of United
`
`Kingdom
`
`[75]
`
`
`
`
`
`
`
`
`
`
`
`[86]
`
`
`
`[87]
`
`[60]
`
`
`
`
`
`[73] Assignee: Novell, Inc., Provo, Utah
`.
`
`
`
`08/700’487
`[21] Appl. No”
`
`
`
`
`PCT Filed:
`Jul. 18, 1996
`[22]
`
`
`PCT/US96/11901
`PCT N05
`Jul. 3, 1997
`§ 371 Date:
`
`
`
`
`
`
`
`
`Jul. 3: 1997
`§ 102(6) Date:
`.
`
`
`
`
`PCT Pub. No" W097/04389
`
`
`
`
`
`PCT Pub. Date: Feb. 6, 1997
`
`
`
`
`Related US. Application Data
`
`
`
`
`
`
`
`Provisional application No. 60/001,261, Jul. 20, 1995.
`6
`
`
`
`
`
`[51]
`...................................................... G06F 17/00
`Int. Cl.
`[52] US. Cl.
`....................... 707/202; 707/201; 395/182.1;
`
`
`
`
`
`
`
`395/182”
`_
`
`
`
`
`
`
`[58] Fleld of Search .................................. 707/8, 10, 201,
`707/203, 200, 202; 395/180, 182.1, 182.13
`
`
`
`
`
`
`
`[56]
`
`
`
`..
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`iJnligersity Of California At Los Angeles, Mar. 1991, pp.
`
`
`
`
`
`
`
`“Coda: A Highly Available file System for a Distributed
`
`
`
`
`Workstation Environment”, M. Satyanarayanan et al., IEEE
`Transactions 0n Computers, vol. 39 No. 4 Apr. 1990, pp.
`
`
`
`
`
`
`
`
`447—459.
`
`
`
`
`“Coding for Compression in Full—Text Retrieval Systems”,
`
`
`
`
`
`
`A. Moffat et 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
`
`
`[57]
`A method and apparatus are disclosed for synchronizing
`
`
`
`
`
`
`
`transactions in a disconnectable network. Each transaction
`
`
`
`
`
`
`
`
`
`
`mellldes Operanons that we?“ 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-
`th
`h
`t
`t
`.
`f
`th
`t
`d
`
`
`
`
`
`
`
`man?“ mm 6“ comp“ far 0
`e 0 6? comp“ er 3}“
`
`
`
`
`
`applies updates to both replicas as appropriate. Transaction
`
`
`
`
`
`
`
`
`
`logs and clash handling tools may be used with the inven-
`Hon.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ABSTRACT
`
`
`
`References Clted
`U.S. PATENT DOCUMENTS
`
`
`
`............................ 364/200
`3/1986 Morel et a1.
`4,575,793
`
`
`
`
`
`
`......
`11/1986 Frank et a1.
`4 622 631
`364/200
`
`
`
`
`
`
`
`9/1988 Kollin et a1.
`4,774,655
`..
`364/200
`
`
`
`
`
`
`
`
`
`
`
`9/1988 Kampati ........
`4,774,661
`364/300
`
`
`
`
`
`5/1989 Shlbayama
`498279399
`364/200
`
`
`
`
`
`
`
`4,878,167 10/1989 Kapulka et al.
`364/200
`7/1990 Eppley et a1.
`4,941,845
`439/505
`
`
`
`
`
`
`
`3/1991 Johnson et a1.
`5,001,628
`364/200
`
`
`
`
`
`
`
`5,008,814
`4/1991 Mathur ..............
`364/200
`
`
`
`
`
`
`
`5/1991 Alderson et a1.
`.
`5,019,963
`364/200
`
`
`
`
`
`
`8/1991 Terry ....................................... 364/200
`5,043,876
`
`
`
`
`
`
`
`
`
`
`
`
`34 Claims, 4 Drawing Sheets
`(List continued on next page.)
`
`
`28, 40
`COMPUTER
`COMPUTER
`
`
`
`
`
`
`DATABASE MANAGER
` DATABASE MANAGER
`
`
`
`
`
`
`
`[44
`
`
`
`-”
`
`
`I
`AGENTS |'
`
`REPLICA MANAGER
`
`
`
`
`
`
`I
`REPLICA MANAGER
`fl ,
`
`
`
`NETWORK
`
`
`
`
`SYSTEM
`FILE
`
`LINK
`
`INTERFACE
`
`INTERFACE
`
`
`
`
`
`STORAGE DEVICE
`
`
`
`AND CONTROLLER
`
`56
`
`
`REPLICA
`
`
`
`
`
`
`
`
`
`
`NETWORK
`
`LINK
`
`INTERFACE
`
`
`
`
`
`
`
`
`
`
`
`I
`
`
`
`
`
`
`
`52
`
`
`
`FILE
`
`SYSTEM
`
`INTERFACE
`
`
`
`
`
`
`
`
`
`STORAGE DEVICE
`
`
`AND CONTROLLER
`
`56
`
`
`REPLICA
`
`
`
`
`
`
`
`
`
`
`
`
`Starbucks Corporation, et al. — EX. 1017
`US. 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
`......................... 395/600
`5/1992 Johnson et al.
`
`
`
`
`
`
`8/1992 Ottman et al.
`5,142,680
`395/700
`
`
`
`
`
`
`
`395/200
`9/1992 Carey et al.
`......
`5,146,561
`
`
`
`
`
`
`
`9/1992 Johnson et al.
`5,151,989
`395/600
`
`
`
`
`
`
`
`395/600
`5,155,847 10/1992 Kirouac et al.
`
`
`
`
`
`
`
`10/1992 Trigg et al.
`.......
`5,159,669
`395/159
`
`
`
`
`
`
`
`.......................... 395/600
`5,170,480 12/1992 Mohan et al.
`
`
`
`
`
`
`.................... 395/148
`5,185,857
`2/1993 Rozmanith et al.
`
`
`
`
`
`
`395/600
`5/1993 Rago .................
`5,212,789
`
`
`
`
`
`
`
`7/1993 Thomas ............... 341/51
`5,229,768
`
`
`
`
`
`
`5,237,680
`8/1993 Adams et al.
`395/600
`
`
`
`
`
`
`
`9/1993 Holmes et al.
`......................... 395/700
`5,247,683
`
`
`
`
`
`
`12/1993 Dubin et al.
`............................ 395/600
`5,274,803
`
`
`
`
`
`
`5,276,868
`1/1994 Poole ........
`395/600
`
`
`
`
`
`
`
`1/1994 Howarth ........
`395/600
`5,276,871
`
`
`
`
`
`
`1/1994 Coleman et al.
`.
`5,276,876
`395/650
`
`
`
`
`
`
`
`1/1994 Foster et al.
`......
`395/600
`5,278,979
`
`
`
`
`
`
`
`
`5,278,982
`1/1994 Daniels et al.
`395/600
`
`
`
`
`
`
`395/600
`3/1994 Kawano et al.
`..
`5,291,591
`
`
`
`
`
`
`
`......
`3/1994 Wang et al.
`5,297,278
`395/600
`
`
`
`
`
`
`
`
`5,313,646
`5/1994 Hendricks et al.
`395/600
`
`
`
`
`
`
`5/1994 Tevis et al.
`5,317,728
`.......
`395/600
`
`
`
`
`
`
`
`
`5,321,832
`6/1994 Tanaka et al.
`395/600
`
`
`
`
`
`
`
`5,325,524
`6/1994 Black et al.
`......
`395/600
`
`
`
`
`
`
`
`7/1994 Saether et al.
`395/600
`5,333,315
`
`
`
`
`
`
`
`
`
`9/1994 Flynn et al.
`..
`5,347,653
`395/600
`
`
`
`
`
`
`
`10/1994 Fukumara .....
`395/600
`5,355,476
`
`
`
`
`
`
`
`
`5,375,207 12/1994 Blakely et al.
`395/200
`
`
`
`
`
`
`
`12/1994 Murata et al.
`5,377,326
`395/200
`
`
`
`
`
`
`
`395/600
`2/1995 Herbert
`.............
`5,388,256
`
`
`
`
`
`
`2/1995 Stephan et al.
`5,390,335
`395/800
`
`
`
`
`
`
`4/1995 Belsan et al.
`.. 395/600
`.
`5,403,639
`
`
`
`
`
`
`
`395/325
`4/1995 Oran ..............
`5,408,619
`
`
`
`
`
`
`
`4/1995 Seitz et al.
`........
`370/85.13
`5,410,543
`
`
`
`
`
`
`4/1995 Ainsworth et al.
`5,410,684
`395/575
`
`
`
`
`
`
`
`5/1995 de Remer et al.
`...................... 395/575
`5,412,801
`
`
`
`
`
`
`
`5/1995 Narayan .................................. 395/700
`5,418,957
`
`
`
`
`
`395/600
`5,423,034
`6/1995 Cohen—Levy et al.
`
`
`
`
`
`
`7/1995 Jamoussi et al.
`.....
`5,430,871
`395/600
`
`
`
`
`
`
`
`
`7/1995 Shaheen et al.
`..
`5,434,994
`395/500
`
`
`
`
`
`
`
`5,452,450
`9/1995 Delory .................................... 395/600
`
`
`
`
`
`
`9/1996 Goldring ................................. 395/600
`5,553,279
`
`
`
`
`
`
`5,588,147 12/1996 Neeman et al.
`395/601
`
`
`
`
`
`
`3/1997 Goldring .......
`5,613,113
`395/618
`
`
`
`
`
`
`9/1997 Clark et al.
`.. 395/617
`5,666,530
`
`
`
`
`
`
`
`395/610
`5,684,984
`11/1997 Jones et al.
`
`
`
`
`
`
`11/1997 Sonderegger et a .
`.. 395/200.11
`5,692,129
`
`
`
`
`
`
`1/1998 Alley et al. .............. 395/617
`5,710,922
`
`
`
`
`
`
`5,737,600
`4/1998 Geiner et al.
`.
`395/616
`
`
`
`
`
`
`4/1998 Jain et al.
`5,737,601
`395/617
`
`
`
`
`
`
`
`4/1998 Carr et al.
`395/618
`5,740,433
`
`
`
`
`
`
`..
`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
`
`
`
`
`
`
`9/1998 Jain et al.
`5,806,075
`707/201
`
`
`
`
`
`
`
`11/1998 Mastors .........
`.. 707/202
`5,832,518
`
`
`
`
`
`
`5,878,434
`3/1999 Draper et al.
`........................i
`707/202
`
`
`
`
`
`
`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, N0. 3,
`May 1979, pp. 188—194.
`
`
`
`
`“Conflict Detection Tradeoffs for Replicated Data”, M.
`
`
`
`
`
`
`
`
`
`
`
`
`Carey et al., ACM Transactions on Database Systems, vol.
`16, N0. 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, N0. 1, Mar. 1993, pp.
`
`
`
`
`
`
`
`
`
`
`34—39.
`
`
`
`
`
`
`“Data Replicas in Distributed Information Services”, H.
`
`
`
`
`
`
`Gladney, ACM Transactions on Database Systems, vol. 14,
`
`
`
`
`
`N0. 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. Huston et 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. 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, N0. 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, N0. 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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`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., 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, 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.
`
`
`
`
`
`
`
`
`Liskov et 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.
`
`
`
`
`
`
`
`
`
`
`“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 ofthe 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%Vinth 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, p p. 50, 52.
`
`
`
`
`
`
`
`
`
`
`Summary of Fitler et al. Invention, 1992.
`
`
`
`
`
`
`
`Mobile NetWare Lite Specification, Version 1.0, Aug. 20,
`
`
`
`
`1992 (best available copy).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`US. Patent
`
`
`
`
`
`N0V.23, 1999
`
`
`
`
`
`Sheet 1 0f4
`
`5,991,771
`
`
`
`IE!
`
`9‘:
`
`
`
`I?I(}.Al
`
`
`
`202428
`
`Q
`
`
`
`
`
`[320,28,36
`
`
`ii!
`
`14
`
`L— D2016,28EE
`
`STORAGE
`
`MEDIA
`
`
`
`16,28,3834
`
`[EDDIE é
`
`
`
`
`\
`
`10
`
`
`
`D
`
`
`
`
`
`U)
`
`
`
`
`
`
`
`: O 3l
`
`w z
`
`x c
`
`.—
`
`OTHER
`
`

`

`US. Patent
`
`Nov. 23, 1999
`
`Sheet 2 0f 4
`
`5,991,771
`
`3»
`
`KwPZm0<
`
`EMF—402200
`
`3K
`
`4szmo<“
`
`EmO<Z<E
`
`
`
`mm0<z<§<O_._n_mm_
`
`
`
`mw®<z<2<O_|_n_wm
`
`m.=n_
`
`_>_m_._.m>m
`
`wO<HEMHZ_
`
`VEO>>._.mz
`
`x23
`
`mo<n_mm:.2_
`
`vEO>>._.m_Z
`
`xz:
`
`m0<mIMHZ_
`
`m.__u_
`
`Em+m>m
`
`m0<mmm_._.z_
`
`mw<m<k<o
`mmG<Z<E
`mm<m<b<o
`
`N,mv~5~
`
`mm
`
`<O_._&m_m
`
`
`
`m0_>mn_mO<IO._.m
`
`mm._._Om._.ZOOOZ<
`
`mm
`
`Evin—mm
`
`
`
`mO_>m_Dw0<m0hm
`
`ImIIOm—HZOODZ<
`
`
`
`
`

`

`
`US. Patent
`
`
`
`
`
`N0V.23, 1999
`
`
`
`
`Sheet 3 0f4
`
`5,991,771
`
`
`
`
`REPLICA MANAGER
`
`
`
`
`
`
`REPLICA DISTRIBUTOR
`
`
`
`
`
`
`
`
`CONSISTENCY DISTRIBUTOR
`
`
`
`
`
`
`LOCATION DISTRIBUTOR
`
`
`
`
`OBJECT DISTRIBUTOR
`
`
`
`
`
`OBJECT SCHEMA
`FILE DISTRIBUTOR
`
`
`
`
`.
`
`TRIGGER FUNCTION REGISTRATIONS
`
`
`
`
`
`
`REPLICA PROCESSOR
`
`
`
`
`CONSISTENCY PROCESSOR
`
`
`
`
`
`LOCATION STATE PROCESSOR
`
`
`
`
`OBJECT PROCESSOR
`
`
`
`
`TRANSACTION LOGGER
`
`
`
`
`FILE PROCESSOR
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 3
`
`

`

`
`US. Patent
`
`
`
`
`
`N0V.23, 1999
`
`
`
`
`Sheet 4 0f 4
`
`5,991,771
`
`
`
`
`
`OBTAIN NETWORK CONNECTION
`
`
`
`
`RECORD TRANSACTION
`
`
`
`
`
`IDENTIFY FIRST TRANSACTION
`
`
`
`
`
`LOCATE REPLICA TO SYNCHRONIZE
`
`
`
`
`
`
`
`TRANSFER UPDATE FROM FIRST
`
`
`COMPUTER TO SECOND COMPUTER
`
`
`
`
`
`DETECT MISSED UPDA
`
`
`
`
`
`APPLY UPDATE TO REPLICA ON
`
`
`SECOND COMPUTER
`
`
`
`
`RECORD TRANSACTION
`
`
`
`
`IDENTIFY SECOND TRANSACTION
`
`
`
`
`
`
`TRANSFER UPDATE FROM SECOND
`
`
`
`COMPUTER TO FIRST COMPUTER
`
`
`
`
`
`DETECT MISSED UPDA
`
`
`
`
`
`APPLY UPDATE TO REPLICA ON
`
`
`FIRST COMPUTER
`
`
`
`
`FIG. 4
`
`
`100
`
`102
`
`
`
`
`104
`
`
`106
`
`
`108
`
`
`110
`
`112
`
`
`
`114
`
`
`
`

`

`5,991,771
`
`
`1
`TRANSACTION SYNCHRONIZATION IN 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 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
`
`5
`
`
`
`10
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`
`
`
`
`
`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®
`
`
`
`
`
`
`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.
`
`
`
`
`
`

`

`5,991,771
`
`10
`
`
`
`15
`
`
`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.
`
`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 networ ” 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
`
`
`
`
`
`
`
`
`
`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.
`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