java 带通配符的黑名单

Question

我有一个 table 在数据库中有 4 个字符串列，每一行代表被阻止的用户或组。

referrer | ip | userAgent | email

按组我的意思是其中一列（任何）可以有通配符（星号），这意味着 "block all of them"

例如这一行

www.google.com | 127.0.0.2 | * | yahoo.com

意味着每个用户请求以 "google.com" 作为引用，“127.0.0.2”作为 IP 和 "yahoo.com" 作为电子邮件，需要在不考虑 UserAgent 的情况下被阻止，因为它有通配符

以下代码在 O(n) 复杂度下工作，这对于小尺寸来说已经足够了 table 但我的 table 包含超过百万行

class BlacklistEntry {

    private String referrer, ip, userAgent, email;
    private static List<BlacklistEntry> cache = new ArrayList<>();

    BlacklistEntry(String referrer, String ip, String userAgent, String email) {
        this.referrer = referrer;
        this.ip = ip;
        this.userAgent = userAgent;
        this.email = email;
    }

    private static boolean isBlacklisted(String ref, String ip, String ue, String email) {
        final String MATCH_ALL = "*";
        return cache.stream()
            .filter(e ->
                (MATCH_ALL.equals(e.getReferrer()) || e.getReferrer().equals(ref)) &&
                (MATCH_ALL.equals(e.getIp()) || e.getIp().equals(ip)) &&
                (MATCH_ALL.equals(e.getUserAgent()) || e.getUserAgent().equals(ue)) &&
                (MATCH_ALL.equals(e.getEmail()) || e.getEmail().equals(email)))
            .findFirst()
            .isPresent();
    }

    public String getReferrer() {
        return referrer;
    }

    public void setReferrer(String referrer) {
        this.referrer = referrer;
    }

    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public String getUserAgent() {
        return userAgent;
    }

    public void setUserAgent(String userAgent) {
        this.userAgent = userAgent;
    }

    public String getEmail() {
        return email;
    }

    public void setEmail(String email) {
        this.email = email;
    }

    public static void main(String[] args) {

        cache.add(new BlacklistEntry("google.com", "127.0.0.2", "Mozilla", "yahoo.com"));
        cache.add(new BlacklistEntry("r1.com", "127.0.0.3", "Mozilla", "*"));
        cache.add(new BlacklistEntry("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));

        System.out.println(isBlacklisted("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));
        System.out.println(isBlacklisted("r1.com", "127.0.0.3", "Mozilla", "sould be true"));
        System.out.println(isBlacklisted("*", "127.0.0.3", "*", "*"));
    }
}

有没有比 O(n) 更好的东西？我应该考虑使用 Lucene 吗？

Answer 1

我推荐你使用RDB或者Lucene。

不过，我认为使用二叉树可以降低成本。这保证了 log(n) 时间成本。

程序

准备 BlacklistEntry class 实施 Comparator (Java Platform SE 8 )
覆盖方法 equals、hashCode 并为 Comparator

compare

声明 TreeSet<BlacklistEntry> 并附加您的数据
执行BlacklistEntry#contains(object)，这将return它是否被列入黑名单。

TreeSet (Java Platform SE 7 )

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

示例

黑名单条目

package org.Whosebug.btree;

import java.util.Comparator;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class BlacklistEntry implements Comparator<BlacklistEntry> {

    private String referrer, ip, userAgent, email;

    @Override
    public boolean equals(Object obj) {

        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof BlacklistEntry))
            return false;

        BlacklistEntry other = (BlacklistEntry) obj;

        // You need to deal with "*" for all elements
        // There should be another implementations to solve troublesome
        // boiler-plate codes, for example to use reflection or commons.lang.
        if (email == null) {
            if (other.email != null) {
                return false;
            }
        } else if (!email.equals(other.email) && !(email.equals("*") || other.email.equals("*")) ) {
            return false;
        }

        if (ip == null) {
            if (other.ip != null) {
                return false;
            }
        } else if (!ip.equals(other.ip) && !(ip.equals("*") || other.ip.equals("*")) ) {
            return false;
        }

        if (referrer == null) {
            if (other.referrer != null) {
                return false;
            }
        } else if (!referrer.equals(other.referrer) && !(referrer.equals("*") || other.referrer.equals("*")) ) {
            return false;
        }

        if (userAgent == null) {
            if (other.userAgent != null) {
                return false;
            }
        } else if (!userAgent.equals(other.userAgent) && !(userAgent.equals("*") || other.userAgent.equals("*")) ) {
            return false;
        }

        return true;
    }

    // I just generated #hashCode with eclipse
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((email == null) ? 0 : email.hashCode());
        result = prime * result + ((ip == null) ? 0 : ip.hashCode());
        result = prime * result + ((referrer == null) ? 0 : referrer.hashCode());
        result = prime * result + ((userAgent == null) ? 0 : userAgent.hashCode());
        return result;
    }

    // if left obj & right obj is equals == true
    //   --> "*" or just completely matching
    // else
    //   --> detect which is larger than the another one
    //   (this #compare method is used by binary-tree)
    public int compare(BlacklistEntry o1, BlacklistEntry o2) {
        if (o1.equals(o2)) {
            return 0;
        } else {
            return (o1.hashCode() < o2.hashCode()) ? -1 : 1;
        }
    }

}

主要

package org.Whosebug.btree;

import java.util.TreeSet;

public class Main {

