Changes between Initial Version and Version 1 of DiskManagement

Timestamp:

Apr 29, 2007, 8:48:59 PM (18 years ago)

Author:

KSMarksPsych

Comment:

Added page

DiskManagement

@@ +1 @@
+= Disk space management =
+        
+== THIS FILE IS DEPRECATED ==
+
+This document describes the core client's policies for managing disk space. The goals are the following (highest to lowest priority):
+
+   1. '''Enforce user disk usage preferences.'''
+   2. '''Enforce resource shares.'''
+   3. '''Provide disk space for completed results.'''
+   4. '''Provide disk space for active results.'''
+   5. '''Provide disk space for queued results.'''
+   6. '''Provide disk space for project file storage ('sticky files'). '''
+
+'''Total_Limit'''; disk usage limit as determined by prefs, disk size, and non-BOINC usage
+
+'''Core_Usage'''; space currently being used by core client
+
+'''all_Projects_limit [aPl] =''' total_limit - core_usage, this is space that projects can use [aPL]
+
+'''Project_usage(p) =''' The size of all files associated with a project p, returns project->size in most cases;
+
+'''all_Project_usage[aPu] =''' {Project_usage(p)} for all Project p
+
+'''Project_limit(p) =''' aPl*resource_share(p)
+
+The '''free space''' on a client is determined by
+
+    free_space = all_Projects_Limit - all_Project_usage
+
+A project is an '''offender''' if
+
+    project_usage(p) - project_limit(p) > 0
+
+The '''greatest offender''' is the project with
+
+    max {project_usage(p) - project_limit(p))} for all p. 
+
+The client will always try to remove files from the greatest offender first before querying other projects.
+
+== A Project_limit(p) Example ==
+
+Consider a system participating two projects, A and B, with resource shares 75% and 25%, respectively. After computing the aPl available, A would receive 75% of the aPL as its project limit and B would receive 25% of the aPL as its project limit.
+
+If P_u(A) < P_l(A), Project A is not utilizing all Project_limit(A). Therefore, B should be able to use the difference (P_u(A) - P_l(A)) if it needs to. This applies to all projects in any situation where a project is not utilizing all its Project_limit(p). This unused space will show up as free_space in most cases.
+
+When A wants to add a new file, if adding the file would cause all_Project_usage >= aPL, a project must delete a file first. If A is not an offender, then files are deleted from an offender, in this case, Project B. Files will be deleted from B as described in ''Adding a File to a Project'' below.
+
+== What BOINC does in problem situations ==
+
+    * The current project has a disk share large enough for all the workunits needed to keep itself busy, but there is not enough disk space available for all the files because of other projects.
+
+          When the BOINC client requests work, it tells the scheduling server how much free space it has on the client, as well as how much space it could potentially free. It is then the projects decision on how much work to award the client based on these values. When the files are downloaded, others are deleted as described below 
+
+    * A large file was moved somewhere into the BOINC directory structure and begins to contribute to the space BOINC takes up.
+
+          Because of the way BOINC calculates the program size, this kind of error is unavoidable. The client will notice that BOINC has violated its disk share and will do the necessary steps described above (see first priority in Maintaining Project Disk Share). The user will have to find the problematic file and remove it in order for BOINC to reclaim that space. Deleted files will not be restored. 
+
+    * A compution creates large temp files and stores them in its slot directory. These temp files are so large that they fill up the project disk size and the client no longer has enough space to run any computations .
+
+          The client will try to create space for these temporary files as much it can, to the point where all files except those running a computation for a project are deleted. Because BOINC makes computation a priority over storage at this time, this is a very bad situation as it will delete all files in all other projects to ensure the work continues. If the total space for the BOINC client is still larger than the preferences allow, the client will suspend all activities and notify the user of the issue. The user can either drop the offending project or increase its disk size for BOINC in their preferences. 
+
+== Adding a file to a project ==
+
+The algorithm is run whenever:
+
+    * A file is added to a project via an RPC reply 
+
+The client will first attempt to use all the PDS that is free. When all the space for BOINC projects is used by some combination of projects, files must be deleted to make space.
+
+The client maintains the project share sizes and workunit queues by:
+
+    * Try deleting files up to the point where a project is no longer an offender
+    * Starting deletion with the lowest priority files first
+          * Being the greatest offender doesn't guarantee that it will be the first to loose files, will delete lower priority files from other offenders first. 
+    * Never deleting workunit files associated with the requesting project, give up this point
+    * Never delete results that have finished computation, let them be uploaded and recorded properly. 
+
+The client's method of creating free_space ensures the above:
+
+   1. If there enough free_space in the aPl,
+          * If yes, return ''true'' and ''increase project->size by file->nbytes''
+   2. Else check if there are any projects that are offending their project share,
+          * If yes, delete files starting with the greatest offender and the lowest priority/expired files
+          * Delete these priority/expired files until the project size is below the project's share size
+          * If there is not enough space made, increase the priority to delete and repeat
+   3. Else check if there can be room made in the project by deleting any non-workunit files,
+          * If yes, delete them.
+          * If there is now enough free space, return ''true'' and ''increase project->size by file->nbytes''
+   4. Else, return false, there is no way to associate the file with the project and guarantee the statements above
+
+=== Pseudo Code ===
+
+{{{
+PROJECT:
+   double size
+        double share_size
+        double resource_share
+FILE_INFO:
+        double nbytes
+        
+get_more_disk_space():
+   for some PROJECT p and space_needed = number of bytes required
+        init total_space = 0
+        
+        total_space = free space in the project disk size
+   if (total_space > space_needed):
+        return true
+
+        mark all projects as unchecked
+        
+        while(total_space < space_needed):
+                g_of = the greatest_offender
+        if(couldn't find one or g_of == p):
+                        increase priority to delete from
+                if can't increase anymore, return false         
+        mark g_of as checked
+                only delete low priority files up to the point when it isn't an offender
+        return true
+
+
+associate_file():
+        for some FILE_INFO fip and a PROJECT p
+   init space_made = 0  
+   // check offenders
+   if(get_more_disk_space(p, fip->size)):
+        p.size += fip.nbytes
+                return true
+        // check self
+   is there any free space?
+   try and delete expendable files from p
+   if(space_made > fip->nbytes):
+        return true
+        // if hasn't return true yet, failure
+   return false
+}}}
+
+== Violating User Disk Usage Preferences ==
+
+This checking is done in the `data_manager_poll()` which is placed at the top of the client's FSM hierarchy. If there is no space violation, it takes no action and returns false. If BOINC is larger than the Total_Limit, the client will reduce Project_usages using the following method:
+
+   1. Check all the offending projects and delete files from them until they are all not offenders or no more files can be deleted
+   2. Cycle through each project, deleting one files at a time from each project, starting with the lowest priority and expired files, until only referenced files are left for the project.
+   3. Cycle through each project, deleting one result at a time from each project until there are only results that are waiting for thier 'server ack' or are part of a current computation. This will removed references to files and hence mark them available for deletion.
+
+If all three conditions fail, all computation is suspended, a messsage is sent to the user explaining the problem and the function returns true. If at any time in the function, the total used space falls below the allowed disk usage set by the user preferences, the function returns false.
+
+== Work Fetch Policy ==
+
+In conjunction with the CPU Scheduler's work fetch policy, the data manager's work fetch policy's goals are to:
+
+    * Calculate total free space.
+    * Calculate total free space if lowest priority files were deleted.
+    * Calculate total free space if highest priority files were deleted.
+
+When an RPC request is made, the client communicates to the server the values described above and the server can make a decision on how much work to send to the client.
+
+=== Calculating free space ===
+
+'''Psuedocode'''
+
+{{{
+anything_free():
+        init total_size = 0
+        foreach p in projects:
+        total_size += p.size
+    get project disk size
+        free space = project disk size - total_size
+
+// get the total number of bytes that would be free
+// if files with priority < pr were deleted from all other projects
+// and low priority files were deleted from this project
+//
+
+total_potentially_free():
+        for some project my_p and some priority pr
+        init tps = anything_free();
+
+        ref_count all files in file_infos
+    foreach p in projects
+    if(p != my_p):
+            tps += potentially free space from p with priority less than pr
+
+
+   foreach fip in file_infos
+   if(fip.project == my_p, is permantent, and not part of a computation):       
+                and if(fip has lowest priority or is expired):
+                tps += fip->nbytes
+ 
+potentially_free():
+    for a project p and some priority pr
+    if it is not an offender:
+            return 0;
+        foreach fip in file_infos:
+    if(fip.project == p, is permantent, and not part of a computation):         
+            and if(fip.priority <= pr or is expired):
+                tps += fip->nbytes   }
+    return tps
+}}}
+
+== Project Deletion Policy ==
+
+There are three types of deletion policy that a project can specify in its config.xml
+
+   1. '''Priority deletion'''. Files with the lowest priority level get deleted first in the order they were introduced to the client (downloaded).
+   2. '''Expiration deletion'''. Whenever space runs out, all files that have past their expiration date are deleted first. Any file who's the expiration_date is less than the time now is deleted.
+   3. '''Least Recently Used (LRU)'''. The DEFAULT method, the last file to be downloaded/uploaded is deleted first. The LRU policy is always used to determine the next file to delete.
+
+The policies are invoked by including the following in the config.xml file
+
+    <deletion_policy_priority/>
+    <deletion_policy_expire/>
+    - the LRU policy in inbedded in the core-client as the default 
+
+If any of these flags are present in the config.xml, a similar tag will be included in a successful RPC request.
+
+=== Using a Project Deletion Policy ===
+
+A FILE_INFO, when created, has the following default values related to a projects deletion policy. These values are created for every file.
+
+    priority = P_LOW;
+    time_last_used = time now
+    exp_date = 60 days from now 
+
+where P_LOW is defined in client_types.h as the following
+
+    #define P_LOW 1
+    #define P_MEDIUM 3
+    #define P_HIGH 5
+
+If using the defualts, files will not be guarenteed to survive more than sixty days if <deletion_policy_expire> is true.
+
+If a priority or exp_date other than the default is required, the priority must be set when the workunit is created. By including the following tags in a workunit or result template, the default information is replaced.
+
+    <priority>(int; 1-5)<priority>
+    <exp_days>(int; # of days to keep)<exp_days> 
+
+== Scheduling Server Changes ==
+
+The client communicates three values of disk usage to the server.
+
+   1. The amount of free_space
+   2. The amount of free_space if the client were to delete files from offending projects
+   3. The amount of free_space if the client were to delete files from offending projects & itself
+
+The server will assign workunits normally using the first amount. If no workunits were assigned, a second pass of the database is made using the second amount. If no workunits were assigned and the following is in the config.xml:
+
+    <delete_from_self/>
+
+the third amound of free_space is used and a third pass of the database is made. Return whatever workunits were deemed acceptable for the host.
+
+Under most circumstances, the amount of free_space will be enough to get workunits for a project. If a project has larger workunits (> 1 gb) or the host is storing many files for a project, amounts 2 & 3 become more important. The amount of free_space if files are deleted is found by:
+
+    * For offending projects, marking files that could be deleted up to where the project is no longer an offender
+    * For the requesing project, marking all files that could be deleted
+          * Files that are not expired are never included if deletion_policy_expire is true
+
+== TODO: Future Changes ==
+
+There is currently a method for requesting a list of files from the project. There needs to be a way to communicate the information back to the project, such as an xml doc that can be parsed by the project.
+
+There also needs to be a database, separate from the scheduling database, which keeps track of the files on host's clients.