You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@stormcrawler.apache.org by "rzo1 (via GitHub)" <gi...@apache.org> on 2026/08/29 11:28:11 UTC
[I] CommaSeparatedToMultivaluedMetadata appends one token at a time, which is quadratic [stormcrawler]
rzo1 opened a new issue, #2107:
URL: https://github.com/apache/stormcrawler/issues/2107
## 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`:
```java
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`.
```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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@stormcrawler.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] CommaSeparatedToMultivaluedMetadata appends one token at a time, which is quadratic [stormcrawler]
Posted by "jnioche (via GitHub)" <gi...@apache.org>.
jnioche closed issue #2107: CommaSeparatedToMultivaluedMetadata appends one token at a time, which is quadratic
URL: https://github.com/apache/stormcrawler/issues/2107
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@stormcrawler.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] CommaSeparatedToMultivaluedMetadata appends one token at a time, which is quadratic [stormcrawler]
Posted by "abhinav-phi (via GitHub)" <gi...@apache.org>.
abhinav-phi commented on issue #2107:
URL: https://github.com/apache/stormcrawler/issues/2107#issuecomment-5462626830
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
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@stormcrawler.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org