内存数据跨天原子切换设计与实现

原创
2014/03/28 00:33
阅读数 806

问题背景

在开发积分系统过程有一个业务需求:

用户每天可以通过分享或邀请获得相应的积分,但每天分享或邀请次数有上限。比如分享到QQ空间每天最多前2次可以获得积分,而分享到新浪微博每天最多前3次可以获得积分。

考虑到用户赚取/消费积分行为很频繁,对应的积分流水表也会很大,所以不可能每次都直接查询积分流水表来判断是否达到次数限制。

然后可能有人会选择另外开辟一张表记录每个用户每天已分享次数,分享前先去查询下看有没有达到限制,如果没有达到限制就+1,然后再继续后面的加积分操作。显然这种方案也不靠谱,因为增加了额外的数据库查询和更新,性能较差。

接下来可能又有人会建议用Redis,为每个用户每种分享类型维护一个计数器,比如1001:QQShare => 1,这样比上面这种稍微好点,但考虑到下面几点也否决了这种方案:

  • 还是需要先查询,再更新计数值

  • 用户数据量千万级(假如一种分享类型一千万,十种分享类型就一亿,如果每个条目100字节,那么需要9.3G内存),全部存在Redis中,内存开销太高

  • Redis基于TCP/IP协议,网络传输也有开销

最后我想出了一个方案,使用Counting Bloom Filter:只要哈希函数选择得当,哈希运算次数得当,我可以通过牺牲微乎其微的准确性(False Positive误判概率)达到高效判断(平均每次判断0.006ms),并大大减少内存消耗(1.34亿只需要32MB左右内存)。最后选择的是Hadoop库的CountingBloomFilter实现,我只在其基础上稍稍修改了下序列化和反序列化方法。

OK,说了这么一大堆,终于要引出本文的主题了,本文重点当然不是讲CountingBloomFilter,而是讲CountingBloomFilter这个存在内存中的对象如何实现跨天原子切换。

何为跨天原子切换?

首先,跨天指的是内存中的对象存在时效性,比如4.1号的CountingBloomFilter对象只能用于4.1号,因为4.2号需要重新开始计数,即需要另外一个CountingBloomFilter对象。

其次原子切换指的是过期的内存对象需要尽可能快地被清除,以释放它占用的内存,当然清除的前提是它确实满足清除条件(即确定现在已经没有人在使用这个对象并且将来也不会有人再使用这个对象了,举个例子现在是4.2号12点过一秒,4.1号的CountingBloomFilter对象可能仍然被4.1号11点59分59秒的1个线程访问,那么必须等那个线程访问完毕后才能够放心清理对象)。

最后尤其注意一点:内存中的对象被多线程并发访问,后面的实现代码中有多处因为这点而做特殊处理。


设计

首先考虑到跨天,当然很直观地需要两个对象。然后这些对象有实效性,所以每个对象都带有一个创建日期属性:如果当前日期大于这个对象的创建日期,那么就应该准备回收这个对象了。但不能够一检查到对象的创建日期是昨天就马上回收,原因前面说过了因为可能还有昨天的请求还在使用这个“应该过期回收的对象”,所以对象自然还有一个使用者计数属性。所以我初步抽象出一个DataSection分区类包装内存对象及其他属性:

import java.util.concurrent.atomic.AtomicInteger;

public class DataSection<T> {

	private int createdDay; // 创建日期
	private T data;         // 实际对象
	private AtomicInteger useCount = new AtomicInteger(0); // 使用者计数

	public DataSection(int createdDay, T data) {
		if (createdDay <= 0 || data == null) {
			throw new IllegalArgumentException(
					"createdDay should > 0 and data should not null");
		}

		this.createdDay = createdDay;
		this.data = data;
	}

	// 释放对象内存,设置最占内存的data对象为null
	public void clear() {
		this.data = null;
	}

	public int getCreatedDay() {
		return this.createdDay;
	}

	public T getData() {
		return this.data;
	}

