subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From stef...@apache.org
Subject svn commit: r1443803 - in /subversion/branches/fsfs-format7: subversion/include/private/svn_cache.h subversion/libsvn_fs_fs/caching.c subversion/libsvn_subr/cache-membuffer.c subversion/tests/libsvn_subr/cache-test.c tools/server-side/fsfs-stats.c
Date Fri, 08 Feb 2013 00:10:46 GMT
Author: stefan2
Date: Fri Feb  8 00:10:45 2013
New Revision: 1443803

URL: http://svn.apache.org/r1443803
Log:
On the fsfs-format7 branch:  introduce the notion of priority classes
to cached data.  With that, block-read may prefetch lots of data even
into small caches without evicting the parts that are most effective
to keep in cache.

More tuning on the insertion / eviction heuristics can be expected in
the near future.

* subversion/include/private/svn_cache.h
  (SVN_CACHE__MEMBUFFER_HIGH_PRIORITY,
   SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY,
   SVN_CACHE__MEMBUFFER_LOW_PRIORITY): define standard priority classes
  (svn_cache__create_membuffer_cache): add priority parameter to cache

* subversion/libsvn_subr/cache-membuffer.c
  (entry_t): tag all entries with a priority
  (find_entry): make high-prio entries less likely to be evicted
  (ensure_data_insertable): adapt eviction code
  (membuffer_cache_set_internal,
   membuffer_cache_set,
   svn_membuffer_cache_set,
   svn_membuffer_cache_set_partial,
   svn_cache__create_membuffer_cache): pass priority info through
  (svn_membuffer_cache_t): add priority class info

* subversion/libsvn_fs_fs/caching.c
  (create_cache): add priority parameter
  (svn_fs_fs__initialize_caches,
   svn_fs_fs__initialize_txn_caches): assign priority classes to caches

* subversion/tests/libsvn_subr/cache-test.c
  (test_membuffer_cache_basic): update caller

* tools/server-side/fsfs-stats.c
  (read_revisions): ditto

Modified:
    subversion/branches/fsfs-format7/subversion/include/private/svn_cache.h
    subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/caching.c
    subversion/branches/fsfs-format7/subversion/libsvn_subr/cache-membuffer.c
    subversion/branches/fsfs-format7/subversion/tests/libsvn_subr/cache-test.c
    subversion/branches/fsfs-format7/tools/server-side/fsfs-stats.c