    static TreeSet<BlacklistEntry> cache = new TreeSet<BlacklistEntry>(new BlacklistEntry());

    public static boolean isBlacklisted(String ref, String ip, String ue, String email) {
        return isBlacklisted(new BlacklistEntry(ref, ip, ue, email));
    }
    public static boolean isBlacklisted(BlacklistEntry e) {
        return cache.contains(e);
    }
    public static void main(String[] args) {
        cache.add(new BlacklistEntry("www.google.com", "127.0.0.2", "*", "yahoo.com") );

        System.out.println(isBlacklisted("www.google.com", "127.0.0.1", "IE", "yahoo.com"));
        System.out.println(isBlacklisted("www.google.com", "127.0.0.2", "Chrome", "yahoo.com"));
        System.out.println(isBlacklisted("www.google.com", "127.0.0.3", "Edge", "yahoo.com"));
        System.out.println(isBlacklisted("www.google.com", "127.0.0.4", "Mozilla", "yahoo.com"));
        System.out.println(isBlacklisted("www.google.com", "127.0.0.5", "Ruby", "yahoo.com"));
    }

}

输出

false
true
false
false
false

Answer 2

假设对于每一行，四列中只有一列可以有通配符，一种简单的方法是有五个散列集：一组匹配所有列，每个通配符列一组匹配三个非- 通配符列。然后，检查黑名单包括在五个集合中的每个集合中查找条目，这是渐近常数时间（O(1)）。

概念验证代码（当然可以改进）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;

public class Blacklist {

    private static class BlacklistEntry {
        private String[] fields;

        private BlacklistEntry(String... fields) {
            this.fields = fields;
        }

        @Override
        public int hashCode() {
            return Objects.hash(fields);
        }

        @Override
        public boolean equals(final Object obj) {
            return obj instanceof BlacklistEntry && Arrays.equals(fields, ((BlacklistEntry)obj).fields);
        }
    }

    private static List<Set<BlacklistEntry>> wildcardSets = new ArrayList<>();

    private static final int FIELD_COUNT = 4;

    static {
        for (int i = 0; i < FIELD_COUNT; i++) {
            wildcardSets.add(new HashSet<>());
        }
    }
    private static Set<BlacklistEntry> fullMatchSet = new HashSet<>();

    private static boolean isBlacklisted(String... fields) {
        if (fullMatchSet.contains(new BlacklistEntry(fields))) {
            return true;
        }
        for (int i = 0; i < FIELD_COUNT; i++) {
            if (wildcardSets.get(i).contains(new BlacklistEntry(removeField(fields, i)))) {
                return true;
            }
        }
        return false;
    }

    private static void addEntry(BlacklistEntry entry) {
        if (entry.fields.length != FIELD_COUNT) {
            throw new RuntimeException("Invalid entry, should contain four fields");
        }
        for (int i = 0; i < FIELD_COUNT; i++) {
            if ("*".equals(entry.fields[i])) {
                // Make a copy of the fields list without the wildcard, and add it to the correct set.
                String[] fields = removeField(entry.fields, i);
                wildcardSets.get(i).add(new BlacklistEntry(fields));
                return;
            }
        }
        // No wildcards in field list.
        fullMatchSet.add(entry);
    }

    private static String[] removeField(final String[] fields, final int index) {
        String[] newFields = new String[fields.length - 1];
        for (int i = 0; i < index; i++) {
            newFields[i] = fields[i];
        }
        for (int i = index + 1; i < FIELD_COUNT; i++) {
            newFields[i - 1] = fields[i];
        }
        return newFields;
    }