	// 获取用户使用计数
	public int getUseCount() {
		return useCount.get();
	}

	// 用户使用计数加1
	public void increaseUseCount() {
		useCount.incrementAndGet();
	}

	// 用户使用计数减1
	public void decreaseUseCount() {
		useCount.decrementAndGet();
	}

}

代码很直观,然后我就在纸上画了两个方框表示两个内存对象,然后思考该如何实现它们的切换,应该如何让“过期对象”释放内存。我一开始想到轮询法:新开一个监控线程,每隔5s访问两个DataSection对象的useCount和createdDay,如果当前日期不等于createdDay(可能比createdDay大1,也可能比createdDay小,比如跨月),并且对象的useCount值为0,那么就释放这个对象,简单代码演示如下(仅演示,实际代码不应该如此):

DataSection dataSectionA;
DataSection dataSectionB;

while(true) {
   int curDay = curDay();

   if(dataSectionA != null && dataSectionA.getCreatedDay() != curDay) {
      dataSectionA.clear();
   }

   if(dataSectionB != null && dataSectionB.getCreatedDay() != curDay) {
      dataSectionB.clear();
   }

   Thread.sleep(5000);
}

这种释放对象内存的方法很被动,没法做到实时清理过期对象内存。那么要做到实时清理过期对象内存就必须由对象使用者主动释放过期对象内存。写这篇文章时 我想到一个比喻能够帮助理解主动释放对象内存和被动释放对象内存的区别:

假如有一个自助咖啡厅,咖啡厅正常每天晚上8点关门,但如果8点时还有客人在喝咖啡,那么不能关门。但8点之后自动咖啡机不再提供咖啡,意味着8点之后不再会有人来自助咖啡厅喝咖啡了。
咖啡厅有一个管理员,他从7点55开始每隔2分钟就来检查一下咖啡厅是否可以关门(时间超过8点,并且没有客人了才可以关门)。
管理员日复一日做着这种事,厌烦透顶,某一日他终于不干了。头脑灵活的咖啡厅经理想到个好主意:让客人自己关门。即每个客人喝完咖啡后都看下现在还有没有人在喝咖啡,并且是否到了晚上8点,如果是那么他就帮忙把咖啡厅门关上。

显然管理员关门方案是被动方案,客人关门方案是主动方案,也是更聪明、更实时的方案。

所以我很自然地放弃了那种不够聪明和实时的被动轮询方案。然后我继续在纸上比划着,某一瞬间我突然想到年轻代的两个Survivor区:from区和to区。虽然最终发现没法照搬,但也确实启发了我:from区并不是一直都是from区,from区某些情况会切换成to区,而同时to区会切换成from区。这足够了,于是我给DataSection添加了一个新属性isMaster,表明它是主区(isMaster为true)还是从区(isMaster为false),主区并不一直是主区,从区也并不一直是从区:

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class DataSection<T> {

	private int createdDay; // 创建日期
	private T data; // 实际对象
	private AtomicInteger useCount = new AtomicInteger(0);       // 使用者计数
	private AtomicBoolean isMaster = new AtomicBoolean(false);   // 是否主区,默认为false

	public DataSection(int createdDay, T data, boolean isMaster) {
		if (createdDay <= 0 || data == null) {
			throw new IllegalArgumentException(
					"createdDay should > 0 and data should not null");
		}

		this.createdDay = createdDay;
		this.data = data;
		this.isMaster.set(isMaster);
	}

	// 清理方法,设置最占内存的data为null
	public void clear() {
		this.data = null;
	}

	public int getCreatedDay() {
		return this.createdDay;
	}

	public T getData() {
		return this.data;
	}

	// 获取用户使用计数
	public int getUseCount() {
		return useCount.get();
	}

	// 用户使用计数加1
	public void increaseUseCount() {
		useCount.incrementAndGet();
	}

	// 用户使用计数减1
	public void decreaseUseCount() {
		useCount.decrementAndGet();
	}
	
        // 将当前分区设为主分区
	public void setAsMaster() { 
		isMaster.set(true); 
	}
	
	// 将当前分区设为从分区
	public void setAsSlave() { 
		isMaster.set(false); 
	}
	
	// 判断当前分区是否是否主分区
	public boolean isMaster() { 
		return isMaster.get(); 
	} 

}

