Caching that's multi-process safe - Revision history

Jimg: /* Problem */

2015-01-22T23:48:21Z

Problem

← Older revision		Revision as of 23:48, 22 January 2015
Line 1:		Line 1:
	== Problem ==		== Problem ==
	Develop a general procedure (or software) for implementing a cache that can be shared by several processes. There seems to be no readily available library that implements caching. It certainly needs to work for Unix; Windows suport would be good, but i of less importance because the OC library may take over or client role on that platform.		Develop a general procedure (or software) for implementing a cache that can be shared by several processes. There seems to be no readily available library that implements caching. It certainly needs to work for Unix; Windows suport would be good, but is of less importance because the OC library may take over or client role on that platform.

	== Background ==		== Background ==

Jimg: /* Cache design */

2012-03-23T16:01:49Z

Cache design

← Older revision		Revision as of 16:01, 23 March 2012
Line 79:		Line 79:
	# for every file deleted, update that size		# for every file deleted, update that size
	# use an exclusive rd/wr lock for those updates		# use an exclusive rd/wr lock for those updates
	# Note: ''This technically locks the entire cache for write operations, but does not lock it for read operations. Also, the time the file is locked can be much smaller than the time required to actually write one of the data files.''		# Note: ''This is a compromise given our original goal of not ever locking the whole cace because it technically locks the entire cache for write operations, but does not lock it for read operations. Also, the time the file is locked can be much smaller than the time required to actually write one of the data files.''

	===== Software we have =====		===== Software we have =====

Jimg: /* Cache design */

2012-03-23T16:00:49Z

Cache design

← Older revision		Revision as of 16:00, 23 March 2012
Line 79:		Line 79:
	# for every file deleted, update that size		# for every file deleted, update that size
	# use an exclusive rd/wr lock for those updates		# use an exclusive rd/wr lock for those updates
	# Note: ''This technically locks the entire cache for write operations, but not for read operations.''		# Note: ''This technically locks the entire cache for write operations, but does not lock it for read operations. Also, the time the file is locked can be much smaller than the time required to actually write one of the data files.''

	===== Software we have =====		===== Software we have =====

Jimg: /* Cache design */

2012-03-22T19:18:25Z

Cache design

← Older revision		Revision as of 19:18, 22 March 2012
Line 55:		Line 55:

	It would be best if the size and last use time for each file in the cache was not recorded in a single file.		It would be best if the size and last use time for each file in the cache was not recorded in a single file.
			<!--
	Idea: For each file, use a companion file to record size and last use time. Updates won't change the size, they will only change the time. The cache does not actually need to be too picky about getting the exact time of the last access in the file. If two processes update it at overlapping times, the time recorded will be close enough. The file will contain one value, that will be the time at which the matched data fie was last read. We will update the time when the lock on the data was was obtained, not released. The name of the file will be the be made of the data file name, a dot and the size in bytes of the data file. Example:		Idea: For each file, use a companion file to record size and last use time. Updates won't change the size, they will only change the time. The cache does not actually need to be too picky about getting the exact time of the last access in the file. If two processes update it at overlapping times, the time recorded will be close enough. The file will contain one value, that will be the time at which the matched data fie was last read. We will update the time when the lock on the data was was obtained, not released. The name of the file will be the be made of the data file name, a dot and the size in bytes of the data file. Example:
	* Data file: #usr#local#data#modis#hdf		* Data file: #usr#local#data#modis#hdf
Line 64:		Line 64:
	# Store the basename (i.e., data file name), size and last used time		# Store the basename (i.e., data file name), size and last used time
	# Find the oldest files and remove until the total size of the cache falls below 90% of the max size.		# Find the oldest files and remove until the total size of the cache falls below 90% of the max size.
			-->

			How to purge:
			# Look at every data file
			# Store the basename (i.e., data file name), size and last used (access) time
			# Find the oldest files and remove until the total size of the cache falls below 90% of the max size.
			#* if a file is locked when the cache tries to delete it, just skip it, since its access is clearly just become recent!
			# with every delete, update the 'total size' file

	How to track the total size of the cache's data:		How to track the total size of the cache's data:

