oscache源代码阅读(三) -- 基本缓存实现

oscache的默认缓存实现是由4个类组成的，如下图所示：



首先来看一下是如何放入缓存的操作吧，也就是AbstractConcurrentReadCache类的#put()方法：

	public Object put(Object key, Object value) {
		return put(key, value, true);
	}

	// 这里的第三个参数代表是否持久化缓存
	private Object put(Object key, Object value, boolean persist) {
		if (value == null) {// 默认是不支持空值的
			throw new NullPointerException();
		}

		// 计算hash
		int hash = hash(key);
		// hash表，其实Entry本身是一个链表的结构，也就是hash桶
		Entry[] tab = table;

		// 将hash值与hash表的长度按位与得到初始位置
		int index = hash & (tab.length - 1);

		// first指的是hash表中Entry链表的第一个元素
		Entry first = tab[index];
		Entry e = first;

		for (;;) {
			if (e == null) {// 如果哈希表当前位置是空位
				synchronized (this) {
					tab = table;

					Object oldValue = null;

					// Remove an item if the cache is full
					if (size() >= maxEntries) {// 如果缓存已满，需要挑选一个Entry移出
						// part of fix CACHE-255: method should return old value
						// 挑选要移出的key的方法#removeItem()是由之类去实现的
						oldValue = remove(removeItem(), false, false);
					}

					if (first == tab[index]) {// 这里是对可能存在的并发更新的处理
						// Add to front of list
						Entry newEntry = null;

						if (memoryCaching) {
							newEntry = new Entry(hash, key, value, first);
						} else {
							newEntry = new Entry(hash, key, NULL, first);
						}

						tab[index] = newEntry;

						// 通知具体实现值已经放入缓存的回调
						itemPut(key);

						// Persist if required
						// 这里如果配置文件中cache.memory=false并且cache.persistence.overflow.only=true程序就进入了一个混乱的状态了
						// 因为内存中的Entry值为NULL，并且不会调用持久化存储
						// 所以这两个配置项配合的话只有3种情况了
						// (1) memory=true, overflow=true：使用内存缓存，溢出的数据持久化
						// (1) memory=true, overflow=false：使用内存缓存，溢出的数据不处理
						// (1) memory=false, overflow=false：使用持久化缓存

						if (persist && !overflowPersistence) {// 如果需要持久化保存
							persistStore(key, value);
						}

						// If we have a CacheEntry, update the group lookups
						if (value instanceof CacheEntry) {
							// 更新缓存的分组信息，其实AbstractConcurrentReadCache
							// 用一个HashMap保存了分组名和各个key之间的一个映射 groupname -> Set<Key>
							updateGroups(null, (CacheEntry) value, persist);
						}

						// 如果数量大于threshold(capacity * 装填因子(loadfactor))
						if (++count >= threshold) {// 是否rehash
							rehash();
						} else {
							recordModification(newEntry);
						}

						return oldValue;
					} else {
						// 如果当前hash表发生了变化，即发生了并发插入缓存的操作，此时需要进入这个分支
						// #sput()里边的逻辑和#put()是类似的
						return sput(key, value, hash, persist);
					}
				}
			} else if ((key == e.key) || ((e.hash == hash) && key.equals(e.key))) {// 如果当前的key已经存在了，更新值
				// synch to avoid race with remove and to
				// ensure proper serialization of multiple replaces
				synchronized (this) {
					tab = table;

					Object oldValue = e.value;

					// [CACHE-118] - get the old cache entry even if there's no
					// memory cache
					// oldValue为NULL代表了是磁盘缓存
					if (persist && (oldValue == NULL)) {
						// 在磁盘里去的缓存值
						oldValue = persistRetrieve(key);
					}

					if ((first == tab[index]) && (oldValue != null)) {
						if (memoryCaching) {
							// 缓存更新值
							e.value = value;
						}

						// Persist if required
						if (persist && overflowPersistence) {
							// 如果缓存溢出需要持久化，在缓存持久化处移除这个值
							// 因为现在内存中已经有这个值了，不能再持久化了
							// 这里因为是更新，所以按理说不会有它对应的overflow缓存的啊？
							persistRemove(key);
						} else if (persist) {// 持久化保存
							persistStore(key, value);
						}

						updateGroups(oldValue, value, persist);
						itemPut(key);

						return oldValue;
					} else {
						return sput(key, value, hash, persist);
					}
				}
			} else {// 将e指向Entry链表的下一个项目
				e = e.next;
			}
		}
	}