Modified: subversion/branches/fsfs-format7/subversion/include/private/svn_cache.h
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/include/private/svn_cache.h?rev=1443803&r1=1443802&r2=1443803&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/include/private/svn_cache.h (original)
+++ subversion/branches/fsfs-format7/subversion/include/private/svn_cache.h Fri Feb  8 00:10:45
2013
@@ -299,6 +299,33 @@ svn_cache__membuffer_cache_create(svn_me
                                   apr_pool_t *result_pool);
 
 /**
+ * @defgroup Standard priority classes for #svn_cache__create_membuffer_cache.
+ * @{
+ */
+
+/**
+ * Data in this priority class should not be removed from the cache unless
+ * absolutely necessary.  Use of this should be very restricted.
+ */
+#define SVN_CACHE__MEMBUFFER_HIGH_PRIORITY   10000
+
+/**
+ * Data in this priority class has a good chance to remain in cache unless
+ * there is more data in this class than the cache's capcity.  Use of this
+ * as the default for all information that is costly to fetch from disk.
+ */
+#define SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY 1000
+
+/**
+ * Data in this priority class will be removed as soon as the cache starts
+ * filling up.  Use of this for ephemeral data that can easisly be acquired
+ * again from other sources.
+ */
+#define SVN_CACHE__MEMBUFFER_LOW_PRIORITY      100
+
+/** @} */
+
+/**
  * Creates a new cache in @a *cache_p, storing the data in a potentially
  * shared @a membuffer object.  The elements in the cache will be indexed
  * by keys of length @a klen, which may be APR_HASH_KEY_STRING if they
@@ -306,7 +333,9 @@ svn_cache__membuffer_cache_create(svn_me
  * serialize_func and deserialized using @a deserialize_func.  Because
  * the same memcache object may cache many different kinds of values
  * form multiple caches, @a prefix should be specified to differentiate
- * this cache from other caches.  @a *cache_p will be allocated in @a result_pool.
+ * this cache from other caches.  All entries written through this cache
+ * interface will be assigned into the given @a priority class.  @a *cache_p
+ * will be allocated in @a result_pool.
  *
  * If @a deserialize_func is NULL, then the data is returned as an
  * svn_string_t; if @a serialize_func is NULL, then the data is
@@ -325,6 +354,7 @@ svn_cache__create_membuffer_cache(svn_ca
                                   svn_cache__deserialize_func_t deserialize,
                                   apr_ssize_t klen,
                                   const char *prefix,
+                                  apr_uint32_t priority,
                                   svn_boolean_t thread_safe,
                                   apr_pool_t *result_pool);
 

Modified: subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/caching.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/caching.c?rev=1443803&r1=1443802&r2=1443803&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/caching.c (original)
+++ subversion/branches/fsfs-format7/subversion/libsvn_fs_fs/caching.c Fri Feb  8 00:10:45
2013
@@ -232,7 +232,8 @@ init_callbacks(svn_cache__t *cache,
  * Creates memcache if MEMCACHE is not NULL. Creates membuffer cache if
  * MEMBUFFER is not NULL. Fallbacks to inprocess cache if MEMCACHE and
  * MEMBUFFER are NULL and pages is non-zero.  Sets *CACHE_P to NULL
- * otherwise.
+ * otherwise.  Use the given PRIORITY class for the new cache.  If it
+ * is 0, then use the default priority class.
  *
  * Unless NO_HANDLER is true, register an error handler that reports errors
  * as warnings to the FS warning callback.
@@ -249,6 +250,7 @@ create_cache(svn_cache__t **cache_p,
              svn_cache__deserialize_func_t deserializer,
              apr_ssize_t klen,
              const char *prefix,
+             apr_uint32_t priority,
              svn_fs_t *fs,
              svn_boolean_t no_handler,
              apr_pool_t *pool)
@@ -256,6 +258,8 @@ create_cache(svn_cache__t **cache_p,
   svn_cache__error_handler_t error_handler = no_handler
                                            ? NULL
                                            : warn_and_fail_on_cache_errors;
+  if (priority == 0)
+    priority = SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY;
 
   if (memcache)
     {
@@ -270,7 +274,7 @@ create_cache(svn_cache__t **cache_p,
     {
       SVN_ERR(svn_cache__create_membuffer_cache(
                 cache_p, membuffer, serializer, deserializer,
-                klen, prefix, FALSE, pool));
+                klen, prefix, priority, FALSE, pool));
     }
   else if (pages)
     {
@@ -331,6 +335,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__deserialize_id,
                        sizeof(svn_revnum_t),
                        apr_pstrcat(pool, prefix, "RRI", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -345,6 +350,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__dag_deserialize,
                        APR_HASH_KEY_STRING,
                        apr_pstrcat(pool, prefix, "DAG", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -361,6 +367,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__deserialize_dir_entries,
                        sizeof(pair_cache_key_t),
                        apr_pstrcat(pool, prefix, "DIR", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -376,6 +383,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        sizeof(svn_revnum_t),
                        apr_pstrcat(pool, prefix, "PACK-MANIFEST",
                                    (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -389,6 +397,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__deserialize_node_revision,
                        sizeof(pair_cache_key_t),
                        apr_pstrcat(pool, prefix, "NODEREVS", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -402,6 +411,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__deserialize_rep_header,
                        sizeof(pair_cache_key_t),
                        apr_pstrcat(pool, prefix, "REPHEADER", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -415,6 +425,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                        svn_fs_fs__deserialize_changes,
                        sizeof(svn_revnum_t),
                        apr_pstrcat(pool, prefix, "CHANGES", (char *)NULL),
+                       0,
                        fs,
                        no_handler,
                        fs->pool));
@@ -430,6 +441,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            NULL, NULL,
                            sizeof(pair_cache_key_t),
                            apr_pstrcat(pool, prefix, "TEXT", (char *)NULL),
+                           SVN_CACHE__MEMBUFFER_LOW_PRIORITY,
                            fs,
                            no_handler,
                            fs->pool));
@@ -443,6 +455,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            sizeof(pair_cache_key_t),
                            apr_pstrcat(pool, prefix, "PROP",
                                        (char *)NULL),
+                           0,
                            fs,
                            no_handler,
                            fs->pool));
@@ -456,6 +469,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            APR_HASH_KEY_STRING,
                            apr_pstrcat(pool, prefix, "MERGEINFO",
                                        (char *)NULL),
+                           0,
                            fs,
                            no_handler,
                            fs->pool));
@@ -469,6 +483,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            APR_HASH_KEY_STRING,
                            apr_pstrcat(pool, prefix, "HAS_MERGEINFO",
                                        (char *)NULL),
+                           0,
                            fs,
                            no_handler,
                            fs->pool));
@@ -493,6 +508,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            sizeof(pair_cache_key_t),
                            apr_pstrcat(pool, prefix, "REVPROP",
                                        (char *)NULL),
+                           0,
                            fs,
                            no_handler,
                            fs->pool));
@@ -514,6 +530,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            sizeof(window_cache_key_t),
                            apr_pstrcat(pool, prefix, "TXDELTA_WINDOW",
                                        (char *)NULL),
+                           0,
                            fs,
                            no_handler,
                            fs->pool));
@@ -527,6 +544,7 @@ svn_fs_fs__initialize_caches(svn_fs_t *f
                            sizeof(window_cache_key_t),
                            apr_pstrcat(pool, prefix, "COMBINED_WINDOW",
                                        (char *)NULL),
+                           SVN_CACHE__MEMBUFFER_LOW_PRIORITY,
                            fs,
                            no_handler,
                            fs->pool));
@@ -630,6 +648,7 @@ svn_fs_fs__initialize_txn_caches(svn_fs_
                        APR_HASH_KEY_STRING,
                        apr_pstrcat(pool, prefix, "TXNDIR",
                                    (char *)NULL),
+                       0,
                        fs,
                        TRUE,
                        pool));

Modified: subversion/branches/fsfs-format7/subversion/libsvn_subr/cache-membuffer.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/libsvn_subr/cache-membuffer.c?rev=1443803&r1=1443802&r2=1443803&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/libsvn_subr/cache-membuffer.c (original)
+++ subversion/branches/fsfs-format7/subversion/libsvn_subr/cache-membuffer.c Fri Feb  8 00:10:45
2013
@@ -350,6 +350,10 @@ typedef struct entry_t
    */
   apr_uint32_t previous;
 
