分页查询总行数缓存策略

文章有点长。。。

以前看到的分页模型大同小异，都是一个POJO结合各类视图技术实现的，但对于每次查询，都要计算总页数（统计记录总行数），对于记录数较少、并发不高的系统来讲，这似乎没有什么问题，但对于高并发，记录行数很多（千万级）的情况，每次的统计行数就要花费不少时间。我这里尝试着设计了一个行数缓存和一个简单的分页POJO（跟传统的POJO大同小异），请大家批评讨论，并提出一些建议。分享才能进步！

1、在哪里缓存
可以在客户端（使用Cookie），也可以在服务器端（设计一个Cache）。服务器端可以灵活定义缓存时间、刷新策略，这里仅讨论服务器端缓存（大家也可以提提客户端缓存的优缺点）。

2、使用什么作为缓存的Key
缓存当然要有Key-Value，什么作为Key合适呢？
对于每次查询，查询条件是不一样的，尤其对于复杂的多条件动态查询，即同一个Service方法可能会有不同的查询条件，这样每次的记录行数是不确定的。所以，可以唯一标示一个查询的就是请求调用的方法（Controler里分发）和对应的查询参数，如：/listUsers.do?name=xxx&curPage=1 。那么就需要在服务器端获取这个url，然后把&curPage=1 这个条件去掉。需要注意的是：对于form的提交，需要以get方式，参数才可以用request.getQueryString()获取。

确定使用url作为缓存的key后，就要设计Page模型和缓存模型了。一般情况下，在Controler里调用Service，需要传入一个Page对象，在Dao中需要根据url进行缓存查询，决定是否要统计行数，将url直接作为Dao层中方法的参数是很不优雅的。这里我将url设计成Page的一个属性，在Dao中可以方便的使用page.getUrl()获取url了。

3、缓存策略
我们以<url,RowCount>的key-value形式在HashMap中缓存一个行数记录。关于缓存策略，可以有很多种，这里分析一下。

1）每个url具有独立的缓存策略
就是说，每个url可以有不同的缓存时间、刷新策略。缓存时间可以根据这个url对应的预计并发情况、统计耗时确定。
刷新可以访问后无论缓存中是否有对应的行数记录立刻重置计时，也可以只在缓存过期后才刷新，而缓存有效时不进行刷新。

2）统一定义每个url的缓存策略
这种情况下只需要每隔一段时间重置所有缓存中的记录的计时器即可，是最简单的一种。然而间隔时间多少不好估计。

3）是否需要换出内存
一个url按100个字符计算，加上RowCount（含2个int，一个long）本身的内存占用大概30byte，一个记录大概230byte，如果一个系统有10000个需要分页的查询（若查询参数不同，数目远不止这个），缓存占用约2Mb。还是占用了不少的内存，因此需要设计内存换出策略。可以采用最近最少使用原则LRU（Least Recently Used）、最不常用原则LFU（Least Frequently Used）等。前者简单，后者貌似更公平。我们简单采用LRU的一个简化版本：当缓存条目达到限制时，将最近最久未访问的缓存记录换出（LRU是计数，这里是计时）。

4、示例代码
Page分页模型：

/**
 * A pagination tool,default pageSize:20
 * @author chen
 */
public class Page {
	private int totalRow;
	private int totalPage;
	private int curPage;
	private int pageSize;
	private String url;
	private static final int DEFAULT_PAGESIZE=20;
	/**
	 * Default page size is 20
	 * @param url A string in the address field of the browser
	 * @param curPage current page index
	 */
	public Page(String url,int curPage) {
		this.url=url.replaceAll("&?curPage=\\d*", "");
		this.curPage = curPage < 1 ? 1 : curPage;
		this.pageSize = DEFAULT_PAGESIZE;
	}

	/**
	 * @param url A string in the address field of the browser
	 * @param curPage Current page index
	 * @param pageSize Size of the page
	 */
	public Page(String url,int curPage, int pageSize) {
		this.url=url.replaceAll("&?curPage=\\d*", "");
		this.curPage = curPage < 1 ? 1 : curPage;
		this.pageSize = pageSize;
	}
	/**
	 * Set total row of the pager
	 */
	public void setTotalRow(int totalRow) {
		this.totalRow =totalRow;
		this.totalPage=this.totalRow < 1 ? 0 : (this.totalRow - 1) / pageSize + 1;
		//invalid state
		if(curPage>this.totalPage || curPage<1){
			this.totalPage=0;
			this.totalRow=0;
			this.curPage=1;
		}
	}
	......
}

缓存模型：

public class RowCountCache {
	private RowCountCache() {
	}
	private Map<String, RowCount> m = new HashMap<String, RowCount>();
	private static RowCountCache cache = new RowCountCache();
	private static final int MAXSIZE=10000;
	private static Calendar c=Calendar.getInstance();
	/**
	 * An object of this cache.
	 * @return this
	 */
	public static RowCountCache getInstance() {
		return cache;
	}
	/**
	 * Cache state of the object: In the cache and is valid.
	 */
	public static final int CACHESTATE_VALID=1;
	/**
	 * Cache state of the object: Cache is expired
	 */
	public static final int CACHESTATE_EXPIRED=-1;
	/**
	 * Cache state of the object: Not in the cache.
	 */
	public static final int CACHESTATE_UNCACHED=-2;
	
