Всем привет!
В общем, в эти каникулы, после успешной сдачи сесcии, я решил устроиться на работу. Сами понимаете, сколько шансов у второкурсника получить работу программиста,да плюс еще и неполный рабочий день (после университета). Как можно догадаться, я до сих пор безработный) Но, вопреки моим пессимистическим прогнозам, мне даже выслали, как я потом узнал, "классическое тестовое задание" для юниор-программиста - создание двухуровневого кэша. Об этом и пойдет речь далее.
Я получил письмо от потенциального работодателя, которое содержало текст
"Create a configurable two-level cache (for caching Objects). Level 1 is
memory, level 2 is filesystem. Config params should let one specify the
cache strategies and max sizes of level 1 and 2."
Собственно, этого и следовало ожидать - меня проверяли по стандарту, снабдив минимумом условий. Для начала давайте разберемся, чего от нас хотят. Я распишу все по пунктам:
Но начнем мы с проектирования интерфейсов)
Написание интерфейса ICache
Вообще, главным условием потенциального работодателя было написание на Java. Это было отличным поводом изучить новый язык) Далее я приведу код интерфейса IСache, который будет являться базовым для любого кэша:
public interface ICache<KeyType,ValueType > {
void cache(KeyType key, ValueType value) throws IOException, ClassNotFoundException;
ValueType getObject(KeyType key) throws IOException, ClassNotFoundException;
void deleteObject(KeyType key);
void clearCache();
ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException;
boolean containsKey(KeyType key);
int size();
}
никаких тайн) Методы cache и removeObject могут бросить эти исключения, так как этот интерфейс еще также будет использоваться кэшем жесткого диска, а там при сериализации и приведении могут быть сгенерированы эти исключения (но об этом чуть позднее). Итак, первый интерфейс готов.
Интерфейс IFrecquencyCallObject
Вообще говоря, мы упоминали о рекэшировании внутри двухуровнего кэша, но алгоритмы вытеснения требуют, соответственно, какие-то данные, на основе которых и будет происходить вытеснение в другие кэши и связь между ними. Для этого я предлагаю написать интерфейс IFrecquencyCallObject:
public interface IFrecquencyCallObject<KeyType> {
Set<KeyType> getMostFrequentlyUsedKeys();
int getFrecquencyOfCallingObject(KeyType key);
}
все также прозрачно и наглядно. Пока лишь отмечу, что getMostFrequentlyUsedKeys будет возвращать сет отсортированных ключей (сортироваться они будут, впрочем говоря, по убыванию частоты вызова).
Создание класса RamCacheClass
Вот и пришло время написания класса кэша в оперативной памяти. Далее приведен код:
public class RamCacheClass <KeyType, ValueType> implements ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType> {
private HashMap<KeyType,ValueType> hashMap;
private TreeMap<KeyType, Integer> frequencyMap;
public RamCacheClass(){
hashMap = new HashMap<KeyType, ValueType>();
frequencyMap = new TreeMap<KeyType, Integer>();
}
@Override
public void cache(KeyType key, ValueType value) {
frequencyMap.put(key,1);
hashMap.put(key, value);
}
@Override
public ValueType getObject(KeyType key) {
if(hashMap.containsKey(key)){
int frequency = frequencyMap.get(key);
frequencyMap.put(key,++frequency);
return hashMap.get(key);
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(hashMap.containsKey(key)){
hashMap.remove(key);
frequencyMap.remove(key);
}
}
@Override
public void clearCache() {
hashMap.clear();
frequencyMap.clear();
}
@Override
public ValueType removeObject(KeyType key) {
if(hashMap.containsKey(key)){
ValueType result = this.getObject(key);
this.deleteObject(key);
return result;
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
return hashMap.containsKey(key);
}
@Override
public int size() {
return hashMap.size();
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
ComparatorClass comparator = new ComparatorClass(frequencyMap);
TreeMap<KeyType,Integer> sorted = new TreeMap(comparator);
sorted.putAll(frequencyMap);
return sorted.keySet();
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(hashMap.containsKey(key)){
return frequencyMap.get(key);
}
return 0;
}
}
В принципе, работа класса весьма прозрачна. Отмечу лишь, что кэширование будет происходить при помощи HashMap, хранения частот вызова по ключам - в TreeMap. В методах вы можете наглядно заметить, как происходит учет количества вызов из HashMap, а также как добавляются объекты в кэш. Обратить ваше внимания я хочу на перегрузку метода etMostFrequentlyUsedKeys. Для него был написал свой класс Comparator, код которого приведен ниже. Он ничем не отличается от стандартной реализации с той лишь разницей, что он сортирует все объекты и не удаляет из сета объекты с одинаковой частотой:
public class ComparatorClass implements Comparator{
Map base;
public ComparatorClass(Map base) {
this.base = base;
}
@Override
public int compare(Object o1, Object o2) {
if((Integer)base.get(o1) < (Integer)base.get(o2)) {
return 1;
} else if((Integer)base.get(o1) == (Integer)base.get(o2)) {
return 1;
} else {
return -1;
}
}
}
Ну вот и класс для кэша в оперативной памяти и готов. Дальше - интереснее. Мы погрузимся в сериализацию и хранение объектов на жестком диске.
Создание класса MemoryCacheClass
Дальше мы рассмотрим создание класса MemoryCacheClass. Его реализация будет осложнена лишь дополнительными операциями сериализации и десериализации. Код класса приведен далее:
public class MemoryCacheClass<KeyType, ValueType extends Serializable> implements ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType> {
HashMap<KeyType,String> hashMap;
TreeMap<KeyType,Integer> frequencyMap;
public MemoryCacheClass()
{
hashMap = new HashMap<KeyType, String>();
frequencyMap = new TreeMap<KeyType, Integer>();
File tempFolder = new File("temp\\");
if(!tempFolder.exists()){
tempFolder.mkdirs();
}
}
@Override
public void cache(KeyType key, ValueType value) throws IOException {
String pathToObject;
pathToObject = "temp\\" + UUID.randomUUID().toString() + ".temp";
frequencyMap.put(key,1);
hashMap.put(key, pathToObject);
FileOutputStream fileStream = new FileOutputStream(pathToObject);
ObjectOutputStream objectStream = new ObjectOutputStream(fileStream);
objectStream.writeObject(value);
objectStream.flush();
objectStream.close();
fileStream.flush();
fileStream.close();
}
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key)){
String pathToObject = hashMap.get(key);
try
{
FileInputStream fileStream = new FileInputStream(pathToObject);
ObjectInputStream objectStream = new ObjectInputStream(fileStream);
ValueType deserializedObject = (ValueType)objectStream.readObject();
int frecquency = frequencyMap.remove(key);
frequencyMap.put(key,++frecquency);
fileStream.close();
objectStream.close();
return deserializedObject;
}
catch (IOException ex)
{
return null;
}
catch (ClassNotFoundException ex)
{
return null;
}
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(hashMap.containsKey(key))
{
File deletingFile = new File(hashMap.remove(key));
frequencyMap.remove(key);
deletingFile.delete();
}
}
@Override
public void clearCache() {
for(KeyType key : hashMap.keySet()){
File deletingFile = new File(hashMap.get(key));
deletingFile.delete();
}
hashMap.clear();
frequencyMap.clear();
}
@Override
public ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key))
{
ValueType result = this.getObject(key);
this.deleteObject(key);
return result;
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
return hashMap.containsKey(key);
}
@Override
public int size() {
return hashMap.size();
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
ComparatorClass comparator = new ComparatorClass(frequencyMap);
TreeMap<KeyType,Integer> sorted = new TreeMap(comparator);
sorted.putAll(frequencyMap);
return sorted.keySet();
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(hashMap.containsKey(key)){
return frequencyMap.get(key);
}
return 0;
}
}
Суть работы абсолютно аналогична. Остановимся только на реализации метод кэширования и получения из кэша:
@Override
public void cache(KeyType key, ValueType value) throws IOException {
String pathToObject;
pathToObject = "temp\\" + UUID.randomUUID().toString() + ".temp";
frequencyMap.put(key,1);
hashMap.put(key, pathToObject);
FileOutputStream fileStream = new FileOutputStream(pathToObject);
ObjectOutputStream objectStream = new ObjectOutputStream(fileStream);
objectStream.writeObject(value);
objectStream.flush();
objectStream.close();
fileStream.flush();
fileStream.close();
}
метод UUID.randomUUID().toString() используется для получения уникального идентификационного имени для хранения на жестком диске в папке temp. Ну и соответственно, в hashMap помещается полный путь до этого объекта, а в качестве ключа используется хэш этого объекта в системе. Далее стандартные процедуры для записи и очистки всех буферов.
Теперь рассмотрим метод получения объекта из памяти по его хэш-ключу. Собственно, тут опять же все наглядно - получаем по ключу адрес файла на жестком диске из hashMap, далее читаем его, десериализуем, увеличиваем на один частоту вызова, очищаем потоки и обрабатываем исключения (в моем случае - просто заглушки)
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key)){
String pathToObject = hashMap.get(key);
try
{
FileInputStream fileStream = new FileInputStream(pathToObject);
ObjectInputStream objectStream = new ObjectInputStream(fileStream);
ValueType deserializedObject = (ValueType)objectStream.readObject();
int frecquency = frequencyMap.remove(key);
frequencyMap.put(key,++frecquency);
fileStream.close();
objectStream.close();
return deserializedObject;
}
catch (IOException ex)
{
return null;
}
catch (ClassNotFoundException ex)
{
return null;
}
}
return null;
}
Далее перейдем к реализации многоуровневого кэша, в нашем случае-двухуровневого.
Интерфейс ILeveledCache
Вообще говоря, этот интерфейс наследуется от двух предыдущих интерфейсов и несет в себе сигнатуру лишь одного метода - recache(). Наследование от двух предыдущих интерфейсов обеспечивает поведение этого кэша, как абсолютно обычного кэша, так как он есть ни что иное, как просто некоторая совокупность двух разных кэшей. Код интерфейса:
public interface ILeveledCache<KeyType,ValueType> extends ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType>{
void recache() throws IOException, ClassNotFoundException;
}
Все весьма очевидно) Дальше перейдем к нашему главному объекту - классу двухуровневого кэша, к которому мы так долго шли.
Главный класс - TwoLevelCacheClass
Вот и настало время реализации главного класса нашей программы. Сначала рассмотрим код и разберем его отдельные части:
public class TwoLevelCacheClass<KeyType,ValueType extends Serializable> extends Object implements ILeveledCache<KeyType,ValueType>{
RamCacheClass<KeyType,ValueType> ramCache;
MemoryCacheClass<KeyType,ValueType> memoryCache;
int maxRamCacheCapacity;
int numberOfRequests;
int numberOfRequestsForRecahce;
public TwoLevelCacheClass(int _maxRamCacheCapacity, int _numberOfRequestsForRecache)
{
maxRamCacheCapacity = _maxRamCacheCapacity;
numberOfRequestsForRecahce = _numberOfRequestsForRecache;
ramCache = new RamCacheClass<KeyType, ValueType>();
memoryCache = new MemoryCacheClass<KeyType, ValueType>();
numberOfRequests = 0;
}
@Override
public void cache(KeyType key, ValueType value) throws IOException, ClassNotFoundException {
ramCache.cache(key,value);
}
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(ramCache.containsKey(key)){
numberOfRequests++;
if(numberOfRequests > numberOfRequestsForRecahce){
this.recache();
numberOfRequests = 0;
}
return ramCache.getObject(key);
}
if(memoryCache.containsKey(key)){
numberOfRequests++;
if(numberOfRequests > numberOfRequestsForRecahce){
this.recache();
numberOfRequests = 0;
}
return memoryCache.getObject(key);
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(ramCache.containsKey(key)){
ramCache.deleteObject(key);
}
if(memoryCache.containsKey(key)){
memoryCache.deleteObject(key);
}
}
@Override
public void clearCache() {
memoryCache.clearCache();
ramCache.clearCache();
}
@Override
public ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException {
if(ramCache.containsKey(key)){
return ramCache.removeObject(key);
}
if(memoryCache.containsKey(key)){
return memoryCache.removeObject(key);
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
if(ramCache.containsKey(key)){
return true;
}
if(memoryCache.containsKey(key)){
return true;
}
return false;
}
@Override
public int size() {
return ramCache.size() + memoryCache.size();
}
@Override
public void recache() throws IOException, ClassNotFoundException {
TreeSet<KeyType> ramKeySet = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
int boundFrecquency = 0;
// вычисление среднего арифметического для отбрасывания редко вызываемых объектов
for(KeyType key: ramKeySet)
{
boundFrecquency += ramCache.getFrecquencyOfCallingObject(key);
}
boundFrecquency /= ramKeySet.size();
for(KeyType key: ramKeySet)
{
if(ramCache.getFrecquencyOfCallingObject(key) <= boundFrecquency){
memoryCache.cache(key,ramCache.removeObject(key));
}
}
TreeSet<KeyType> memoryKeySet = new TreeSet<KeyType>(memoryCache.getMostFrequentlyUsedKeys());
for(KeyType key : memoryKeySet)
{
try{
if(memoryCache.getFrecquencyOfCallingObject(key) > boundFrecquency)
{
ramCache.cache(key,memoryCache.removeObject(key));
}
}
catch (IOException ex)
{
memoryCache.deleteObject(key);
continue;
}
catch (ClassNotFoundException ex)
{
// simply dummy
continue;
}
}
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
TreeSet<KeyType> set = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
set.addAll(memoryCache.getMostFrequentlyUsedKeys());
return set;
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(ramCache.containsKey(key))
{
return ramCache.getFrecquencyOfCallingObject(key);
}
if(memoryCache.containsKey(key))
{
return memoryCache.getFrecquencyOfCallingObject(key);
}
return 0;
}
}
Теперь разберем все по частям.Во первых, набор переменных
int maxRamCacheCapacity;
int numberOfRequests;
int numberOfRequestsForRecahce;
Эти переменные должны инициализироваться в конструкторе класса. Они будут отвечать за простейшую логику стратегии рекэширования. Соответственно,
maxRamCacheCapacity - максимальное количество записей в кэше оперативной памяти. Если количество элементов превосходит это число - вызывается алгоритм рекэширования.
numberOfRequests - количество запросов к кэшу после последнего рекэширования.
numberOfRequestsForRecahce - количество запросов, необходимое для рекэширования. Если numberOfRequests превышает numberOfRequestsForRecahce, то numberOfRequests обнуляется и вызывается recache().
Добавлять объекты мы будем соответственно в ramCache, а искать, извлекать, удалять и возвращать из всех кешей. В принципе, реализация всех методов стандартная, остановимся только лишь на методе recache(), реализация которого представляет наибольший интерес (хотя, следует отметить, что ничего нетривиального там нет). Я выбрал алгоритм вытеснения на основе самых редко вызываемых объектов. При рекэшировании я нахожу среднее арифметическое количества вызовов каждого объекта и переношу объекты из оперативной памяти, на жесткий диск. В свою же очередь, все объекты, хранящиеся на жестком диске и вызывавшиеся больше раз, чем это среднее арифметическое, забрасываются в оперативную память. Таким образом, происходит постоянное перетасовывание объектов между двумя кэшами. Внизу приведен код:
@Override
public void recache() throws IOException, ClassNotFoundException {
TreeSet<KeyType> ramKeySet = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
int boundFrecquency = 0;
// вычисление среднего арифметического для отбрасывания редко вызываемых объектов
for(KeyType key: ramKeySet)
{
boundFrecquency += ramCache.getFrecquencyOfCallingObject(key);
}
boundFrecquency /= ramKeySet.size();
for(KeyType key: ramKeySet)
{
if(ramCache.getFrecquencyOfCallingObject(key) <= boundFrecquency){
memoryCache.cache(key,ramCache.removeObject(key));
}
}
TreeSet<KeyType> memoryKeySet = new TreeSet<KeyType>(memoryCache.getMostFrequentlyUsedKeys());
for(KeyType key : memoryKeySet)
{
try{
if(memoryCache.getFrecquencyOfCallingObject(key) > boundFrecquency)
{
ramCache.cache(key,memoryCache.removeObject(key));
}
}
catch (IOException ex)
{
memoryCache.deleteObject(key);
continue;
}
catch (ClassNotFoundException ex)
{
// simply dummy
continue;
}
}
}
В объяснении перед кодом был подробно изложен принцип работы рекэширования, и, я полагаю, дальнейшие объяснения будут неуместны.
Заключение
В заключении хочу лишь сказать, что это был хороший опыт программирования на Java. Меня приятно порадовал этот язык, богатый своими конструкциями. Особенно впечатлила среда разработки Intellij Idea 11.0, стол дружелюбная и полезная для рядового программиста. Также отмечу, что мое решение не претендует на идеальный пример проектирования программ, но, быть может, окажется хорошим подспорьем для начинающих программистов.
Всем, кто дочитал до этого места, спасибо за внимание и до новых встреч!
В общем, в эти каникулы, после успешной сдачи сесcии, я решил устроиться на работу. Сами понимаете, сколько шансов у второкурсника получить работу программиста,да плюс еще и неполный рабочий день (после университета). Как можно догадаться, я до сих пор безработный) Но, вопреки моим пессимистическим прогнозам, мне даже выслали, как я потом узнал, "классическое тестовое задание" для юниор-программиста - создание двухуровневого кэша. Об этом и пойдет речь далее.
Я получил письмо от потенциального работодателя, которое содержало текст
"Create a configurable two-level cache (for caching Objects). Level 1 is
memory, level 2 is filesystem. Config params should let one specify the
cache strategies and max sizes of level 1 and 2."
Собственно, этого и следовало ожидать - меня проверяли по стандарту, снабдив минимумом условий. Для начала давайте разберемся, чего от нас хотят. Я распишу все по пунктам:
- Создать кэш, в котором всего два уровня. Первый уровень - кэширование объектов на уровне памяти, второй уровень - кэширование объектов на жестком диске.
- Кэш должен быть частично настраиваемым, то есть мы должны сами установить максимальное количество записей в памяти RAM, а также условия для рекэширования объектов и перемещения их между уровнями кэша.
- Реализация одного из алгоритмов вытеснения.
- Создать кэш объектов в оперативной памяти
- Создать кэш файлов на жестком диске
- Объединить работу этих кэшей в один законченный двухуровневый кэш
- Реализовать алгоритмы рекэширования (алгоритмы вытеснения)
Но начнем мы с проектирования интерфейсов)
Написание интерфейса ICache
Вообще, главным условием потенциального работодателя было написание на Java. Это было отличным поводом изучить новый язык) Далее я приведу код интерфейса IСache, который будет являться базовым для любого кэша:
public interface ICache<KeyType,ValueType > {
void cache(KeyType key, ValueType value) throws IOException, ClassNotFoundException;
ValueType getObject(KeyType key) throws IOException, ClassNotFoundException;
void deleteObject(KeyType key);
void clearCache();
ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException;
boolean containsKey(KeyType key);
int size();
}
никаких тайн) Методы cache и removeObject могут бросить эти исключения, так как этот интерфейс еще также будет использоваться кэшем жесткого диска, а там при сериализации и приведении могут быть сгенерированы эти исключения (но об этом чуть позднее). Итак, первый интерфейс готов.
Интерфейс IFrecquencyCallObject
Вообще говоря, мы упоминали о рекэшировании внутри двухуровнего кэша, но алгоритмы вытеснения требуют, соответственно, какие-то данные, на основе которых и будет происходить вытеснение в другие кэши и связь между ними. Для этого я предлагаю написать интерфейс IFrecquencyCallObject:
public interface IFrecquencyCallObject<KeyType> {
Set<KeyType> getMostFrequentlyUsedKeys();
int getFrecquencyOfCallingObject(KeyType key);
}
все также прозрачно и наглядно. Пока лишь отмечу, что getMostFrequentlyUsedKeys будет возвращать сет отсортированных ключей (сортироваться они будут, впрочем говоря, по убыванию частоты вызова).
Создание класса RamCacheClass
Вот и пришло время написания класса кэша в оперативной памяти. Далее приведен код:
public class RamCacheClass <KeyType, ValueType> implements ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType> {
private HashMap<KeyType,ValueType> hashMap;
private TreeMap<KeyType, Integer> frequencyMap;
public RamCacheClass(){
hashMap = new HashMap<KeyType, ValueType>();
frequencyMap = new TreeMap<KeyType, Integer>();
}
@Override
public void cache(KeyType key, ValueType value) {
frequencyMap.put(key,1);
hashMap.put(key, value);
}
@Override
public ValueType getObject(KeyType key) {
if(hashMap.containsKey(key)){
int frequency = frequencyMap.get(key);
frequencyMap.put(key,++frequency);
return hashMap.get(key);
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(hashMap.containsKey(key)){
hashMap.remove(key);
frequencyMap.remove(key);
}
}
@Override
public void clearCache() {
hashMap.clear();
frequencyMap.clear();
}
@Override
public ValueType removeObject(KeyType key) {
if(hashMap.containsKey(key)){
ValueType result = this.getObject(key);
this.deleteObject(key);
return result;
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
return hashMap.containsKey(key);
}
@Override
public int size() {
return hashMap.size();
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
ComparatorClass comparator = new ComparatorClass(frequencyMap);
TreeMap<KeyType,Integer> sorted = new TreeMap(comparator);
sorted.putAll(frequencyMap);
return sorted.keySet();
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(hashMap.containsKey(key)){
return frequencyMap.get(key);
}
return 0;
}
}
В принципе, работа класса весьма прозрачна. Отмечу лишь, что кэширование будет происходить при помощи HashMap, хранения частот вызова по ключам - в TreeMap. В методах вы можете наглядно заметить, как происходит учет количества вызов из HashMap, а также как добавляются объекты в кэш. Обратить ваше внимания я хочу на перегрузку метода etMostFrequentlyUsedKeys. Для него был написал свой класс Comparator, код которого приведен ниже. Он ничем не отличается от стандартной реализации с той лишь разницей, что он сортирует все объекты и не удаляет из сета объекты с одинаковой частотой:
public class ComparatorClass implements Comparator{
Map base;
public ComparatorClass(Map base) {
this.base = base;
}
@Override
public int compare(Object o1, Object o2) {
if((Integer)base.get(o1) < (Integer)base.get(o2)) {
return 1;
} else if((Integer)base.get(o1) == (Integer)base.get(o2)) {
return 1;
} else {
return -1;
}
}
}
Ну вот и класс для кэша в оперативной памяти и готов. Дальше - интереснее. Мы погрузимся в сериализацию и хранение объектов на жестком диске.
Создание класса MemoryCacheClass
Дальше мы рассмотрим создание класса MemoryCacheClass. Его реализация будет осложнена лишь дополнительными операциями сериализации и десериализации. Код класса приведен далее:
public class MemoryCacheClass<KeyType, ValueType extends Serializable> implements ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType> {
HashMap<KeyType,String> hashMap;
TreeMap<KeyType,Integer> frequencyMap;
public MemoryCacheClass()
{
hashMap = new HashMap<KeyType, String>();
frequencyMap = new TreeMap<KeyType, Integer>();
File tempFolder = new File("temp\\");
if(!tempFolder.exists()){
tempFolder.mkdirs();
}
}
@Override
public void cache(KeyType key, ValueType value) throws IOException {
String pathToObject;
pathToObject = "temp\\" + UUID.randomUUID().toString() + ".temp";
frequencyMap.put(key,1);
hashMap.put(key, pathToObject);
FileOutputStream fileStream = new FileOutputStream(pathToObject);
ObjectOutputStream objectStream = new ObjectOutputStream(fileStream);
objectStream.writeObject(value);
objectStream.flush();
objectStream.close();
fileStream.flush();
fileStream.close();
}
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key)){
String pathToObject = hashMap.get(key);
try
{
FileInputStream fileStream = new FileInputStream(pathToObject);
ObjectInputStream objectStream = new ObjectInputStream(fileStream);
ValueType deserializedObject = (ValueType)objectStream.readObject();
int frecquency = frequencyMap.remove(key);
frequencyMap.put(key,++frecquency);
fileStream.close();
objectStream.close();
return deserializedObject;
}
catch (IOException ex)
{
return null;
}
catch (ClassNotFoundException ex)
{
return null;
}
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(hashMap.containsKey(key))
{
File deletingFile = new File(hashMap.remove(key));
frequencyMap.remove(key);
deletingFile.delete();
}
}
@Override
public void clearCache() {
for(KeyType key : hashMap.keySet()){
File deletingFile = new File(hashMap.get(key));
deletingFile.delete();
}
hashMap.clear();
frequencyMap.clear();
}
@Override
public ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key))
{
ValueType result = this.getObject(key);
this.deleteObject(key);
return result;
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
return hashMap.containsKey(key);
}
@Override
public int size() {
return hashMap.size();
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
ComparatorClass comparator = new ComparatorClass(frequencyMap);
TreeMap<KeyType,Integer> sorted = new TreeMap(comparator);
sorted.putAll(frequencyMap);
return sorted.keySet();
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(hashMap.containsKey(key)){
return frequencyMap.get(key);
}
return 0;
}
}
Суть работы абсолютно аналогична. Остановимся только на реализации метод кэширования и получения из кэша:
@Override
public void cache(KeyType key, ValueType value) throws IOException {
String pathToObject;
pathToObject = "temp\\" + UUID.randomUUID().toString() + ".temp";
frequencyMap.put(key,1);
hashMap.put(key, pathToObject);
FileOutputStream fileStream = new FileOutputStream(pathToObject);
ObjectOutputStream objectStream = new ObjectOutputStream(fileStream);
objectStream.writeObject(value);
objectStream.flush();
objectStream.close();
fileStream.flush();
fileStream.close();
}
метод UUID.randomUUID().toString() используется для получения уникального идентификационного имени для хранения на жестком диске в папке temp. Ну и соответственно, в hashMap помещается полный путь до этого объекта, а в качестве ключа используется хэш этого объекта в системе. Далее стандартные процедуры для записи и очистки всех буферов.
Теперь рассмотрим метод получения объекта из памяти по его хэш-ключу. Собственно, тут опять же все наглядно - получаем по ключу адрес файла на жестком диске из hashMap, далее читаем его, десериализуем, увеличиваем на один частоту вызова, очищаем потоки и обрабатываем исключения (в моем случае - просто заглушки)
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(hashMap.containsKey(key)){
String pathToObject = hashMap.get(key);
try
{
FileInputStream fileStream = new FileInputStream(pathToObject);
ObjectInputStream objectStream = new ObjectInputStream(fileStream);
ValueType deserializedObject = (ValueType)objectStream.readObject();
int frecquency = frequencyMap.remove(key);
frequencyMap.put(key,++frecquency);
fileStream.close();
objectStream.close();
return deserializedObject;
}
catch (IOException ex)
{
return null;
}
catch (ClassNotFoundException ex)
{
return null;
}
}
return null;
}
Далее перейдем к реализации многоуровневого кэша, в нашем случае-двухуровневого.
Интерфейс ILeveledCache
Вообще говоря, этот интерфейс наследуется от двух предыдущих интерфейсов и несет в себе сигнатуру лишь одного метода - recache(). Наследование от двух предыдущих интерфейсов обеспечивает поведение этого кэша, как абсолютно обычного кэша, так как он есть ни что иное, как просто некоторая совокупность двух разных кэшей. Код интерфейса:
public interface ILeveledCache<KeyType,ValueType> extends ICache<KeyType,ValueType>,IFrecquencyCallObject<KeyType>{
void recache() throws IOException, ClassNotFoundException;
}
Все весьма очевидно) Дальше перейдем к нашему главному объекту - классу двухуровневого кэша, к которому мы так долго шли.
Главный класс - TwoLevelCacheClass
Вот и настало время реализации главного класса нашей программы. Сначала рассмотрим код и разберем его отдельные части:
public class TwoLevelCacheClass<KeyType,ValueType extends Serializable> extends Object implements ILeveledCache<KeyType,ValueType>{
RamCacheClass<KeyType,ValueType> ramCache;
MemoryCacheClass<KeyType,ValueType> memoryCache;
int maxRamCacheCapacity;
int numberOfRequests;
int numberOfRequestsForRecahce;
public TwoLevelCacheClass(int _maxRamCacheCapacity, int _numberOfRequestsForRecache)
{
maxRamCacheCapacity = _maxRamCacheCapacity;
numberOfRequestsForRecahce = _numberOfRequestsForRecache;
ramCache = new RamCacheClass<KeyType, ValueType>();
memoryCache = new MemoryCacheClass<KeyType, ValueType>();
numberOfRequests = 0;
}
@Override
public void cache(KeyType key, ValueType value) throws IOException, ClassNotFoundException {
ramCache.cache(key,value);
}
@Override
public ValueType getObject(KeyType key) throws IOException, ClassNotFoundException {
if(ramCache.containsKey(key)){
numberOfRequests++;
if(numberOfRequests > numberOfRequestsForRecahce){
this.recache();
numberOfRequests = 0;
}
return ramCache.getObject(key);
}
if(memoryCache.containsKey(key)){
numberOfRequests++;
if(numberOfRequests > numberOfRequestsForRecahce){
this.recache();
numberOfRequests = 0;
}
return memoryCache.getObject(key);
}
return null;
}
@Override
public void deleteObject(KeyType key) {
if(ramCache.containsKey(key)){
ramCache.deleteObject(key);
}
if(memoryCache.containsKey(key)){
memoryCache.deleteObject(key);
}
}
@Override
public void clearCache() {
memoryCache.clearCache();
ramCache.clearCache();
}
@Override
public ValueType removeObject(KeyType key) throws IOException, ClassNotFoundException {
if(ramCache.containsKey(key)){
return ramCache.removeObject(key);
}
if(memoryCache.containsKey(key)){
return memoryCache.removeObject(key);
}
return null;
}
@Override
public boolean containsKey(KeyType key) {
if(ramCache.containsKey(key)){
return true;
}
if(memoryCache.containsKey(key)){
return true;
}
return false;
}
@Override
public int size() {
return ramCache.size() + memoryCache.size();
}
@Override
public void recache() throws IOException, ClassNotFoundException {
TreeSet<KeyType> ramKeySet = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
int boundFrecquency = 0;
// вычисление среднего арифметического для отбрасывания редко вызываемых объектов
for(KeyType key: ramKeySet)
{
boundFrecquency += ramCache.getFrecquencyOfCallingObject(key);
}
boundFrecquency /= ramKeySet.size();
for(KeyType key: ramKeySet)
{
if(ramCache.getFrecquencyOfCallingObject(key) <= boundFrecquency){
memoryCache.cache(key,ramCache.removeObject(key));
}
}
TreeSet<KeyType> memoryKeySet = new TreeSet<KeyType>(memoryCache.getMostFrequentlyUsedKeys());
for(KeyType key : memoryKeySet)
{
try{
if(memoryCache.getFrecquencyOfCallingObject(key) > boundFrecquency)
{
ramCache.cache(key,memoryCache.removeObject(key));
}
}
catch (IOException ex)
{
memoryCache.deleteObject(key);
continue;
}
catch (ClassNotFoundException ex)
{
// simply dummy
continue;
}
}
}
@Override
public Set<KeyType> getMostFrequentlyUsedKeys() {
TreeSet<KeyType> set = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
set.addAll(memoryCache.getMostFrequentlyUsedKeys());
return set;
}
@Override
public int getFrecquencyOfCallingObject(KeyType key) {
if(ramCache.containsKey(key))
{
return ramCache.getFrecquencyOfCallingObject(key);
}
if(memoryCache.containsKey(key))
{
return memoryCache.getFrecquencyOfCallingObject(key);
}
return 0;
}
}
Теперь разберем все по частям.Во первых, набор переменных
int maxRamCacheCapacity;
int numberOfRequests;
int numberOfRequestsForRecahce;
Эти переменные должны инициализироваться в конструкторе класса. Они будут отвечать за простейшую логику стратегии рекэширования. Соответственно,
maxRamCacheCapacity - максимальное количество записей в кэше оперативной памяти. Если количество элементов превосходит это число - вызывается алгоритм рекэширования.
numberOfRequests - количество запросов к кэшу после последнего рекэширования.
numberOfRequestsForRecahce - количество запросов, необходимое для рекэширования. Если numberOfRequests превышает numberOfRequestsForRecahce, то numberOfRequests обнуляется и вызывается recache().
Добавлять объекты мы будем соответственно в ramCache, а искать, извлекать, удалять и возвращать из всех кешей. В принципе, реализация всех методов стандартная, остановимся только лишь на методе recache(), реализация которого представляет наибольший интерес (хотя, следует отметить, что ничего нетривиального там нет). Я выбрал алгоритм вытеснения на основе самых редко вызываемых объектов. При рекэшировании я нахожу среднее арифметическое количества вызовов каждого объекта и переношу объекты из оперативной памяти, на жесткий диск. В свою же очередь, все объекты, хранящиеся на жестком диске и вызывавшиеся больше раз, чем это среднее арифметическое, забрасываются в оперативную память. Таким образом, происходит постоянное перетасовывание объектов между двумя кэшами. Внизу приведен код:
@Override
public void recache() throws IOException, ClassNotFoundException {
TreeSet<KeyType> ramKeySet = new TreeSet<KeyType>(ramCache.getMostFrequentlyUsedKeys());
int boundFrecquency = 0;
// вычисление среднего арифметического для отбрасывания редко вызываемых объектов
for(KeyType key: ramKeySet)
{
boundFrecquency += ramCache.getFrecquencyOfCallingObject(key);
}
boundFrecquency /= ramKeySet.size();
for(KeyType key: ramKeySet)
{
if(ramCache.getFrecquencyOfCallingObject(key) <= boundFrecquency){
memoryCache.cache(key,ramCache.removeObject(key));
}
}
TreeSet<KeyType> memoryKeySet = new TreeSet<KeyType>(memoryCache.getMostFrequentlyUsedKeys());
for(KeyType key : memoryKeySet)
{
try{
if(memoryCache.getFrecquencyOfCallingObject(key) > boundFrecquency)
{
ramCache.cache(key,memoryCache.removeObject(key));
}
}
catch (IOException ex)
{
memoryCache.deleteObject(key);
continue;
}
catch (ClassNotFoundException ex)
{
// simply dummy
continue;
}
}
}
В объяснении перед кодом был подробно изложен принцип работы рекэширования, и, я полагаю, дальнейшие объяснения будут неуместны.
Заключение
В заключении хочу лишь сказать, что это был хороший опыт программирования на Java. Меня приятно порадовал этот язык, богатый своими конструкциями. Особенно впечатлила среда разработки Intellij Idea 11.0, стол дружелюбная и полезная для рядового программиста. Также отмечу, что мое решение не претендует на идеальный пример проектирования программ, но, быть может, окажется хорошим подспорьем для начинающих программистов.
Всем, кто дочитал до этого места, спасибо за внимание и до новых встреч!
Комментариев нет:
Отправить комментарий