    public static void main(String[] args) {

        addEntry(new BlacklistEntry("r1.com", "127.0.0.1", "UA1", "*"));
        addEntry(new BlacklistEntry("r2.com", "127.0.0.2", "*", "e1.com"));
        addEntry(new BlacklistEntry("r3.com", "*", "UA2", "e2.com"));
        addEntry(new BlacklistEntry("*", "127.0.0.3", "UA3", "e3.com"));
        addEntry(new BlacklistEntry("r4.com", "127.0.0.4", "UA4", "e4.com"));

        // All these should return true
        System.out.println(isBlacklisted("r1.com", "127.0.0.1", "UA1", "wildcard"));
        System.out.println(isBlacklisted("r2.com", "127.0.0.2", "wildcard", "e1.com"));
        System.out.println(isBlacklisted("r3.com", "wildcard", "UA2", "e2.com"));
        System.out.println(isBlacklisted("wildcard", "127.0.0.3", "UA3", "e3.com"));
        System.out.println(isBlacklisted("r4.com", "127.0.0.4", "UA4", "e4.com"));

        // All these should return false
        System.out.println(isBlacklisted("r1.com", "127.0.0.1", "no match", "wildcard"));
        System.out.println(isBlacklisted("no match", "127.0.0.2", "wildcard", "e1.com"));
        System.out.println(isBlacklisted("r3.com", "wildcard", "no match", "e2.com"));
        System.out.println(isBlacklisted("wildcard", "127.0.0.3", "UA3", "no match"));
        System.out.println(isBlacklisted("r5.com", "127.0.0.5", "UA4", "e5.com"));
    }

}

Answer 3

感谢您的回答

我的第一个尝试是获取所有排列（使用番石榴感谢我的队友让它变得干净清晰），这使它成为 numberParameters^2 并检查缓存中的集合是否包含其中任何一个

private static boolean check(Set cache, String ref, String ip, String ue, String mail) {
    return Sets.powerSet(ImmutableSet.of(0, 1, 2, 3)).stream().map(set -> {
        BlacklistKey key = new BlacklistKey("*", "*", "*", "*");
        for (Integer idx : set) {
            switch (idx) {
                case 0:
                    key.setReferrer(ref);
                    break;
                case 1:
                    key.setIp(ip);
                    break;
                case 2:
                    key.setUserAgent(ue);
                    break;
                case 3:
                    key.setEmail(mail);
            }
        }
        return key;
    }).anyMatch(keys::contains);
}

最终使用 Lucene

import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.StringField;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.BooleanClause;
import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.store.RAMDirectory;

import java.io.IOException;

class Blacklist {

    private static final String MATCH_ALL = "*";
    private static IndexSearcher cache;

    private enum Fields {
        REFERRER, IP, USER_AGENT, EMAIL
    }

    private static Document getDocument(String referrer, String ip, String userAgent, String email) {
        Document doc = new Document();
        doc.add(getStringField(referrer, Fields.REFERRER.name()));
        doc.add(getStringField(ip, Fields.IP.name()));
        doc.add(getStringField(userAgent, Fields.USER_AGENT.name()));
        doc.add(getStringField(email, Fields.EMAIL.name()));
        return doc;
    }

    private static StringField getStringField(String val, String field) {
        return new StringField(field, val, Field.Store.NO);
    }

    private static BooleanQuery createQuery(String referrer, String ip, String userAgent, String email) {
        return new BooleanQuery.Builder()
                .add(createBooleanQuery(Fields.REFERRER.name(), referrer), BooleanClause.Occur.FILTER)
                .add(createBooleanQuery(Fields.IP.name(), ip), BooleanClause.Occur.FILTER)
                .add(createBooleanQuery(Fields.USER_AGENT.name(), userAgent), BooleanClause.Occur.FILTER)
                .add(createBooleanQuery(Fields.EMAIL.name(), email), BooleanClause.Occur.FILTER)
                .build();
    }

    private static BooleanQuery createBooleanQuery(String key, String value) {
        return new BooleanQuery.Builder()
                .add(new TermQuery(new Term(key, value)), BooleanClause.Occur.SHOULD)
                .add(new TermQuery(new Term(key, MATCH_ALL)), BooleanClause.Occur.SHOULD)
                .build();
    }

    private static boolean isBlacklisted(String ref, String ip, String ue, String email) throws IOException {
        BooleanQuery query = createQuery(ref, ip, ue, email);
        return cache.search(query, 1).totalHits > 0;
    }


    public static void main(String[] args) throws IOException {
        RAMDirectory directory = new RAMDirectory();
        IndexWriter writer = new IndexWriter(directory, new IndexWriterConfig(new StandardAnalyzer()));
        writer.addDocument(getDocument("ref1", "127.0.0.ip1", "Mozilla UserAgent1", "email.com"));
        writer.addDocument(getDocument("ref2", "127.0.0.ip2", "Mozilla UserAgent2", "*"));
        writer.close();
        DirectoryReader reader = DirectoryReader.open(directory);
        cache = new IndexSearcher(reader);

        System.out.println(isBlacklisted("ref1", "127.0.0.ip1", "Mozilla UserAgent1", "email.com"));
        System.out.println(isBlacklisted("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));
        System.out.println(isBlacklisted("ref2", "127.0.0.ip2", "Mozilla UserAgent2", "this is ignored"));
        System.out.println(isBlacklisted("*", "127.0.0.ip2", "Mozilla UserAgent2", "*"));
    }
}

java 带通配符的黑名单

java blacklist with wildcard

java

lucene

algorithm

equals

hashset