	/**
	 * Get the row-count number from the cache of the given url.
	 * @return A row-count number,-1 if was not cached.
	 */
	public int get(String url) {
		RowCount r = m.get(url);
		return r==null ? -1 : r.getTotalRow();
	}
	
	/**
	 * Put or refresh cached row-count corresponding given url with default cache time.
	 * @param totalRow A row-count number corresponding a specify url.
	 */
	public void putOrRefresh(String url,int totalRow) {
		int cacheState=RowCountCache.getInstance().getCacheState(url);
		if(cacheState==RowCountCache.CACHESTATE_UNCACHED){
			this.put(url, totalRow);
		}else{
			this.refresh(url, totalRow);
		}
	}
	/**
	 * Put or refresh cached row-count corresponding given url with custom cache time.
	 * @param totalRow A row-count number corresponding a specify url.
	 * @param cacheTime Time the totalRow will be cached, in seconds.
	 */
	public void putOrRefresh(String url,int totalRow,int cacheTime) {
		int cacheState=RowCountCache.getInstance().getCacheState(url);
		if(cacheState==RowCountCache.CACHESTATE_UNCACHED){
			this.put(url, totalRow,cacheTime);
		}
		if(cacheState==RowCountCache.CACHESTATE_EXPIRED){
			this.refresh(url, totalRow);
		}
	}
	private void put(String url,int totalRow) {
		if(m.size()>=MAXSIZE){
			Set<Map.Entry<String, RowCount>> set = m.entrySet();
			c.setTime(new Date());
			long max_interval=-1;
			String key="";
			//find the farthest unused RowCount record
			for(Iterator<Map.Entry<String, RowCount>> iter=set.iterator();iter.hasNext();){
				Map.Entry<String, RowCount> e = iter.next();
				RowCount r=e.getValue();
				long interval=c.getTimeInMillis()-r.getLastVisit();
				if(max_interval<interval){
					max_interval=interval;
					key=e.getKey();
				}
			}
			m.remove(key);
		}
		m.put(url, new RowCount(totalRow));
	}
	private void put(String url,int totalRow,int cacheTime) {
		m.put(url, new RowCount(totalRow,cacheTime));
	}
	private void refresh(String url,int totalRow) {
		RowCount r =m.get(url);
		r.refresh(totalRow);
	}
	/**
	 * Get the cache state of RowCount corresponding the given url
	 * @return cache state
	 */
	public int getCacheState(String url) {
		RowCount r=m.get(url);
		if(r==null){
			return RowCountCache.CACHESTATE_UNCACHED;
		}else if(r.isExpired()){
			return RowCountCache.CACHESTATE_EXPIRED;
		}else{
			return RowCountCache.CACHESTATE_VALID;
		}
	}
}
/**
 * An object in the cache corresponding a specify url.
 * @author chen
 */
class RowCount{
	//Default cached time,5sec.
	private static final int DEFAULT_CACHE_TIME=5;
	private static Calendar c=Calendar.getInstance();
	private int totalRow;
	private int cacheTime;
	private long lastVisit;
	/**
	 * Construct RowCount with default cached time,5sec.
	 * @param totalRow A row count number corresponding a specify url.
	 */
	public RowCount(int totalRow){
		this.totalRow=totalRow;
		this.cacheTime=DEFAULT_CACHE_TIME;
		c.setTime(new Date());
		this.lastVisit=c.getTimeInMillis();
	}
	/**
	 * Construct RowCount with custom cached time,5sec.
	 * @param totalRow A row count number corresponding a specify url.
	 * @param cacheTime Time of the object will be cached,in seconds.
	 */
	public RowCount(int totalRow,int cacheTime){
		this.totalRow=totalRow;
		this.cacheTime=cacheTime;
		c.setTime(new Date());
		this.lastVisit=c.getTimeInMillis();;
	}
	/**
	 * Get the value of the row count.
	 * @return the value of the row count.Return -1 if the cache is expired.
	 */
	public int getTotalRow(){
		if(!isExpired()){
			return this.totalRow;
		}
		return -1;
	}
	/**
	 * Refresh this RowCount object in the cache.
	 * @param row A new row count number.
	 */
	protected void refresh(int row){
		this.totalRow=row;
		c.setTime(new Date());
		this.lastVisit=c.getTimeInMillis();;
	}
	/**
	 * Check whether the cache is expired
	 * @return true,expired; false,unexpired
	 */
	public boolean isExpired(){
		c.setTime(new Date());
		long t=c.getTimeInMillis();
		return t > this.lastVisit + this.cacheTime*1000;
	}
	/**
	 * Get the last visit date of the object in milliseconds.
	 */
	protected long getLastVisit(){
		return this.lastVisit;
	}
}

下面是一个使用的Demo（部分代码）
一个请求发送到Controler（为简化，省略了Service层）

