Java 8 中的响应式异步搜索

Question

我正在尝试在 Java 中实现“键入时搜索”模式。

设计的目标是不会丢失任何更改，但与此同时，（耗时的）搜索操作应该能够提前中止并尝试更新的模式。

这是我到目前为止的结果（Java 8 伪代码）：

AtomicReference<String> patternRef
AtomicLong modificationCount
ReentrantLock busy;
Consumer<List<ResultType>> resultConsumer;

// This is called in a background thread every time the user presses a key
void search(String pattern) {
    // Update the pattern
    synchronized {
        patternRef.set(pattern)
        modificationCount.inc()
    }

    try {
        if (!busy.tryLock()) {
            // Another search is already running, let it handle the change
            return;
        }

        // Get local copy of the pattern and modCount
        synchronized {
            String patternCopy = patternRef.get();
            long modCount = modificationCount.get()
        }

        while (true) {
            // Try the search. It will return false when modificationCount changes before the search is finished
            boolean success = doSearch(patternCopy, modCount)
            if (success) {
                // Search completed before modCount was changed again
                break
            }

            // Try again with new pattern+modCount
            synchronized {
                patternCopy = patternRef.get();
                modCount = modificationCount.get()
            }
        }
    } finally {
        busy.unlock();
    }
}

boolean doSearch(String pattern, long modCount)

    ... search database ...
    if (modCount != modificationCount.get()) {
        return false;
    }

    ... prepare results ...
    if (modCount != modificationCount.get()) {
        return false;
    }

    resultConsumer.accept(result); // Consumer for the UI code to do something

    return modCount == modificationCount.get();
}

我是不是漏掉了重要的一点？竞争条件或类似情况？

Java8 中有什么东西可以使上面的代码更简单吗？

Answer 1

这段代码的根本问题可以概括为“试图通过多个不同的原子构造来实现原子性”。多个原子构造的组合不是原子的，尝试重新建立原子性会导致代码非常复杂、通常会损坏且效率低下。

在你的例子中，doSearch 的最后一次检查 modCount == modificationCount.get() 在仍然持有锁的情况下发生。在那之后，另一个线程（或多个其他线程）可以更新搜索字符串和 mod 计数，然后找到被占用的锁，因此，得出另一个搜索是运行的结论并会处理。

但是在最后一次 modCount == modificationCount.get() 检查之后那个线程并不关心。调用者只执行 if (success) { break; }，然后是 finally { busy.unlock(); } 和 return。

所以答案是，是的，您有潜在的竞争条件。

因此，与其选择两个原子变量 synchronized 块和一个 ReentrantLock，不如使用一个原子构造，例如单个原子变量：

final AtomicReference<String> patternRef = new AtomicReference<>();
Consumer<List<ResultType>> resultConsumer;

// This is called in a background thread every time the user presses a key
void search(String pattern) {
    if(patternRef.getAndSet(pattern) != null) return;
    // Try the search. doSearch will return false when not completed
    while(!doSearch(pattern) || !patternRef.compareAndSet(pattern, null))
        pattern = patternRef.get();
}

boolean doSearch(String pattern) {
    //... search database ...
    if(pattern != (Object)patternRef.get()) {
        return false;
    }

    //... prepare results ...
    if(pattern != (Object)patternRef.get()) {
        return false;
    }

    resultConsumer.accept(result); // Consumer for the UI code to do something

    return true;
}

这里，null的值表示没有搜索是运行，所以如果后台线程将它设置为非null值并找到旧值是null（在原子操作中），它知道它必须执行实际的搜索。搜索后，它尝试再次将引用设置为 null，使用 compareAndSet 和用于搜索的模式。因此，它只有在没有再次更改的情况下才能成功。否则，它将获取新值并重复。

这两个原子更新已经足以确保一次只有一个搜索操作，同时不会丢失更新的搜索模式。 doSearch 在检测到变化时及早 return 的能力非常好，调用者的循环不需要。

请注意，在此示例中，doSearch 中的检查已简化为引用比较（使用强制转换为 Object 以防止编译器警告），以证明它可以同样便宜作为您原始方法的 int 比较。只要没有设置新的字符串，引用都是一样的。

但是，实际上，您也可以使用字符串比较，即 if(!pattern.equals(patternRef.get())) { return false; } 而不会显着降低性能。 Java 中的字符串比较并不（必然）昂贵。 String 的 equals 的实现首先要做的是引用比较。所以如果字符串没有改变，它会立即return true。否则，它将随后检查长度（与 C 字符串不同，长度是事先已知的）并在不匹配时立即 return false 。因此，在用户键入另一个字符或按退格键的典型情况下，长度会有所不同，比较会立即退出。

Java 8 中的响应式异步搜索

Responsive asynchronous search-as-you-type in Java 8

concurrency

java.util.concurrent

java-8

responsiveness