规则引擎的设计

规则引擎

我要做一个需求是要实现一个规则引擎,目的呢就是要进行一系列规则的判断,比如是否有重复,是否超过频率,是否达到最早开始时间和最晚结束时间,不符合条件的都被过滤掉,过滤的规模在2000w,尽量在2小时内完成。

初步想法

最开始的想法就是单次过滤要非常的快。由于一个要进行这么多的判断,是否重复,是否超过频率。这种类型的判断,实际上是要进行历史的对比,所以这些信息只能存在内存里,才能保证单个判断是比较快的。如果单个判断是2ms,那么多个的判断就会在10ms内就有可能满足条件。对于历史的消息的存储想好了就用redis来存了。

引擎的设计

由于判断时,如是否重复,需要加锁,因为有多线程竞态条件,所以必须加锁,如果是直接锁判断的的方法的话,并发发送时估计性能不够。当时就想起来HashMap内部的实现,使用KEY的HASH把竞态的条件分布到不同的区去,在各自的区上加锁。把这个模块做成一个服务,供外部的来调用。但实现难度有点大,这个引擎得自己写啊。

灵机一动

后面突然灵机一动,可以用Redis的乐观锁来实现刚才说的竞态条件啊。使用它的乐观锁。流程大概如下:

watch key
    exists?
    multi
    if(exist)
        //这个时间有可能出现竞态,键被删除,他又不算重复了。
        return 重复
     else
         添加条目
         return 不重复
     exec

这样就既用Redis为存了数据,又利用它的乐观锁的特性实现了业务。突然发现这里应该深补下Redis乐观锁的性能哈,这样按每个key加一个锁,粒度很小了。

进一步加强

刚才用Redis虽然实现了这个,但日志数据2000W需要存来对比量还是蛮大,未来规则复杂了还有扩大的可能,且单个Redis还有单点故障,存在一个Redis里面还不是很安全,后面就想做个Redis集群吧。但是常用的集群插件如Codis,twenty什么的不支持高级命令如事务这些。但我这里的规则在业务上只会针对一个key的操作,所以这样的限制对我其实无意义。后面就自己用jedis支持了通过Key的hash实现的集群

关于hash算法

关于hash算法经管Redis服务器的同学的提点,说可以用一个一致性hash算法,又简单看了下jedis的分片实现源码,本来想自己改一个,后面在网上找到了一个类似的实现,将hash算法改为了jedis的算法。

实际上线情况

上线前压测单次判断是2ms,后面在预生产环境压测时是10ms,当时奇了怪了,找了半天结果发现原来是redis在生产环境配置过大,全在初始化(使用houseMD跟踪,全在init),所以很慢。当时大概的测试逻辑是200个线程同时对10000数进行判断重复。相当于每个数会有200个线程进行竞争的重复判断。测试环境大概7ms左右,生产环境大概2ms单次。后面竞态条件去掉,在生产环境单个判断也差不多要2ms,难道已是极限了?

小插曲

由于一般进行批量推送,单次判断约有200个消息,每个消息进行约5次规则判断,按2ms算,用时要2秒。当时要每次用户存的时候就判断,那么每次用户访问要2s.完全不能接受,后面就只有把这个流程放到其它地方了。可以用多线程批量调用的地方。

JAVA的List使用Remove时的问题

近日在项目中遇到了一个诡异的问题,参考代码如下:

[java]
public class ListTest {
public static List listFactory() {
return new ArrayList(Arrays.asList("a", "b", "c", "d"));
}

public static void main(String[] args) {
List testList = null;
String t;

// 尝试移除集合中的间隔元素a、c
testList = listFactory();
for (int i = 0; i < testList.size(); i++) {
t = testList.get(i);
if (t.equals("a") || t.equals("c")) {
testList.remove(t);
}
}
System.out.println("移除间隔元素a、c后结果:" + testList);

// 尝试移除集合中的相邻元素a、b
testList = listFactory();
for (int i = 0; i < testList.size(); i++) {
t = testList.get(i);
if (t.equals("a") || t.equals("b")) {
testList.remove(t);
}
}
System.out.println("移除相邻元素a、b后结果:" + testList);
}
}
[/java]

而运行后的结果如下:

[java]
移除间隔元素a、c后结果:[b, d]
移除相邻元素a、b后结果:[b, c, d]
[/java]

从运行的结果来看,在操作List时使用remove方法在移除间隔元素成功,而移除相邻元素时会导致漏删除。

失败原因

通过查看remove()的源码后发现,List内实现remove是通过如下方法实现的。