...
Page p=new Page(HttpUtil.getUrl(),HttpUtil.getInteger(request, "curPage"));
request.setAttribute("all", userDao.find(cond,p));
request.setAttribute("page", p);
return mapping.findForward("find.do");

Dao：

...
int cacheState=RowCountCache.getInstance().getCacheState(p.getUrl());
if(cacheState==RowCountCache.CACHESTATE_VALID){
     p.setTotalRow(RowCountCache.getInstance().get(p.getUrl()));
}else{
     p.setTotalRow(this.countRow(cond, p));
}
//Whatever the cache is valid,refresh it.You can aslo refresh only when the cache is expired
RowCountCache.getInstance().putOrRefresh(p.getUrl(), p.getTotalRow());
List<Users> all=ct.setFirstResult(p.getFirstRow()).setMaxResults(p.getPageSize()).list();
return all;

终于写完了，请大家多多提意见，共同进步。~~

多谢楼主 很详细的代码和注释

看了一半 有点头大 先顶下

请问下楼主做JAVA开发几年了 哪年的 呵呵

最近写代码感觉没前途似的 以前出来的几个朋友都做其它的去了 一半以上开外贸公司 多的月10万 去年开始的

LZ的写的很好，但我想请教几个问题：
    1.在内存中用map缓存用户的请求参数，如果是同一个用户在一段时间内发同一请求，但不同的curPage参数，LZ的做法是多进行了缓存，却没有想覆盖，这样是否是浪费而没意义的呢
    2.List<Users> all=ct.setFirstResult(p.getFirstRow()).setMaxResults(p.getPageSize()).list(); Lz使用hibernate吧，那hibernate的一二级缓存为何不考虑使用呢？
    3.分页吧，是Web应用吧？那服务器的session来缓存应该是最妥当的，缓存用户会话期间的请求参数，会话结束，即可以自动在设置的时间内销毁。
    4.在页面用数据岛缓存，但这需要js控制，也是不错的选择
最后 Lz代码写得很棒，学习了！

你说的是“钱途”，不是“前途”
做事情要静心，别人赚并不一定自己也会赚
要明白自己适合做什么
坚持自己的理想
祝你成功！

1、代码中已经把curPage这个参数忽略掉了，即使不同的curPage，只要缓存有效，也不会重新计算总行数。

public Page(String url,int curPage, int pageSize) {   
        this.url=url.replaceAll("&?curPage=\\d*", "");//就在这里   
        this.curPage = curPage < 1 ? 1 : curPage;   
        this.pageSize = pageSize;   
    }

2、你当然可以不使用Hibernate，代码只是一个示例，Dao层可以使用其他实现。Hibernate的二级缓存用来缓存总行数是不合适的，每次的查询条件是不一样的。
3、session在web应用中最好少用，占用服务器较大资源。
4、js当然也可以，可惜我不太熟悉。。。

LZ写的很清晰，在这里说一下我的想法:
1）LZ的缓存是为了当用户查看第2页，第3页等情况设计的？如果是这样，总页数我觉得可以在第一次查询以后就放入client端，当用户查看N页时，把当前的总页数一起提交到Server端，或者在web页面时不去刷新总页数部分。

2）对于LZ在Server端进行缓存，如果用户用不同的查询条件，又或者在text框中多输入了一个空格，缓存都会重新查询的。
3）假如用户第一次查询数据之后，新增了一条记录，这时的再次查询时，由于Server端的缓存，用户应该不会查询到新加入的记录的。
4）个人觉得，这个总页数应该存储在client端，当查看N页时，可以一并提交到Server,如果是重新查询数据的话，应该再次查询DB，还计算总页数。

设计的初衷就是解决高并发、记录量大的情况下统计行数出现的性能问题。放在客户端，则每个用户的第一次查询都会统计行数，而服务器端缓存可以实现所有用户共享行数记录，尤其对于高并发的情况下（如5秒内有1000个不同的用户访问，则只需要统计一次，而在客户端要统计1000次）。


这个空格（首尾）是需要过滤掉的，而字符中间的空格无需关心，本身就是不同的查询参数（当然你也可以过滤掉）。

在高并发下，你会在乎是否可以马上看到最新的内容？况且5秒的延迟还可以忍受吧（5秒钟之后即可看到新增的内容）。

  我们就是这么处理的, 在客户端缓存了总页数.
  只是在第一次查询时获得总页数, 分页是把总页数再传回去, 如果用户想刷新总页数, 就点击"刷新"按钮.

感觉LZ这样子把问题复杂化了，把总数当做一个参数传递到客户端再通过url传递回来就行了，如果第一次请求那后面读不到这个参数就说明是第一次查询，去查一次。

楼主想得有点简单了，总行数并不是URL参数能确定的，不同的人提交相同的参数，但因为权限的不同，查到的数目是不一样的；另外，新增记录后，你好像没有立即把缓存清除，客户如果新增后立即查一下结果，细心的可能会发现查是查到了，但是总行数没有变化，会认为你的程序有问题，这个问题可以在RowCount类中加入一个类别属性，值为对应POJO的全类名，这样你提供一个类似这样的方法clearCacheByType(Class pojoClass)，新增记录就可以通过POJO类一下把所有相关的缓存清除。