+  /* Priority of this entry.  This entry will not be replaced by lower-
+   * priority items.
+   */
+  apr_uint32_t priority;
 #ifdef SVN_DEBUG_CACHE_MEMBUFFER
   /* Remember type, content and key hashes.
    */
@@ -919,7 +923,8 @@ find_entry(svn_membuffer_t *cache,
            */
           entry = &group->entries[rand() % GROUP_SIZE];
           for (i = 1; i < GROUP_SIZE; ++i)
-            if (entry->hit_count > group->entries[i].hit_count)
+            if (  entry->hit_count * entry->priority
+                > group->entries[i].hit_count * group->entries[i].priority)
               entry = &group->entries[i];
 
           /* for the entries that don't have been removed,
@@ -983,12 +988,16 @@ move_entry(svn_membuffer_t *cache, entry
 }
 
 /* If necessary, enlarge the insertion window until it is at least
- * SIZE bytes long. SIZE must not exceed the data buffer size.
+ * SIZE bytes long.  SIZE must not exceed the data buffer size.  The
+ * new item will be of the given PRIORITY class.
+ *
  * Return TRUE if enough room could be found or made. A FALSE result
  * indicates that the respective item shall not be added.
  */
 static svn_boolean_t
-ensure_data_insertable(svn_membuffer_t *cache, apr_size_t size)
+ensure_data_insertable(svn_membuffer_t *cache,
+                       apr_uint32_t priority,
+                       apr_size_t size)
 {
   entry_t *entry;
   apr_uint64_t average_hit_value;
@@ -997,7 +1006,7 @@ ensure_data_insertable(svn_membuffer_t *
   /* accumulated size of the entries that have been removed to make
    * room for the new one.
    */
-  apr_size_t drop_size = 0;
+  apr_size_t moved_size = 0;
 
   /* This loop will eventually terminate because every cache entry
    * would get dropped eventually:
@@ -1024,15 +1033,11 @@ ensure_data_insertable(svn_membuffer_t *
       if (end >= size + cache->current_data)
         return TRUE;
 
-      /* Don't be too eager to cache data. Smaller items will fit into
-       * the cache after dropping a single item. Of the larger ones, we
-       * will only accept about 50%. They are also likely to get evicted
-       * soon due to their notoriously low hit counts.
-       *
-       * As long as enough similarly or even larger sized entries already
-       * exist in the cache, much less insert requests will be rejected.
+      /* Don't be too eager to cache data.  If a lot of data has been 
+       * moved around, the current item has probably a relatively low
+       * priority.  So, give up after some time.
        */
-      if (2 * drop_size > size)
+      if (moved_size > 16 * size)
         return FALSE;
 
       /* try to enlarge the insertion window
@@ -1049,6 +1054,7 @@ ensure_data_insertable(svn_membuffer_t *
         }
       else
         {
+          svn_boolean_t keep;
           entry = get_entry(cache, cache->next);
 
           /* Keep entries that are very small. Those are likely to be data
@@ -1059,45 +1065,45 @@ ensure_data_insertable(svn_membuffer_t *
           if (   (apr_uint64_t)entry->size * cache->used_entries
                < cache->data_used / 8)
             {
-              move_entry(cache, entry);
+              keep = TRUE;
             }
-          else
+          else if (priority != entry->priority)
             {
-              svn_boolean_t keep;
-
-              if (cache->hit_count > cache->used_entries)
-                {
-                  /* Roll the dice and determine a threshold somewhere from 0 up
-                   * to 2 times the average hit count.
-                   */
-                  average_hit_value = cache->hit_count / cache->used_entries;
-                  threshold = (average_hit_value+1) * (rand() % 4096) / 2048;
+              /* strictly let the higher priority win */
+              keep = entry->priority > priority;
+            }
+          else if (cache->hit_count > cache->used_entries)
+            {
+              /* Roll the dice and determine a threshold somewhere
+               * from 0 up to 2 times the average hit count.
+               */
+              average_hit_value = cache->hit_count / cache->used_entries;
+              threshold = (average_hit_value+1) * (rand() % 4096) / 2048;
 
-                  keep = entry->hit_count >= threshold;
-                }
-              else
-                {
-                  /* general hit count is low. Keep everything that got hit
-                   * at all and assign some 50% survival chance to everything
-                   * else.
-                   */
-                  keep = (entry->hit_count > 0) || (rand() & 1);
-                }
+              keep = entry->hit_count > threshold;
+            }
+          else
+            {
+              /* general hit count is low. Keep everything that got hit
+               * at all and assign some 50% survival chance to everything
+               * else.
+               */
+              keep = rand() & 1;
+            }
 
-              /* keepers or destroyers? */
-              if (keep)
-                {
-                  move_entry(cache, entry);
-                }
-              else
-                {
-                 /* Drop the entry from the end of the insertion window, if it
-                  * has been hit less than the threshold. Otherwise, keep it and
-                  * move the insertion window one entry further.
-                  */
-                  drop_size += entry->size;
-                  drop_entry(cache, entry);
-                }
+          /* keepers or destroyers? */
+          if (keep)
+            {
+              moved_size += entry->size;
+              move_entry(cache, entry);
+            }
+          else
+            {
+              /* Drop the entry from the end of the insertion window, if it
+               * has been hit less than the threshold. Otherwise, keep it and
+               * move the insertion window one entry further.
+               */
+              drop_entry(cache, entry);
             }
         }
     }