Jimg: /* Cache design */

2012-03-22T19:00:45Z

Cache design

← Older revision		Revision as of 19:00, 22 March 2012
Line 50:		Line 50:
	The cache will be a directory.		The cache will be a directory.

	Each file to be cached with have a name that is a function of its pathname, so it is guaranteed to be unique.		Each file to be cached with have a name that is a function of its pathname, so it is guaranteed to be unique. The BES decomp cache will use the 'take the pathname and replace the slashes with hashes' technique to make the names unique. Example:
			/usr/local/data/modis.hdf --> #usr#local#data#modis#hdf
			The leading hash can be used or not, but it's probably easier to include it. This is a pretty easy transform; simply replace the characters [/.] with #

	It would be best if the size and last use time for each file in the cache was not recorded in a single file.		It would be best if the size and last use time for each file in the cache was not recorded in a single file.

	Idea: For each file, use a companion file to record size and last use time. Updates won't change the size, they will only change the time. The cache does not actually need to be too picky about getting the exact time		Idea: For each file, use a companion file to record size and last use time. Updates won't change the size, they will only change the time. The cache does not actually need to be too picky about getting the exact time of the last access in the file. If two processes update it at overlapping times, the time recorded will be close enough. The file will contain one value, that will be the time at which the matched data fie was last read. We will update the time when the lock on the data was was obtained, not released. The name of the file will be the be made of the data file name, a dot and the size in bytes of the data file. Example:
			* Data file: #usr#local#data#modis#hdf
			* Cache control file: #usr#local#data#modis#hdf.123456789; where 123456789 is the size in bytes and the file contains the last used time as its sole value.

			How to purge:
			# Look at every control file
			# Store the basename (i.e., data file name), size and last used time
			# Find the oldest files and remove until the total size of the cache falls below 90% of the max size.

			How to track the total size of the cache's data:
			# maintain a single 'global' cache control file
			# store the total size there.
			# for every file created, update that size
			# for every file deleted, update that size
			# use an exclusive rd/wr lock for those updates
			# Note: ''This technically locks the entire cache for write operations, but not for read operations.''

	===== Software we have =====		===== Software we have =====

Jimg: /* Cache design */

2012-03-22T17:58:43Z

Cache design

← Older revision		Revision as of 17:58, 22 March 2012
Line 48:		Line 48:
	In addition to the files themselves, maintain information about the time each file was last used and their size. The cache should also probably have information about its total size. Store this in the cache in files, so that it's accessible for the processes accessing the cache.		In addition to the files themselves, maintain information about the time each file was last used and their size. The cache should also probably have information about its total size. Store this in the cache in files, so that it's accessible for the processes accessing the cache.

	~~In the ''make~~ a ~~file'' step in the ''write a file'' operation, make sure to use open(2) in its atomic file creation mode (O_CREAT, ...)~~.		The cache will be a directory.

			Each file to be cached with have a name that is a function of its pathname, so it is guaranteed to be unique.

			It would be best if the size and last use time for each file in the cache was not recorded in a single file.

			Idea: For each file, use a companion file to record size and last use time. Updates won't change the size, they will only change the time. The cache does not actually need to be too picky about getting the exact time

			===== Software we have =====
	In the BES software, the class ''BESContainer'' provides a partially abstract base class that holds two methods: ''access()'' and ''release()'' that are used to access and release the 'container' that holds the data. The class ''BESFileContainer'' has concrete implementations for these methods that uncompress files if need be. The class ''BESUncompressManager'' performs the decompression operation and uses the ''BESCache'' class to store the result. BESCache handles the locking operations.		In the BES software, the class ''BESContainer'' provides a partially abstract base class that holds two methods: ''access()'' and ''release()'' that are used to access and release the 'container' that holds the data. The class ''BESFileContainer'' has concrete implementations for these methods that uncompress files if need be. The class ''BESUncompressManager'' performs the decompression operation and uses the ''BESCache'' class to store the result. BESCache handles the locking operations.

	To avoid making a new BESCache object on every call to BESContainer::access(), maybe move BESCache into BESUncompressManager.		To avoid making a new BESCache object on every call to BESContainer::access(), maybe move BESCache into BESUncompressManager.