主分区的数据一般是最新的数据,除了跨天切换过程的短暂时间可能不是。

接下来我继续思考如何 主动释放过期分区包装的对象数据。我想象4.1号有一个dataSectionA分区,它是主分区;4.2号凌晨过1秒有一个线程来访问,这时它发现dataSectionA的日期是昨天,那么它会创建另外一个dataSectionB分区以提供给4.2号的线程使用。它创建并使用完dataSectionB之后,它会检查下dataSectionA是否还有人在用:

  • 如果没有,那么它就帮忙释放dataSectionA

  • 如果仍然有,那么麻烦一些,它没法直接释放dataSectionA,这时它标记下dataSectionA满足释放条件中的过期条件,然后让还在使用dataSectionA的线程使用完dataSectionA后自己检查下是否带有过期条件标记和使用者计数是否为0,如果二者都是那就释放

于是我又为DataSection添加一个属性isGCCandidate,如下:

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class DataSection<T> {

	private int createdDay; // 创建日期
	private T data; // 实际对象
	private AtomicInteger useCount = new AtomicInteger(0);           // 使用者计数
	private AtomicBoolean isMaster = new AtomicBoolean(false);       // 是否主区,默认为false
	private AtomicBoolean isGCCandidate = new AtomicBoolean(false);  // 标记是否GC候选,默认为false 

	public DataSection(int createdDay, T data, boolean isMaster) {
		if (createdDay <= 0 || data == null) {
			throw new IllegalArgumentException(
					"createdDay should > 0 and data should not null");
		}

		this.createdDay = createdDay;
		this.data = data;
		this.isMaster.set(isMaster);
	}

	// 清理方法,设置最占内存的data为null
	public void clear() {
		this.data = null;
	}

	public int getCreatedDay() {
		return this.createdDay;
	}

	public T getData() {
		return this.data;
	}

	// 获取用户使用计数
	public int getUseCount() {
		return useCount.get();
	}

	// 用户使用计数加1
	public void increaseUseCount() {
		useCount.incrementAndGet();
	}

	// 用户使用计数减1
	public void decreaseUseCount() {
		useCount.decrementAndGet();
	}
	
	// 将当前分区设为主分区
	public void setAsMaster() { 
		isMaster.set(true); 
	}
	
	// 将当前分区设为从分区
	public void setAsSlave() { 
		isMaster.set(false); 
	}
	
	// 判断当前分区是否是否主分区
	public boolean isMaster() { 
		return isMaster.get(); 
	}
	
	// 标记该数据区为GC候选
	public void markAsGCCandidate() { 
		isGCCandidate.set(true); 
	} 

	public boolean isGCCandidate() { 
		return isGCCandidate.get(); 
	} 

}

好了,设计思路讲述得差不多了,其实我在思考和实现这个东西的过程还是很快速的,这里为了尽量讲清楚所以才说了那么多,下面是实现代码。

import java.util.Calendar;

public class DataSectionAccessDemo {

	public static void main(String[] args) {

	}

	DataSection<CBF> dataSectionA;
	DataSection<CBF> dataSectionB;

	public DataSectionAccessDemo() {
		dataSectionA = new DataSection<CBF>(getCurDay(), new CBF(), true); // 此时dataSectioinA为主分区,dataSectionB仍然为null
	}

