alluxio-master-2.x/core/client/fs/src/main/java/alluxio/client/file/cache/evictor/TwoChoiceRandomEvictor.java
/*
 * The Alluxio Open Foundation licenses this work under the Apache License, version 2.0
 * (the "License"). You may not use this work except in compliance with the License, which is
 * available at www.apache.org/licenses/LICENSE-2.0
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
 * either express or implied, as more fully set forth in the License.
 *
 * See the NOTICE file distributed with this work for information regarding copyright ownership.
 */

package alluxio.client.file.cache.evictor;

import alluxio.client.file.cache.PageId;

import java.time.Instant;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.function.Predicate;
import javax.annotation.Nullable;
import javax.annotation.concurrent.ThreadSafe;

/**
 * Two Choice Random client-side cache eviction policy.
 * It selects two random page IDs and evicts the one least-recently used.
 */
@ThreadSafe
public class TwoChoiceRandomEvictor implements CacheEvictor {
  private final Map<PageId, Long> mCache = Collections.synchronizedMap(new HashMap<>());

  /**
   * Constructor.
   * @param options
   */
  public TwoChoiceRandomEvictor(CacheEvictorOptions options) {
  }

  @Override
  public void updateOnGet(PageId pageId) {
    mCache.put(pageId, Instant.now().toEpochMilli());
  }

  @Override
  public void updateOnPut(PageId pageId) {
    mCache.put(pageId, Instant.now().toEpochMilli());
  }

  @Override
  public void updateOnDelete(PageId pageId) {
    mCache.remove(pageId);
  }

  @Nullable
  @Override
  public PageId evict() {
    synchronized (mCache) {
      if (mCache.isEmpty()) {
        return null;
      }

      // TODO(chunxu): improve the performance here
      List<PageId> keys = new ArrayList<>(mCache.keySet());
      Random rand = new Random();
      PageId key1 = keys.get(rand.nextInt(keys.size()));
      PageId key2 = keys.get(rand.nextInt(keys.size()));
      if (mCache.get(key1) < mCache.get(key2)) {
        return key1;
      }
      return key2;
    }
  }

  @Nullable
  @Override
  public PageId evictMatching(Predicate<PageId> criterion) {
    synchronized (mCache) {
      for (PageId candidate : mCache.keySet()) {
        if (criterion.test(candidate)) {
          return candidate;
        }
      }
      return null;
    }
  }

  @Override
  public void reset() {
    mCache.clear();
  }
}