Jimg: /* There are three basic operations that must be implemented */

2012-03-22T17:42:05Z

There are three basic operations that must be implemented

← Older revision		Revision as of 17:42, 22 March 2012
Line 29:		Line 29:
	The ''[http://linux.die.net/man/2/fcntl fcntl]'' command makes locks that are removed whenever ''any'' of the file descriptors to an open file are closed. So long as we use advisory locking and program logic follows the rules, we can use these locks and be sure that files will be unlocked whenever a handler closes the file, without any need to actually close the lock in the using the same file descriptor used to obtain the lock. This is apparently not the case for [http://linux.die.net/man/2/flock flock] or [http://linux.die.net/man/3/lockf lockf]. Both the BES and the HTTP caching code in libdap have support for releasing resources, so it's possible to use flock(2), et c., for this which also means we can use the open(2) and creat(2) calls for lock management.		The ''[http://linux.die.net/man/2/fcntl fcntl]'' command makes locks that are removed whenever ''any'' of the file descriptors to an open file are closed. So long as we use advisory locking and program logic follows the rules, we can use these locks and be sure that files will be unlocked whenever a handler closes the file, without any need to actually close the lock in the using the same file descriptor used to obtain the lock. This is apparently not the case for [http://linux.die.net/man/2/flock flock] or [http://linux.die.net/man/3/lockf lockf]. Both the BES and the HTTP caching code in libdap have support for releasing resources, so it's possible to use flock(2), et c., for this which also means we can use the open(2) and creat(2) calls for lock management.

	=== There are ~~three~~ basic operations that must be implemented ===		<!-- === There are basic operations that must be implemented ===

	;Is a file in the cache: Try to get a ''shared lock''. If the shared lock attempt was successful, the file can be read (because it's locked for read). (It's important to lock the file for read, because locking it is the only way to ensure it won't be deleted by the time the caller reads & processes the response.) Return status (successful lock or not) with the lock as a side effect.		;Is a file in the cache: Try to get a ''shared lock''. If the shared lock attempt was successful, the file can be read (because it's locked for read). (It's important to lock the file for read, because locking it is the only way to ensure it won't be deleted by the time the caller reads & processes the response.) Return status (successful lock or not) with the lock as a side effect.

	;Write a new file: Make the file and get an exclusive lock on it. Write the data to the file. release the exclusive lock. The trick here is that the ''make the file'' step may return an error because to processes could try to make the same file at the file at the same time, so the caller of this code must deal with the error that it cannot write the file and should then assume that another process is making a file of the same name and try to obtain a read-lock on it.		;Write a new file: Make the file and get an exclusive lock on it. Write the data to the file. release the exclusive lock. The trick here is that the ''make the file'' step may return an error because two processes could try to make the same file at the file at the same time, so the caller of this code must deal with the error that it cannot write the file and should then assume that another process is making a file of the same name and try to obtain a read-lock on it.

	;Delete a file: Get an ''exclusive lock'' on the file. Delete it.		;Delete a file: Get an ''exclusive lock'' on the file. Delete it.
			-->
			=== Operations the cache must provide ===

			# Create and lock a file so that data cam be decompressed
			#* Determine the cache size
			#* If it's too big, purge to 90% of max size
			# Get a shared lock to decompressed data

	=== Cache design ===		=== Cache design ===

Jimg: /* Assumptions */

2012-03-22T17:35:37Z

Assumptions

← Older revision		Revision as of 17:35, 22 March 2012
Line 13:		Line 13:

	=== Assumptions ===		=== Assumptions ===
			# The consistency of objects in the cache is most important
	# The ~~size of the cache can only change by the number of active processes using the cache (at any given instance).~~		# We do not want to lock the entire cache
	~~# The size~~ of the cache ~~will likely change only by the average size of a cached object times some constant that's less than or equal to the number of processes.~~		# The cache must work with multiple processes
	# We ~~accept as tolerable that the cache might grow beyond its bounds by a 'little bit' but that's an OK tradeoff if we don't have~~ to lock the cache ~~to count its size.~~		# we can tolerate some errors when computing the size of the cache (objects and their size, in the cache)
	# ~~We will count the size of the~~ cache ~~before every attempt to write a new item.~~		# The BES cache for compressed data will be one directory
	# We can ~~store~~ the size of the cache ~~in a file~~ and ~~access that using an exclusive lock (but that might make item #3 moot~~, ~~because then we always know the exact size of~~ the cache).		# It should use some sort if LRU or similar scheme

	=== Definitions ===		=== Definitions ===

Jimg: /* Releasing locks */

2012-03-22T15:36:53Z

Releasing locks

← Older revision		Revision as of 15:36, 22 March 2012
Line 27:		Line 27:
	=== Releasing locks ===		=== Releasing locks ===

	The ''[http://linux.die.net/man/2/fcntl fcntl]'' command makes locks that are removed whenever ''any'' of the file descriptors to an open file are closed. So long as we use advisory locking and program logic follows the rules, we can use these locks and be sure that files will be unlocked whenever a handler closes the file, without any need to actually close the lock in the using the same file descriptor used to obtain the lock. This is apparently not the case for [http://linux.die.net/man/2/flock flock] or [http://linux.die.net/man/3/lockf lockf].		The ''[http://linux.die.net/man/2/fcntl fcntl]'' command makes locks that are removed whenever ''any'' of the file descriptors to an open file are closed. So long as we use advisory locking and program logic follows the rules, we can use these locks and be sure that files will be unlocked whenever a handler closes the file, without any need to actually close the lock in the using the same file descriptor used to obtain the lock. This is apparently not the case for [http://linux.die.net/man/2/flock flock] or [http://linux.die.net/man/3/lockf lockf]. Both the BES and the HTTP caching code in libdap have support for releasing resources, so it's possible to use flock(2), et c., for this which also means we can use the open(2) and creat(2) calls for lock management.

	=== There are three basic operations that must be implemented ===		=== There are three basic operations that must be implemented ===

Jimg: /* Cache design */

2012-03-22T04:09:26Z

Cache design

← Older revision		Revision as of 04:09, 22 March 2012
Line 39:		Line 39:
	=== Cache design ===		=== Cache design ===

	In addition to the files themselves, maintain information about the time each file was last used and their size. The cache should also probably have information about its total size.		In addition to the files themselves, maintain information about the time each file was last used and their size. The cache should also probably have information about its total size. Store this in the cache in files, so that it's accessible for the processes accessing the cache.

	In the ''make a file'' step in the ''write a file'' operation, make sure to use open(2) in its atomic file creation mode (O_CREAT, ...).		In the ''make a file'' step in the ''write a file'' operation, make sure to use open(2) in its atomic file creation mode (O_CREAT, ...).

	In the BES software, the class ''BESContainer'' provides a partially abstract base class that holds two methods: ''access()'' and ''release()'' that are used to access and release the 'container' that holds the data. The class ''BESFileContainer'' has concrete implementations for these methods that uncompress files if need be. The class ''BESUncompressManager'' performs the decompression operation and uses the ''BESCache'' class to store the result. BESCache handles the locking operations.		In the BES software, the class ''BESContainer'' provides a partially abstract base class that holds two methods: ''access()'' and ''release()'' that are used to access and release the 'container' that holds the data. The class ''BESFileContainer'' has concrete implementations for these methods that uncompress files if need be. The class ''BESUncompressManager'' performs the decompression operation and uses the ''BESCache'' class to store the result. BESCache handles the locking operations.

			To avoid making a new BESCache object on every call to BESContainer::access(), maybe move BESCache into BESUncompressManager.