分布式计算论文_分布式_其他

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/6272fb457ec58a2c01185528/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6272fb457ec58a2c01185528/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Leases: An Efficient Fault-Tolerant Mechanism </div><div class="t m0 x2 h2 y2 ff1 fs0 fc0 sc0 ls5 ws5">for Distributed File Cache Consistency </div><div class="t m1 x3 h3 y3 ff1 fs1 fc0 sc0 lsa wsa">Cary G. Gray and David R. </div><div class="t m2 x4 h4 y3 ff1 fs2 fc0 sc0 ls10 ws10">Cheriton </div><div class="t m1 x5 h3 y4 ff1 fs1 fc0 sc0 ls11 ws11">Computer Science Department </div><div class="t m1 x6 h3 y5 ff1 fs1 fc0 sc0 ls14 ws14">!3tanford University </div><div class="t m3 x7 h5 y6 ff1 fs3 fc0 sc0 ls16 ws16">Abstract </div><div class="t m1 x8 h3 y7 ff1 fs1 fc0 sc0 ls17 ws17">Caching introduces the overbead and complexity of ensur- </div><div class="t m1 x7 h3 y8 ff1 fs1 fc0 sc0 ls1e ws1e">ing consistency, reducing some of its performance bene- </div><div class="t m1 x7 h3 y9 ff1 fs1 fc0 sc0 ls25 ws25">fits. In a distributed system, caching must deal ,wit.h the </div><div class="t m1 x7 h3 ya ff1 fs1 fc0 sc0 ls2e ws2e">additional complications of communication and host fail- </div><div class="t m1 x7 h3 yb ff1 fs1 fc0 sc0 ls32 ws33">ures. </div><div class="t m3 x9 h6 yc ff1 fs4 fc0 sc0 ls33 ws34">Leases </div><div class="t m1 xa h3 yc ff1 fs1 fc0 sc0 ls34 ws35">are proposed as a time-based mechanism that </div><div class="t m1 x7 h3 yd ff1 fs1 fc0 sc0 ls39 ws3a">provides efficient consistent access to cached data in dis- </div><div class="t m1 x7 h3 ye ff1 fs1 fc0 sc0 ls42 ws43">tributed systems. Non-Byzantine failures affect perfor- </div><div class="t m1 x7 h3 yf ff1 fs1 fc0 sc0 ls48 ws49">mance, not correctness, with their effect minimized by </div><div class="t m1 x7 h3 y10 ff1 fs1 fc0 sc0 ls32 ws33">short leases. An analytic model and an evaluation for file </div><div class="t m1 x8 h3 y11 ff1 fs1 fc0 sc0 ls3c ws3d">access in the V system show that leases of short duration </div><div class="t m1 x7 h3 y12 ff1 fs1 fc0 sc0 ls5a ws5a">provide good performance. The impact of leases on per- </div><div class="t m1 x8 h3 y13 ff1 fs1 fc0 sc0 ls5f ws5f">formance grows more significant in systems of lar;ger scale </div><div class="t m1 x8 h3 y14 ff1 fs1 fc0 sc0 lsd wsd">and higher processor performance. </div><div class="t m3 x8 h5 y15 ff1 fs3 fc0 sc0 ls68 ws68">1 Introduction </div><div class="t m1 x8 h3 y16 ff1 fs1 fc0 sc0 ls17 ws17">Caching introduces the problem of ensuring consistency </div><div class="t m1 x7 h3 y17 ff1 fs1 fc0 sc0 ls6d ws6d">between the cached data and its primary location of stor- </div><div class="t m1 x8 h3 y18 ff1 fs1 fc0 sc0 ls3f ws40">age. By </div><div class="t m3 xb h6 y18 ff1 fs4 fc0 sc0 ls71 ws72">consistent, </div><div class="t m1 xc h3 y18 ff1 fs1 fc0 sc0 ls72 ws73">we mean that the behavior is equiv- </div><div class="t m1 x8 h3 y19 ff1 fs1 fc0 sc0 ls76 ws76">alent to there being only a single (uncached) copy of the </div><div class="t m1 x8 h3 y1a ff1 fs1 fc0 sc0 ls3f ws40">data except for the performance benefit of the cache. With </div><div class="t m1 x7 h3 y1b ff1 fs1 fc0 sc0 ls32 ws33">large caches, the traffic required to maintain consistency </div><div class="t m1 x8 h3 y1c ff1 fs1 fc0 sc0 ls84 ws85">can be the dominant factor in cache performance. </div><div class="t m1 xd h3 y1d ff1 fs1 fc0 sc0 ls88 ws89">Cache consistency protocols have been extensively </div><div class="t m1 x8 h3 y1e ff1 fs1 fc0 sc0 ls8d ws8e">studied in the work on shared memory multiprocessor </div><div class="t m4 xe h7 y1f ff1 fs5 fc0 sc0 ls92 ws93">This work was </div><div class="t m1 xf h3 y1f ff1 fs1 fc0 sc0 ls95 ws96">supported </div><div class="t m4 x10 h7 y1f ff1 fs5 fc0 sc0 ls96 ws97">in part by the Defense Advanced Re- </div><div class="t m4 x8 h7 y20 ff1 fs5 fc0 sc0 ls9c ws9e">search Projects Agency under contract NOO039-84-C-02 11, by the Na- </div><div class="t m4 x8 h7 y21 ff1 fs5 fc0 sc0 lsa3 wsa5">tional Science Foundation Grant DCR-83-52048, and by Digital Equip- </div><div class="t m4 x8 h7 y22 ff1 fs5 fc0 sc0 lsab wsab">ment Corporation. </div><div class="t m4 x11 h7 y23 ff1 fs5 fc0 sc0 lsac wsad">Permission to copy without fee all or part of this material is granted provided </div><div class="t m4 x11 h7 y24 ff1 fs5 fc0 sc0 lsb7 wsb8">that the copies are not made or distributed for direct commercial advantage, </div><div class="t m4 x11 h7 y25 ff1 fs5 fc0 sc0 ls98 ws9a">the ACM copyright notice and the title of the publication and its date appear, </div><div class="t m4 x11 h7 y26 ff1 fs5 fc0 sc0 lsa8 wsa8">and notice is given that copying is by permission of the Association for </div><div class="t m4 x11 h7 y27 ff1 fs5 fc0 sc0 lsca wscb">Computing Machinery. To copy otherwise, or to republish, requires a fee </div><div class="t m4 x11 h7 y28 ff1 fs5 fc0 sc0 lsd1 wsd2">and/or specific permission. </div><div class="t m4 x11 h7 y29 ff1 fs5 fc0 sc0 lsd4 wsd5">0 </div><div class="t m5 x12 h8 y29 ff1 fs6 fc0 sc0 lsd5 wsd6">1989 ACM089791-338-3/89/0012/0202 </div><div class="t m4 x13 h7 y29 ff1 fs5 fc0 sc0 lsd7 wsd8">$1.50 </div><div class="t m1 x14 h3 y6 ff1 fs1 fc0 sc0 lsd8 wsd9">architectures; this work relies on reliable, synchronous </div><div class="t m1 x14 h3 y2a ff1 fs1 fc0 sc0 lsdc wsdc">broadcast communication as provided by the system bus. </div><div class="t m1 x14 h3 y2b ff1 fs1 fc0 sc0 ls56 ws56">A distributed system, however, can experience partial fail- </div><div class="t m1 x14 h3 y2c ff1 fs1 fc0 sc0 ls32 ws33">ures: a host may crash or messages may be lost. Existing </div><div class="t m1 x14 h3 y2d ff1 fs1 fc0 sc0 lse6 wse6">approaches to consistency for file caches fall into two cat- </div><div class="t m1 x14 h3 y2e ff1 fs1 fc0 sc0 lsea wseb">egories: those that assume reliable broadcast, and so do </div><div class="t m1 x14 h3 y2f ff1 fs1 fc0 sc0 ls19 ws19">not tolerate communication failures, and those that require </div><div class="t m1 x14 h3 y30 ff1 fs1 fc0 sc0 ls27 ws27">a consistency check for every read, </div><div class="t m3 x15 h6 y30 ff1 fs4 fc0 sc0 lsf5 wsf5">and </div><div class="t m1 x16 h3 y30 ff1 fs1 fc0 sc0 lsb wsb">so fail to deliver </div><div class="t m1 x14 h3 y31 ff1 fs1 fc0 sc0 ls27 ws27">good performance. </div><div class="t m1 x17 h3 y32 ff1 fs1 fc0 sc0 ls26 ws26">In this paper, leases are proposed as a consistency pro- </div><div class="t m1 x14 h3 y33 ff1 fs1 fc0 sc0 lsea wsf8">tocol that handles host and communication failures us- </div><div class="t m1 x14 h3 y34 ff1 fs1 fc0 sc0 ls1e ws1e">ing physical clocks. An analytic model and an evalua- </div><div class="t m1 x14 h3 y35 ff1 fs1 fc0 sc0 lse8 wsfe">tion using file access characteristics of the V system show </div><div class="t m1 x14 h3 y36 ff1 fs1 fc0 sc0 ls38 ws39">that short-term leases provide near optimal efficiency for </div><div class="t m1 x14 h3 y37 ff1 fs1 fc0 sc0 ls27 ws27">a large class of systems in spite of the fault-tolerance pro- </div><div class="t m1 x14 h3 y38 ff1 fs1 fc0 sc0 ls103 wsf6">visions. We argue that leases are of increased benefit in </div><div class="t m1 x14 h3 y39 ff1 fs1 fc0 sc0 ls106 ws109">future distributed systems of larger scale with their larger </div><div class="t m1 x14 h3 y3a ff1 fs1 fc0 sc0 ls108 ws10b">ratio of processor speed to network delay and larger ag- </div><div class="t m1 x14 h3 y3b ff1 fs1 fc0 sc0 ls10c ws10f">gregate rate of failure. </div><div class="t m1 x17 h3 y3c ff1 fs1 fc0 sc0 ls5c ws5c">The next section describes leases and how they are used </div><div class="t m1 x14 h3 y3d ff1 fs1 fc0 sc0 ls3d ws3e">to implement cache consistency. Section 3 derives our </div><div class="t m1 x14 h3 y3e ff1 fs1 fc0 sc0 ls117 ws11c">simple analytic model for picking lease terms and explores </div><div class="t m1 x14 h3 y3f ff1 fs1 fc0 sc0 ls4b ws4c">their application using data from the V distributed sys- </div><div class="t m1 x14 h3 y40 ff1 fs1 fc0 sc0 ls11c ws122">tem [4]. Section 4 describes some optimizations in lease </div><div class="t m1 x14 h3 y41 ff1 fs1 fc0 sc0 ls11f ws125">management. Section 5 examines the fault-tolerance of </div><div class="t m1 x14 h3 y42 ff1 fs1 fc0 sc0 ls6f ws126">leasing. Section 6 compares leases with other work on </div><div class="t m1 x14 h3 y43 ff1 fs1 fc0 sc0 ls28 ws28">distributed cache consistency and related problems. The </div><div class="t m1 x14 h3 y44 ff1 fs1 fc0 sc0 ls123 ws129">concluding section summarizes our results and speculates </div><div class="t m1 x14 h3 y45 ff1 fs1 fc0 sc0 ls52 ws53">on further applications of leases and directions for future </div><div class="t m1 x14 h3 y46 ff1 fs1 fc0 sc0 ls129 ws12f">research. </div><div class="t m3 x14 h5 y47 ff1 fs3 fc0 sc0 ls68 ws68">2 Leases and Cache Consistency </div><div class="t m1 x14 h3 y48 ff1 fs1 fc0 sc0 ls56 ws56">A lease is a contract that gives its holder specified rights </div><div class="t m1 x14 h3 y49 ff1 fs1 fc0 sc0 ls131 ws136">over property for a limited period of time. In the context </div><div class="t m1 x18 h3 y4a ff1 fs1 fc0 sc0 ls1c ws1c">of caching, a lease grants to its holder control over writes </div><div class="t m1 x14 h3 y4b ff1 fs1 fc0 sc0 ls3d ws3e">to the covered datum during the term of the lease, such that </div><div class="t m1 x14 h3 y4c ff1 fs1 fc0 sc0 ls19 ws19">the server must obtain the approval of the leaseholder be- </div><div class="t m1 x18 h3 y4d ff1 fs1 fc0 sc0 ls7 ws144">fore the datum may be written. When a leaseholder grants </div><div class="t m1 x18 h3 y29 ff1 fs1 fc0 sc0 lsdd ws142">approval for a write, it invalidates its local copy of the da- </div><div class="t m3 x19 h6 y4e ff1 fs4 fc0 sc0 ls141 ws14a">202 </div></div><div class="pi" data-data='{"ctm":[1.566069,0.000000,0.000000,1.566069,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w2 h9" data-page-no="2"><div class="pc pc2 w2 h9"><img class="bi x0 y0 w3 ha" alt="" src="https://static.pudn.com/prod/directory_preview_static/6272fb457ec58a2c01185528/bg2.jpg"><div class="t m3 x1a h6 y4f ff1 fs4 fc0 sc0 ls142 ws14b">mm. </div><div class="t m1 x1b h3 y50 ff1 fs1 fc0 sc0 ls56 ws56">A cache using leases requires a valid lease on the da- </div><div class="t m1 x1a h3 y51 ff1 fs1 fc0 sc0 ls101 ws14e">tum (in addition to holding the datum) before it returns the </div><div class="t m1 x1a h3 y52 ff1 fs1 fc0 sc0 ls139 ws13e">datum in response to a read, or modifies the datum in re- </div><div class="t m1 x1a h3 y53 ff1 fs1 fc0 sc0 ls3e ws3f">sponse to a write. When a datum is fetched from the server </div><div class="t m1 x1a h3 y54 ff1 fs1 fc0 sc0 ls6f ws126">(the primary storage site of the datum), the server also re- </div><div class="t m1 x1a h3 y55 ff1 fs1 fc0 sc0 ls14f ws15b">turns a lease guaranteeing that the data will not be writ- </div><div class="t m1 x1a h3 y56 ff1 fs1 fc0 sc0 ls19 ws15e">ten by any client during the lease rerm unless the server </div><div class="t m1 x1a h3 y57 ff1 fs1 fc0 sc0 ls155 ws160">first obtains the approval of this leaseholder. If the da- </div><div class="t m1 x1a h3 y58 ff1 fs1 fc0 sc0 ls101 ws14e">tum is read again within the term of the lease (and the da- </div><div class="t m1 x1a h3 y59 ff1 fs1 fc0 sc0 ls101 ws14e">tum is still in the cache), the cache provides immediate ac- </div><div class="t m1 x1a h3 y5a ff1 fs1 fc0 sc0 ls14 ws16a">cess to the datum without communicating with the server. </div><div class="t m1 x1a h3 y5b ff1 fs1 fc0 sc0 ls9 ws16e">After the lease expires, a read of the datum requires that </div><div class="t m1 x1a h3 y5c ff1 fs1 fc0 sc0 ls19 ws19">the cache first extend the lease on the datum, updating the </div><div class="t m1 x1a h3 y5d ff1 fs1 fc0 sc0 ls87 ws88">cache if the datum has been modified since the lease ex- </div><div class="t m1 x1a h3 y5e ff1 fs1 fc0 sc0 ls165 ws176">pired. When a client writes a datum, the server must defer </div><div class="t m1 x1a h3 y5f ff1 fs1 fc0 sc0 ls19 ws19">the request until each leaseholder has granted approval or </div><div class="t m1 x1a h3 y60 ff1 fs1 fc0 sc0 ls19 ws19">the term of its lease has expired. </div><div class="t m1 x1b h3 y61 ff1 fs1 fc0 sc0 ls104 ws107">We limit ourselves here to write-through caches, for do- </div><div class="t m1 x1a h3 y62 ff1 fs1 fc0 sc0 ls1e ws1e">ing so simplifies the explanation; extending the mecha- </div><div class="t m1 x1a h3 y63 ff1 fs1 fc0 sc0 lsa ws183">nism to support non-write-through caches is straightfor- </div><div class="t m1 x1a h3 y64 ff1 fs1 fc0 sc0 ls171 ws185">ward. Write-through gives clean failure semantics: no </div><div class="t m1 x1a h3 y65 ff1 fs1 fc0 sc0 ls173 ws18a">write that has been made visible to any client can be lost; </div><div class="t m1 x1a h3 y66 ff1 fs1 fc0 sc0 ls127 ws12d">applications must otherwise be prepared to recover from </div><div class="t m1 x1a h3 y67 ff1 fs1 fc0 sc0 ls101 ws158">lost writes. Though the cost of write-through for file </div><div class="t m1 x1a h3 y68 ff1 fs1 fc0 sc0 lse7 wse7">caches is considered prohibitive by some [ 16], the cost can </div><div class="t m1 x1a h3 y69 ff1 fs1 fc0 sc0 ls27 ws27">be largely eliminated by giving special handling to tempo- </div><div class="t m1 x1a h3 y6a ff1 fs1 fc0 sc0 ls181 ws19a">rary files [9,24], since they receive the majority of writes. </div><div class="t m1 x1b h3 y6b ff1 fs1 fc0 sc0 ls58 ws58">To illustrate the operation of a file cache using leases, </div><div class="t m1 x1a h3 y6c ff1 fs1 fc0 sc0 ls39 ws3a">consider a diskless workstation being used for document </div><div class="t m1 x1a h3 y6d ff1 fs1 fc0 sc0 ls99 ws1a2">production. When the workstation executes latex for </div><div class="t m1 x1a h3 y6e ff1 fs1 fc0 sc0 ls19 ws19">the first time, it obtains a lease on the binary file contain- </div><div class="t m1 x1a h3 y6f ff1 fs1 fc0 sc0 ls1e ws1e">ing latex for a term of (say) 10 seconds. Another ac- </div><div class="t m1 x1a h3 y70 ff1 fs1 fc0 sc0 ls14 ws16a">cess to the same file 5 seconds later can use the cached </div><div class="t m1 x1a h3 y71 ff1 fs1 fc0 sc0 ls18c ws1a7">version of this file without checking with the file server. </div><div class="t m1 x1a h3 y72 ff1 fs1 fc0 sc0 ls4f ws50">An access to this file after the lo-second term has expired </div><div class="t m1 x1a h3 y73 ff1 fs1 fc0 sc0 ls143 ws14c">requires the cache to check with the server. When a new </div><div class="t m1 x1a h3 y74 ff1 fs1 fc0 sc0 ls18c ws1a7">version of latex is installed, the write is delayed until </div><div class="t m1 x1a h3 y75 ff1 fs1 fc0 sc0 lsf3 wsf3">every leaseholder has approved the write. If some host </div><div class="t m1 x1a h3 y76 ff1 fs1 fc0 sc0 ls147 ws151">holding a lease for this file is unreachable, the delay con- </div><div class="t m1 x1a h3 y77 ff1 fs1 fc0 sc0 ls191 ws1ac">tinues until the lease expires. </div><div class="t m1 x1b h3 y78 ff1 fs1 fc0 sc0 ls26 ws26">In the preceding example, the relevant reads and writes </div><div class="t m1 x1a h3 y79 ff1 fs1 fc0 sc0 ls34 ws35">are not limited to operations on the contents of the file. In </div><div class="t m1 x1a h3 y7a ff1 fs1 fc0 sc0 ls65 ws65">order to support a repeated open, the cache must also hold </div><div class="t m1 x1a h3 y7b ff1 fs1 fc0 sc0 ls19 ws19">the name-to-file binding and permission information, and </div><div class="t m1 x1a h3 y7c ff1 fs1 fc0 sc0 ls13e ws147">it needs a lease over this information in order to use that </div><div class="t m1 x1a h3 y7d ff1 fs1 fc0 sc0 ls102 ws1b8">information to perform the open. Similarly, modification </div><div class="t m1 x1a h3 y7e ff1 fs1 fc0 sc0 ls1c ws1c">of this information, such as renaming the file, would con- </div><div class="t m3 x1a h6 y7f ff1 fs4 fc0 sc0 ls19f ws1bd">stitute </div><div class="t m1 x1c h3 y7f ff1 fs1 fc0 sc0 ls27 ws27">a write. </div><div class="t m1 x1b h3 y80 ff1 fs1 fc0 sc0 ls118 ws11d">Short lease terms have several advantages. One is that </div><div class="t m1 x1a h3 y81 ff1 fs1 fc0 sc0 ls111 ws116">they minimize the delay resulting from client and server </div><div class="t m1 x1a h3 y82 ff1 fs1 fc0 sc0 ls45 ws46">failures (and partitioning communication failures). When </div><div class="t m1 x1a h3 y83 ff1 fs1 fc0 sc0 ls19 ws19">the server cannot communicate with a client, the server </div><div class="t m1 x1d h3 y84 ff1 fs1 fc0 sc0 ls2b ws2b">must delay writes to a file for which the failed client holds </div><div class="t m1 x1e h3 y4f ff1 fs1 fc0 sc0 ls27 ws27">a lease until that lease expires.] When a server is recover- </div><div class="t m1 x1e h3 y85 ff1 fs1 fc0 sc0 ls1e ws1e">ing after crashing, it must honor the leases it granted be- </div><div class="t m1 x1e h3 y86 ff1 fs1 fc0 sc0 ls7 ws144">fore it crashed. This is most easily done if it remembers </div><div class="t m1 x1e h3 y87 ff1 fs1 fc0 sc0 ls19 ws19">the maximum term for which it had granted a lease, and </div><div class="t m1 x1e h3 y88 ff1 fs1 fc0 sc0 ls13e ws147">it delays writes to all tiles for that period, effectively in- </div><div class="t m1 x1e h3 y89 ff1 fs1 fc0 sc0 ls39 ws3a">creasing the time to fully recover by the maximum term. </div><div class="t m1 x1e h3 y8a ff1 fs1 fc0 sc0 ls58 ws58">Alternately, the server can maintain a more detailed record </div><div class="t m1 x1e h3 y8b ff1 fs1 fc0 sc0 ls1c ws1c">of leases on persistent storage, but the additional I/O traffic </div><div class="t m1 x1e h3 y8c ff1 fs1 fc0 sc0 ls74 ws28">is unlikely to be justified unless terms of leases are much </div><div class="t m1 x1e h3 y8d ff1 fs1 fc0 sc0 ls12e ws133">longer than the time to recover. </div><div class="t m1 x1f h3 y8e ff1 fs1 fc0 sc0 ls118 ws11d">Short leases also minimize the false write-sharing that </div><div class="t m1 x1e h3 y8f ff1 fs1 fc0 sc0 ls101 ws158">occurs. False sharing refers here to a lease conflict when </div><div class="t m1 x1e h3 y90 ff1 fs1 fc0 sc0 ls52 ws189">no actual conflict in file access exists. Speciftcally, false </div><div class="t m1 x1e h3 y91 ff1 fs1 fc0 sc0 lsfc wsfd">sharing occurs when a client writes to a file which is cov- </div><div class="t m1 x20 h3 y5d ff1 fs1 fc0 sc0 ls157 ws163">ered by a lease held by another client when the other client </div><div class="t m1 x20 h3 y5e ff1 fs1 fc0 sc0 ls74 ws28">is not currently accessing the tie. False sharing introduces </div><div class="t m1 x20 h3 y92 ff1 fs1 fc0 sc0 ls19 ws19">the overhead of a callback to the leaseholder(s) (thereby </div><div class="t m1 x20 h3 y60 ff1 fs1 fc0 sc0 ls1c5 ws1ee">delaying the requesting client and loading the leaseholder </div><div class="t m1 x20 h3 y93 ff1 fs1 fc0 sc0 lsd wsd">and server) in a situation where without leases there would </div><div class="t m1 x20 h3 y94 ff1 fs1 fc0 sc0 ls27 ws27">be no conflict. In the extreme, a lease term should be set </div><div class="t m1 x20 h3 y95 ff1 fs1 fc0 sc0 ls3d ws3e">to zero if a client is not going to access the file before it is </div><div class="t m1 x20 h3 y96 ff1 fs1 fc0 sc0 ls163 ws174">modified by another client. </div><div class="t m1 x21 h3 y97 ff1 fs1 fc0 sc0 ls1ce ws1f8">Finally, short lease terms reduce the storage require- </div><div class="t m1 x20 h3 y98 ff1 fs1 fc0 sc0 ls51 ws1fa">ments at the server, since the record of expired leases </div><div class="t m1 x20 h3 y99 ff1 fs1 fc0 sc0 ls10b ws115">could be reclaimed. However, the storage overhead for the </div><div class="t m1 x20 h3 y9a ff1 fs1 fc0 sc0 ls13a ws140">server to keep track of the leases it has granted is modest. </div><div class="t m1 x20 h3 y69 ff1 fs1 fc0 sc0 ls5c ws5c">The server requires a record of each leaseholder’s identity </div><div class="t m1 x20 h3 y9b ff1 fs1 fc0 sc0 lsd wsd">and a list of the leases it holds; each lease requires only a </div><div class="t m1 x20 h3 y9c ff1 fs1 fc0 sc0 ls7d ws7d">couple of pointers. For a client holding about one hundred </div><div class="t m1 x20 h3 y9d ff1 fs1 fc0 sc0 ls4e ws4f">leases, the total is around one kilobyte per client. Even </div><div class="t m1 x20 h3 y9e ff1 fs1 fc0 sc0 ls162 ws172">if this were a problem, it could be reduced by recording </div><div class="t m1 x20 h3 y9f ff1 fs1 fc0 sc0 ls34 ws35">leases at a larger granularity, so that each client holds few </div><div class="t m1 x20 h3 ya0 ff1 fs1 fc0 sc0 ls4e ws4f">leases, at the expense of some increase in contention. We </div><div class="t m1 x20 h3 ya1 ff1 fs1 fc0 sc0 ls58 ws58">show later how the per-client record can be eliminated for </div><div class="t m1 x20 h3 ya2 ff1 fs1 fc0 sc0 ls19 ws19">the most common class of widely-shared files. </div><div class="t m1 x21 h3 ya3 ff1 fs1 fc0 sc0 ls19d ws211">Longer-term leases are significantly more efficient both </div><div class="t m1 x20 h3 ya4 ff1 fs1 fc0 sc0 ls54 ws55">for the client and server on files that are accessed repeat- </div><div class="t m1 x20 h3 ya5 ff1 fs1 fc0 sc0 ls1e3 ws214">edly and have relatively little write-sharing. This may be </div><div class="t m1 x20 h3 ya6 ff1 fs1 fc0 sc0 ls132 ws138">observed in the Andrew file system project [lo], which </div><div class="t m1 x20 h3 ya7 ff1 fs1 fc0 sc0 ls7c ws21a">went from using a lease term of zero in the prototype to </div><div class="t m1 x20 h3 ya8 ff1 fs1 fc0 sc0 ls1b0 ws1d2">effectively a lease term of infinity in the revised version.’ </div><div class="t m1 x20 h3 ya9 ff1 fs1 fc0 sc0 ls5c ws5c">The next section presents an analytic model of lease per- </div><div class="t m1 x20 h3 yaa ff1 fs1 fc0 sc0 ls5f ws5f">formance and detemrines appropriate lease terms using </div><div class="t m1 x20 h3 yab ff1 fs1 fc0 sc0 ls1eb ws21e">parameters based on data from the V distributed system. </div><div class="t m6 x20 hb y7d ff1 fs7 fc0 sc0 ls1ec ws21f">3 Choosing the Lease Term </div><div class="t m1 x20 h3 yac ff1 fs1 fc0 sc0 ls5c ws5c">The choice of lease term is based on the trade-off between </div><div class="t m1 x20 h3 yad ff1 fs1 fc0 sc0 ls1f2 wsd0">minimizing lease extension overhead versus minimizing </div><div class="t m4 x22 h7 yae ff1 fs5 fc0 sc0 ls1f5 ws227">‘To avoid starvation of writes, the server does not grant new leases </div><div class="t m4 x1e h7 yaf ff1 fs5 fc0 sc0 ls1fc ws226">on a file when a write is waiting for approval or for leases to expire. </div><div class="t m4 x22 h7 yb0 ff1 fs5 fc0 sc0 ls96 ws97">‘At the expense of failing to guarantee consistency after a communi- </div><div class="t m4 x20 h7 y84 ff1 fs5 fc0 sc0 lsae wsaf">cations failure. </div><div class="t m1 x23 h3 yb1 ff1 fs1 fc0 sc0 ls27 ws27">203 </div></div><div class="pi" data-data='{"ctm":[1.566069,0.000000,0.000000,1.566069,0.000000,0.000000]}'></div></div>