CommaSeparatedToMultivaluedMetadata appends one token at a time, which is quadratic

[rzo1]

What happens

Metadata.addValue allocates a new array of size n+1 and copies the existing n values on every call. CommaSeparatedToMultivaluedMetadata.filter removes the key, splits the value on commas and then calls addValue once per token, so splitting n tokens costs n^2/2 element copies and the same order of transient allocation. The key was just removed, so the whole set could be stored with one setValues call. Metadata.addValues has the same shape: when the key already exists it loops over addValue.

Where

core/src/main/java/org/apache/stormcrawler/parse/filter/CommaSeparatedToMultivaluedMetadata.java:61:

            m.remove(key);
            String[] tokens = val.split(" *, *");
            for (String t : tokens) {
                m.addValue(key, t);

core/src/main/java/org/apache/stormcrawler/Metadata.java:188 is the copy-on-append write path. Related config: http.content.limit, which is -1 in crawler-default.yaml:125 and 65536 in the archetype's crawler-conf.yaml:78.

Why it matters

The archetype wires this onto page content by default: jsoupfilters.json maps parse.keywords to //META[@name="keywords"]/@content, and parsefilters.json runs this filter on parse.keywords. So the token list comes from the crawled page. At the archetype's 65536 byte content limit the filter takes over a hundred milliseconds per page on a comma-heavy value (the test below prints the figure), which is well inside Storm's default 30 second tuple timeout but is still a large multiple of normal parse cost, paid again on every replay. Because the cost is quadratic in the number of tokens, raising http.content.limit, which is routine, multiplies it by the square of the increase. The library default of -1 has no bound at all.

Reproduction

Save as core/src/test/java/org/apache/stormcrawler/parse/filter/CommaSeparatedToMultivaluedMetadataTest.java.

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to you under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.stormcrawler.parse.filter;

import com.fasterxml.jackson.databind.JsonNode;
import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.Map;
import org.apache.stormcrawler.Metadata;
import org.apache.stormcrawler.parse.ParseResult;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class CommaSeparatedToMultivaluedMetadataTest {

    /** Counts how often the copy-on-append write path is used. */
    private static class CountingMetadata extends Metadata {
        int addValueCalls = 0;

        @Override
        public void addValue(String key, String value) {
            addValueCalls++;
            super.addValue(key, value);
        }
    }

    private static CommaSeparatedToMultivaluedMetadata newFilter() throws Exception {
        ObjectMapper mapper = new ObjectMapper();
        JsonNode params = mapper.readTree("{\"keys\": [\"parse.keywords\"]}");
        CommaSeparatedToMultivaluedMetadata filter = new CommaSeparatedToMultivaluedMetadata();
        filter.configure(Map.of(), params);
        return filter;
    }

    private static String commaList(int tokens) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tokens; i++) {
            if (i > 0) {
                sb.append(',');
            }
            sb.append('a');
        }
        return sb.toString();
    }

    @Test
    void splittingUsesABulkAppend() throws Exception {
        final String url = "https://example.com/";
        CountingMetadata md = new CountingMetadata();
        md.setValue("parse.keywords", commaList(1000));

        ParseResult parse = new ParseResult();
        parse.set(url, md);

        newFilter().filter(url, new byte[0], null, parse);

        Assertions.assertEquals(1000, md.getValues("parse.keywords").length);
        Assertions.assertTrue(
                md.addValueCalls <= 1,
                "the filter appended one token at a time: "
                        + md.addValueCalls
                        + " calls to Metadata.addValue, each copying the whole array");
    }

    @Test
    void timeAtArchetypeContentLimit() throws Exception {
        final String url = "https://example.com/";
        // 65536 chars, the http.content.limit used by the archetype configuration
        String value = commaList(32768);
        Assertions.assertEquals(65535, value.length());

        Metadata md = new Metadata();
        md.setValue("parse.keywords", value);
        ParseResult parse = new ParseResult();
        parse.set(url, md);

        long start = System.nanoTime();
        newFilter().filter(url, new byte[0], null, parse);
        long msec = (System.nanoTime() - start) / 1_000_000;

        System.out.println("32768 tokens took " + msec + " ms");
        Assertions.assertEquals(32768, md.getValues("parse.keywords").length);
    }
}

Run it:

mvn -pl core test -Dtest=CommaSeparatedToMultivaluedMetadataTest

The first case counts the calls to the copy-on-append path through a Metadata subclass and fails on main. The second case prints the time at the archetype content limit and passes.

[INFO] Running org.apache.stormcrawler.parse.filter.CommaSeparatedToMultivaluedMetadataTest
32768 tokens took 162 ms       # varies by machine
[ERROR] Tests run: 2, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 0.365 s

CommaSeparatedToMultivaluedMetadataTest.splittingUsesABulkAppend -- FAILURE!
org.opentest4j.AssertionFailedError: the filter appended one token at a time: 1000 calls to Metadata.addValue, each copying the whole array ==> expected: <true> but was: <false>

Suggested fix

In CommaSeparatedToMultivaluedMetadata.filter, replace the loop with a single m.setValues(key, tokens). The key is removed on the line above, so the result is identical. Cap the number of tokens taken from one value and log when the cap trims, so that a page cannot decide how much metadata it produces. Separately, give Metadata an append that builds one array and copies once, and use it from addValues(String, String[]) so the pattern cannot come back through another caller.

[abhinav-phi]

Hi! I'd like to work on this.
Plan: I'll fix CommaSeparatedToMultivaluedMetadata so it splits values correctly instead of appending an extra/incorrect entry, and add a regression test with multi-valued metadata.
Could you please assign this to me? Thanks!

/assign
take