Repository: mesos Updated Branches: refs/heads/master 9c905880a -> 18248d0f8
Implemented a LRU entry selection criteria for cache eviction. A linked list is used to keep cache entries in LRU-to-MRU order. Each time an existing cache entry is requested, it is moved to the back of the list. During cache eviction entries are removed from the front of the list until enough cache space can be freed. Review: https://reviews.apache.org/r/36773 Project: http://git-wip-us.apache.org/repos/asf/mesos/repo Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/18248d0f Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/18248d0f Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/18248d0f Branch: refs/heads/master Commit: 18248d0f8f64437cb8f93ffbe91fd22e82fb1af4 Parents: 9c90588 Author: Jan Schlicht <[email protected]> Authored: Mon Aug 3 13:24:45 2015 +0200 Committer: Bernd Mathiske <[email protected]> Committed: Mon Aug 3 13:24:45 2015 +0200 ---------------------------------------------------------------------- docs/fetcher-cache-internals.md | 2 +- src/slave/containerizer/fetcher.cpp | 26 +++++++---- src/slave/containerizer/fetcher.hpp | 4 ++ src/tests/fetcher_cache_tests.cpp | 77 ++++++++++++++++++++++++++++++++ 4 files changed, 99 insertions(+), 10 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/mesos/blob/18248d0f/docs/fetcher-cache-internals.md ---------------------------------------------------------------------- diff --git a/docs/fetcher-cache-internals.md b/docs/fetcher-cache-internals.md index 327cbc3..d17b41e 100644 --- a/docs/fetcher-cache-internals.md +++ b/docs/fetcher-cache-internals.md @@ -104,7 +104,7 @@ Besides, everything touched in 1/a and 1/b needs to be prevented from being cach The resources named "A" and "B" have been fetched with caching into sandbox 1 and 2 below. In the course of this, two cache entries have been created and two files have been downloaded into the cache and named "1" and "2". (Cache file names have unique names that comprise serial numbers.) -The next figure illustrates the state after fetching a different cached URI into sandbox 3, which in this case requires evicting a cache-resident file and its entry. Steps: +The next figure illustrates the state after fetching a different cached URI into sandbox 3, which in this case requires evicting a cache-resident file and its entry. Cache eviction removes cache entries in the order of the least recently used cache entries. Steps if "A" was fetched before "B": 1. Remove the cache entry for "A" from the fetcher process' cache entry table. Its faded depiction is supposed to indicate this. This immediately makes it appear as if the URI has never been cached, even though the cache file is still around. 2. Proceed with fetching "C". This creates a new cache file, which has a different unique name. (The fetcher process remembers in its cache entry which file name belongs to which URI.) http://git-wip-us.apache.org/repos/asf/mesos/blob/18248d0f/src/slave/containerizer/fetcher.cpp ---------------------------------------------------------------------- diff --git a/src/slave/containerizer/fetcher.cpp b/src/slave/containerizer/fetcher.cpp index e030dea..2b2298c 100644 --- a/src/slave/containerizer/fetcher.cpp +++ b/src/slave/containerizer/fetcher.cpp @@ -869,6 +869,7 @@ shared_ptr<FetcherProcess::Cache::Entry> FetcherProcess::Cache::create( new Cache::Entry(key, cacheDirectory, filename)); table.put(key, entry); + lruSortedEntries.push_back(entry); VLOG(1) << "Created cache entry '" << key << "' with file: " << filename; @@ -883,7 +884,14 @@ FetcherProcess::Cache::get( { const string key = cacheKey(user, uri); - return table.get(key); + Option<shared_ptr<Entry>> entry = table.get(key); + if (entry.isSome()) { + // Refresh the cache entry by moving it to the back of lruSortedEntries. + lruSortedEntries.remove(entry.get()); + lruSortedEntries.push_back(entry.get()); + } + + return entry; } @@ -891,7 +899,8 @@ bool FetcherProcess::Cache::contains( const Option<string>& user, const string& uri) { - return get(user, uri).isSome(); + const string key = cacheKey(user, uri); + return table.get(key).isSome(); } @@ -947,6 +956,7 @@ Try<Nothing> FetcherProcess::Cache::remove( CHECK(contains(entry)); table.erase(entry->key); + lruSortedEntries.remove(entry); // We may or may not have started downloading. The download may or may // not have been partial. In any case, clean up whatever is there. @@ -973,23 +983,21 @@ Try<Nothing> FetcherProcess::Cache::remove( } +// Select LRU cache entries for cache eviction. Try<list<shared_ptr<FetcherProcess::Cache::Entry>>> FetcherProcess::Cache::selectVictims(const Bytes& requiredSpace) { - // TODO(bernd-mesos): Implement more elaborate selection criteria - // (LRU/MRU, etc.). - - list<shared_ptr<FetcherProcess::Cache::Entry>> result; + list<shared_ptr<FetcherProcess::Cache::Entry>> victims; Bytes space = 0; - foreachvalue (const shared_ptr<Cache::Entry>& entry, table) { + foreach (const shared_ptr<Cache::Entry>& entry, lruSortedEntries) { if (!entry->isReferenced()) { - result.push_back(entry); + victims.push_back(entry); space += entry->size; if (space >= requiredSpace) { - return result; + return victims; } } } http://git-wip-us.apache.org/repos/asf/mesos/blob/18248d0f/src/slave/containerizer/fetcher.hpp ---------------------------------------------------------------------- diff --git a/src/slave/containerizer/fetcher.hpp b/src/slave/containerizer/fetcher.hpp index 1722507..30891d4 100644 --- a/src/slave/containerizer/fetcher.hpp +++ b/src/slave/containerizer/fetcher.hpp @@ -19,6 +19,7 @@ #ifndef __SLAVE_CONTAINERIZER_FETCHER_HPP__ #define __SLAVE_CONTAINERIZER_FETCHER_HPP__ +#include <list> #include <string> #include <mesos/mesos.hpp> @@ -282,6 +283,9 @@ public: // Maps keys (cache directory / URI combinations) to cache file // entries. hashmap<std::string, std::shared_ptr<Entry>> table; + + // Stores cache file entries sorted from LRU to MRU. + std::list<std::shared_ptr<Entry>> lruSortedEntries; }; // Public and virtual for mock testing. http://git-wip-us.apache.org/repos/asf/mesos/blob/18248d0f/src/tests/fetcher_cache_tests.cpp ---------------------------------------------------------------------- diff --git a/src/tests/fetcher_cache_tests.cpp b/src/tests/fetcher_cache_tests.cpp index 4e1d348..b709b1e 100644 --- a/src/tests/fetcher_cache_tests.cpp +++ b/src/tests/fetcher_cache_tests.cpp @@ -42,6 +42,7 @@ #include <stout/option.hpp> #include <stout/os.hpp> +#include <stout/path.hpp> #include <stout/try.hpp> #include "master/flags.hpp" @@ -1408,6 +1409,82 @@ TEST_F(FetcherCacheTest, FallbackFromEviction) EXPECT_EQ(1u, fetcherProcess->cacheFiles(slaveId, flags).get().size()); } +// Tests LRU cache eviction strategy. +TEST_F(FetcherCacheTest, RemoveLRUCacheEntries) +{ + // Let only two downloads fit in the cache. + flags.fetcher_cache_size = COMMAND_SCRIPT.size() * 2; + + startSlave(); + driver->start(); + + // Start commands using a pattern that will fill the cache with two entries + // and request the second entry again. The first entry is then the LRU. + // Adding a new entry should therefore evict the first entry. + vector<int> commandCreationPattern; + commandCreationPattern.push_back(0); + commandCreationPattern.push_back(1); + commandCreationPattern.push_back(1); + commandCreationPattern.push_back(2); + + int taskIndex = 0; + + // Fill up the cache + foreach (const int i, commandCreationPattern) { + string commandFilename = "cmd" + stringify(i); + string command = commandFilename + " " + taskName(taskIndex); + + commandPath = path::join(assetsDirectory, commandFilename); + ASSERT_SOME(os::write(commandPath, COMMAND_SCRIPT)); + + CommandInfo::URI uri; + uri.set_value(commandPath); + uri.set_executable(true); + uri.set_cache(true); + + CommandInfo commandInfo; + commandInfo.set_value("./" + command); + commandInfo.add_uris()->CopyFrom(uri); + + const Try<Task> task = launchTask(commandInfo, taskIndex); + ASSERT_SOME(task); + + AWAIT_READY(awaitFinished(task.get())); + + // Check that the task succeeded. + EXPECT_TRUE(isExecutable( + path::join(task.get().runDirectory.value, commandFilename))); + EXPECT_TRUE(os::exists(path::join(task.get().runDirectory.value, + COMMAND_NAME + taskName(taskIndex)))); + + ++taskIndex; + } + + EXPECT_EQ(2u, fetcherProcess->cacheSize()); + + // FetcherProcess::cacheFiles returns all cache files that are in the cache + // directory. We expect cmd1 and cmd2 to be there, cmd0 should have been + // evicted. + Try<list<Path>> cacheFiles = fetcherProcess->cacheFiles(slaveId, flags); + ASSERT_SOME(cacheFiles); + + bool cmd1Found = false; + bool cmd2Found = false; + + foreach (const Path& cacheFile, cacheFiles.get()) { + if (strings::contains(cacheFile.basename(), "cmd1")) { + cmd1Found = true; + } + + if (strings::contains(cacheFile.basename(), "cmd2")) { + cmd2Found = true; + } + } + + EXPECT_TRUE(cmd1Found); + EXPECT_TRUE(cmd2Found); +} + } // namespace tests { } // namespace internal { } // namespace mesos {