	// 访问数据分区方法
	public void accessDataSection() {
		DataSection<CBF> masterSection = getMasterSection(); // 此处获得的masterSection的cbf原则上不可能为nul
		int curDay = getCurDay(); // 获取当前日期

		if (masterSection.getData() == null) { // 此处再增加判断,防止下面“Mark”处代码可能在此时已经clear了masterSection的数据
			masterSection = getMasterSection();
			curDay = getCurDay();
		}

		if (curDay == masterSection.getCreatedDay()) { // 当前请求发生日期和主数据分区的创建日期相等,99.99%以上的情况都走这个分支
			masterSection.increaseUseCount(); // 增加masterSection使用计数
			// 使用masterSection代码略
			masterSection.decreaseUseCount(); // 减少masterSecton使用计数

			// 跨天旧数据处理
			if (masterSection != null && masterSection.getUseCount() == 0
					&& masterSection.isGCCandidate()) {
				masterSection.clear();
			}
		} else {
			DataSection<CBF> slaveSection = dataSectionA == masterSection ? dataSectionB
					: dataSectionA;

			// 双重加锁+双重检测防止并发场景下重复实例化
			if (slaveSection == null || slaveSection.getData() == null) {
				synchronized (this) { // 锁为当前DataSectionAccessDemo对象
					DataSection<CBF> tempSection = slaveSection;
					if (tempSection == null || tempSection.getData() == null) {
						synchronized (this) {
							tempSection = new DataSection<CBF>(curDay,
									new CBF(), true);
						}

						if (slaveSection == cbfSection1) {
							cbfSection1 = tempSection;
						} else {
							cbfSection2 = tempSection;
						}
						slaveSection = tempSection; // slaveSection现在已经升级为主分区
						masterSection.setAsSlave(); // 切换原来的masterSection为从分区
						masterSection.markAsGCCandidate(); // 标识masterSection为过期对象
					}
				}
			}

			slaveSection.increaseUseCount();
			// 使用slaveSection代码略
			slaveSection.decreaseUseCount();

			// 检查masterSection此时是否可以被回收
			if (masterSection != null && masterSection.getUseCount() == 0
					&& masterSection.isGCCandidate()) {
				masterSection.clear(); // Mark
			}
		}
	}

	// 获取主数据区。Invariant: 必须始终有且仅有一个主数据区,即该方法返回值必须始终不为null
	public DataSection<CBF> getMasterSection() {
		if (dataSectionA != null && dataSectionA.isMaster()) {
			return dataSectionA;
		}

		return dataSectionB;
	}

	// 获取创建日期较新的DataSection
	public DataSection<CBF> getNewerSection() {
		if (dataSectionA == null) {
			return dataSectionB;
		} else if (dataSectionB == null) {
			return dataSectionA;
		}

		if (Math.abs(dataSectionA.getCreatedDay()
				- dataSectionB.getCreatedDay()) < 2) {
			return dataSectionA.getCreatedDay() > dataSectionB.getCreatedDay() ? dataSectionA
					: dataSectionB;
		}

		return dataSectionA.getCreatedDay() > dataSectionB.getCreatedDay() ? dataSectionB
				: dataSectionA;
	}

	public DataSection<CBF> getDataSectionA() {
		return dataSectionA;
	}

	public DataSection<CBF> getDataSectionB() {
		return dataSectionB;
	}

	// 获取当前日期
	private static int getCurDay() {
		return Calendar.getInstance().get(Calendar.DAY_OF_MONTH);
	}

}

class CBF {
}

看上面的accessDataSection方法时头脑中要时刻想象有多个线程同时在调用它,并且它们的时序也是无法确定的,以这种思维才能更好地理解上面这段代码中几块看起来略古怪的代码。

上面判断获得的masterSection的创建日期不等于当前日期时,就直接创建了新的DataSection对象并将slaveSection指向它。其实在else分支里还可以这么做:

  • 继续判断masterSection是否还有线程在使用,如果没有那么新建一个DataSection对象并直接让masterSection指向这个对象,这样不用改变主从分区

  • 如果还有线程在使用,那么接下来的逻辑和else分支内的逻辑一样

本文完!转载请注明出处 http://my.oschina.net/feichexia/blog/213601,谢谢!

展开阅读全文
加载中
点击加入讨论🔥(24) 发布并加入讨论🔥
打赏
24 评论
6 收藏
0
分享
返回顶部
顶部