[java]
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}

private void fastRemove(int index) {
modCount++;
int numMoved = size – index – 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[–size] = null; // Let gc do its work
}
[/java]

fastRemove方法是实现的关键,从实现上来看,他是将要删除的元素后的元素逐一向前挪一位来实现的。我们在循环删除时若外层当前的index为1,将之删除,后续元素往前挪,然后外层的index加1继续循环,这样会导致被删除元素的后面紧邻元素不会被遍历到,从而导致漏删。

解决办法

  1. 使用逆序删除的办法[java]
    public class ListTest {
    public static List listFactory() {
    return new ArrayList(Arrays.asList("a", "b", "c", "d"));
    }

    public static void main(String[] args) {
    List testList = null;
    String t;

    // 逆序移除相邻元素a、b后
    testList = listFactory();
    int size = testList.size();
    for (int i = size – 1; i >= 0; i–) {
    t = testList.get(i);
    if (t.equals("a") || t.equals("b")) {
    testList.remove(t);
    }
    }
    System.out.println("逆序移除相邻元素a、b后结果:" + testList);
    }
    }
    [/java]

  2. 使用iterator删除[java]
    public class ListTest {
    public static List<String> listFactory() {
    return new ArrayList<String>(Arrays.asList("a", "b", "c", "d"));
    }

    public static void main(String[] args) {
    List<String> testList = null;
    String t;

    // 使用iterator移除相邻元素a、b后
    testList = listFactory();
    Iterator<String> iter = testList.iterator();
    while (iter.hasNext()) {
    t = iter.next();
    if (t.equals("a") || t.equals("b")) {
    iter.remove();
    }
    }
    System.out.println("使用iterator移除相邻元素a、b后结果:" + testList);
    }
    }
    [/java]

java.util.ConcurrentModificationException原因及解决办法

这个异常一般在我们遍历删除集合元素时出现。写了下面这个代码来展示这个异常。

[java]
import java.util.ArrayList;
import java.util.List;

public class ExeptionTest {
public static void main(String[] args) {
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");

for (String s : list) {
if ("c".equals(s)) {
list.remove("c");
}
}
}
}
[/java]

控制台报错如下:

[java]
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:819)
at java.util.ArrayList$Itr.next(ArrayList.java:791)
at ExeptionTest.main(ExeptionTest.java:14)
[/java]

出现异常原因分析:

for循环执行时内部实际是调用的List实现了Iterator接口的方法,换句话说所有实现了Iterator接口的都可以使用for。追查JDK源码可以看到异常报错正是来自ArrayList内部实现的迭代器类Itr的checkForComodification()方法。

[java]
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
[/java]

其实这个方法只做了一件事就是检查迭代器当前的大小是否和原始大小一样,如果不一样。则认为原始的集合已经在其它地方被修改,故而出现此异常。

解决方法

既然报错的原因清楚了,那么我们只要不混用两种遍历方法就没有问题了。

[java]
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ExeptionTest {
public static void main(String[] args) {
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");

// 法一
for (int i = 0; i < list.size(); i++) {
if (i == 2) {
list.remove(i);
}
}
System.out.println(list);

// 法二
Iterator iter = list.iterator();
while (iter.hasNext()) {
if ("d".equals(iter.next())) {
iter.remove();
}
}
System.out.println(list);
}
}

[/java]

ConcurrentModificationException进阶

某些时候我们可能会遇到遍历时还要再遍历删除的情况。这时该怎么解决呢?对于这样的情况我们有二种解决办法

  1. 将要删除的对象收集到另一个集合中一起删除[java]import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;

    public class ExeptionTest {
    public static void main(String[] args) {
    List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");

    Iterator iter = list.iterator();
    List toBeRemove = new ArrayList();
    String t = null;
    while (iter.hasNext()) {
    t = iter.next();
    if (t.equals("c")) {
    toBeRemove.add(t);
    }
    }
    //使用removeAll一起删除
    list.removeAll(toBeRemove);
    System.out.println(list);

    }
    }[/java]

  2. 第一轮遍历时使用复制对象。[java]import java.util.ArrayList;
    import java.util.List;

    public class ExeptionTest {
    public static void main(String[] args) {
    List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");
    // 遍历复制集合,此时实际使用的是iterator.
    for (String s : new ArrayList(list)) {
    if (s.equals("c"))
    //移除时使用的是非iterator的方式
    list.remove(s);
    }
    System.out.println(list);
    }
    }
    [/java]

本次的文章就写到这里,如有疏漏,欢迎指正。