You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Davi Arnaut <da...@haxent.com.br> on 2006/07/24 02:50:32 UTC
[patch 02/10] revamped mod_disk_cache directory structure
This patch converts the mod_disk_cache cache directory structure to a
uniformly distributed N level hierarchy. The admin specifies the number
of levels (or directories) and the files are scattered across the
directories. Example:
CacheRoot /cache/
# CacheDirLevels n l1 l2 ln
CacheDirLevels 2 4 256 16
In this example, the directory tree will be three levels deep. The first
level will have 4 directories, each of the 4 first level directories will
have 256 directories (second level) and so on to the last level.
Directory tree layout for the example:
/cache/
/cache/0d
/cache/0d/36
/cache/0d/36/06
/cache/0d/36/06/7a50a5c38a73abdb6db28a2b0f6881e5.data
/cache/0d/36/06/7a50a5c38a73abdb6db28a2b0f6881e5.header
This patch adds support for symlinking the directories to separate disk
or partitions by creating the cache files on their destination directory.
The symlinks can also be used to load balance the cache files between
disks because each last level directory gets the same (on average) number
of files -- on a cache setup with 4 first level directories each one
receives 25%, linking the three of them to disk A and the last one to
disk B yields a 75/25 distribution between disks A (75) and B (25).
Index: trunk/modules/cache/cache_util.c
===================================================================
--- trunk.orig/modules/cache/cache_util.c
+++ trunk/modules/cache/cache_util.c
@@ -19,6 +19,7 @@
#include "mod_cache.h"
#include <ap_provider.h>
+#include <util_md5.h>
/* -------------------------------------------------------------- */
@@ -489,54 +490,49 @@ CACHE_DECLARE(void) ap_cache_usec2hex(ap
y[sizeof(j) * 2] = '\0';
}
-static void cache_hash(const char *it, char *val, int ndepth, int nlength)
+static unsigned int cdb_string_hash(const char *str)
{
- apr_md5_ctx_t context;
- unsigned char digest[16];
- char tmp[22];
- int i, k, d;
- unsigned int x;
- static const char enc_table[64] =
- "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_@";
-
- apr_md5_init(&context);
- apr_md5_update(&context, (const unsigned char *) it, strlen(it));
- apr_md5_final(digest, &context);
-
- /* encode 128 bits as 22 characters, using a modified uuencoding
- * the encoding is 3 bytes -> 4 characters* i.e. 128 bits is
- * 5 x 3 bytes + 1 byte -> 5 * 4 characters + 2 characters
- */
- for (i = 0, k = 0; i < 15; i += 3) {
- x = (digest[i] << 16) | (digest[i + 1] << 8) | digest[i + 2];
- tmp[k++] = enc_table[x >> 18];
- tmp[k++] = enc_table[(x >> 12) & 0x3f];
- tmp[k++] = enc_table[(x >> 6) & 0x3f];
- tmp[k++] = enc_table[x & 0x3f];
- }
-
- /* one byte left */
- x = digest[15];
- tmp[k++] = enc_table[x >> 2]; /* use up 6 bits */
- tmp[k++] = enc_table[(x << 4) & 0x3f];
-
- /* now split into directory levels */
- for (i = k = d = 0; d < ndepth; ++d) {
- memcpy(&val[i], &tmp[k], nlength);
- k += nlength;
- val[i + nlength] = '/';
- i += nlength + 1;
- }
- memcpy(&val[i], &tmp[k], 22 - k);
- val[i + 22 - k] = '\0';
-}
-
-CACHE_DECLARE(char *)ap_cache_generate_name(apr_pool_t *p, int dirlevels,
- int dirlength, const char *name)
-{
- char hashfile[66];
- cache_hash(name, hashfile, dirlevels, dirlength);
- return apr_pstrdup(p, hashfile);
+ unsigned int hash = 5381;
+
+ while (*str) {
+ hash += (hash << 5);
+ hash ^= *str++;
+ }
+
+ return hash;
+}
+
+#define MD5_HEXDIGESTSIZE (APR_MD5_DIGESTSIZE * 2 + 1)
+
+CACHE_DECLARE(char *)ap_cache_generate_name(apr_pool_t *p, unsigned int nlevels,
+ unsigned int *dirlevels,
+ unsigned int *divisors,
+ const char *name)
+{
+ char *md5_hash;
+ unsigned int i;
+ char *ptr, *key;
+ unsigned char h;
+ unsigned int cdb_hash;
+ static const char hex[] = "0123456789abcdef";
+
+ md5_hash = ap_md5_binary(p, (unsigned char *) name, (int) strlen(name));
+
+ cdb_hash = cdb_string_hash(name);
+
+ key = ptr = apr_palloc(p, nlevels * LEVEL_DIR_LENGTH +
+ MD5_HEXDIGESTSIZE);
+
+ for (i = 0; i < nlevels; i++) {
+ h = (cdb_hash / divisors[i]) % dirlevels[i];
+ *ptr++ = hex[h >> 4];
+ *ptr++ = hex[h & 0xf];
+ *ptr++ = '/';
+ }
+
+ memcpy(ptr, md5_hash, MD5_HEXDIGESTSIZE);
+
+ return key;
}
/* Create a new table consisting of those elements from an input
Index: trunk/modules/cache/mod_cache.h
===================================================================
--- trunk.orig/modules/cache/mod_cache.h
+++ trunk/modules/cache/mod_cache.h
@@ -72,6 +72,8 @@
#include "apr_atomic.h"
+#define LEVEL_DIR_LENGTH 3
+
#ifndef MAX
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#endif
@@ -274,8 +276,9 @@ CACHE_DECLARE(void) ap_cache_accept_head
CACHE_DECLARE(apr_time_t) ap_cache_hex2usec(const char *x);
CACHE_DECLARE(void) ap_cache_usec2hex(apr_time_t j, char *y);
-CACHE_DECLARE(char *) ap_cache_generate_name(apr_pool_t *p, int dirlevels,
- int dirlength,
+CACHE_DECLARE(char *) ap_cache_generate_name(apr_pool_t *p, unsigned int nlevels,
+ unsigned int *dirlevels,
+ unsigned int *divisors,
const char *name);
CACHE_DECLARE(cache_provider_list *)ap_cache_get_providers(request_rec *r, cache_server_conf *conf, apr_uri_t uri);
CACHE_DECLARE(int) ap_cache_liststr(apr_pool_t *p, const char *list,
Index: trunk/modules/cache/mod_disk_cache.c
===================================================================
--- trunk.orig/modules/cache/mod_disk_cache.c
+++ trunk/modules/cache/mod_disk_cache.c
@@ -70,13 +70,14 @@ static char *header_file(apr_pool_t *p,
disk_cache_object_t *dobj, const char *name)
{
if (!dobj->hashfile) {
- dobj->hashfile = ap_cache_generate_name(p, conf->dirlevels,
- conf->dirlength, name);
+ dobj->hashfile = ap_cache_generate_name(p, conf->nlevels, conf->dirlevels,
+ conf->divisors, name);
}
if (dobj->prefix) {
return apr_pstrcat(p, dobj->prefix, CACHE_VDIR_SUFFIX, "/",
- dobj->hashfile, CACHE_HEADER_SUFFIX, NULL);
+ dobj->hashfile + (conf->nlevels + LEVEL_DIR_LENGTH),
+ CACHE_HEADER_SUFFIX, NULL);
}
else {
return apr_pstrcat(p, conf->cache_root, "/", dobj->hashfile,
@@ -88,13 +89,14 @@ static char *data_file(apr_pool_t *p, di
disk_cache_object_t *dobj, const char *name)
{
if (!dobj->hashfile) {
- dobj->hashfile = ap_cache_generate_name(p, conf->dirlevels,
- conf->dirlength, name);
+ dobj->hashfile = ap_cache_generate_name(p, conf->nlevels, conf->dirlevels,
+ conf->divisors, name);
}
if (dobj->prefix) {
return apr_pstrcat(p, dobj->prefix, CACHE_VDIR_SUFFIX, "/",
- dobj->hashfile, CACHE_DATA_SUFFIX, NULL);
+ dobj->hashfile + (conf->nlevels + LEVEL_DIR_LENGTH),
+ CACHE_DATA_SUFFIX, NULL);
}
else {
return apr_pstrcat(p, conf->cache_root, "/", dobj->hashfile,
@@ -102,7 +104,7 @@ static char *data_file(apr_pool_t *p, di
}
}
-static void mkdir_structure(disk_cache_conf *conf, const char *file, apr_pool_t *pool)
+static void mkdir_structure(disk_cache_conf *conf, char *file, apr_pool_t *pool)
{
apr_status_t rv;
char *p;
@@ -123,11 +125,41 @@ static void mkdir_structure(disk_cache_c
}
}
+static apr_status_t disk_mktemp(apr_file_t **fp, const char *dest, char **tempfile,
+ apr_int32_t flags, disk_cache_conf *conf,
+ apr_pool_t *p)
+{
+ char *temp;
+ apr_status_t rv;
+ struct iovec iov[2];
+
+ iov[0].iov_base = (char *) dest;
+ iov[0].iov_len = conf->nlevels * LEVEL_DIR_LENGTH +
+ conf->cache_root_len;
+
+ iov[1].iov_base = AP_TEMPFILE;
+ iov[1].iov_len = sizeof AP_TEMPFILE;
+
+ temp = apr_pstrcatv(p, iov, 2, NULL);
+
+ rv = apr_file_mktemp(fp, temp, flags, p);
+
+ if (APR_STATUS_IS_ENOENT(rv)) {
+ mkdir_structure(conf, temp, p);
+ memcpy(temp + iov[0].iov_len, AP_TEMPFILE, sizeof AP_TEMPFILE);
+ rv = apr_file_mktemp(fp, temp, flags, p);
+ }
+
+ *tempfile = temp;
+
+ return rv;
+}
+
/* htcacheclean may remove directories underneath us.
* So, we'll try renaming three times at a cost of 0.002 seconds.
*/
static apr_status_t safe_file_rename(disk_cache_conf *conf,
- const char *src, const char *dest,
+ const char *src, char *dest,
apr_pool_t *pool)
{
apr_status_t rv;
@@ -359,7 +391,6 @@ static int create_entity(cache_handle_t
dobj->root_len = conf->cache_root_len;
dobj->datafile = data_file(r->pool, conf, dobj, key);
dobj->hdrsfile = header_file(r->pool, conf, dobj, key);
- dobj->tempfile = apr_pstrcat(r->pool, conf->cache_root, AP_TEMPFILE, NULL);
return OK;
}
@@ -467,7 +498,6 @@ static int open_entity(cache_handle_t *h
dobj->key = nkey;
dobj->name = key;
dobj->datafile = data_file(r->pool, conf, dobj, nkey);
- dobj->tempfile = apr_pstrcat(r->pool, conf->cache_root, AP_TEMPFILE, NULL);
/* Open the data file */
flags = APR_READ|APR_BINARY;
@@ -841,11 +871,9 @@ static apr_status_t store_headers(cache_
apr_array_header_t* varray;
apr_uint32_t format = VARY_FORMAT_VERSION;
- mkdir_structure(conf, dobj->hdrsfile, r->pool);
-
- rv = apr_file_mktemp(&dobj->tfd, dobj->tempfile,
- APR_CREATE | APR_WRITE | APR_BINARY | APR_EXCL,
- r->pool);
+ rv = disk_mktemp(&dobj->tfd, dobj->hdrsfile, &dobj->tempfile,
+ APR_CREATE | APR_WRITE | APR_BINARY | APR_EXCL,
+ conf, r->pool);
if (rv != APR_SUCCESS) {
return rv;
@@ -876,7 +904,6 @@ static apr_status_t store_headers(cache_
return rv;
}
- dobj->tempfile = apr_pstrcat(r->pool, conf->cache_root, AP_TEMPFILE, NULL);
tmp = regen_key(r->pool, r->headers_in, varray, dobj->name);
dobj->prefix = dobj->hdrsfile;
dobj->hashfile = NULL;
@@ -885,10 +912,9 @@ static apr_status_t store_headers(cache_
}
}
-
- rv = apr_file_mktemp(&dobj->hfd, dobj->tempfile,
- APR_CREATE | APR_WRITE | APR_BINARY |
- APR_BUFFERED | APR_EXCL, r->pool);
+ rv = disk_mktemp(&dobj->hfd, dobj->hdrsfile, &dobj->tempfile,
+ APR_CREATE | APR_WRITE | APR_BINARY | APR_BUFFERED |
+ APR_EXCL, conf, r->pool);
if (rv != APR_SUCCESS) {
return rv;
@@ -956,9 +982,6 @@ static apr_status_t store_headers(cache_
* about to write the new headers file.
*/
rv = apr_file_remove(dobj->hdrsfile, r->pool);
- if (rv != APR_SUCCESS) {
- mkdir_structure(conf, dobj->hdrsfile, r->pool);
- }
rv = safe_file_rename(conf, dobj->tempfile, dobj->hdrsfile, r->pool);
if (rv != APR_SUCCESS) {
@@ -969,8 +992,6 @@ static apr_status_t store_headers(cache_
return rv;
}
- dobj->tempfile = apr_pstrcat(r->pool, conf->cache_root, AP_TEMPFILE, NULL);
-
ap_log_error(APLOG_MARK, APLOG_DEBUG, 0, r->server,
"disk_cache: Stored headers for URL %s", dobj->name);
return APR_SUCCESS;
@@ -989,9 +1010,9 @@ static apr_status_t store_body(cache_han
* in file_cache_el_final().
*/
if (!dobj->tfd) {
- rv = apr_file_mktemp(&dobj->tfd, dobj->tempfile,
- APR_CREATE | APR_WRITE | APR_BINARY |
- APR_BUFFERED | APR_EXCL, r->pool);
+ rv = disk_mktemp(&dobj->tfd, dobj->datafile, &dobj->tempfile,
+ APR_CREATE | APR_WRITE | APR_BINARY |
+ APR_BUFFERED | APR_EXCL, conf, r->pool);
if (rv != APR_SUCCESS) {
return rv;
}
@@ -1067,19 +1088,35 @@ static apr_status_t store_body(cache_han
return APR_SUCCESS;
}
+static void calculate_divisors(unsigned int nlevels, unsigned int *dirlevels,
+ unsigned int *divisors)
+{
+ unsigned int i;
+
+ divisors[0] = 1;
+
+ for (i = 1; i < nlevels; i++) {
+ divisors[i] = divisors[i-1] * dirlevels[i-1];
+ }
+}
+
static void *create_config(apr_pool_t *p, server_rec *s)
{
+ unsigned int divisors[DEFAULT_NLEVELS];
disk_cache_conf *conf = apr_pcalloc(p, sizeof(disk_cache_conf));
+ unsigned int dirlevels[] = { DEFAULT_DIRLEVEL1, DEFAULT_DIRLEVEL2 };
- /* XXX: Set default values */
- conf->dirlevels = DEFAULT_DIRLEVELS;
- conf->dirlength = DEFAULT_DIRLENGTH;
+ conf->nlevels = sizeof dirlevels/sizeof *dirlevels;
+ conf->dirlevels = dirlevels;
+ conf->divisors = divisors;
conf->maxfs = DEFAULT_MAX_FILE_SIZE;
conf->minfs = DEFAULT_MIN_FILE_SIZE;
conf->cache_root = NULL;
conf->cache_root_len = 0;
+ calculate_divisors(conf->nlevels, conf->dirlevels, conf->divisors);
+
return conf;
}
@@ -1098,40 +1135,36 @@ static const char
return NULL;
}
-/*
- * Consider eliminating the next two directives in favor of
- * Ian's prime number hash...
- * key = hash_fn( r->uri)
- * filename = "/key % prime1 /key %prime2/key %prime3"
- */
static const char
-*set_cache_dirlevels(cmd_parms *parms, void *in_struct_ptr, const char *arg)
+*set_cache_dirlevels(cmd_parms *parms, void *in_struct_ptr, int argc,
+ char *const argv[])
{
+ unsigned int len;
disk_cache_conf *conf = ap_get_module_config(parms->server->module_config,
&disk_cache_module);
- int val = atoi(arg);
- if (val < 1)
- return "CacheDirLevels value must be an integer greater than 0";
- if (val * conf->dirlength > CACHEFILE_LEN)
- return "CacheDirLevels*CacheDirLength value must not be higher than 20";
- conf->dirlevels = val;
- return NULL;
-}
-static const char
-*set_cache_dirlength(cmd_parms *parms, void *in_struct_ptr, const char *arg)
-{
- disk_cache_conf *conf = ap_get_module_config(parms->server->module_config,
- &disk_cache_module);
- int val = atoi(arg);
- if (val < 1)
- return "CacheDirLength value must be an integer greater than 0";
- if (val * conf->dirlevels > CACHEFILE_LEN)
- return "CacheDirLevels*CacheDirLength value must not be higher than 20";
- conf->dirlength = val;
+ if (!argc)
+ return "The number of levels was not specified.";
+
+ conf->nlevels = atoi(*argv);
+
+ if (conf->nlevels != --argc)
+ return apr_psprintf(parms->pool, "%u levels, but only %u were given.",
+ conf->nlevels, argc);
+
+ len = conf->nlevels * sizeof(*conf->dirlevels);
+
+ conf->dirlevels = apr_palloc(parms->pool, len);
+ conf->divisors = apr_palloc(parms->pool, len);
+
+ while (argc--) {
+ conf->dirlevels[argc] = atoi(argv[argc+1]);
+ }
+
+ calculate_divisors(conf->nlevels, conf->dirlevels, conf->divisors);
+
return NULL;
}
-
static const char
*set_cache_minfs(cmd_parms *parms, void *in_struct_ptr, const char *arg)
{
@@ -1153,14 +1186,12 @@ static const command_rec disk_cache_cmds
{
AP_INIT_TAKE1("CacheRoot", set_cache_root, NULL, RSRC_CONF,
"The directory to store cache files"),
- AP_INIT_TAKE1("CacheDirLevels", set_cache_dirlevels, NULL, RSRC_CONF,
- "The number of levels of subdirectories in the cache"),
- AP_INIT_TAKE1("CacheDirLength", set_cache_dirlength, NULL, RSRC_CONF,
- "The number of characters in subdirectory names"),
AP_INIT_TAKE1("CacheMinFileSize", set_cache_minfs, NULL, RSRC_CONF,
"The minimum file size to cache a document"),
AP_INIT_TAKE1("CacheMaxFileSize", set_cache_maxfs, NULL, RSRC_CONF,
"The maximum file size to cache a document"),
+ AP_INIT_TAKE_ARGV("CacheDirLevels", set_cache_dirlevels, NULL, RSRC_CONF,
+ "The number of levels of subdirectories in the cache"),
{NULL}
};
Index: trunk/modules/cache/mod_disk_cache.h
===================================================================
--- trunk.orig/modules/cache/mod_disk_cache.h
+++ trunk/modules/cache/mod_disk_cache.h
@@ -61,10 +61,10 @@ typedef struct disk_cache_object {
char *tempfile; /* temp file tohold the content */
const char *prefix;
const char *datafile; /* name of file where the data will go */
- const char *hdrsfile; /* name of file where the hdrs will go */
+ char *hdrsfile; /* name of file where the hdrs will go */
const char *hashfile; /* Computed hash key for this URI */
- const char *name; /* Requested URI without vary bits - suitable for mortals. */
- const char *key; /* On-disk prefix; URI with Vary bits (if present) */
+ const char *name; /* Requested URI without vary bits - suitable for mortals. */
+ const char *key; /* On-disk prefix; URI with Vary bits (if present) */
apr_file_t *fd; /* data file */
apr_file_t *hfd; /* headers file */
apr_file_t *tfd; /* temporary file for data */
@@ -78,16 +78,19 @@ typedef struct disk_cache_object {
*/
/* TODO: Make defaults OS specific */
#define CACHEFILE_LEN 20 /* must be less than HASH_LEN/2 */
-#define DEFAULT_DIRLEVELS 3
-#define DEFAULT_DIRLENGTH 2
+#define DEFAULT_NLEVELS 2
+#define DEFAULT_DIRLEVEL1 16
+#define DEFAULT_DIRLEVEL2 256
+#define DEFAULT_DIRLEVEL_MAX 256
#define DEFAULT_MIN_FILE_SIZE 1
#define DEFAULT_MAX_FILE_SIZE 1000000
typedef struct {
const char* cache_root;
apr_size_t cache_root_len;
- int dirlevels; /* Number of levels of subdirectories */
- int dirlength; /* Length of subdirectory names */
+ unsigned int nlevels; /* number of directories levels */
+ unsigned int *dirlevels; /* number of subdirs for each level */
+ unsigned int *divisors; /* divisor for each level */
apr_size_t minfs; /* minumum file size for cached files */
apr_size_t maxfs; /* maximum file size for cached files */
} disk_cache_conf;
--