整个的流程用代码的注释其实就可以写清楚了，注意，在更新缓存后会调用给之类的回调函数#itemPut()，另外还有参数cache.memory和cache.persistence.overflow.only对流程的影响。

下面看下#get()，这里#remove()就不写了其实过程反倒和#get()也差不多：

	public Object get(Object key) {
		if (log.isDebugEnabled()) {
			log.debug("get called (key=" + key + ")");
		}

		// 计算hash
		int hash = hash(key);

		/*
		 * Start off at the apparently correct bin. If entry is found, we need
		 * to check after a barrier anyway. If not found, we need a barrier to
		 * check if we are actually in right bin. So either way, we encounter
		 * only one barrier unless we need to retry. And we only need to fully
		 * synchronize if there have been concurrent modifications.
		 */
		// 计算在hash表中的位置
		Entry[] tab = table;
		int index = hash & (tab.length - 1);
		// Entry链表中的第一个数据
		Entry first = tab[index];
		Entry e = first;

		for (;;) {
			if (e == null) {
				// If key apparently not there, check to
				// make sure this was a valid read
				// key没找到，再次查看hash表确定是否真的找不到了
				tab = getTableForReading();

				if (first == tab[index]) {
					// Not in the table, try persistence
					// 试着在持久化处找
					Object value = persistRetrieve(key);

					if (value != null) {
						// Update the map, but don't persist the data
						// 在持久化处找到数据的话需要更新hash表，但不去重新持久化
						put(key, value, false);
					}

					return value;
				} else {
					// Wrong list -- must restart traversal at new first
					e = first = tab[index = hash & (tab.length - 1)];
				}
			}
			// checking for pointer equality first wins in most applications
			else if ((key == e.key) || ((e.hash == hash) && key.equals(e.key))) {// 找到了数据
				Object value = e.value;

				if (value != null) {
					if (NULL.equals(value)) {
						// Memory cache disable, use disk
						// 需要去缓存找数据
						value = persistRetrieve(e.key);

						if (value != null) {
							// 调用回调
							itemRetrieved(key);
						}

						return value; // fix [CACHE-13]
					} else {
						// 调用回调
						itemRetrieved(key);

						return value;
					}
				}

				// Entry was invalidated during deletion. But it could
				// have been re-inserted, so we must retraverse.
				// To avoid useless contention, get lock to wait out
				// modifications
				// before retraversing.
				synchronized (this) {
					tab = table;
				}

				// 到这里其实是列表处于一个错误的状态了，重新循环
				e = first = tab[index = hash & (tab.length - 1)];
			} else {// 需要查看链表中的下一个元素
				e = e.next;
			}
		}
	}

其实这个#get()在一些并发控制的精妙上我也看不出来，只能留待以后水平高了的时候去研究了，现在能看懂的也只有大致的流程。

最后对3个默认缓存实现中的LRU进行下简单的分析，实现方法挺简单的，不过有一些借鉴意义。

首先，LRUCache使用LinkedHashSet来将key值进行是否最近使用的排序，越往后越是最近使用的Key

    private Collection list = new LinkedHashSet();

前面不是说在put，get，remove中都有之类的回调函数吗，这里就派上用场了

	protected void itemRetrieved(Object key) {
		while (removeInProgress) {
			try {
				Thread.sleep(5);
			} catch (InterruptedException ie) {
			}
		}

		// 这里改变了list中元素的顺序
		synchronized (list) {
			list.remove(key);
			list.add(key);
		}
	}

	protected void itemPut(Object key) {
		// 这里改变了list中元素的顺序
		synchronized (list) {
			list.remove(key);
			list.add(key);
		}
	}

这样，在缓存已满需要查找待移除的Key时，就可以使用list的顺序了，很简单，但是很有效。

	private Object removeFirst() {
		Object toRemove = null;

		synchronized (list) { // A further fix for CACHE-44 and CACHE-246
			Iterator it = list.iterator();
			toRemove = it.next();
			it.remove();
		}

		return toRemove;
	}