带有通配符的java黑名单

Question

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

referrer | ip | userAgent | email

按组我的意思是其中一列(任何)可以有通配符(星号)，这意味着“阻止所有这些”

例如这一行

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

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

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

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

感谢解答

我的第一个尝试是获取所有排列(使用 Guava 感谢我的队友让它变得干净清晰)，这使它成为 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", "*"));
    }
}