{"action":"created","comment":{"url":"https://api.github.com/repos/Alluxio/alluxio/pulls/comments/58469669","id":58469669,"diff_hunk":"@@ -0,0 +1,573 @@\n+/*\r\n+ * The Alluxio Open Foundation licenses this work under the Apache License, version 2.0\r\n+ * (the “License”). You may not use this work except in compliance with the License, which is\r\n+ * available at www.apache.org/licenses/LICENSE-2.0\r\n+ *\r\n+ * This software is distributed on an \"AS IS\" basis, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,\r\n+ * either express or implied, as more fully set forth in the License.\r\n+ *\r\n+ * See the NOTICE file distributed with this work for information regarding copyright ownership.\r\n+ */\r\n+\r\n+package alluxio.worker.block.evictor;\r\n+\r\n+import alluxio.Configuration;\r\n+import alluxio.Constants;\r\n+import alluxio.collections.Pair;\r\n+import alluxio.exception.BlockDoesNotExistException;\r\n+import alluxio.worker.WorkerContext;\r\n+import alluxio.worker.block.BlockMetadataManagerView;\r\n+import alluxio.worker.block.BlockStoreLocation;\r\n+import alluxio.worker.block.allocator.Allocator;\r\n+import alluxio.worker.block.meta.BlockMeta;\r\n+import alluxio.worker.block.meta.StorageDirView;\r\n+import alluxio.worker.block.meta.StorageTierView;\r\n+\r\n+import com.google.common.base.Function;\r\n+import com.google.common.base.Preconditions;\r\n+import com.google.common.collect.Iterators;\r\n+import org.slf4j.Logger;\r\n+import org.slf4j.LoggerFactory;\r\n+\r\n+import java.util.ArrayList;\r\n+import java.util.Collections;\r\n+import java.util.Iterator;\r\n+import java.util.LinkedHashMap;\r\n+import java.util.List;\r\n+import java.util.Map;\r\n+import java.util.Map.Entry;\r\n+import java.util.concurrent.ConcurrentHashMap;\r\n+\r\n+/**\r\n+ * This class is used to evict blocks with LIRS policy on each tier. Different from LRU and LRFU,\r\n+ * LIRS evicts the block with maximum Inter-Reference Recency (IRR). IRR is the number of distinct\r\n+ * blocks between last access and second-to-last access to the block. Block with high IRR is\r\n+ * predicted to be accessed again in a long time, so they need to be evicted first to make room for\r\n+ * other blocks which will be accessed soon. LIRS divides the tier into 2 parts: LIR cache and HIR\r\n+ * cache. LIR cache holds blocks with low IRR and HIR cache holds blocks with high IRR. So blocks\r\n+ * in HIR cache needs to be evicted first. If blocks in HIR cache gets a low IRR, they will be\r\n+ * moved to LIR cache. And if the LIR cache is full, some blocks with relatively high IRR will be\r\n+ * moved to HIR cache. LIRS can achieve better performance than LRU and LRFU in loop access pattern.\r\n+ * For example, a list of files contain blocks: a1,a2,...,ak. When iterating accessing these files,\r\n+ * the blocks will be referenced in the order: a1,a2,...,ak,a1,a2,...,ak,.... some blocks of them\r\n+ * will be stored in LIR cache and the others in HIR cache. No HIR blocks will be moved to LIR cache\r\n+ * because all blocks have equal IRR. Therefore, all blocks in LIR cache will never be removed which\r\n+ * promise the hit rate is at least (number of LIR blocks)/(number of all blocks). while if these\r\n+ * blocks cannot be held in the memory in this case, LRU will achieve zero hit rate. It's also\r\n+ * verified with Spark kmeans that the hit rate of LIRS policy improves a lot than other policies.\r\n+ * So if your workloads contain a lot of iterations like kmeans, LIRS policy is recommended for you.\r\n+ * Besides, LIRS can achieve as good performance as LRU and LRFU in most of workloads.\r\n+ */\r\n+public final class LIRSEvictor extends AbstractEvictor {\r\n+  private static final Logger LOG = LoggerFactory.getLogger(Constants.LOGGER_TYPE);\r\n+\r\n+  private static final int LINKED_HASH_MAP_INIT_CAPACITY = 200;\r\n+  private static final float LINKED_HASH_MAP_INIT_LOAD_FACTOR = 0.75f;\r\n+  private static final boolean LINKED_HASH_MAP_ACCESS_ORDERED = false;\r\n+  private static final boolean UNUSED_MAP_VALUE = true;\r\n+\r\n+  // The percent of HIR blocks on each tier\r\n+  private final double mHIRPercent;\r\n+  // The percent of LIR blocks on each tier\r\n+  private final double mLIRPercent;\r\n+  private final Configuration mConfiguration;\r\n+  // Map from the location of a StorageDir to its condition of used space\r\n+  private Map<BlockStoreLocation, SpaceContainer> mSpaceManager =\r\n+      new ConcurrentHashMap<BlockStoreLocation, SpaceContainer>();\r\n+  /**\r\n+   * Map from the the block id to the block size. Maintain the information of block size is because\r\n+   * the space of HIR block or LIR block need to be reclaimed when\r\n+   * {@link #onRemoveBlockByClient(long, long)} or {@link #onRemoveBlockByWorker(long, long)} is\r\n+   * called.\r\n+   */\r\n+  private Map<Long, Long> mBlockIdToSize = new ConcurrentHashMap<Long, Long>();\r\n+  /**\r\n+   * Record the information of all LIR blocks. Pair<BlockStoreLocation, Long> identifies a block\r\n+   * because a block may contain more than one ghost blocks on all tiers.\r\n+   */\r\n+  private Map<Pair<BlockStoreLocation, Long>, BlockLIRSInfo> mLIRCache =\r\n+      Collections.synchronizedMap(new LinkedHashMap<Pair<BlockStoreLocation, Long>, BlockLIRSInfo>(\r\n+          LINKED_HASH_MAP_INIT_CAPACITY, LINKED_HASH_MAP_INIT_LOAD_FACTOR,\r\n+          LINKED_HASH_MAP_ACCESS_ORDERED));\r\n+  // Record the information of all HIR blocks.\r\n+  private Map<Pair<BlockStoreLocation, Long>, BlockLIRSInfo> mHIRCache =\r","path":"core/server/src/main/java/alluxio/worker/block/evictor/LIRSEvictor.java","position":93,"original_position":93,"commit_id":"f307828b583d714b57c4ec3425f7e883bbb9820b","original_commit_id":"f307828b583d714b57c4ec3425f7e883bbb9820b","user":{"login":"uronce-cc","id":3663941,"avatar_url":"https://avatars.githubusercontent.com/u/3663941?v=3","gravatar_id":"","url":"https://api.github.com/users/uronce-cc","html_url":"https://github.com/uronce-cc","followers_url":"https://api.github.com/users/uronce-cc/followers","following_url":"https://api.github.com/users/uronce-cc/following{/other_user}","gists_url":"https://api.github.com/users/uronce-cc/gists{/gist_id}","starred_url":"https://api.github.com/users/uronce-cc/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/uronce-cc/subscriptions","organizations_url":"https://api.github.com/users/uronce-cc/orgs","repos_url":"https://api.github.com/users/uronce-cc/repos","events_url":"https://api.github.com/users/uronce-cc/events{/privacy}","received_events_url":"https://api.github.com/users/uronce-cc/received_events","type":"User","site_admin":false},"body":"If a block is not in LIR set, it must belong to HIR set? If so, no need for both of the above maps.","created_at":"2016-04-05T00:08:22Z","updated_at":"2016-04-05T00:08:22Z","html_url":"https://github.com/Alluxio/alluxio/pull/2931#discussion_r58469669","pull_request_url":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931","_links":{"self":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/comments/58469669"},"html":{"href":"https://github.com/Alluxio/alluxio/pull/2931#discussion_r58469669"},"pull_request":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931"}}},"pull_request":{"url":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931","id":64260510,"html_url":"https://github.com/Alluxio/alluxio/pull/2931","diff_url":"https://github.com/Alluxio/alluxio/pull/2931.diff","patch_url":"https://github.com/Alluxio/alluxio/pull/2931.patch","issue_url":"https://api.github.com/repos/Alluxio/alluxio/issues/2931","number":2931,"state":"open","locked":false,"title":"[ALLUXIO-1844] Implement LIRSEvictor","user":{"login":"Yours-shupeng","id":8843442,"avatar_url":"https://avatars.githubusercontent.com/u/8843442?v=3","gravatar_id":"","url":"https://api.github.com/users/Yours-shupeng","html_url":"https://github.com/Yours-shupeng","followers_url":"https://api.github.com/users/Yours-shupeng/followers","following_url":"https://api.github.com/users/Yours-shupeng/following{/other_user}","gists_url":"https://api.github.com/users/Yours-shupeng/gists{/gist_id}","starred_url":"https://api.github.com/users/Yours-shupeng/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Yours-shupeng/subscriptions","organizations_url":"https://api.github.com/users/Yours-shupeng/orgs","repos_url":"https://api.github.com/users/Yours-shupeng/repos","events_url":"https://api.github.com/users/Yours-shupeng/events{/privacy}","received_events_url":"https://api.github.com/users/Yours-shupeng/received_events","type":"User","site_admin":false},"body":"[add LIRSEvictor](https://alluxio.atlassian.net/browse/ALLUXIO-1844)","created_at":"2016-03-27T08:30:06Z","updated_at":"2016-04-05T00:08:22Z","closed_at":null,"merged_at":null,"merge_commit_sha":"f29a619b4856cd92bff4ff9f3cfb102f1ade76b0","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931/commits","review_comments_url":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931/comments","review_comment_url":"https://api.github.com/repos/Alluxio/alluxio/pulls/comments{/number}","comments_url":"https://api.github.com/repos/Alluxio/alluxio/issues/2931/comments","statuses_url":"https://api.github.com/repos/Alluxio/alluxio/statuses/f307828b583d714b57c4ec3425f7e883bbb9820b","head":{"label":"PasaLab:ALLUXIO-1844-V0","ref":"ALLUXIO-1844-V0","sha":"f307828b583d714b57c4ec3425f7e883bbb9820b","user":{"login":"PasaLab","id":6230048,"avatar_url":"https://avatars.githubusercontent.com/u/6230048?v=3","gravatar_id":"","url":"https://api.github.com/users/PasaLab","html_url":"https://github.com/PasaLab","followers_url":"https://api.github.com/users/PasaLab/followers","following_url":"https://api.github.com/users/PasaLab/following{/other_user}","gists_url":"https://api.github.com/users/PasaLab/gists{/gist_id}","starred_url":"https://api.github.com/users/PasaLab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/PasaLab/subscriptions","organizations_url":"https://api.github.com/users/PasaLab/orgs","repos_url":"https://api.github.com/users/PasaLab/repos","events_url":"https://api.github.com/users/PasaLab/events{/privacy}","received_events_url":"https://api.github.com/users/PasaLab/received_events","type":"Organization","site_admin":false},"repo":{"id":21603565,"name":"tachyon","full_name":"PasaLab/tachyon","owner":{"login":"PasaLab","id":6230048,"avatar_url":"https://avatars.githubusercontent.com/u/6230048?v=3","gravatar_id":"","url":"https://api.github.com/users/PasaLab","html_url":"https://github.com/PasaLab","followers_url":"https://api.github.com/users/PasaLab/followers","following_url":"https://api.github.com/users/PasaLab/following{/other_user}","gists_url":"https://api.github.com/users/PasaLab/gists{/gist_id}","starred_url":"https://api.github.com/users/PasaLab/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/PasaLab/subscriptions","organizations_url":"https://api.github.com/users/PasaLab/orgs","repos_url":"https://api.github.com/users/PasaLab/repos","events_url":"https://api.github.com/users/PasaLab/events{/privacy}","received_events_url":"https://api.github.com/users/PasaLab/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/PasaLab/tachyon","description":"Memory-centric Storage System for Big Data Analytics","fork":true,"url":"https://api.github.com/repos/PasaLab/tachyon","forks_url":"https://api.github.com/repos/PasaLab/tachyon/forks","keys_url":"https://api.github.com/repos/PasaLab/tachyon/keys{/key_id}","collaborators_url":"https://api.github.com/repos/PasaLab/tachyon/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/PasaLab/tachyon/teams","hooks_url":"https://api.github.com/repos/PasaLab/tachyon/hooks","issue_events_url":"https://api.github.com/repos/PasaLab/tachyon/issues/events{/number}","events_url":"https://api.github.com/repos/PasaLab/tachyon/events","assignees_url":"https://api.github.com/repos/PasaLab/tachyon/assignees{/user}","branches_url":"https://api.github.com/repos/PasaLab/tachyon/branches{/branch}","tags_url":"https://api.github.com/repos/PasaLab/tachyon/tags","blobs_url":"https://api.github.com/repos/PasaLab/tachyon/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/PasaLab/tachyon/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/PasaLab/tachyon/git/refs{/sha}","trees_url":"https://api.github.com/repos/PasaLab/tachyon/git/trees{/sha}","statuses_url":"https://api.github.com/repos/PasaLab/tachyon/statuses/{sha}","languages_url":"https://api.github.com/repos/PasaLab/tachyon/languages","stargazers_url":"https://api.github.com/repos/PasaLab/tachyon/stargazers","contributors_url":"https://api.github.com/repos/PasaLab/tachyon/contributors","subscribers_url":"https://api.github.com/repos/PasaLab/tachyon/subscribers","subscription_url":"https://api.github.com/repos/PasaLab/tachyon/subscription","commits_url":"https://api.github.com/repos/PasaLab/tachyon/commits{/sha}","git_commits_url":"https://api.github.com/repos/PasaLab/tachyon/git/commits{/sha}","comments_url":"https://api.github.com/repos/PasaLab/tachyon/comments{/number}","issue_comment_url":"https://api.github.com/repos/PasaLab/tachyon/issues/comments{/number}","contents_url":"https://api.github.com/repos/PasaLab/tachyon/contents/{+path}","compare_url":"https://api.github.com/repos/PasaLab/tachyon/compare/{base}...{head}","merges_url":"https://api.github.com/repos/PasaLab/tachyon/merges","archive_url":"https://api.github.com/repos/PasaLab/tachyon/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/PasaLab/tachyon/downloads","issues_url":"https://api.github.com/repos/PasaLab/tachyon/issues{/number}","pulls_url":"https://api.github.com/repos/PasaLab/tachyon/pulls{/number}","milestones_url":"https://api.github.com/repos/PasaLab/tachyon/milestones{/number}","notifications_url":"https://api.github.com/repos/PasaLab/tachyon/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/PasaLab/tachyon/labels{/name}","releases_url":"https://api.github.com/repos/PasaLab/tachyon/releases{/id}","deployments_url":"https://api.github.com/repos/PasaLab/tachyon/deployments","created_at":"2014-07-08T07:42:41Z","updated_at":"2016-01-27T01:44:37Z","pushed_at":"2016-04-02T09:08:28Z","git_url":"git://github.com/PasaLab/tachyon.git","ssh_url":"git@github.com:PasaLab/tachyon.git","clone_url":"https://github.com/PasaLab/tachyon.git","svn_url":"https://github.com/PasaLab/tachyon","homepage":"http://tachyon-project.org","size":47116,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":2,"mirror_url":null,"open_issues_count":0,"forks":2,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"Alluxio:master","ref":"master","sha":"1811da52638e2e94c3dd0e709a767f16b937cf27","user":{"login":"Alluxio","id":16203694,"avatar_url":"https://avatars.githubusercontent.com/u/16203694?v=3","gravatar_id":"","url":"https://api.github.com/users/Alluxio","html_url":"https://github.com/Alluxio","followers_url":"https://api.github.com/users/Alluxio/followers","following_url":"https://api.github.com/users/Alluxio/following{/other_user}","gists_url":"https://api.github.com/users/Alluxio/gists{/gist_id}","starred_url":"https://api.github.com/users/Alluxio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Alluxio/subscriptions","organizations_url":"https://api.github.com/users/Alluxio/orgs","repos_url":"https://api.github.com/users/Alluxio/repos","events_url":"https://api.github.com/users/Alluxio/events{/privacy}","received_events_url":"https://api.github.com/users/Alluxio/received_events","type":"Organization","site_admin":false},"repo":{"id":7276954,"name":"alluxio","full_name":"Alluxio/alluxio","owner":{"login":"Alluxio","id":16203694,"avatar_url":"https://avatars.githubusercontent.com/u/16203694?v=3","gravatar_id":"","url":"https://api.github.com/users/Alluxio","html_url":"https://github.com/Alluxio","followers_url":"https://api.github.com/users/Alluxio/followers","following_url":"https://api.github.com/users/Alluxio/following{/other_user}","gists_url":"https://api.github.com/users/Alluxio/gists{/gist_id}","starred_url":"https://api.github.com/users/Alluxio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Alluxio/subscriptions","organizations_url":"https://api.github.com/users/Alluxio/orgs","repos_url":"https://api.github.com/users/Alluxio/repos","events_url":"https://api.github.com/users/Alluxio/events{/privacy}","received_events_url":"https://api.github.com/users/Alluxio/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Alluxio/alluxio","description":"Memory-Speed Virtual Distributed Storage System","fork":false,"url":"https://api.github.com/repos/Alluxio/alluxio","forks_url":"https://api.github.com/repos/Alluxio/alluxio/forks","keys_url":"https://api.github.com/repos/Alluxio/alluxio/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Alluxio/alluxio/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Alluxio/alluxio/teams","hooks_url":"https://api.github.com/repos/Alluxio/alluxio/hooks","issue_events_url":"https://api.github.com/repos/Alluxio/alluxio/issues/events{/number}","events_url":"https://api.github.com/repos/Alluxio/alluxio/events","assignees_url":"https://api.github.com/repos/Alluxio/alluxio/assignees{/user}","branches_url":"https://api.github.com/repos/Alluxio/alluxio/branches{/branch}","tags_url":"https://api.github.com/repos/Alluxio/alluxio/tags","blobs_url":"https://api.github.com/repos/Alluxio/alluxio/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Alluxio/alluxio/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Alluxio/alluxio/git/refs{/sha}","trees_url":"https://api.github.com/repos/Alluxio/alluxio/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Alluxio/alluxio/statuses/{sha}","languages_url":"https://api.github.com/repos/Alluxio/alluxio/languages","stargazers_url":"https://api.github.com/repos/Alluxio/alluxio/stargazers","contributors_url":"https://api.github.com/repos/Alluxio/alluxio/contributors","subscribers_url":"https://api.github.com/repos/Alluxio/alluxio/subscribers","subscription_url":"https://api.github.com/repos/Alluxio/alluxio/subscription","commits_url":"https://api.github.com/repos/Alluxio/alluxio/commits{/sha}","git_commits_url":"https://api.github.com/repos/Alluxio/alluxio/git/commits{/sha}","comments_url":"https://api.github.com/repos/Alluxio/alluxio/comments{/number}","issue_comment_url":"https://api.github.com/repos/Alluxio/alluxio/issues/comments{/number}","contents_url":"https://api.github.com/repos/Alluxio/alluxio/contents/{+path}","compare_url":"https://api.github.com/repos/Alluxio/alluxio/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Alluxio/alluxio/merges","archive_url":"https://api.github.com/repos/Alluxio/alluxio/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Alluxio/alluxio/downloads","issues_url":"https://api.github.com/repos/Alluxio/alluxio/issues{/number}","pulls_url":"https://api.github.com/repos/Alluxio/alluxio/pulls{/number}","milestones_url":"https://api.github.com/repos/Alluxio/alluxio/milestones{/number}","notifications_url":"https://api.github.com/repos/Alluxio/alluxio/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Alluxio/alluxio/labels{/name}","releases_url":"https://api.github.com/repos/Alluxio/alluxio/releases{/id}","deployments_url":"https://api.github.com/repos/Alluxio/alluxio/deployments","created_at":"2012-12-21T17:43:46Z","updated_at":"2016-04-04T05:37:12Z","pushed_at":"2016-04-04T23:45:38Z","git_url":"git://github.com/Alluxio/alluxio.git","ssh_url":"git@github.com:Alluxio/alluxio.git","clone_url":"https://github.com/Alluxio/alluxio.git","svn_url":"https://github.com/Alluxio/alluxio","homepage":"http://www.alluxio.org/","size":56897,"stargazers_count":2269,"watchers_count":2269,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":873,"mirror_url":null,"open_issues_count":24,"forks":873,"open_issues":24,"watchers":2269,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931"},"html":{"href":"https://github.com/Alluxio/alluxio/pull/2931"},"issue":{"href":"https://api.github.com/repos/Alluxio/alluxio/issues/2931"},"comments":{"href":"https://api.github.com/repos/Alluxio/alluxio/issues/2931/comments"},"review_comments":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931/comments"},"review_comment":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/Alluxio/alluxio/pulls/2931/commits"},"statuses":{"href":"https://api.github.com/repos/Alluxio/alluxio/statuses/f307828b583d714b57c4ec3425f7e883bbb9820b"}}}}