@@ -1364,6 +1370,7 @@ membuffer_cache_set_internal(svn_membuff
                              apr_uint32_t group_index,
                              char *buffer,
                              apr_size_t size,
+                             apr_uint32_t priority,
                              DEBUG_CACHE_MEMBUFFER_TAG_ARG
                              apr_pool_t *scratch_pool)
 {
@@ -1376,6 +1383,7 @@ membuffer_cache_set_internal(svn_membuff
     {
       cache->data_used += size - entry->size;
       entry->size = size;
+      entry->priority = priority;
 
 #ifdef SVN_DEBUG_CACHE_MEMBUFFER
 
@@ -1397,7 +1405,7 @@ membuffer_cache_set_internal(svn_membuff
    */
   if (   buffer != NULL
       && cache->max_entry_size >= size
-      && ensure_data_insertable(cache, size))
+      && ensure_data_insertable(cache, priority, size))
     {
       /* Remove old data for this key, if that exists.
        * Get an unused entry for the key and and initialize it with
@@ -1406,6 +1414,7 @@ membuffer_cache_set_internal(svn_membuff
       entry = find_entry(cache, group_index, to_find, TRUE);
       entry->size = size;
       entry->offset = cache->current_data;
+      entry->priority = priority;
 
 #ifdef SVN_DEBUG_CACHE_MEMBUFFER
 
@@ -1455,6 +1464,7 @@ membuffer_cache_set(svn_membuffer_t *cac
                     entry_key_t key,
                     void *item,
                     svn_cache__serialize_func_t serializer,
+                    apr_uint32_t priority,
                     DEBUG_CACHE_MEMBUFFER_TAG_ARG
                     apr_pool_t *scratch_pool)
 {
@@ -1479,6 +1489,7 @@ membuffer_cache_set(svn_membuffer_t *cac
                                                group_index,
                                                buffer,
                                                size,
+                                               priority,
                                                DEBUG_CACHE_MEMBUFFER_TAG
                                                scratch_pool));
   return SVN_NO_ERROR;
@@ -1793,9 +1804,10 @@ membuffer_cache_set_partial_internal(svn
             {
               /* Remove the old entry and try to make space for the new one.
                */
+              apr_uint32_t priority = entry->priority;
               drop_entry(cache, entry);
               if (   (cache->max_entry_size >= size)
-                  && ensure_data_insertable(cache, size))
+                  && ensure_data_insertable(cache, priority, size))
                 {
                   /* Write the new entry.
                    */
@@ -1900,6 +1912,9 @@ typedef struct svn_membuffer_cache_t
    */
   apr_ssize_t key_len;
 
+  /* priority class for all items written through this interface */
+  apr_uint32_t priority;
+  
   /* Temporary buffer containing the hash key for the current access
    */
   entry_key_t combined_key;
@@ -2083,6 +2098,7 @@ svn_membuffer_cache_set(void *cache_void
                              cache->combined_key,
                              value,
                              cache->serializer,
+                             cache->priority,
                              DEBUG_CACHE_MEMBUFFER_TAG
                              cache->pool);
 }
@@ -2401,6 +2417,7 @@ svn_cache__create_membuffer_cache(svn_ca
                                   svn_cache__deserialize_func_t deserializer,
                                   apr_ssize_t klen,
                                   const char *prefix,
+                                  apr_uint32_t priority,
                                   svn_boolean_t thread_safe,
                                   apr_pool_t *pool)
 {
@@ -2421,6 +2438,7 @@ svn_cache__create_membuffer_cache(svn_ca
                       ? deserializer
                       : deserialize_svn_stringbuf;
   cache->full_prefix = apr_pstrdup(pool, prefix);
+  cache->priority = priority;
   cache->key_len = klen;
   cache->pool = svn_pool_create(pool);
   cache->alloc_counter = 0;

Modified: subversion/branches/fsfs-format7/subversion/tests/libsvn_subr/cache-test.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/subversion/tests/libsvn_subr/cache-test.c?rev=1443803&r1=1443802&r2=1443803&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/subversion/tests/libsvn_subr/cache-test.c (original)
+++ subversion/branches/fsfs-format7/subversion/tests/libsvn_subr/cache-test.c Fri Feb  8
00:10:45 2013
@@ -193,6 +193,7 @@ test_membuffer_cache_basic(apr_pool_t *p
                                             deserialize_revnum,
                                             APR_HASH_KEY_STRING,
                                             "cache:",
+                                            SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY,
                                             FALSE,
                                             pool));
 

Modified: subversion/branches/fsfs-format7/tools/server-side/fsfs-stats.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsfs-format7/tools/server-side/fsfs-stats.c?rev=1443803&r1=1443802&r2=1443803&view=diff
==============================================================================
--- subversion/branches/fsfs-format7/tools/server-side/fsfs-stats.c (original)
+++ subversion/branches/fsfs-format7/tools/server-side/fsfs-stats.c Fri Feb  8 00:10:45 2013
@@ -1414,7 +1414,9 @@ read_revisions(fs_fs_t **fs,
                                             svn_cache__get_global_membuffer_cache(),
                                             NULL, NULL,
                                             sizeof(window_cache_key_t),
-                                            "", FALSE, pool));
+                                            "",
+                                            SVN_CACHE__MEMBUFFER_DEFAULT_PRIORITY,
+                                            FALSE, pool));
 
   /* read all packed revs */
   for ( revision = start_revision



Mime
View raw message