Abstract:
One embodiment of the present invention provides a system that facilitates delayed block allocation in a distributed file system. During operation, the system receives a write command at a client, wherein the write command includes a buffer containing data to be written and a file identifier. In response to receiving the write command, the system reserves a set of disk blocks for the file from a virtual pool of disk blocks allocated to the client. The system also transfers the data to be written to the kernel of the client where the data waits to be transferred to the disk.

Description:
BACKGROUND  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to the design of distributed file systems. More specifically, the present invention relates to a method and an apparatus for facilitating delayed block allocation in a distributed file system.  
           [0003]    2. Related Art  
           [0004]    Distributed file systems are typically based on a client-server model, wherein a client wishing to access a file sends a request to a server to perform a file system operation, such as reading from a file or writing to a file. A file system write operation typically involves a number of steps. The first step usually involves allocating space on disk for the file that is being written to. This ensures that space is available to accommodate data associated with the write operation. At the same time, data for the write operation is moved from the address space of the application into kernel space within the operating system of the client. Next, the system transfers the data from the kernel space of the client to the disk at the server.  
           [0005]    The step of allocating space is often very slow because it typically involves communicating with the server to ask the server to allocate space. The server then determines if space is available for the write operation and if so typically allocates space by actually reserving disk blocks for the file being written to. Finally, the server sends an acknowledgement to the client indicating that the allocation was successful.  
           [0006]    Note that the step of transferring data from the client to the disk at the server typically has very little impact on write performance because this operation is typically performed asynchronously. Hence, the client application can go on to do other tasks while the data is being transferred to the disk.  
           [0007]    Attempts have been made to speed up the allocation step by pre-allocating disk blocks to the client to satisfy write operations. For example, see “Disk Space Guarantees as a Distributed Resource Management Problem: A Case Study”, by Murthy Devarakonda, Anada Rao Ladi, Andy Zlotek, and Ajay Mohindra, Proceedings of the IEEE Symposium on Parallel and Distributed Processing, October 1995, pp. 289-292. This paper describes a system that pre-allocates a small number of blocks for a file when the application first creates a file page. As the file grows, the client has to continually return to the server to allocate more disk blocks. While this system speeds up the allocation process, the system suffers from having to continually allocate more disk blocks from the server for the file.  
           [0008]    What is needed is a method and an apparatus that facilitates delayed block allocation in a distributed file system without the problems described above.  
         SUMMARY  
         [0009]    One embodiment of the present invention provides a system that facilitates delayed block allocation in a distributed file system. During operation, the system receives a write command at a client, wherein the write command includes a buffer containing data to be written and a file identifier. In response to receiving the write command, the system reserves a set of disk blocks for the file from a virtual pool of disk blocks allocated to the client. The system also transfers the data to be written to the kernel of the client where the data waits to be transferred to the disk.  
           [0010]    In one embodiment of the present invention, prior to receiving the write command, the system allocates the virtual pool of disk blocks for the client from the server.  
           [0011]    In one embodiment of the present invention, the system reserves sufficient space from the virtual pool of disk blocks to ensure that the buffer and subsidiary data can be written to the disk.  
           [0012]    In one embodiment of the present invention, the system maintains a count at the client of disk blocks available in the virtual pool of disk blocks.  
           [0013]    In one embodiment of the present invention, the system additionally sends the data from the kernel of the client to the server for writing to the file on disk.  
           [0014]    In one embodiment of the present invention, the system sends a count of disk blocks reserved for the file to the server while sending the data from the kernel of the client to the server, thereby updating the server with a latest count of disk blocks reserved for the file.  
           [0015]    In one embodiment of the present invention, upon receiving the count of disk blocks reserved for the file, the system allocates additional disk blocks for the client, if necessary, to replenish the virtual pool of disk blocks. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGS.  
       [0016]    [0016]FIG. 1 illustrates a number of computer systems in accordance with an embodiment of the present invention.  
         [0017]    [0017]FIG. 2 illustrates a client in accordance with an embodiment of the present invention.  
         [0018]    [0018]FIG. 3 illustrates a server in accordance with an embodiment, of the present invention.  
         [0019]    [0019]FIG. 4 is a flowchart illustrating the process of pre-allocating disk blocks to the client in accordance with an embodiment of the present invention.  
         [0020]    [0020]FIG. 5 is a flowchart illustrating the process of writing to a file on disk and receiving a new allocation of disk blocks in accordance with an embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0021]    The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.  
         [0022]    The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data, for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet.  
         [0023]    Computer Systems  
         [0024]    [0024]FIG. 1 illustrates a client  102  and a server  106  coupled together by a network  104  in accordance with an embodiment of the present invention. Network  104  can generally include any type of wire or wireless communication channel capable of coupling together computing nodes. This includes, but is not limited to, a local area network, a wide area network, or a combination of networks. In one embodiment of the present invention, network  104  includes a private interconnect between client  102  and server  106 .  
         [0025]    Client  102  and server  106  can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. Furthermore, client  102  includes a mechanism for making requests upon server  106  for computational and/or data storage resources, and server  106  includes a mechanism for servicing requests from client  102  for computational and/or data storage resources.  
         [0026]    In the embodiment of the present invention illustrated in FIG. 1, client  102  is a distributed file system client and server  106  is file server for the distributed file system. In this embodiment, server  106  is attached to a disk system  108 , wherein server  106  stores files.  
         [0027]    During operation, server  106  determines the number of available disk blocks on disk system  108  and then allocates some of the available disk blocks to client  102 . The number of disk blocks that are allocated to client  102  can depend on a number of factors, including: the number of clients coupled to server  106 ; the number of available disk blocks on disk system  108 ; and predetermined system parameters.  
         [0028]    When client  102  writes a new file to the file system, client  102  first reserves disk blocks from its allocation for the new file. While reserving these disk blocks, client  102  allows space for internal file structures. Client  102  also moves the data from the application&#39;s buffer into a kernel buffer within client  102 . After reserving the disk blocks from its allocation and after transferring the data into the kernel, client  102  acknowledges the write to the originating application so that the originating application can continue executing.  
         [0029]    At some later time, client  102  asynchronously transfers the data to server  106  across network  104  to complete the write operation. While sending this data to server  106 , client  102  also sends the number of disk blocks that were reserved for the write operation by the client. This allows server  106  to calculate the number of remaining blocks allocated to client  102 . Additionally, server  106  determines the number of disk blocks remaining on disk system  108  and can allocate more disk blocks to client  102 , if necessary. Next, client  102  receives an acknowledgement message from server  106  indicating that the file was successfully written to disk. This acknowledgement message can additionally include a new allocation of disk blocks for client  102 .  
         [0030]    Client  
         [0031]    [0031]FIG. 2 illustrates client  102  in accordance with an embodiment of the present invention. Client  102  contains application  202 , user buffer  204 , file buffer cache  206 , disk block available counter  208 , and client interface  210 . User buffer  204  holds data to be written to a file by application  202 . Although FIG. 2 only illustrates a single application  202 , in general, client  102  can host multiple applications, each with zero or more open files.  
         [0032]    File buffer cache  206  contains kernel buffers that are used for holding data from user buffer  204  before the data is transferred to disk system  108  to complete the write operation. Note that user buffer  204  and file buffer cache  206  are replicated within client  102  for each open file. Disk block available counter  208  is used by client  102  to keep track of the number of disk blocks allocated to client  102  by server  106 .  
         [0033]    During operation, server  106  initially allocates a number of disk blocks to client  102  as described below with reference to FIG. 3. When application  202  writes to an open file, client  102  estimates the number of blocks required for the write operation. This estimate accounts for blocks associated with the file such as directory entries and indirect blocks that point to data blocks.  
         [0034]    Note that the system typically overestimates the number of blocks required to ensure that the file can be written to disk system  108 .  
         [0035]    If the estimate is greater than the count in disk block available counter  208 , client  102  notifies application  202  that insufficient disk space is available, or alternatively, can request a greater allocation of blocks from server  106 . Otherwise, client  102  transfers the write data from user buffer  204  to file buffer cache  206 . Client  102  also subtracts the blocks from disk block available counter  208 , and notifies application  202  that the file has been sent to disk system  108 . Application  202  is then free to continue execution.  
         [0036]    After notifying application  202  that the file has been sent to disk system  108 , client  102  transfers the write data from file buffer cache  206  to server  106 , so that server  106  can write the data to disk system  108 . In doing so, client  102  includes the estimated number of blocks along with the data. This allows server  106  to update its counter within server file buffer cache  304  as is described in more detail below with reference to FIG. 3.  
         [0037]    When server  106  subsequently acknowledges that the write successfully completed, server  106  can include a count of additional blocks reserved for client  102  in the acknowledgement. Client  102  then adds these additional blocks to disk block available counter  208 .  
         [0038]    Finally, client interface  210  contains mechanisms that allow client  102  to communicate with server  106 . For example, client interface  210  can contain a communication stack, such as a TCP/IP stack, for communicating across network  104  with server  106 .  
         [0039]    Server  
         [0040]    [0040]FIG. 3 illustrates server  106  in accordance with an embodiment of the present invention. As is illustrated in FIG. 3, server  106  contains a file system  205 , which includes an available disk block counter  302  and a server file buffer cache  304 . Server  106  also contains a server interface  306  and a disk system interface  308 .  
         [0041]    Available disk block counter  302  keeps track of the number of available disk blocks on disk system  108 . Server  106  initially allocates disk blocks to clients, such as client  102 , based on a number of factors, including: the number in available disk block counter  302 ; and the number of clients coupled to server  106 .  
         [0042]    Server file buffer cache  304  is used by file system  205  as a cache for disk blocks from disk system  108 . Note that server file buffer cache  304  is replicated per-client so that each client coupled to server  106  has its own server file buffer cache.  
         [0043]    Server  106  uses mechanisms within server interface  306  to communicate with client  102 . For example, server interface  306  can include a communication stack, such as a TCP/IP stack, for communicating across network  104  to client  102 .  
         [0044]    During operation, server  106  sends an initial disk block allocation to client  102 . When server  106  subsequently receives data to be written during a write operation, this data includes a count of disk blocks reserved for the write operation. Server  106  then subtracts the count of disk blocks reserved for the write operation from disk block available counter  208  and writes the data to disk system  108  through disk system interface  308 .  
         [0045]    Server  106  can then allocate additional disk blocks to client  102 , if necessary. The current number of disk blocks allocated to client  102  can then be communicated to client  102  in the acknowledgement message that acknowledges successful completion of the write operation.  
         [0046]    Process of Pre-allocating Disk Blocks  
         [0047]    [0047]FIG. 4 presents a flowchart illustrating the process of pre-allocating disk blocks to a client in accordance with an embodiment of the present invention. The process starts when disk system interface  308  determines the number of disk blocks available on disk system  108  (step  402 ). Server  106  then allocates disk blocks for each client coupled to server  106  (step  404 ). The number of blocks allocated for each client is saved in a server file buffer cache for each client, such as server file buffer cache  304  for client  102 . Next, the number of blocks allocated to client  102  is communicated to client  102  across network  104 .  
         [0048]    After allocating disk blocks to the clients, server  106  waits for a new file to be committed to disk system  108  (step  406 ). After the new file is committed to disk system  108 , server  106  subtracts the number of disk blocks used by the new file from available disk block counter  302  (step  408 ). Server  106  then allocates additional disk blocks for client  102 , if necessary, and notifies client  102  of the new allocation in the message acknowledging that the new file has been successfully written to disk system  108  (step  410 ). Note that this allocation process can take place asynchronously. The system then returns to step  406  to wait for another file to be committed to disk.  
         [0049]    Process of Writing a File to the Disk System  
         [0050]    [0050]FIG. 5 is a flowchart illustrating the process of writing a file to a disk and receiving a new allocation of disk blocks in accordance with an embodiment of the present invention. The system starts when client  102  receives a disk block allocation from server  106  (step  502 ). Next, the system waits for a write command from an application, such as application  202  (step  504 ). Upon receiving a write command, client  102  reserves disk blocks from the allocation for the write command and stores the write data into file buffer cache  206  (step  506 ). The number of reserved disk blocks is subtracted from disk block available counter  208 . Client  102  sends an acknowledgement of completion of the write operation to application  202  (step  508 ).  
         [0051]    After sending the acknowledgement to application  202 , client  102  sends the write data and the count of disk blocks reserved for the write operation to server  106  (step  510 ). Client  102  may subsequently receive an additional disk block allocation from server  106  in the acknowledge message for the write operation (step  512 ). This new allocation is added to disk block available counter  208  in client  102 . The process then returns to step  504  to wait for the next disk write command.  
         [0052]    The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.