diff options
56 files changed, 840 insertions, 273 deletions
diff --git a/.gitignore b/.gitignore index c1d500c3c4f..870db7d4a66 100644 --- a/.gitignore +++ b/.gitignore @@ -40,6 +40,7 @@ Testing /.ninja_log /build.ninja /rules.ninja +*_benchmark_app *_test_app /cmake-build-debug/ /mvnw diff --git a/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedFields.java b/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedFields.java index 053a5ac777b..7659a1e6562 100644 --- a/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedFields.java +++ b/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedFields.java @@ -159,7 +159,7 @@ public class ConvertParsedFields { var dataType = field.getDataType(); var otherType = summaryField.getType(); if (otherType != null && summaryField.getHasExplicitType()) { - schema.getDeployLogger().log(Level.FINE, () -> "For schema '" + schema.getName() + + schema.getDeployLogger().log(Level.WARNING, () -> "For schema '" + schema.getName() + "', field '" + field.getName() + "', summary '" + summaryField.name() + "': Specifying the type is deprecated, ignored and will be an error in Vespa 9." + diff --git a/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedSchemas.java b/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedSchemas.java index ee15b95b198..3c87044850f 100644 --- a/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedSchemas.java +++ b/config-model/src/main/java/com/yahoo/schema/parser/ConvertParsedSchemas.java @@ -233,7 +233,7 @@ public class ConvertParsedSchemas { var parsedType = parsedField.getType(); if (parsedType != null) { var log = schema.getDeployLogger(); - log.log(Level.FINE, () -> "For schema '" + schema.getName() + + log.log(Level.WARNING, () -> "For schema '" + schema.getName() + "', document-summary '" + parsed.name() + "', summary field '" + parsedField.name() + "': Specifying the type is deprecated, ignored and will be an error in Vespa 9." + diff --git a/config-model/src/main/java/com/yahoo/schema/processing/AddExtraFieldsToDocument.java b/config-model/src/main/java/com/yahoo/schema/processing/AddExtraFieldsToDocument.java index 67297245ff1..e736f289003 100644 --- a/config-model/src/main/java/com/yahoo/schema/processing/AddExtraFieldsToDocument.java +++ b/config-model/src/main/java/com/yahoo/schema/processing/AddExtraFieldsToDocument.java @@ -41,10 +41,8 @@ public class AddExtraFieldsToDocument extends Processor { for (var summaryField : docsum.getSummaryFields().values()) { var transform = summaryField.getTransform(); if (transform.isDynamic() && DynamicSummaryTransformUtils.summaryFieldIsRequiredInDocumentType(summaryField) || - transform == SummaryTransform.NONE || - transform == SummaryTransform.DOCUMENT_ID) + transform == SummaryTransform.NONE) { - // TODO: Adding the 'documentid' field should no longer be needed when the docsum framework in the backend has been simplified and the transform is always used. addSummaryField(schema, document, summaryField, validate); } else { // skip: generated from attribute or similar, diff --git a/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryCollector.java b/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryCollector.java index 73275a36804..fcd587622da 100644 --- a/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryCollector.java +++ b/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryCollector.java @@ -3,7 +3,9 @@ package com.yahoo.vespa.model.admin.otel; import com.yahoo.cloud.config.OpenTelemetryConfig; import com.yahoo.config.model.ApplicationConfigProducerRoot; +import com.yahoo.config.model.deploy.DeployState; import com.yahoo.config.model.producer.TreeConfigProducer; +import com.yahoo.config.provision.Zone; import com.yahoo.vespa.model.AbstractService; import com.yahoo.vespa.model.PortAllocBridge; @@ -14,8 +16,18 @@ import java.util.Optional; public class OpenTelemetryCollector extends AbstractService implements OpenTelemetryConfig.Producer { + private final Zone zone; + public OpenTelemetryCollector(TreeConfigProducer<?> parent) { super(parent, "otelcol"); + this.zone = null; + setProp("clustertype", "admin"); + setProp("clustername", "admin"); + } + + public OpenTelemetryCollector(TreeConfigProducer<?> parent, DeployState deployState) { + super(parent, "otelcol"); + this.zone = deployState.zone(); setProp("clustertype", "admin"); setProp("clustername", "admin"); } @@ -38,7 +50,7 @@ public class OpenTelemetryCollector extends AbstractService implements OpenTelem @Override public void getConfig(OpenTelemetryConfig.Builder builder) { - var generator = new OpenTelemetryConfigGenerator(); + var generator = new OpenTelemetryConfigGenerator(zone); AnyConfigProducer pp = this; AnyConfigProducer p = pp.getParent(); while (p != null && p != pp) { diff --git a/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGenerator.java b/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGenerator.java index ebf692fd6ff..36eab6a04b3 100644 --- a/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGenerator.java +++ b/config-model/src/main/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGenerator.java @@ -1,58 +1,206 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vespa.model.admin.otel; +import com.fasterxml.jackson.core.JsonEncoding; +import com.fasterxml.jackson.core.JsonFactory; +import com.fasterxml.jackson.core.JsonGenerator; import com.yahoo.config.model.ApplicationConfigProducerRoot.StatePortInfo; +import com.yahoo.config.provision.Zone; + +import java.io.ByteArrayOutputStream; +import java.nio.charset.StandardCharsets; +import java.util.ArrayList; import java.util.List; +import static com.yahoo.vespa.defaults.Defaults.getDefaults; + /** * @author olaa */ public class OpenTelemetryConfigGenerator { - // For now - just create dummy config + private final boolean useTls; + private final String ca_file; + private final String cert_file; + private final String key_file; + private List<StatePortInfo> statePorts = new ArrayList<>(); + + OpenTelemetryConfigGenerator(Zone zone) { + boolean isCd = true; + boolean isPublic = true; + if (zone != null) { + isCd = zone.system().isCd(); + isPublic = zone.system().isPublic(); + this.useTls = true; + } else { + // for manual testing + this.useTls = false; + } + if (isCd) { + if (isPublic) { + this.ca_file = "/opt/vespa/var/vespa/trust-store.pem"; + this.cert_file = "/var/lib/sia/certs/vespa.external.cd.tenant.cert.pem"; + this.key_file = "/var/lib/sia/keys/vespa.external.cd.tenant.key.pem"; + } else { + this.ca_file = "/opt/yahoo/share/ssl/certs/athenz_certificate_bundle.pem"; + this.cert_file = "/var/lib/sia/certs/vespa.vespa.cd.tenant.cert.pem"; + this.key_file = "/var/lib/sia/keys/vespa.vespa.cd.tenant.key.pem"; + } + } else { + if (isPublic) { + this.ca_file = "/opt/vespa/var/vespa/trust-store.pem"; + this.cert_file = "/var/lib/sia/certs/vespa.external.tenant.cert.pem"; + this.key_file = "/var/lib/sia/keys/vespa.external.tenant.key.pem"; + } else { + this.ca_file = "/opt/yahoo/share/ssl/certs/athenz_certificate_bundle.pem"; + this.cert_file = "/var/lib/sia/certs/vespa.vespa.tenant.cert.pem"; + this.key_file = "/var/lib/sia/keys/vespa.vespa.tenant.key.pem"; + } + } + } + + String receiverName(int index) { + return "prometheus_simple/s" + index; + } + + private void addReceivers(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("receivers"); + g.writeStartObject(); + int counter = 0; + for (var statePort : statePorts) { + addReceiver(g, ++counter, statePort); + } + g.writeEndObject(); // receivers + } + private void addReceiver(JsonGenerator g, int index, StatePortInfo statePort) throws java.io.IOException { + g.writeFieldName(receiverName(index)); + g.writeStartObject(); + g.writeStringField("collection_interval", "60s"); + g.writeStringField("endpoint", statePort.hostName() + ":" + statePort.portNumber()); + addUrlInfo(g); + if (useTls) addTls(g); + { + g.writeFieldName("labels"); + g.writeStartObject(); + g.writeStringField("service_type", statePort.serviceType()); + g.writeEndObject(); + } + g.writeEndObject(); + } + private void addTls(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("tls"); + g.writeStartObject(); + g.writeStringField("ca_file", ca_file); + g.writeStringField("cert_file", cert_file); + g.writeBooleanField("insecure_skip_verify", true); + g.writeStringField("key_file", key_file); + g.writeEndObject(); // tls + } + private void addUrlInfo(JsonGenerator g) throws java.io.IOException { + g.writeStringField("metrics_path", "/state/v1/metrics"); + g.writeFieldName("params"); + g.writeStartObject(); + g.writeStringField("format", "prometheus"); + g.writeEndObject(); + } + private void addExporters(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("exporters"); + g.writeStartObject(); + addFileExporter(g); + g.writeEndObject(); // exporters + } + private void addFileExporter(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("file"); + g.writeStartObject(); + g.writeStringField("path", getDefaults().underVespaHome("logs/vespa/otel-test.json")); + { + g.writeFieldName("rotation"); + g.writeStartObject(); + g.writeNumberField("max_megabytes", 10); + g.writeNumberField("max_days", 3); + g.writeNumberField("max_backups", 1); + g.writeEndObject(); // rotation + } + g.writeEndObject(); // file + } + private void addServiceBlock(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("service"); + g.writeStartObject(); + { + g.writeFieldName("telemetry"); + g.writeStartObject(); + { + g.writeFieldName("logs"); + g.writeStartObject(); + g.writeStringField("level", "debug"); + g.writeEndObject(); + } + g.writeEndObject(); + } + { + g.writeFieldName("pipelines"); + g.writeStartObject(); + addMetricsPipelines(g); + g.writeEndObject(); // pipelines + } + g.writeEndObject(); // service + } + private void addMetricsPipelines(JsonGenerator g) throws java.io.IOException { + g.writeFieldName("metrics"); + g.writeStartObject(); + { + g.writeFieldName("receivers"); + g.writeStartArray(); + int counter = 0; + for (var statePort : statePorts) { + g.writeString(receiverName(++counter)); + } + g.writeEndArray(); + } + g.writeFieldName("processors"); + g.writeStartArray(); + g.writeEndArray(); + { + g.writeFieldName("exporters"); + g.writeStartArray(); + g.writeString("file"); + g.writeEndArray(); + } + g.writeEndObject(); // metrics + } + + // For now - mostly dummy config /* TODO: Create config - 1. polling /state/v1 handler of every service + 1. polling /state/v1 handler of every service (mostly done) 2. Processing with mapping/filtering from metric sets 3. Exporter to correct endpoint (alternatively amended) */ public String generate() { - - return """ - receivers: - prometheus_simple: - collection_interval: 60s - endpoint: 'localhost:4080' - metrics_path: '/state/v1/metrics' - params: - format: 'prometheus' - tls: - ca_file: '/opt/vespa/var/vespa/trust-store.pem' - cert_file: '/var/lib/sia/certs/vespa.external.cd.tenant.cert.pem' - insecure_skip_verify: true - key_file: '/var/lib/sia/keys/vespa.external.cd.tenant.key.pem' - exporters: - file: - path: /opt/vespa/logs/vespa/otel-test.json - rotation: - max_megabytes: 10 - max_days: 3 - max_backups: 1 - service: - pipelines: - metrics: - receivers: [ prometheus_simple ] - processors: [ ] - exporters: [ file ] - """; + if (statePorts.isEmpty()) { + return ""; + } + ByteArrayOutputStream out = new ByteArrayOutputStream(); + try { + JsonGenerator g = new JsonFactory().createGenerator(out, JsonEncoding.UTF8); + g.writeStartObject(); + addReceivers(g); + addExporters(g); + addServiceBlock(g); + g.writeEndObject(); // root + g.close(); + } catch (java.io.IOException e) { + System.err.println("unexpected error: " + e); + return ""; + } + return out.toString(StandardCharsets.UTF_8); } void addStatePorts(List<StatePortInfo> portList) { - // XXX not used yet + this.statePorts = portList; } List<String> referencedPaths() { - return List.of("/var/lib/sia/certs/vespa.external.cd.tenant.cert.pem", - "/var/lib/sia/keys/vespa.external.cd.tenant.key.pem"); + return List.of(ca_file, cert_file, key_file); } } diff --git a/config-model/src/main/java/com/yahoo/vespa/model/application/validation/CloudClientsValidator.java b/config-model/src/main/java/com/yahoo/vespa/model/application/validation/CloudClientsValidator.java index 9a8c8435790..5e6bd2a4b7f 100644 --- a/config-model/src/main/java/com/yahoo/vespa/model/application/validation/CloudClientsValidator.java +++ b/config-model/src/main/java/com/yahoo/vespa/model/application/validation/CloudClientsValidator.java @@ -31,20 +31,17 @@ public class CloudClientsValidator implements Validator { if (extensions == null) return; // Certificate without any extensions is okay if (extensions.getExtensionOIDs().length == 0) { /* - BouncyCastle 1.77 no longer accepts certificates having an empty sequence of extensions. + BouncyCastle 1.77 and 1.78 did not accept certificates having an empty sequence of extensions. Earlier releases violated the ASN.1 specification as the specification forbids empty extension sequence. See https://github.com/bcgit/bc-java/issues/1479. - - Detect such certificates and issue a warning for now. - Validation will be implicitly enforced once we upgrade BouncyCastle past 1.76. + The restriction was lifted on 1.78.1 although it's a reasonble to warn users still. */ var message = "The certificate's ASN.1 structure contains an empty sequence of extensions, " + "which is a violation of the ASN.1 specification. " + "Please update the application package with a new certificate, " + - "e.g by generating a new one using the Vespa CLI `$ vespa auth cert`. " + - "Such certificate will no longer be accepted in near future."; + "e.g by generating a new one using the Vespa CLI `$ vespa auth cert`. "; state.getDeployLogger() - .logApplicationPackage(Level.WARNING, errorMessage(clusterName, clientId, message)); + .log(Level.INFO, errorMessage(clusterName, clientId, message)); } } catch (CertificateEncodingException e) { reporter.accept(errorMessage(clusterName, clientId, e.getMessage()), e); diff --git a/config-model/src/main/java/com/yahoo/vespa/model/builder/xml/dom/DomAdminV4Builder.java b/config-model/src/main/java/com/yahoo/vespa/model/builder/xml/dom/DomAdminV4Builder.java index 23a46b3e065..347bb504857 100644 --- a/config-model/src/main/java/com/yahoo/vespa/model/builder/xml/dom/DomAdminV4Builder.java +++ b/config-model/src/main/java/com/yahoo/vespa/model/builder/xml/dom/DomAdminV4Builder.java @@ -123,7 +123,7 @@ public class DomAdminV4Builder extends DomAdminBuilderBase { private void addOtelcol(TreeConfigProducer<?> parent, DeployState deployState, HostResource hostResource) { - var otelcol = new OpenTelemetryCollector(parent); + var otelcol = new OpenTelemetryCollector(parent, deployState); otelcol.setHostResource(hostResource); otelcol.initService(deployState); } diff --git a/config-model/src/test/derived/imported_struct_fields/index-info.cfg b/config-model/src/test/derived/imported_struct_fields/index-info.cfg index f023328380c..2b8a6fc344d 100644 --- a/config-model/src/test/derived/imported_struct_fields/index-info.cfg +++ b/config-model/src/test/derived/imported_struct_fields/index-info.cfg @@ -9,10 +9,6 @@ indexinfo[].command[].indexname "parent_ref" indexinfo[].command[].command "type Reference<parent>" indexinfo[].command[].indexname "parent_ref" indexinfo[].command[].command "word" -indexinfo[].command[].indexname "documentid" -indexinfo[].command[].command "string" -indexinfo[].command[].indexname "documentid" -indexinfo[].command[].command "type string" indexinfo[].command[].indexname "my_elem_array.name" indexinfo[].command[].command "lowercase" indexinfo[].command[].indexname "my_elem_array.name" diff --git a/config-model/src/test/java/com/yahoo/schema/SummaryTestCase.java b/config-model/src/test/java/com/yahoo/schema/SummaryTestCase.java index 6442edd547d..8ffbab84fd7 100644 --- a/config-model/src/test/java/com/yahoo/schema/SummaryTestCase.java +++ b/config-model/src/test/java/com/yahoo/schema/SummaryTestCase.java @@ -359,7 +359,7 @@ public class SummaryTestCase { ApplicationBuilder.createFromStrings(logger, sd); if (explicit) { assertEquals(1, logger.entries.size()); - assertEquals(Level.FINE, logger.entries.get(0).level); + assertEquals(Level.WARNING, logger.entries.get(0).level); assertEquals("For schema 'test', field 'foo', summary 'bar':" + " Specifying the type is deprecated, ignored and will be an error in Vespa 9." + " Remove the type specification to silence this warning.", logger.entries.get(0).message); @@ -392,7 +392,7 @@ public class SummaryTestCase { ApplicationBuilder.createFromStrings(logger, sd); if (explicit) { assertEquals(1, logger.entries.size()); - assertEquals(Level.FINE, logger.entries.get(0).level); + assertEquals(Level.WARNING, logger.entries.get(0).level); assertEquals("For schema 'test', document-summary 'bar', summary field 'foo':" + " Specifying the type is deprecated, ignored and will be an error in Vespa 9." + " Remove the type specification to silence this warning.", logger.entries.get(0).message); diff --git a/config-model/src/test/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGeneratorTest.java b/config-model/src/test/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGeneratorTest.java new file mode 100644 index 00000000000..7c4968aac84 --- /dev/null +++ b/config-model/src/test/java/com/yahoo/vespa/model/admin/otel/OpenTelemetryConfigGeneratorTest.java @@ -0,0 +1,22 @@ +// Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +package com.yahoo.vespa.model.admin.otel; + +import com.yahoo.config.model.ApplicationConfigProducerRoot.StatePortInfo; +import org.junit.jupiter.api.Test; +import java.util.List; +import static org.junit.jupiter.api.Assertions.*; + +/** + * @author arnej + */ +public class OpenTelemetryConfigGeneratorTest { + + @Test + void testBuildsYaml() { + var generator = new OpenTelemetryConfigGenerator(null); + generator.addStatePorts(List.of(new StatePortInfo("localhost", 19098, "config-sentinel", "sentinel"))); + String yaml = generator.generate(); + assertTrue(yaml.contains("sentinel")); + } + +} diff --git a/config-model/src/test/java/com/yahoo/vespa/model/application/validation/CloudClientsValidatorTest.java b/config-model/src/test/java/com/yahoo/vespa/model/application/validation/CloudClientsValidatorTest.java index 6fbca76ccbc..72230a580d7 100644 --- a/config-model/src/test/java/com/yahoo/vespa/model/application/validation/CloudClientsValidatorTest.java +++ b/config-model/src/test/java/com/yahoo/vespa/model/application/validation/CloudClientsValidatorTest.java @@ -18,8 +18,6 @@ class CloudClientsValidatorTest { @Test void logs_deployment_warning_on_certificate_with_empty_sequence_of_extensions() { - // Test should fail on BouncyCastle 1.77 or later - var logger = new DeployLoggerStub(); var state = new DeployState.Builder().deployLogger(logger).build(); var cert = readTestCertificate("cert-with-empty-sequence-of-extensions.pem"); @@ -30,8 +28,7 @@ class CloudClientsValidatorTest { "The certificate's ASN.1 structure contains an empty sequence of extensions, " + "which is a violation of the ASN.1 specification. " + "Please update the application package with a new certificate, " + - "e.g by generating a new one using the Vespa CLI `$ vespa auth cert`. " + - "Such certificate will no longer be accepted in near future."; + "e.g by generating a new one using the Vespa CLI `$ vespa auth cert`. "; assertEquals(expected, logger.getLast().message); } diff --git a/config-provisioning/src/main/java/com/yahoo/config/provision/CloudAccount.java b/config-provisioning/src/main/java/com/yahoo/config/provision/CloudAccount.java index 36a37d61b13..de68dbd7a11 100644 --- a/config-provisioning/src/main/java/com/yahoo/config/provision/CloudAccount.java +++ b/config-provisioning/src/main/java/com/yahoo/config/provision/CloudAccount.java @@ -19,7 +19,8 @@ public class CloudAccount implements Comparable<CloudAccount> { private static final Map<String, CloudMeta> META_BY_CLOUD = Map.of( "aws", new CloudMeta("Account ID", Pattern.compile("[0-9]{12}")), "azure", new CloudMeta("Subscription ID", Pattern.compile("[0-9a-f]{8}-([0-9a-f]{4}-){3}[0-9a-f]{12}")), - "gcp", new CloudMeta("Project ID", Pattern.compile("[a-z][a-z0-9-]{4,28}[a-z0-9]"))); + "gcp", new CloudMeta("Project ID", Pattern.compile("[a-z][a-z0-9-]{4,28}[a-z0-9]")), + "yahoo", new CloudMeta("OpenStack Project", Pattern.compile("[a-zA-Z0-9._-]+"))); /** Empty value. When this is used, either implicitly or explicitly, the zone will use its default account */ public static final CloudAccount empty = new CloudAccount("", CloudName.DEFAULT); diff --git a/config-provisioning/src/test/java/com/yahoo/config/provision/CloudAccountTest.java b/config-provisioning/src/test/java/com/yahoo/config/provision/CloudAccountTest.java index 5af9cdb9263..68bde6ee471 100644 --- a/config-provisioning/src/test/java/com/yahoo/config/provision/CloudAccountTest.java +++ b/config-provisioning/src/test/java/com/yahoo/config/provision/CloudAccountTest.java @@ -73,7 +73,7 @@ class CloudAccountTest { assertInvalidAccount("aws:123", "Invalid cloud account 'aws:123': Account ID must match '[0-9]{12}'"); assertInvalidAccount("gcp:123", "Invalid cloud account 'gcp:123': Project ID must match '[a-z][a-z0-9-]{4,28}[a-z0-9]'"); assertInvalidAccount("$something", "Invalid cloud account '$something': Must be on format '<cloud-name>:<account>' or 'default'"); - assertInvalidAccount("unknown:account", "Invalid cloud account 'unknown:account': Cloud name must be one of: aws, azure, gcp"); + assertInvalidAccount("unknown:account", "Invalid cloud account 'unknown:account': Cloud name must be one of: aws, azure, gcp, yahoo"); } private static void assertInvalidAccount(String account, String message) { diff --git a/dependency-versions/pom.xml b/dependency-versions/pom.xml index b37c97c5a71..693210d26cf 100644 --- a/dependency-versions/pom.xml +++ b/dependency-versions/pom.xml @@ -68,7 +68,7 @@ <assertj.vespa.version>3.25.3</assertj.vespa.version> <!-- Athenz dependencies. Make sure these dependencies match those in Vespa's internal repositories --> - <aws-sdk.vespa.version>1.12.703</aws-sdk.vespa.version> + <aws-sdk.vespa.version>1.12.704</aws-sdk.vespa.version> <athenz.vespa.version>1.11.56</athenz.vespa.version> <!-- Athenz END --> @@ -78,7 +78,7 @@ find zkfacade/src/main/java/org/apache/curator -name package-info.java | \ xargs perl -pi -e 's/major = [0-9]+, minor = [0-9]+, micro = [0-9]+/major = 5, minor = 3, micro = 0/g' --> - <bouncycastle.vespa.version>1.76</bouncycastle.vespa.version> + <bouncycastle.vespa.version>1.78.1</bouncycastle.vespa.version> <byte-buddy.vespa.version>1.14.13</byte-buddy.vespa.version> <checker-qual.vespa.version>3.38.0</checker-qual.vespa.version> <commons-beanutils.vespa.version>1.9.4</commons-beanutils.vespa.version> diff --git a/flags/src/main/java/com/yahoo/vespa/flags/Dimension.java b/flags/src/main/java/com/yahoo/vespa/flags/Dimension.java index b02fa949dbb..d6affae5b03 100644 --- a/flags/src/main/java/com/yahoo/vespa/flags/Dimension.java +++ b/flags/src/main/java/com/yahoo/vespa/flags/Dimension.java @@ -68,6 +68,12 @@ public enum Dimension { ENVIRONMENT("environment"), /** + * The machine flavor from com.yahoo.vespa.hosted.spec.VespaFlavor::vespaFlavorName, e.g. aws-g4dn.xlarge, + * gcp-n2d-highmem-2-375, C-2E/64/960. + */ + FLAVOR("flavor"), + + /** * Fully qualified hostname. * * <p>NOTE: There is seldom any need to set HOSTNAME, as it is always set implicitly (in {@link Flags}) diff --git a/flags/src/main/java/com/yahoo/vespa/flags/PermanentFlags.java b/flags/src/main/java/com/yahoo/vespa/flags/PermanentFlags.java index 43bf3ec02c5..24e385a59e0 100644 --- a/flags/src/main/java/com/yahoo/vespa/flags/PermanentFlags.java +++ b/flags/src/main/java/com/yahoo/vespa/flags/PermanentFlags.java @@ -14,7 +14,9 @@ import java.util.function.Predicate; import java.util.regex.Pattern; import static com.yahoo.vespa.flags.Dimension.APPLICATION; +import static com.yahoo.vespa.flags.Dimension.ARCHITECTURE; import static com.yahoo.vespa.flags.Dimension.CERTIFICATE_PROVIDER; +import static com.yahoo.vespa.flags.Dimension.CLAVE; import static com.yahoo.vespa.flags.Dimension.CLOUD_ACCOUNT; import static com.yahoo.vespa.flags.Dimension.INSTANCE_ID; import static com.yahoo.vespa.flags.Dimension.CLUSTER_ID; @@ -278,7 +280,8 @@ public class PermanentFlags { public static final UnboundDoubleFlag HOST_MEMORY = defineDoubleFlag( "host-memory", 0.6, "The memory in GB required by a host's management processes.", - "Takes effect immediately" + "Takes effect immediately", + CLOUD_ACCOUNT, CLAVE, ARCHITECTURE ); public static final UnboundBooleanFlag FORWARD_ISSUES_AS_ERRORS = defineFeatureFlag( diff --git a/flags/src/test/java/com/yahoo/vespa/flags/DimensionTest.java b/flags/src/test/java/com/yahoo/vespa/flags/DimensionTest.java index 032874dffac..dcf7d758e48 100644 --- a/flags/src/test/java/com/yahoo/vespa/flags/DimensionTest.java +++ b/flags/src/test/java/com/yahoo/vespa/flags/DimensionTest.java @@ -13,7 +13,7 @@ class DimensionTest { public String remember_to_update_SystemFlagsDataArchive(Dimension dimension) { return switch (dimension) { case APPLICATION, ARCHITECTURE, CERTIFICATE_PROVIDER, CLAVE, CLOUD, CLOUD_ACCOUNT, CLUSTER_ID, CLUSTER_TYPE, - CONSOLE_USER_EMAIL, ENVIRONMENT, HOSTNAME, INSTANCE_ID, NODE_TYPE, SYSTEM, TENANT_ID, + CONSOLE_USER_EMAIL, ENVIRONMENT, FLAVOR, HOSTNAME, INSTANCE_ID, NODE_TYPE, SYSTEM, TENANT_ID, VESPA_VERSION, ZONE_ID -> dimension.toWire(); }; } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableResources.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableResources.java index cb70eb977c4..75a00fa951e 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableResources.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableResources.java @@ -2,6 +2,7 @@ package com.yahoo.vespa.hosted.provision.autoscale; import com.yahoo.config.provision.ApplicationId; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterResources; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.config.provision.Flavor; @@ -35,10 +36,12 @@ public class AllocatableResources { /** Fake allocatable resources from requested capacity */ public AllocatableResources(ClusterResources requested, ClusterSpec clusterSpec, - NodeRepository nodeRepository) { + NodeRepository nodeRepository, + CloudAccount cloudAccount) { this.nodes = requested.nodes(); this.groups = requested.groups(); - this.realResources = nodeRepository.resourcesCalculator().requestToReal(requested.nodeResources(), nodeRepository.exclusiveAllocation(clusterSpec), false); + this.realResources = nodeRepository.resourcesCalculator().requestToReal(requested.nodeResources(), cloudAccount, + nodeRepository.exclusiveAllocation(clusterSpec), false); this.advertisedResources = requested.nodeResources(); this.clusterSpec = clusterSpec; this.fulfilment = 1; @@ -180,17 +183,20 @@ public class AllocatableResources { // We decide resources: Add overhead to what we'll request (advertised) to make sure real becomes (at least) cappedNodeResources var allocatableResources = calculateAllocatableResources(wantedResources, nodeRepository, + model.cloudAccount(), clusterSpec, applicationLimits, exclusive, true); var worstCaseRealResources = nodeRepository.resourcesCalculator().requestToReal(allocatableResources.advertisedResources, + model.cloudAccount(), exclusive, false); if ( ! systemLimits.isWithinRealLimits(worstCaseRealResources, clusterSpec)) { allocatableResources = calculateAllocatableResources(wantedResources, nodeRepository, + model.cloudAccount(), clusterSpec, applicationLimits, exclusive, @@ -210,7 +216,7 @@ public class AllocatableResources { for (Flavor flavor : nodeRepository.flavors().getFlavors()) { // Flavor decide resources: Real resources are the worst case real resources we'll get if we ask for these advertised resources NodeResources advertisedResources = nodeRepository.resourcesCalculator().advertisedResourcesOf(flavor); - NodeResources realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, exclusive, false); + NodeResources realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, model.cloudAccount(), exclusive, false); // Adjust where we don't need exact match to the flavor if (flavor.resources().storageType() == NodeResources.StorageType.remote) { @@ -251,20 +257,21 @@ public class AllocatableResources { private static AllocatableResources calculateAllocatableResources(ClusterResources wantedResources, NodeRepository nodeRepository, + CloudAccount cloudAccount, ClusterSpec clusterSpec, Limits applicationLimits, boolean exclusive, boolean bestCase) { var systemLimits = nodeRepository.nodeResourceLimits(); - var advertisedResources = nodeRepository.resourcesCalculator().realToRequest(wantedResources.nodeResources(), exclusive, bestCase); + var advertisedResources = nodeRepository.resourcesCalculator().realToRequest(wantedResources.nodeResources(), cloudAccount, exclusive, bestCase); advertisedResources = systemLimits.enlargeToLegal(advertisedResources, clusterSpec, exclusive, true); // Ask for something legal advertisedResources = applicationLimits.cap(advertisedResources); // Overrides other conditions, even if it will then fail - var realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, exclusive, bestCase); // What we'll really get + var realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, cloudAccount, exclusive, bestCase); // What we'll really get if ( ! systemLimits.isWithinRealLimits(realResources, clusterSpec) && advertisedResources.storageType() == NodeResources.StorageType.any) { // Since local disk reserves some of the storage, try to constrain to remote disk advertisedResources = advertisedResources.with(NodeResources.StorageType.remote); - realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, exclusive, bestCase); + realResources = nodeRepository.resourcesCalculator().requestToReal(advertisedResources, cloudAccount, exclusive, bestCase); } return new AllocatableResources(wantedResources.with(realResources), advertisedResources, diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocationOptimizer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocationOptimizer.java index 45ef2d1d7b5..61d4ced1367 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocationOptimizer.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocationOptimizer.java @@ -10,7 +10,6 @@ import com.yahoo.vespa.hosted.provision.NodeRepository; import java.util.ArrayList; import java.util.List; import java.util.Optional; -import java.util.stream.Collectors; import static com.yahoo.vespa.hosted.provision.autoscale.Autoscaler.headroomRequiredToScaleDown; @@ -38,9 +37,7 @@ public class AllocationOptimizer { * @return the best allocation, if there are any possible legal allocations, fulfilling the target * fully or partially, within the limits */ - public Optional<AllocatableResources> findBestAllocation(Load loadAdjustment, - ClusterModel model, - Limits limits) { + public Optional<AllocatableResources> findBestAllocation(Load loadAdjustment, ClusterModel model, Limits limits) { return findBestAllocations(loadAdjustment, model, limits).stream().findFirst(); } @@ -51,9 +48,7 @@ public class AllocationOptimizer { * @return the best allocations, if there are any possible legal allocations, fulfilling the target * fully or partially, within the limits. The list contains the three best allocations, sorted from most to least preferred. */ - public List<AllocatableResources> findBestAllocations(Load loadAdjustment, - ClusterModel model, - Limits limits) { + public List<AllocatableResources> findBestAllocations(Load loadAdjustment, ClusterModel model, Limits limits) { if (limits.isEmpty()) limits = Limits.of(new ClusterResources(minimumNodes, 1, NodeResources.unspecified()), new ClusterResources(maximumNodes, maximumNodes, NodeResources.unspecified()), diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModel.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModel.java index 986ab830283..a0f9d6e260a 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModel.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModel.java @@ -1,6 +1,7 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vespa.hosted.provision.autoscale; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.vespa.hosted.provision.Node; import com.yahoo.vespa.hosted.provision.NodeList; @@ -123,6 +124,7 @@ public class ClusterModel { public Application application() { return application; } public ClusterSpec clusterSpec() { return clusterSpec; } + public CloudAccount cloudAccount() { return cluster.cloudAccount().orElse(CloudAccount.empty); } public AllocatableResources current() { return current; } private ClusterNodesTimeseries nodeTimeseries() { return nodeTimeseries; } private ClusterTimeseries clusterTimeseries() { return clusterTimeseries; } @@ -438,6 +440,7 @@ public class ClusterModel { clusterSpec, application.id()); return nodeRepository.resourcesCalculator().requestToReal(initialResources, + cloudAccount(), nodeRepository.exclusiveAllocation(clusterSpec), false).memoryGb(); } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/DirtyExpirer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/DirtyExpirer.java index ab103b0bfcf..939c958efdd 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/DirtyExpirer.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/DirtyExpirer.java @@ -27,8 +27,8 @@ public class DirtyExpirer extends Expirer { private final boolean wantToDeprovisionOnExpiry; - DirtyExpirer(NodeRepository nodeRepository, Duration dirtyTimeout, Metric metric) { - super(Node.State.dirty, History.Event.Type.deallocated, nodeRepository, dirtyTimeout, metric); + DirtyExpirer(NodeRepository nodeRepository, Duration expiryTime, Metric metric) { + super(Node.State.dirty, History.Event.Type.deallocated, nodeRepository, expiryTime, metric); // Deprovision hosts on expiry if dynamically provisioned this.wantToDeprovisionOnExpiry = nodeRepository.zone().cloud().dynamicProvisioning(); } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/InactiveExpirer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/InactiveExpirer.java index d97f4566e57..76abf5c2aef 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/InactiveExpirer.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/InactiveExpirer.java @@ -16,7 +16,7 @@ import java.util.List; /** * Maintenance job which moves inactive nodes to dirty or parked after timeout. * - * The timeout is in place to provide a grace period in which nodes can be brought back to active + * The expiry time is in place to provide a grace period in which nodes can be brought back to active * if they were deactivated in error. As inactive nodes retain their state * they can be brought back to active and correct state faster than a new node. * @@ -32,12 +32,12 @@ import java.util.List; public class InactiveExpirer extends Expirer { private final NodeRepository nodeRepository; - private final Duration timeout; + private final Duration expiryTime; - InactiveExpirer(NodeRepository nodeRepository, Duration timeout, Metric metric) { - super(Node.State.inactive, History.Event.Type.deactivated, nodeRepository, timeout, metric); + InactiveExpirer(NodeRepository nodeRepository, Duration expiryTime, Metric metric) { + super(Node.State.inactive, History.Event.Type.deactivated, nodeRepository, expiryTime, metric); this.nodeRepository = nodeRepository; - this.timeout = timeout; + this.expiryTime = expiryTime; } @Override @@ -49,12 +49,12 @@ public class InactiveExpirer extends Expirer { @Override protected boolean isExpired(Node node) { - return super.isExpired(node, timeout(node)) || + return super.isExpired(node, expiryTime(node)) || node.allocation().get().owner().instance().isTester(); } - private Duration timeout(Node node) { - return timeout; + private Duration expiryTime(Node node) { + return expiryTime; } } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/ProvisionedExpirer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/ProvisionedExpirer.java index 24901cb10a9..adcc486d5b4 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/ProvisionedExpirer.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/ProvisionedExpirer.java @@ -27,8 +27,8 @@ public class ProvisionedExpirer extends Expirer { private final NodeRepository nodeRepository; - ProvisionedExpirer(NodeRepository nodeRepository, Duration timeout, Metric metric) { - super(Node.State.provisioned, History.Event.Type.provisioned, nodeRepository, timeout, metric); + ProvisionedExpirer(NodeRepository nodeRepository, Duration expiryTime, Metric metric) { + super(Node.State.provisioned, History.Event.Type.provisioned, nodeRepository, expiryTime, metric); this.nodeRepository = nodeRepository; } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java index 0d6a98f50a3..dae4b11a609 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java @@ -1,6 +1,7 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vespa.hosted.provision.provisioning; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.Flavor; import com.yahoo.config.provision.NodeResources; import com.yahoo.config.provision.NodeType; @@ -41,10 +42,10 @@ public class EmptyProvisionServiceProvider implements ProvisionServiceProvider { public NodeResources advertisedResourcesOf(Flavor flavor) { return flavor.resources(); } @Override - public NodeResources requestToReal(NodeResources resources, boolean exclusive, boolean bestCase) { return resources; } + public NodeResources requestToReal(NodeResources resources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { return resources; } @Override - public NodeResources realToRequest(NodeResources resources, boolean exclusive, boolean bestCase) { return resources; } + public NodeResources realToRequest(NodeResources resources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { return resources; } @Override public long reservedDiskSpaceInBase2Gb(NodeType nodeType, boolean sharedHost) { return 0; } diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/HostResourcesCalculator.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/HostResourcesCalculator.java index e474ae6eea3..204660f9869 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/HostResourcesCalculator.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/HostResourcesCalculator.java @@ -1,6 +1,7 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vespa.hosted.provision.provisioning; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.Flavor; import com.yahoo.config.provision.NodeResources; import com.yahoo.config.provision.NodeType; @@ -28,13 +29,14 @@ public interface HostResourcesCalculator { * Used with exclusive hosts: * Returns the lowest possible real resources we'll get if requesting the given advertised resources */ - NodeResources requestToReal(NodeResources advertisedResources, boolean exclusiveAllocation, boolean bestCase); + NodeResources requestToReal(NodeResources advertisedResources, CloudAccount cloudAccount, + boolean exclusiveAllocation, boolean bestCase); /** * Used with shared hosts: * Returns the advertised resources we need to request to be sure to get at least the given real resources. */ - NodeResources realToRequest(NodeResources realResources, boolean exclusiveAllocation, boolean bestCase); + NodeResources realToRequest(NodeResources realResources, CloudAccount cloudAccount, boolean exclusiveAllocation, boolean bestCase); /** * Returns the disk space to reserve in base2 GB. This space is reserved for use by the host, e.g. for storing diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeRepositoryProvisioner.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeRepositoryProvisioner.java index 8e910a4d61c..7ac80dfbdb3 100644 --- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeRepositoryProvisioner.java +++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeRepositoryProvisioner.java @@ -6,6 +6,7 @@ import com.yahoo.config.provision.ActivationContext; import com.yahoo.config.provision.ApplicationId; import com.yahoo.config.provision.ApplicationTransaction; import com.yahoo.config.provision.Capacity; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterResources; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.config.provision.HostFilter; @@ -187,7 +188,8 @@ public class NodeRepositoryProvisioner implements Provisioner { boolean firstDeployment = nodes.isEmpty(); var current = firstDeployment // start at min, preserve current resources otherwise - ? new AllocatableResources(initialResourcesFrom(requested, clusterSpec, application.id()), clusterSpec, nodeRepository) + ? new AllocatableResources(initialResourcesFrom(requested, clusterSpec, application.id()), clusterSpec, + nodeRepository, requested.cloudAccount().orElse(CloudAccount.empty)) : new AllocatableResources(nodes, nodeRepository); var model = new ClusterModel(nodeRepository, application, clusterSpec, cluster, nodes, current, nodeRepository.metricsDb(), nodeRepository.clock()); return within(Limits.of(requested), model, firstDeployment); @@ -199,9 +201,7 @@ public class NodeRepositoryProvisioner implements Provisioner { /** Make the minimal adjustments needed to the current resources to stay within the limits */ - private ClusterResources within(Limits limits, - ClusterModel model, - boolean firstDeployment) { + private ClusterResources within(Limits limits, ClusterModel model, boolean firstDeployment) { if (limits.min().equals(limits.max())) return limits.min(); // Don't change current deployments that are still legal @@ -209,9 +209,7 @@ public class NodeRepositoryProvisioner implements Provisioner { return model.current().advertisedResources(); // Otherwise, find an allocation that preserves the current resources as well as possible - return allocationOptimizer.findBestAllocation(Load.one(), - model, - limits) + return allocationOptimizer.findBestAllocation(Load.one(), model, limits) .orElseThrow(() -> newNoAllocationPossible(model.current().clusterSpec(), limits)) .advertisedResources(); } diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModelTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModelTest.java index 5e4dfdc974d..8318ec65f05 100644 --- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModelTest.java +++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/ClusterModelTest.java @@ -3,6 +3,7 @@ package com.yahoo.vespa.hosted.provision.autoscale; import com.yahoo.config.provision.ApplicationId; import com.yahoo.config.provision.Capacity; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterResources; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.config.provision.NodeResources; @@ -92,7 +93,7 @@ public class ClusterModelTest { return new ClusterModel(nodeRepository, application.with(status), clusterSpec, cluster, - new AllocatableResources(clusterResources(), clusterSpec, nodeRepository), + new AllocatableResources(clusterResources(), clusterSpec, nodeRepository, cluster.cloudAccount().orElse(CloudAccount.empty)), clock, Duration.ofMinutes(10), Duration.ofMinutes(5), timeseries(cluster,100, queryRate, writeRate, clock), ClusterNodesTimeseries.empty()); diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/awsnodes/AwsHostResourcesCalculatorImpl.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/awsnodes/AwsHostResourcesCalculatorImpl.java index 0fa73aa50a5..e8a0880f2d7 100644 --- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/awsnodes/AwsHostResourcesCalculatorImpl.java +++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/autoscale/awsnodes/AwsHostResourcesCalculatorImpl.java @@ -1,6 +1,7 @@ // Copyright Vespa.ai. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vespa.hosted.provision.autoscale.awsnodes; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.Flavor; import com.yahoo.config.provision.NodeResources; import com.yahoo.config.provision.NodeType; @@ -43,7 +44,7 @@ public class AwsHostResourcesCalculatorImpl implements HostResourcesCalculator { } @Override - public NodeResources requestToReal(NodeResources advertisedResources, boolean exclusive, boolean bestCase) { + public NodeResources requestToReal(NodeResources advertisedResources, CloudAccount enclaveAccount, boolean exclusive, boolean bestCase) { var consideredFlavors = consideredFlavorsGivenAdvertised(advertisedResources); double memoryOverhead = consideredFlavors.stream() .mapToDouble(flavor -> resourcesCalculator.memoryOverhead(flavor, advertisedResources, false)) @@ -56,7 +57,7 @@ public class AwsHostResourcesCalculatorImpl implements HostResourcesCalculator { } @Override - public NodeResources realToRequest(NodeResources realResources, boolean exclusive, boolean bestCase) { + public NodeResources realToRequest(NodeResources realResources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { double chosenMemoryOverhead = bestCase ? Integer.MAX_VALUE : 0; double chosenDiskOverhead = bestCase ? Integer.MAX_VALUE : 0; for (VespaFlavor flavor : consideredFlavorsGivenReal(realResources)) { diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicProvisioningTester.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicProvisioningTester.java index ca6dc5a0044..52f41d3a55c 100644 --- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicProvisioningTester.java +++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicProvisioningTester.java @@ -3,6 +3,7 @@ package com.yahoo.vespa.hosted.provision.provisioning; import com.yahoo.config.provision.ApplicationId; import com.yahoo.config.provision.Capacity; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterResources; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.config.provision.Flavor; @@ -266,12 +267,12 @@ public class DynamicProvisioningTester { } @Override - public NodeResources requestToReal(NodeResources resources, boolean exclusive, boolean bestCase) { + public NodeResources requestToReal(NodeResources resources, CloudAccount enclaveAccount, boolean exclusive, boolean bestCase) { return resources.withMemoryGb(resources.memoryGb()); } @Override - public NodeResources realToRequest(NodeResources resources, boolean exclusive, boolean bestCase) { + public NodeResources realToRequest(NodeResources resources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { return resources.withMemoryGb(resources.memoryGb()); } diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java index 48bed11d83f..4ec290dd7ba 100644 --- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java +++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java @@ -811,13 +811,13 @@ public class ProvisioningTester { } @Override - public NodeResources requestToReal(NodeResources resources, boolean exclusive, boolean bestCase) { + public NodeResources requestToReal(NodeResources resources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { return resources.withMemoryGb(resources.memoryGb() - memoryTaxGb) .withDiskGb(resources.diskGb() - ( resources.storageType() == local ? localDiskTax : 0) ); } @Override - public NodeResources realToRequest(NodeResources resources, boolean exclusive, boolean bestCase) { + public NodeResources realToRequest(NodeResources resources, CloudAccount cloudAccount, boolean exclusive, boolean bestCase) { return resources.withMemoryGb(resources.memoryGb() + memoryTaxGb) .withDiskGb(resources.diskGb() + ( resources.storageType() == local ? localDiskTax : 0) ); } diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningCompleteHostCalculatorTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningCompleteHostCalculatorTest.java index c18815fc439..1bf42d72180 100644 --- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningCompleteHostCalculatorTest.java +++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningCompleteHostCalculatorTest.java @@ -3,6 +3,7 @@ package com.yahoo.vespa.hosted.provision.provisioning; import com.yahoo.config.provision.ApplicationId; import com.yahoo.config.provision.Capacity; +import com.yahoo.config.provision.CloudAccount; import com.yahoo.config.provision.ClusterResources; import com.yahoo.config.provision.ClusterSpec; import com.yahoo.config.provision.Environment; @@ -62,8 +63,8 @@ public class VirtualNodeProvisioningCompleteHostCalculatorTest { Flavor hostFlavor = new Flavor(new NodeResources(20, 40, 1000, 4)); var calculator = new CompleteResourcesCalculator(hostFlavor); var originalReal = new NodeResources(0.7, 6.0, 12.9, 1.0); - var realToRequest = calculator.realToRequest(originalReal, false, false); - var requestToReal = calculator.requestToReal(realToRequest, false, false); + var realToRequest = calculator.realToRequest(originalReal, CloudAccount.empty, false, false); + var requestToReal = calculator.requestToReal(realToRequest, CloudAccount.empty, false, false); var realResourcesOf = calculator.realResourcesOf(realToRequest); assertEquals(originalReal, requestToReal); assertEquals(originalReal, realResourcesOf); @@ -93,7 +94,8 @@ public class VirtualNodeProvisioningCompleteHostCalculatorTest { } @Override - public NodeResources requestToReal(NodeResources advertisedResources, boolean exclusive, boolean bestCase) { + public NodeResources requestToReal(NodeResources advertisedResources, CloudAccount cloudAccount, + boolean exclusive, boolean bestCase) { double memoryOverhead = memoryOverhead(advertisedResourcesOf(hostFlavor).memoryGb(), advertisedResources, false); double diskOverhead = diskOverhead(advertisedResourcesOf(hostFlavor).diskGb(), advertisedResources, false); return advertisedResources.withMemoryGb(advertisedResources.memoryGb() - memoryOverhead) @@ -108,7 +110,8 @@ public class VirtualNodeProvisioningCompleteHostCalculatorTest { } @Override - public NodeResources realToRequest(NodeResources realResources, boolean exclusive, boolean bestCase) { + public NodeResources realToRequest(NodeResources realResources, CloudAccount cloudAccount, + boolean exclusive, boolean bestCase) { double memoryOverhead = memoryOverhead(advertisedResourcesOf(hostFlavor).memoryGb(), realResources, true); double diskOverhead = diskOverhead(advertisedResourcesOf(hostFlavor).diskGb(), realResources, true); return realResources.withMemoryGb(realResources.memoryGb() + memoryOverhead) diff --git a/searchlib/src/tests/queryeval/iterator_benchmark/iterator_benchmark_test.cpp b/searchlib/src/tests/queryeval/iterator_benchmark/iterator_benchmark_test.cpp index f7a358efb26..f4a1ade8a66 100644 --- a/searchlib/src/tests/queryeval/iterator_benchmark/iterator_benchmark_test.cpp +++ b/searchlib/src/tests/queryeval/iterator_benchmark/iterator_benchmark_test.cpp @@ -750,19 +750,36 @@ void run_intermediate_blueprint_benchmark(const BlueprintFactorySetup& a, const BlueprintFactorySetup& b, size_t num_docs) { print_intermediate_blueprint_result_header(2); + double max_speedup = 0.0; + double min_speedup = std::numeric_limits<double>::max(); for (double b_hit_ratio: b.op_hit_ratios) { auto b_factory = b.make_factory_shared(num_docs, b_hit_ratio); for (double a_hit_ratio : a.op_hit_ratios) { IntermediateBlueprintFactoryType factory; factory.add_child(a.make_factory(num_docs, a_hit_ratio)); factory.add_child(b_factory); - for (auto algo: {PlanningAlgo::Order, PlanningAlgo::Estimate, PlanningAlgo::Cost, PlanningAlgo::CostForceStrict}) { + double time_ms_esti = 0.0; + for (auto algo: {PlanningAlgo::Order, PlanningAlgo::Estimate, PlanningAlgo::Cost, + PlanningAlgo::CostForceStrict}) { auto res = benchmark_search(factory, num_docs + 1, true, false, false, 1.0, algo); print_intermediate_blueprint_result(res, {a_hit_ratio, b_hit_ratio}, algo, num_docs); + if (algo == PlanningAlgo::Estimate) { + time_ms_esti = res.time_ms; + } + if (algo == PlanningAlgo::CostForceStrict) { + double speedup = time_ms_esti / res.time_ms; + if (speedup > max_speedup) { + max_speedup = speedup; + } + if (speedup < min_speedup) { + min_speedup = speedup; + } + std::cout << "speedup (esti/forc)=" << std::setprecision(4) << speedup << std::endl; + } } - std::cout << std::endl; } } + std::cout << "max_speedup=" << max_speedup << ", min_speedup=" << min_speedup << std::endl << std::endl; } void @@ -787,6 +804,12 @@ gen_ratios(double middle, double range_multiplier, size_t num_samples) for (size_t i = 0; i < num_samples; ++i) { res.push_back(ratio); ratio *= factor; + if (ratio > 1.0) { + if (res.size() < num_samples) { + res.push_back(1.0); + } + break; + } } return res; } @@ -831,7 +854,6 @@ TEST(IteratorBenchmark, analyze_term_search_in_disk_index) { BenchmarkSetup setup(num_docs, {str_index}, {QueryOperator::Term}, {true, false}, base_hit_ratios); setup.filter_hit_ratios = filter_hit_ratios; - setup.filter_crossover_factor = 1.0; run_benchmarks(setup, global_summary); } @@ -863,31 +885,24 @@ TEST(IteratorBenchmark, analyze_term_search_in_fast_search_attributes) run_benchmarks(setup, global_summary); } -TEST(IteratorBenchmark, analyze_in_operator_non_strict) +TEST(IteratorBenchmark, analyze_IN_non_strict) { - const std::vector<double> hit_ratios = {0.001, 0.01, 0.1, 0.2, 0.4, 0.6, 0.8}; - BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::In}, {false}, hit_ratios, {5, 9, 10, 100, 1000, 10000}); - setup.disjunct_children = true; - run_benchmarks(setup); + for (auto in_hit_ratio : {0.01, 0.1, 0.5}) { + BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::In}, {false}, {in_hit_ratio}, {2, 5, 9, 10, 100, 1000, 10000}); + setup.filter_hit_ratios = gen_ratios(in_hit_ratio, 10.0, 13); + setup.disjunct_children = true; + run_benchmarks(setup); + } } -TEST(IteratorBenchmark, analyze_in_operator_strict) +TEST(IteratorBenchmark, analyze_IN_strict) { const std::vector<double> hit_ratios = {0.001, 0.01, 0.1, 0.2, 0.4, 0.6, 0.8}; - BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::In}, {true}, hit_ratios, {5, 9, 10, 100, 1000, 10000}); + BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::In}, {true}, hit_ratios, {2, 5, 9, 10, 100, 1000, 10000}); setup.disjunct_children = true; run_benchmarks(setup); } -TEST(IteratorBenchmark, analyze_complex_leaf_operators) -{ - std::vector<FieldConfig> field_cfgs = {int32_array_fs}; - std::vector<QueryOperator> query_ops = {QueryOperator::In, QueryOperator::DotProduct}; - const std::vector<double> hit_ratios = {0.001, 0.01, 0.1, 0.2, 0.4, 0.6, 0.8}; - BenchmarkSetup setup(num_docs, field_cfgs, query_ops, {true, false}, hit_ratios, {1, 2, 10, 100}); - run_benchmarks(setup); -} - TEST(IteratorBenchmark, analyze_weak_and_operators) { std::vector<FieldConfig> field_cfgs = {int32_wset_fs}; @@ -897,24 +912,6 @@ TEST(IteratorBenchmark, analyze_weak_and_operators) run_benchmarks(setup); } -TEST(IteratorBenchmark, term_benchmark) -{ - BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::Term}, {true, false}, base_hit_ratios); - run_benchmarks(setup); -} - -TEST(IteratorBenchmark, and_benchmark) -{ - BenchmarkSetup setup(num_docs, {int32_array_fs}, {QueryOperator::And}, {true, false}, base_hit_ratios, {1, 2, 4, 8}); - run_benchmarks(setup); -} - -TEST(IteratorBenchmark, or_benchmark) -{ - BenchmarkSetup setup(num_docs, {int32_array_fs}, {QueryOperator::Or}, {true, false}, base_hit_ratios, {1, 10, 100, 1000}); - run_benchmarks(setup); -} - TEST(IteratorBenchmark, or_vs_filter_crossover) { auto fixed_or = make_blueprint_factory(int32_array_fs, QueryOperator::Or, num_docs, 0, 0.1, 100, false); @@ -933,16 +930,38 @@ TEST(IteratorBenchmark, or_vs_filter_crossover_with_allow_force_strict) analyze_crossover(*fixed_or, variable_term, num_docs + 1, true, 0.0001); } -TEST(IteratorBenchmark, analyze_and_with_filter_vs_in) +TEST(IteratorBenchmark, analyze_AND_filter_vs_IN) +{ + for (auto in_filter_ratio : {0.01, 0.1, 0.5}) { + for (uint32_t children: {2, 10, 100, 1000}) { + run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(in_filter_ratio, 10.0, 13)}, + {int32_fs, QueryOperator::In, {in_filter_ratio}, children, false}, + num_docs); + } + } +} + +TEST(IteratorBenchmark, analyze_AND_filter_vs_OR) +{ + for (auto or_filter_ratio : {0.01, 0.1, 0.5}) { + for (uint32_t children: {2, 10, 100, 1000}) { + run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(or_filter_ratio, 10, 13)}, + {int32_fs, QueryOperator::Or, {or_filter_ratio}, children, false}, + num_docs); + } + } +} + +TEST(IteratorBenchmark, analyze_AND_filter_vs_IN_array) { - for (uint32_t children: {10, 100, 1000}) { - run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(0.1, 8.0, 15)}, - {int32_fs, QueryOperator::In, {0.1}, children, false}, + for (uint32_t children: {2, 10, 100, 1000}) { + run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(0.1, 10.0, 13)}, + {int32_array_fs, QueryOperator::In, {0.1}, children, false}, num_docs); } } -TEST(IteratorBenchmark, analyze_and_with_bitvector_vs_in) +TEST(IteratorBenchmark, analyze_AND_bitvector_vs_IN) { for (uint32_t children: {10, 100, 1000, 10000}) { run_and_benchmark({int32_fs, QueryOperator::In, {0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.40, 0.45, 0.50, 0.55, 0.60}, children, true}, @@ -951,21 +970,35 @@ TEST(IteratorBenchmark, analyze_and_with_bitvector_vs_in) } } -TEST(IteratorBenchmark, analyze_and_with_filter_vs_in_array) +TEST(IteratorBenchmark, analyze_OR_non_strict_fs) { - for (uint32_t children: {10, 100, 1000}) { - run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(0.1, 8.0, 15)}, - {int32_array_fs, QueryOperator::In, {0.1}, children, false}, - num_docs); + for (auto or_hit_ratio : {0.01, 0.1, 0.5}) { + BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::Or}, {false}, {or_hit_ratio}, + {2, 4, 6, 8, 10, 100, 1000}); + setup.filter_hit_ratios = gen_ratios(or_hit_ratio, 10.0, 13); + run_benchmarks(setup); } } -TEST(IteratorBenchmark, analyze_and_with_filter_vs_or) +TEST(IteratorBenchmark, analyze_OR_non_strict_non_fs) { - for (uint32_t children: {10, 100, 1000}) { - run_and_benchmark({int32_fs, QueryOperator::Term, gen_ratios(0.1, 8.0, 15)}, - {int32_fs, QueryOperator::Or, {0.1}, children, false}, - num_docs); + BenchmarkSetup setup(num_docs, {int32}, {QueryOperator::Or}, {false}, {0.1}, {2, 4, 6, 8, 10}); + setup.filter_hit_ratios = gen_ratios(0.1, 10.0, 13); + run_benchmarks(setup); +} + +TEST(IteratorBenchmark, analyze_OR_strict) +{ + BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::Or}, {true}, {0.01, 0.1, 0.5}, {2, 4, 6, 8, 10, 100, 1000}); + run_benchmarks(setup); +} + +TEST(IteratorBenchmark, analyze_btree_iterator_non_strict) +{ + for (auto term_ratio : {0.01, 0.1, 0.5, 1.0}) { + BenchmarkSetup setup(num_docs, {int32_fs}, {QueryOperator::Term}, {false}, {term_ratio}, {1}); + setup.filter_hit_ratios = gen_ratios(term_ratio, 10.0, 15); + run_benchmarks(setup); } } diff --git a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp index aebfda8fffd..569edc0a4ab 100644 --- a/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp +++ b/searchlib/src/vespa/searchlib/attribute/attribute_blueprint_factory.cpp @@ -166,7 +166,7 @@ public: return {0.5, lookup_cost(indirections), lookup_strict_cost(indirections)}; } else { double rel_est = abs_to_rel_est(_hit_estimate.est_hits(), docid_limit); - return {rel_est, btree_cost(), btree_strict_cost(rel_est)}; + return {rel_est, btree_cost(rel_est), btree_strict_cost(rel_est)}; } } @@ -519,8 +519,9 @@ public: double estimate(const IDirectPostingStore::LookupResult &term) const noexcept { return abs_to_rel_est(term.posting_size, docid_limit); } - double cost(const IDirectPostingStore::LookupResult &) const noexcept { - return btree_cost(); + double cost(const IDirectPostingStore::LookupResult &term) const noexcept { + double rel_est = abs_to_rel_est(term.posting_size, docid_limit); + return btree_cost(rel_est); } double strict_cost(const IDirectPostingStore::LookupResult &term) const noexcept { double rel_est = abs_to_rel_est(term.posting_size, docid_limit); diff --git a/searchlib/src/vespa/searchlib/attribute/direct_multi_term_blueprint.hpp b/searchlib/src/vespa/searchlib/attribute/direct_multi_term_blueprint.hpp index 160bb199fb8..4ede8957f4e 100644 --- a/searchlib/src/vespa/searchlib/attribute/direct_multi_term_blueprint.hpp +++ b/searchlib/src/vespa/searchlib/attribute/direct_multi_term_blueprint.hpp @@ -192,8 +192,9 @@ DirectMultiTermBlueprint<PostingStoreType, SearchType>::calculate_flow_stats(uin double estimate(const IDirectPostingStore::LookupResult &term) const noexcept { return abs_to_rel_est(term.posting_size, docid_limit); } - double cost(const IDirectPostingStore::LookupResult &) const noexcept { - return search::queryeval::flow::btree_cost(); + double cost(const IDirectPostingStore::LookupResult &term) const noexcept { + double rel_est = abs_to_rel_est(term.posting_size, docid_limit); + return search::queryeval::flow::btree_cost(rel_est); } double strict_cost(const IDirectPostingStore::LookupResult &term) const noexcept { double rel_est = abs_to_rel_est(term.posting_size, docid_limit); diff --git a/searchlib/src/vespa/searchlib/diskindex/disktermblueprint.cpp b/searchlib/src/vespa/searchlib/diskindex/disktermblueprint.cpp index c0d0b1baa8c..c30b02a0c37 100644 --- a/searchlib/src/vespa/searchlib/diskindex/disktermblueprint.cpp +++ b/searchlib/src/vespa/searchlib/diskindex/disktermblueprint.cpp @@ -72,7 +72,7 @@ queryeval::FlowStats DiskTermBlueprint::calculate_flow_stats(uint32_t docid_limit) const { double rel_est = abs_to_rel_est(_lookupRes->counts._numDocs, docid_limit); - return {rel_est, disk_index_cost(), disk_index_strict_cost(rel_est)}; + return {rel_est, disk_index_cost(rel_est), disk_index_strict_cost(rel_est)}; } SearchIterator::UP diff --git a/searchlib/src/vespa/searchlib/diskindex/pagedict4file.cpp b/searchlib/src/vespa/searchlib/diskindex/pagedict4file.cpp index 89b5ffb84f8..3991807e731 100644 --- a/searchlib/src/vespa/searchlib/diskindex/pagedict4file.cpp +++ b/searchlib/src/vespa/searchlib/diskindex/pagedict4file.cpp @@ -76,7 +76,7 @@ PageDict4FileSeqRead::DictFileReadContext::DictFileReadContext(vespalib::stringr _file() { _dc.setReadContext(&_readContext); - if (tune.getWantDirectIO()) { + if (tune.getWantDirectIO() && !read_all_upfront) { _file.EnableDirectIO(); } if (read_all_upfront) { diff --git a/searchlib/src/vespa/searchlib/memoryindex/field_index.cpp b/searchlib/src/vespa/searchlib/memoryindex/field_index.cpp index eba135d8519..2bc94073c92 100644 --- a/searchlib/src/vespa/searchlib/memoryindex/field_index.cpp +++ b/searchlib/src/vespa/searchlib/memoryindex/field_index.cpp @@ -261,7 +261,7 @@ public: queryeval::FlowStats calculate_flow_stats(uint32_t docid_limit) const override { double rel_est = abs_to_rel_est(_posting_itr.size(), docid_limit); - return {rel_est, btree_cost(), btree_strict_cost(rel_est)}; + return {rel_est, btree_cost(rel_est), btree_strict_cost(rel_est)}; } SearchIterator::UP createLeafSearch(const TermFieldMatchDataArray& tfmda) const override { diff --git a/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h index 356ecd4c992..e8a58bba9dc 100644 --- a/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h +++ b/searchlib/src/vespa/searchlib/queryeval/flow_tuning.h @@ -7,60 +7,87 @@ namespace search::queryeval::flow { /** - * This function is used when calculating the strict cost of - * intermediate and complex leaf blueprints that use a heap for their strict iterator implementation. - * - * Iterator benchmarking has shown the need to increase the strict cost - * of complex blueprints, to avoid that they are forced strict too early. - * The 5.0 multiplier reflects this. - * - * Program used: searchlib/src/tests/queryeval/iterator_benchmark - * Tests used: analyze_and_with_filter_vs_* - */ -inline double heap_cost(double my_est, size_t num_children) { - return 5.0 * my_est * std::log2(std::max(size_t(1), num_children)); -} - -/** - * The following constants and formulas were derived after analyzing term search over attributes - * (with and without fast-search) and disk index by using the iterator benchmark program: + * The following constants and formulas were derived after benchmarking and analyzing + * using the following benchmark program: * searchlib/src/tests/queryeval/iterator_benchmark * - * The following tests were executed on a machine with an Intel Xeon 2.5 GHz CPU with 48 cores and 256 Gb of memory: - * ./searchlib_iterator_benchmark_test_app --gtest_filter='*analyze_term_search*' - * - * TODO: Add details on OR benchmarking. + * The tests were executed on: + * - Machine with an Intel Xeon 2.5 GHz CPU with 48 cores and 256 Gb of memory. + * - Apple M1 MacBook Pro (2021) 32 GB. * * The benchmark summary shows the 'average ms per cost' of the different benchmark cases. - * The following constants and formulas were derived to balance 'average ms per cost' to be similar + * The constants and formulas are adjusted to balance 'average ms per cost' to be similar * across the different benchmark cases. + * + * The AND benchmark cases outputs the ratio (esti/forc) of the time_ms used by two query planning algorithms: + * 'estimate' (legacy) and 'cost with allowed force strict' (new). + * 'max_speedup' indicates the gain of using the new cost model, while 'min_speedup' indicates the loss. + * The constants and formulas are also adjusted to maximize speedup, while reducing loss. + * Tests used: + * - IteratorBenchmark::analyze_AND_filter_vs_IN + * - IteratorBenchmark::analyze_AND_filter_vs_OR + * - IteratorBenchmark::analyze_AND_filter_vs_IN_array + * - IteratorBenchmark::analyze_AND_bitvector_vs_IN */ +/** + * This function is used when calculating the strict cost of + * intermediate and complex leaf blueprints that use a heap for their strict iterator implementation. + * Tests used: + * - IteratorBenchmark::analyze_IN_strict + * - IteratorBenchmark::analyze_OR_strict + */ +inline double heap_cost(double my_est, size_t num_children) { + return my_est * std::log2(std::max(size_t(1), num_children)); +} + // Non-strict cost of lookup based matching in an attribute (not fast-search). +// Test used: IteratorBenchmark::analyze_term_search_in_attributes_non_strict inline double lookup_cost(size_t num_indirections) { return 1.0 + (num_indirections * 1.0); } // Non-strict cost of reverse lookup into a hash table (containing terms from a multi-term operator). +// Test used: IteratorBenchmark::analyze_IN_non_strict inline double reverse_hash_lookup() { - return 5.0; + return 1.0; } // Strict cost of lookup based matching in an attribute (not fast-search). +// IteratorBenchmark::analyze_term_search_in_attributes_strict inline double lookup_strict_cost(size_t num_indirections) { return lookup_cost(num_indirections); } -// Non-strict cost of matching in a btree posting list (e.g. fast-search attribute or memory index field). -inline double btree_cost() { - return 1.0; +/** + * Estimates the cost of evaluating an always strict iterator (e.g. btree) in a non-strict context. + * + * When the estimate and strict cost is low, this models the cost of checking whether + * the seek docid matches the docid the iterator is already positioned at (the 0.2 factor). + * + * The resulting non-strict cost is most accurate when the inflow is 1.0. + * The resulting non-strict cost is highly underestimated when the inflow goes to 0.0. + * It is important to have a better estimate at higher inflows, + * as the latency (time) penalty is higher if choosing wrong. + * + * Note: This formula is equal to forced_strict_cost() in flow.h. + */ +inline double non_strict_cost_of_strict_iterator(double estimate, double strict_cost) { + return 0.2 * (1.0 - estimate) + strict_cost; } // Strict cost of matching in a btree posting list (e.g. fast-search attribute or memory index field). +// Test used: IteratorBenchmark::analyze_term_search_in_fast_search_attributes inline double btree_strict_cost(double my_est) { return my_est; } +// Non-strict cost of matching in a btree posting list (e.g. fast-search attribute or memory index field). +// Test used: IteratorBenchmark::analyze_btree_iterator_non_strict +inline double btree_cost(double my_est) { + return non_strict_cost_of_strict_iterator(my_est, btree_strict_cost(my_est)); +} + // Non-strict cost of matching in a bitvector. inline double bitvector_cost() { return 1.0; @@ -72,14 +99,16 @@ inline double bitvector_strict_cost(double my_est) { return 1.5 * my_est; } -// Non-strict cost of matching in a disk index posting list. -inline double disk_index_cost() { - return 1.5; -} - // Strict cost of matching in a disk index posting list. +// Test used: IteratorBenchmark::analyze_term_search_in_disk_index inline double disk_index_strict_cost(double my_est) { return 1.5 * my_est; } +// Non-strict cost of matching in a disk index posting list. +// Test used: IteratorBenchmark::analyze_term_search_in_disk_index +inline double disk_index_cost(double my_est) { + return non_strict_cost_of_strict_iterator(my_est, disk_index_strict_cost(my_est)); +} + } diff --git a/vespabase/src/vespa-configserver.service.in b/vespabase/src/vespa-configserver.service.in index a296acf7039..0e8050d41b5 100644 --- a/vespabase/src/vespa-configserver.service.in +++ b/vespabase/src/vespa-configserver.service.in @@ -12,7 +12,7 @@ ExecStop=@CMAKE_INSTALL_PREFIX@/bin/vespa-stop-configserver LimitNOFILE=32768:262144 LimitCORE=0:infinity LimitNPROC=32768:409600 -LimitStack=8388608:16777216 +LimitSTACK=8388608:16777216 [Install] WantedBy=multi-user.target diff --git a/vespabase/src/vespa.service.in b/vespabase/src/vespa.service.in index 272769b111f..bde505947f2 100644 --- a/vespabase/src/vespa.service.in +++ b/vespabase/src/vespa.service.in @@ -12,7 +12,7 @@ ExecStop=@CMAKE_INSTALL_PREFIX@/bin/vespa-stop-services LimitNOFILE=32768:262144 LimitCORE=0:infinity LimitNPROC=32768:409600 -LimitStack=8388608:16777216 +LimitSTACK=8388608:16777216 [Install] WantedBy=multi-user.target diff --git a/vespalib/src/tests/fuzzy/levenshtein_dfa_test.cpp b/vespalib/src/tests/fuzzy/levenshtein_dfa_test.cpp index 69b34ece2c7..dfd1b3b0c3b 100644 --- a/vespalib/src/tests/fuzzy/levenshtein_dfa_test.cpp +++ b/vespalib/src/tests/fuzzy/levenshtein_dfa_test.cpp @@ -24,12 +24,13 @@ using CasingAndDfaType = std::tuple<LevenshteinDfa::Casing, LevenshteinDfa::DfaT namespace { std::optional<uint32_t> do_calculate(std::string_view left, std::string_view right, uint32_t threshold, - LevenshteinDfa::Casing casing, LevenshteinDfa::DfaType dfa_type) + LevenshteinDfa::Casing casing, LevenshteinDfa::DfaType dfa_type, + LevenshteinDfa::Matching matching) { - auto dfa_lhs = LevenshteinDfa::build(left, threshold, casing, dfa_type); + auto dfa_lhs = LevenshteinDfa::build(left, threshold, casing, dfa_type, matching); auto maybe_match_lhs = dfa_lhs.match(right); - auto dfa_rhs = LevenshteinDfa::build(right, threshold, casing, dfa_type); + auto dfa_rhs = LevenshteinDfa::build(right, threshold, casing, dfa_type, matching); auto maybe_match_rhs = dfa_rhs.match(left); EXPECT_EQ(maybe_match_lhs.matches(), maybe_match_rhs.matches()); @@ -40,6 +41,12 @@ std::optional<uint32_t> do_calculate(std::string_view left, std::string_view rig return std::nullopt; } +std::optional<uint32_t> do_calculate(std::string_view left, std::string_view right, uint32_t threshold, + LevenshteinDfa::Casing casing, LevenshteinDfa::DfaType dfa_type) +{ + return do_calculate(left, right, threshold, casing, dfa_type, LevenshteinDfa::Matching::FullString); +} + std::optional<uint32_t> do_calculate(std::u8string_view left, std::u8string_view right, uint32_t threshold, LevenshteinDfa::Casing casing, LevenshteinDfa::DfaType dfa_type) { @@ -74,6 +81,16 @@ struct LevenshteinDfaTest : TestWithParam<CasingAndDfaType> { return do_calculate(left, right, threshold, casing(), dfa_type()); } + static std::optional<uint32_t> prefix_calculate(std::string_view left, std::string_view right, uint32_t threshold) { + // Prefix matching is not symmetric, cannot use do_calculate() as it implicitly checks this. + auto dfa = LevenshteinDfa::build(left, threshold, casing(), dfa_type(), LevenshteinDfa::Matching::Prefix); + auto maybe_match = dfa.match(right); + if (maybe_match.matches()) { + return {maybe_match.edits()}; + } + return std::nullopt; + } + }; // All the baseline DFA tests use lowercase only, so they should have the exact same outcome @@ -98,6 +115,7 @@ TEST_P(LevenshteinDfaTest, edge_cases_have_correct_edit_distance) { EXPECT_EQ(calculate("abc", "ab", max), std::optional{1}) << max; EXPECT_EQ(calculate("abc", "abcd", max), std::optional{1}) << max; EXPECT_EQ(calculate("a", "", max), std::optional{1}) << max; + EXPECT_EQ(calculate("", "", max), std::optional{0}) << max; } EXPECT_EQ(calculate("bc", "abcd", 2), std::optional{2}); EXPECT_EQ(calculate("ab", "abcd", 2), std::optional{2}); @@ -109,6 +127,7 @@ TEST_P(LevenshteinDfaTest, edge_cases_have_correct_edit_distance) { EXPECT_EQ(calculate("ab", "", 2), std::optional{2}); EXPECT_EQ(calculate("abc", "", 2), std::nullopt); EXPECT_EQ(calculate("abc", "123", 2), std::nullopt); + EXPECT_EQ(calculate("abcde", "xad", 2), std::nullopt); } TEST_P(LevenshteinDfaTest, distance_is_in_utf32_code_point_space) { @@ -124,6 +143,37 @@ TEST_P(LevenshteinDfaTest, distance_is_in_utf32_code_point_space) { EXPECT_EQ(calculate(u8"カラオケ", u8"カラoke", 2), std::nullopt); } +TEST_P(LevenshteinDfaTest, can_match_in_target_string_prefix_mode) { + for (auto max : {1, 2}) { + EXPECT_EQ(prefix_calculate("", "literally anything", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("", "", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("x", "", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abc", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "abcd", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "abcdef", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "ab", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("ac", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("acd", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xabcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("bc", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "acb", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "acdefg", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("acb", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abd", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abdcfgh", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abdefgh", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xbc", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xbcdefg", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xy", max), std::nullopt); + } + EXPECT_EQ(prefix_calculate("abc", "xxabc", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abc", "xxabcd", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abcxx", "abc", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abcxx", "abcd", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("xy", "", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("xyz", "", 2), std::nullopt); +} + void test_dfa_successor(const LevenshteinDfa& dfa, std::string_view source, std::string_view expected_successor, std::string_view successor_prefix) { @@ -182,11 +232,22 @@ TEST_P(LevenshteinDfaTest, can_generate_successors_to_mismatching_source_strings "\xf0\x9f\xa4\xa9""food"); // <starry eyed emoji>food // Note that as a general rule, emojis are fickle beasts to deal with since a single - // emoji often takes up multiple code points, which we consider separate characters - // but a user sees as a single actual rendered glyph. + // emoji often takes up multiple code points. We consider these as separate characters + // but from a Unicode perspective they are considered part of an "extended grapheme + // cluster", from which the actually rendered glyph is derived. // Multi-code point character edit distance support is left as an exercise for the reader :D } +TEST_P(LevenshteinDfaTest, can_generate_successors_with_prefix_match_mode) { + auto dfa = LevenshteinDfa::build("ban", 1, casing(), dfa_type(), LevenshteinDfa::Matching::Prefix); + // There is no difference at all in successor output when using Prefix mode as opposed to + // FullString mode, but since we match _more_ source strings in prefix mode we cannot + // simply run the same test set for both modes. This just tests that the wiring seems fine. + test_dfa_successor(dfa, "", "\x01""an"); + test_dfa_successor(dfa, "xy", "yan"); + test_dfa_successor(dfa, "bolle", "bon"); +} + TEST_P(LevenshteinDfaTest, successor_is_well_defined_for_max_unicode_code_point_input) { auto dfa = LevenshteinDfa::build("food", 1, casing(), dfa_type()); // The successor string must be lexicographically larger than the input string. @@ -332,13 +393,21 @@ std::string bits_to_str(T v) { return ret; } -using CasingAndDfaTypeAndMaxEdits = std::tuple<LevenshteinDfa::Casing, LevenshteinDfa::DfaType, uint32_t>; +using CasingAndDfaTypeAndMaxEdits = std::tuple< + LevenshteinDfa::Casing, + LevenshteinDfa::DfaType, + LevenshteinDfa::Matching, + uint32_t +>; struct LevenshteinDfaSuccessorTest : TestWithParam<CasingAndDfaTypeAndMaxEdits> { - // Print test suffix as e.g. "/Uncased_Explicit_1" instead of just a GTest-chosen number. + // Print test suffix as e.g. "/Uncased_Explicit_FullString_1" instead of just a GTest-chosen number. static std::string stringify_params(const TestParamInfo<ParamType>& info) { std::ostringstream ss; - ss << std::get<0>(info.param) << '_' << std::get<1>(info.param) << '_' << std::get<2>(info.param); + ss << std::get<0>(info.param) + << '_' << std::get<1>(info.param) + << '_' << std::get<2>(info.param) + << '_' << std::get<3>(info.param); return ss.str(); } }; @@ -350,6 +419,8 @@ INSTANTIATE_TEST_SUITE_P(SupportedMaxEdits, Values(LevenshteinDfa::DfaType::Explicit, LevenshteinDfa::DfaType::Implicit, LevenshteinDfa::DfaType::Table), + Values(LevenshteinDfa::Matching::FullString, + LevenshteinDfa::Matching::Prefix), Values(1, 2)), LevenshteinDfaSuccessorTest::stringify_params); @@ -369,10 +440,10 @@ INSTANTIATE_TEST_SUITE_P(SupportedMaxEdits, * Inspired by approach used by Lucene DFA exhaustive testing. */ TEST_P(LevenshteinDfaSuccessorTest, exhaustive_successor_test) { - const auto [casing, dfa_type, max_edits] = GetParam(); + const auto [casing, dfa_type, matching, max_edits] = GetParam(); for (uint32_t i = 0; i < 256; ++i) { const auto target = bits_to_str(static_cast<uint8_t>(i)); - auto target_dfa = LevenshteinDfa::build(target, max_edits, casing, dfa_type); + auto target_dfa = LevenshteinDfa::build(target, max_edits, casing, dfa_type, matching); std::string skip_to, successor; for (uint32_t j = 0; j < 256; ++j) { const auto source = bits_to_str(static_cast<uint8_t>(j)); diff --git a/vespalib/src/tests/fuzzy/levenshtein_distance_test.cpp b/vespalib/src/tests/fuzzy/levenshtein_distance_test.cpp index 37d1d4b4c54..918cbc624db 100644 --- a/vespalib/src/tests/fuzzy/levenshtein_distance_test.cpp +++ b/vespalib/src/tests/fuzzy/levenshtein_distance_test.cpp @@ -16,6 +16,13 @@ std::optional<uint32_t> calculate(std::string_view left, std::string_view right, return leftRight; } +// Prefix matching is asymmetric and therefore cannot implicitly test result symmetry +std::optional<uint32_t> prefix_calculate(std::string_view left, std::string_view right, uint32_t threshold) { + auto left_codepoints = vespalib::LowerCase::convert_to_ucs4(left); + auto right_codepoints = vespalib::LowerCase::convert_to_ucs4(right); + return vespalib::LevenshteinDistance::calculate(left_codepoints, right_codepoints, threshold, true); +} + TEST(LevenshteinDistance, calculate_edgecases) { EXPECT_EQ(calculate("abc", "abc", 2), std::optional{0}); EXPECT_EQ(calculate("abc", "ab1", 2), std::optional{1}); @@ -33,6 +40,54 @@ TEST(LevenshteinDistance, calculate_edgecases) { EXPECT_EQ(calculate("ab", "", 2), std::optional{2}); EXPECT_EQ(calculate("abc", "", 2), std::nullopt); EXPECT_EQ(calculate("abc", "123", 2), std::nullopt); + EXPECT_EQ(calculate("abcde", "xad", 2), std::nullopt); +} + +TEST(LevenshteinDistance, prefix_match_edge_cases) { + // Same cases as LevenshteinDfaTest (TODO consolidate these somehow) + for (auto max : {1, 2}) { + EXPECT_EQ(prefix_calculate("", "literally anything", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("", "", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("x", "", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abc", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "abcd", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "abcdef", max), std::optional{0}); + EXPECT_EQ(prefix_calculate("abc", "ab", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("ac", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("acd", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xabcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("bc", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "acb", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "acdefg", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("acb", "abcdef", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abd", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abdcfgh", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "abdefgh", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xbc", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xbcdefg", max), std::optional{1}); + EXPECT_EQ(prefix_calculate("abc", "xy", max), std::nullopt); + } + EXPECT_EQ(prefix_calculate("abc", "xxabc", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abc", "xxabcd", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abcxx", "abc", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("abcxx", "abcd", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("xy", "", 2), std::optional{2}); + EXPECT_EQ(prefix_calculate("xyz", "", 2), std::nullopt); + + // Max edits > 2 cases; not supported by DFA implementation. + EXPECT_EQ(prefix_calculate("abc", "", 3), std::optional{3}); + EXPECT_EQ(prefix_calculate("abc", "xy", 3), std::optional{3}); + EXPECT_EQ(prefix_calculate("abc", "xyz", 3), std::optional{3}); + EXPECT_EQ(prefix_calculate("abc", "xyzzz", 3), std::optional{3}); + EXPECT_EQ(prefix_calculate("abcd", "xyzd", 3), std::optional{3}); + EXPECT_EQ(prefix_calculate("abcd", "xyzz", 3), std::nullopt); + EXPECT_EQ(prefix_calculate("abcd", "", 3), std::nullopt); +} + +TEST(LevenshteinDistance, oversized_max_edits_is_well_defined) { + const auto k = uint32_t(INT32_MAX) + 10000u; + EXPECT_EQ(calculate("abc", "xyz", k), std::optional{3}); + EXPECT_EQ(prefix_calculate("abc", "xyzzzz", k), std::optional{3}); } GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/fuzzy/dfa_matcher.h b/vespalib/src/vespa/vespalib/fuzzy/dfa_matcher.h index c69f414aae6..8b2597dd179 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/dfa_matcher.h +++ b/vespalib/src/vespa/vespalib/fuzzy/dfa_matcher.h @@ -20,6 +20,12 @@ concept DfaMatcher = requires(T a, std::string u8str, std::vector<uint32_t> u32s // matching to have the expected semantics, the actual target string must be pre-lowercased. { a.is_cased() } -> std::same_as<bool>; + // Whether the matching is performed in prefix mode. In prefix mode, a source string is + // considered a match if it matches the target string at any point during DFA traversal. + // I.e. the source string "bananas" prefix-matched against the target (prefix) "ban" will + // be returned as a match with 0 edits. + { a.is_prefix() } -> std::same_as<bool>; + // Initial (starting) state of the DFA { a.start() } -> std::same_as<typename T::StateType>; diff --git a/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.h b/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.h index 490582b5bf7..a3542d61dc8 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.h +++ b/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.h @@ -97,9 +97,11 @@ public: private: std::vector<DfaNodeType> _nodes; const bool _is_cased; + const bool _is_prefix; public: - explicit ExplicitLevenshteinDfaImpl(bool is_cased) noexcept - : _is_cased(is_cased) + ExplicitLevenshteinDfaImpl(bool is_cased, bool is_prefix) noexcept + : _is_cased(is_cased), + _is_prefix(is_prefix) {} ~ExplicitLevenshteinDfaImpl() override; @@ -140,10 +142,12 @@ template <typename Traits> class ExplicitLevenshteinDfaBuilder { const std::vector<uint32_t> _u32_str_buf; // TODO std::u32string const bool _is_cased; + const bool _is_prefix; public: - ExplicitLevenshteinDfaBuilder(std::vector<uint32_t> str, bool is_cased) noexcept + ExplicitLevenshteinDfaBuilder(std::vector<uint32_t> str, bool is_cased, bool is_prefix) noexcept : _u32_str_buf(std::move(str)), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) {} [[nodiscard]] LevenshteinDfa build_dfa() const; diff --git a/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.hpp b/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.hpp index 55dd459ff26..11a822d2d7e 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.hpp +++ b/vespalib/src/vespa/vespalib/fuzzy/explicit_levenshtein_dfa.hpp @@ -22,16 +22,20 @@ struct ExplicitDfaMatcher { const std::span<const DfaNodeType> _nodes; const bool _is_cased; + const bool _is_prefix; - ExplicitDfaMatcher(const std::span<const DfaNodeType> nodes, bool is_cased) noexcept + ExplicitDfaMatcher(const std::span<const DfaNodeType> nodes, bool is_cased, bool is_prefix) noexcept : _nodes(nodes), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) {} static constexpr uint8_t max_edits() noexcept { return MaxEdits; } bool is_cased() const noexcept { return _is_cased; } + bool is_prefix() const noexcept { return _is_prefix; } + StateType start() const noexcept { return &_nodes[0]; } @@ -99,21 +103,21 @@ ExplicitLevenshteinDfaImpl<MaxEdits>::~ExplicitLevenshteinDfaImpl() = default; template <uint8_t MaxEdits> LevenshteinDfa::MatchResult ExplicitLevenshteinDfaImpl<MaxEdits>::match(std::string_view u8str) const { - ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased); + ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased, _is_prefix); return MatchAlgorithm<MaxEdits>::match(matcher, u8str); } template <uint8_t MaxEdits> LevenshteinDfa::MatchResult ExplicitLevenshteinDfaImpl<MaxEdits>::match(std::string_view u8str, std::string& successor_out) const { - ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased); + ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased, _is_prefix); return MatchAlgorithm<MaxEdits>::match(matcher, u8str, successor_out); } template <uint8_t MaxEdits> LevenshteinDfa::MatchResult ExplicitLevenshteinDfaImpl<MaxEdits>::match(std::string_view u8str, std::vector<uint32_t>& successor_out) const { - ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased); + ExplicitDfaMatcher<MaxEdits> matcher(_nodes, _is_cased, _is_prefix); return MatchAlgorithm<MaxEdits>::match(matcher, u8str, successor_out); } @@ -199,10 +203,12 @@ class ExplicitLevenshteinDfaBuilderImpl : public DfaSteppingBase<Traits> { using Base::transitions; const bool _is_cased; + const bool _is_prefix; public: - ExplicitLevenshteinDfaBuilderImpl(std::span<const uint32_t> str, bool is_cased) noexcept + ExplicitLevenshteinDfaBuilderImpl(std::span<const uint32_t> str, bool is_cased, bool is_prefix) noexcept : DfaSteppingBase<Traits>(str), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) { assert(str.size() < UINT32_MAX / max_out_edges_per_node()); } @@ -217,7 +223,7 @@ public: template <typename Traits> LevenshteinDfa ExplicitLevenshteinDfaBuilderImpl<Traits>::build_dfa() const { - auto dfa = std::make_unique<ExplicitLevenshteinDfaImpl<max_edits()>>(_is_cased); + auto dfa = std::make_unique<ExplicitLevenshteinDfaImpl<max_edits()>>(_is_cased, _is_prefix); ExploreState<StateType> exp; // Use BFS instead of DFS to ensure most node edges point to nodes that are allocated _after_ // the parent node, which means the CPU can skip ahead instead of ping-ponging back and forth. @@ -257,7 +263,7 @@ LevenshteinDfa ExplicitLevenshteinDfaBuilderImpl<Traits>::build_dfa() const { template <typename Traits> LevenshteinDfa ExplicitLevenshteinDfaBuilder<Traits>::build_dfa() const { - ExplicitLevenshteinDfaBuilderImpl<Traits> builder(_u32_str_buf, _is_cased); + ExplicitLevenshteinDfaBuilderImpl<Traits> builder(_u32_str_buf, _is_cased, _is_prefix); return builder.build_dfa(); } diff --git a/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.h b/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.h index 20c8e1b7e2b..552fd849734 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.h +++ b/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.h @@ -13,14 +13,16 @@ class ImplicitLevenshteinDfa final : public LevenshteinDfa::Impl { std::string _target_as_utf8; std::vector<uint32_t> _target_utf8_char_offsets; const bool _is_cased; + const bool _is_prefix; public: using MatchResult = LevenshteinDfa::MatchResult; - ImplicitLevenshteinDfa(std::vector<uint32_t> str, bool is_cased) + ImplicitLevenshteinDfa(std::vector<uint32_t> str, bool is_cased, bool is_prefix) : _u32_str_buf(std::move(str)), _target_as_utf8(), _target_utf8_char_offsets(), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) { precompute_utf8_target_with_offsets(); } diff --git a/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.hpp b/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.hpp index 05ef2761f34..7dadcc59b8e 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.hpp +++ b/vespalib/src/vespa/vespalib/fuzzy/implicit_levenshtein_dfa.hpp @@ -32,21 +32,26 @@ struct ImplicitDfaMatcher : public DfaSteppingBase<Traits> { std::span<const char> _target_as_utf8; std::span<const uint32_t> _target_utf8_char_offsets; const bool _is_cased; + const bool _is_prefix; ImplicitDfaMatcher(std::span<const uint32_t> u32_str, std::span<const char> target_as_utf8, std::span<const uint32_t> target_utf8_char_offsets, - bool is_cased) noexcept + bool is_cased, + bool is_prefix) noexcept : Base(u32_str), _target_as_utf8(target_as_utf8), _target_utf8_char_offsets(target_utf8_char_offsets), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) {} // start, is_match, can_match, match_edit_distance are all provided by base type bool is_cased() const noexcept { return _is_cased; } + bool is_prefix() const noexcept { return _is_prefix; } + template <typename F> bool has_any_char_matching(const StateType& state, F&& f) const noexcept(noexcept(f(uint32_t{}))) { for (uint32_t i = 0; i < state.size(); ++i) { @@ -137,21 +142,21 @@ struct ImplicitDfaMatcher : public DfaSteppingBase<Traits> { template <typename Traits> LevenshteinDfa::MatchResult ImplicitLevenshteinDfa<Traits>::match(std::string_view u8str) const { - ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased); + ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased, _is_prefix); return MatchAlgorithm<Traits::max_edits()>::match(matcher, u8str); } template <typename Traits> LevenshteinDfa::MatchResult ImplicitLevenshteinDfa<Traits>::match(std::string_view u8str, std::string& successor_out) const { - ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased); + ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased, _is_prefix); return MatchAlgorithm<Traits::max_edits()>::match(matcher, u8str, successor_out); } template <typename Traits> LevenshteinDfa::MatchResult ImplicitLevenshteinDfa<Traits>::match(std::string_view u8str, std::vector<uint32_t>& successor_out) const { - ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased); + ImplicitDfaMatcher<Traits> matcher(_u32_str_buf, _target_as_utf8, _target_utf8_char_offsets, _is_cased, _is_prefix); return MatchAlgorithm<Traits::max_edits()>::match(matcher, u8str, successor_out); } diff --git a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.cpp b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.cpp index 19c2fffbb3e..468619c8036 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.cpp +++ b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.cpp @@ -41,34 +41,40 @@ void LevenshteinDfa::dump_as_graphviz(std::ostream& out) const { _impl->dump_as_graphviz(out); } -LevenshteinDfa LevenshteinDfa::build(std::string_view target_string, uint8_t max_edits, Casing casing, DfaType dfa_type) { +LevenshteinDfa LevenshteinDfa::build(std::string_view target_string, uint8_t max_edits, + Casing casing, DfaType dfa_type, Matching matching) { if (max_edits != 1 && max_edits != 2) { throw std::invalid_argument(make_string("Levenshtein DFA max_edits must be in {1, 2}, was %u", max_edits)); } - const bool is_cased = (casing == Casing::Cased); + const bool is_cased = (casing == Casing::Cased); + const bool is_prefix = (matching == Matching::Prefix); auto target_string_u32 = is_cased ? utf8_string_to_utf32(target_string) : utf8_string_to_utf32_lowercased(target_string); if (dfa_type == DfaType::Implicit) { if (max_edits == 1) { - return LevenshteinDfa(std::make_unique<ImplicitLevenshteinDfa<FixedMaxEditDistanceTraits<1>>>(std::move(target_string_u32), is_cased)); + return LevenshteinDfa(std::make_unique<ImplicitLevenshteinDfa<FixedMaxEditDistanceTraits<1>>>(std::move(target_string_u32), is_cased, is_prefix)); } else { // max_edits == 2 - return LevenshteinDfa(std::make_unique<ImplicitLevenshteinDfa<FixedMaxEditDistanceTraits<2>>>(std::move(target_string_u32), is_cased)); + return LevenshteinDfa(std::make_unique<ImplicitLevenshteinDfa<FixedMaxEditDistanceTraits<2>>>(std::move(target_string_u32), is_cased, is_prefix)); } } else if(dfa_type == DfaType::Explicit) { if (max_edits == 1) { - return ExplicitLevenshteinDfaBuilder<FixedMaxEditDistanceTraits<1>>(std::move(target_string_u32), is_cased).build_dfa(); + return ExplicitLevenshteinDfaBuilder<FixedMaxEditDistanceTraits<1>>(std::move(target_string_u32), is_cased, is_prefix).build_dfa(); } else { // max_edits == 2 - return ExplicitLevenshteinDfaBuilder<FixedMaxEditDistanceTraits<2>>(std::move(target_string_u32), is_cased).build_dfa(); + return ExplicitLevenshteinDfaBuilder<FixedMaxEditDistanceTraits<2>>(std::move(target_string_u32), is_cased, is_prefix).build_dfa(); } } else { // DfaType::Table if (max_edits == 1) { - return LevenshteinDfa(std::make_unique<TableDfa<1>>(std::move(target_string_u32), is_cased)); + return LevenshteinDfa(std::make_unique<TableDfa<1>>(std::move(target_string_u32), is_cased, is_prefix)); } else { // max_edits == 2 - return LevenshteinDfa(std::make_unique<TableDfa<2>>(std::move(target_string_u32), is_cased)); + return LevenshteinDfa(std::make_unique<TableDfa<2>>(std::move(target_string_u32), is_cased, is_prefix)); } } } +LevenshteinDfa LevenshteinDfa::build(std::string_view target_string, uint8_t max_edits, Casing casing, DfaType dfa_type) { + return build(target_string, max_edits, casing, dfa_type, Matching::FullString); +} + LevenshteinDfa LevenshteinDfa::build(std::string_view target_string, uint8_t max_edits, Casing casing) { // TODO automatically select implementation based on target length/max edits? // Suggestion: @@ -112,4 +118,12 @@ std::ostream& operator<<(std::ostream& os, LevenshteinDfa::Casing c) { return os; } +std::ostream& operator<<(std::ostream& os, LevenshteinDfa::Matching m) { + switch (m) { + case LevenshteinDfa::Matching::FullString: os << "FullString"; return os; + case LevenshteinDfa::Matching::Prefix: os << "Prefix"; return os; + } + abort(); +} + } diff --git a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.h b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.h index 44c62bdb957..feace39b313 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.h +++ b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_dfa.h @@ -265,6 +265,33 @@ public: Cased }; + enum class Matching { + /** + * Edit distance is computed based on the _entire_ source string. Matching is + * symmetric between source and target strings, i.e. match(x, y) and match(y, x) + * will yield the same result. + */ + FullString, + /** + * Edit distance is computed based on a _prefix_ of the source string, as compared + * against the target string. Matching is therefore _asymmetric_ between source and + * target strings. + * + * Example of matching source strings against the target 'ban' (i.e. the prefix query) + * and 1 max edit distance: + * 'bananas' - 0 edits (source prefix 'ban' exact-matches 'ban') + * 'balloons' - 1 edit ('bal' vs 'ban') + * '2bananas' - 1 edit ('2ban' vs 'ban') + * 'boonanas' - mismatch (2 edits) + * + * Note that Prefix matching will match a lot more strings than FullString, so in + * practice it should be combined with prefix _locking_ to constrain the candidate + * result set to a more reasonable cardinality. In particular, max edits >= |target| + * will match _every_ source string trivially. + */ + Prefix + }; + /** * Builds and returns a Levenshtein DFA that matches all strings within `max_edits` * edits of `target_string`. The type of DFA returned is specified by dfa_type. @@ -274,6 +301,9 @@ public: * `target_string` must not contain any null UTF-8 chars. */ [[nodiscard]] static LevenshteinDfa build(std::string_view target_string, uint8_t max_edits, + Casing casing, DfaType dfa_type, Matching matching); + + [[nodiscard]] static LevenshteinDfa build(std::string_view target_string, uint8_t max_edits, Casing casing, DfaType dfa_type); /** @@ -301,5 +331,6 @@ public: std::ostream& operator<<(std::ostream& os, const LevenshteinDfa::MatchResult& mos); std::ostream& operator<<(std::ostream& os, LevenshteinDfa::DfaType dt); std::ostream& operator<<(std::ostream& os, LevenshteinDfa::Casing c); +std::ostream& operator<<(std::ostream& os, LevenshteinDfa::Matching m); } diff --git a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.cpp b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.cpp index 4658635d880..f5b8d0fc0b8 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.cpp +++ b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.cpp @@ -3,31 +3,46 @@ #include "levenshtein_distance.h" +#include <cassert> #include <limits> #include <vector> +namespace vespalib { + std::optional<uint32_t> -vespalib::LevenshteinDistance::calculate(std::span<const uint32_t> left, std::span<const uint32_t> right, uint32_t threshold) +LevenshteinDistance::calculate(std::span<const uint32_t> left, std::span<const uint32_t> right, + uint32_t threshold, bool prefix_match) { + assert(left.size() <= static_cast<size_t>(INT32_MAX)); + assert(right.size() <= static_cast<size_t>(INT32_MAX)); + threshold = std::min(threshold, static_cast<uint32_t>(std::numeric_limits<int32_t>::max())); uint32_t n = left.size(); uint32_t m = right.size(); - if (n > m) { - return calculate(right, left, threshold); - } - - // if one string is empty, the edit distance is necessarily the length - // of the other - if (n == 0) { - return m <= threshold ? std::optional(m) : std::nullopt; - } - if (m == 0) { - return n <= threshold ? std::optional(n) : std::nullopt; - } - - // the edit distance cannot be less than the length difference - if (m - n > threshold) { - return std::nullopt; + if (!prefix_match) { + // These optimizations are only valid when matching with target/source string symmetry. + // Correctness of the main matrix calculation loop should not depend on these. + if (n > m) { + return calculate(right, left, threshold, false); + } + // if one string is empty, the edit distance is necessarily the length + // of the other. + if (n == 0) { + return m <= threshold ? std::optional(m) : std::nullopt; + } + if (m == 0) { + return n <= threshold ? std::optional(n) : std::nullopt; + } + // the edit distance cannot be less than the length difference + if (m - n > threshold) { + return std::nullopt; + } + } else { + // A source (right) cannot be transformed into a target prefix (left) if doing + // so would require inserting more than max edits number of characters. + if ((n > m) && (n - m > threshold)) { + return std::nullopt; + } } std::vector<uint32_t> p(n+1); // 'previous' cost array, horizontally @@ -48,6 +63,7 @@ vespalib::LevenshteinDistance::calculate(std::span<const uint32_t> left, std::sp } // iterates through t + uint32_t min_edits = n; // prefix matching: worst-case to transform to target for (uint32_t j = 1; j <= m; ++j) { uint32_t rightJ = right[j - 1]; // jth character of right d[0] = j; @@ -56,9 +72,9 @@ vespalib::LevenshteinDistance::calculate(std::span<const uint32_t> left, std::sp uint32_t max = j > std::numeric_limits<uint32_t>::max() - threshold ? n : std::min(n, j + threshold); - // ignore entry left of leftmost if (min > 1) { + assert(static_cast<size_t>(min) <= d.size()); d[min - 1] = std::numeric_limits<uint32_t>::max(); } @@ -76,12 +92,35 @@ vespalib::LevenshteinDistance::calculate(std::span<const uint32_t> left, std::sp lowerBound = std::min(lowerBound, d[i]); } if (lowerBound > threshold) { - return std::nullopt; + if (!prefix_match) { + return std::nullopt; // Cannot match + } else { + break; // May already have matched via min_edits + } } std::swap(p, d); + // For prefix matching: + // By definition, the Levenshtein matrix cell at row `i`, column `j` + // provides the minimum number of edits required to transform a prefix of + // source string S (up to and including length `i`) into a prefix of target + // string T (up to and including length `j`). Since we want to match against + // the entire target (prefix query) string with length `n`, the problem is + // reduced to finding the minimum value of the `n`th column that is `<= k` + // (aggregated here and checked after the loop). + min_edits = std::min(p[n], min_edits); } - if (p[n] <= threshold) { + if (prefix_match) { + return ((min_edits <= threshold) ? std::optional<uint32_t>{min_edits} : std::nullopt); + } else if (p[n] <= threshold) { return {p[n]}; } return std::nullopt; } + +std::optional<uint32_t> +LevenshteinDistance::calculate(std::span<const uint32_t> left, std::span<const uint32_t> right, uint32_t threshold) +{ + return calculate(left, right, threshold, false); +} + +} // vespalib diff --git a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.h b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.h index f105dcdaaf4..e284e071731 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.h +++ b/vespalib/src/vespa/vespalib/fuzzy/levenshtein_distance.h @@ -19,7 +19,15 @@ namespace vespalib { */ class LevenshteinDistance { public: - static std::optional<uint32_t> calculate(std::span<const uint32_t> left, std::span<const uint32_t> right, uint32_t threshold); + // Iff `prefix_match` == true, `right` is the candidate to match against prefix `left` + static std::optional<uint32_t> calculate(std::span<const uint32_t> left, + std::span<const uint32_t> right, + uint32_t threshold, + bool prefix_match); + + static std::optional<uint32_t> calculate(std::span<const uint32_t> left, + std::span<const uint32_t> right, + uint32_t threshold); }; } diff --git a/vespalib/src/vespa/vespalib/fuzzy/match_algorithm.hpp b/vespalib/src/vespa/vespalib/fuzzy/match_algorithm.hpp index 388099a0358..e8b1bb5b415 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/match_algorithm.hpp +++ b/vespalib/src/vespa/vespalib/fuzzy/match_algorithm.hpp @@ -25,11 +25,14 @@ struct MatchAlgorithm { static constexpr uint8_t max_edits() noexcept { return MaxEdits; } /** - * Matches UTF-8 source string `source` against the target DFA, optionally generating + * Matches UTF-8/32 source string `source` against the target DFA, optionally generating * the successor string iff the source string is not within the maximum number of edits * of the target string. * - * The actual match loop is very simple: we try to match the DFA as far as we can + * The actual match loop is very simple, but with some subtle differences in semantics + * depending on whether the "full string" or "prefix" matching mode is used. + * + * For the full string matching mode, we try to match the DFA as far as we can * before either consuming all input (source string) characters or ending up in a non- * matching state before we have consumed all input. In the former case, we may be in * a matching state (consider matching "foo" with the target string "food"; after @@ -39,6 +42,15 @@ struct MatchAlgorithm { * If we end up in a matching state, all is well. We simply return a MatchResult with * the number of edits the state represents. * + * Prefix matching is very similar, but since we're interested in the number of edits + * required to transform a _prefix_ of the source into the target string, we cannot + * require matching the entire source string in the case that it is longer than the + * target (as that would not just be a prefix, after all). We consider a source prefix + * to be matched if _any_ DFA state is a match. This may be the initial state. + * Since the first match might not yield the minimum edit distance, we traverse the + * DFA until it no longer matches and return the smallest encountered distance as the + * final result. + * * The interesting bit happens the string does _not_ match and we are asked to provide a * _successor_ string that _does_ match and is strictly greater in lexicographic order. * @@ -143,6 +155,18 @@ struct MatchAlgorithm { * successor "foyd" (and _not_ "FOyd"), as the latter would imply a completely different * ordering when compared byte-wise against an implicitly lowercased dictionary. * + * The successor generation algorithm generalizes without changes to work as expected + * when prefix matching is used. This is because the target string represents the + * prefix and the successor consequently represents the smallest possible greater prefix. + * + * Proof by contradiction: S is a source string that does _not_ prefix match target + * string T, and S' is the returned successor. Assume that discarding (skipping) all + * candidate source strings C with S < C < S' misses at least one such candidate C' + * that has a prefix matching T. This means that it must be possible to traverse the + * DFA with source string C' and end up in a matching state. But by definition the + * successor S' is the smallest possible lexicographically greater string that can + * possibly match the DFA for T; a contradiction. + * * TODO let matcher know if source string is pre-normalized (i.e. lowercased). */ template <DfaMatcher Matcher, typename SuccessorT> @@ -158,6 +182,9 @@ struct MatchAlgorithm { StateType state = matcher.start(); while (u8_reader.hasMore()) { + if (matcher.is_prefix() && matcher.is_match(state)) { + return minimal_matching_prefix_distance(matcher, state, u8_reader); + } const auto pos_before_char = static_cast<uint32_t>(successor_out.size()); const uint32_t raw_mch = u8_reader.getChar(); const uint32_t mch = normalized_match_char(raw_mch, matcher.is_cased()); @@ -198,6 +225,9 @@ struct MatchAlgorithm { Utf8Reader u8_reader(source.data(), source.size()); StateType state = matcher.start(); while (u8_reader.hasMore()) { + if (matcher.is_prefix() && matcher.is_match(state)) { + return minimal_matching_prefix_distance(matcher, state, u8_reader); + } const uint32_t mch = normalized_match_char(u8_reader.getChar(), matcher.is_cased()); auto maybe_next = matcher.match_input(state, mch); if (matcher.can_match(maybe_next)) { @@ -214,6 +244,41 @@ struct MatchAlgorithm { } /** + * Follows the DFA (in an already matching state) until it no longer matches, keeping + * track of the minimum edit distance encountered. This is used to compute the minimum + * number of edits during prefix matching, as just returning the edit distance of the + * _first_ matching state may not result in the minimum. + * + * Example 1: matching the source string 'bananas' against the prefix target 'ban' with + * max edits 2 will be in a matching state already after consuming 'b' (can append 2 + * characters after), but had we processed the remaining characters we would end up with + * the actual prefix edit distance of 0. + * + * Example 2: matching the source string 'abcdef' against target 'acd' with max edits 2 + * will be in a matching state after 'a' (2 edits), but the minimal edit prefix is 'abcd' + * (1 edit). This demonstrates that we may have to process more than |target| number of + * source characters to get a minimal distance. + */ + template <DfaMatcher Matcher> + static MatchResult minimal_matching_prefix_distance(const Matcher& matcher, + typename Matcher::StateType state, + Utf8Reader& u8_reader) + { + auto min_edits = matcher.match_edit_distance(state); + while (u8_reader.hasMore()) { + const uint32_t mch = normalized_match_char(u8_reader.getChar(), matcher.is_cased()); + auto maybe_next = matcher.match_input(state, mch); + if (matcher.can_match(maybe_next)) { + state = maybe_next; + min_edits = std::min(min_edits, matcher.match_edit_distance(state)); + } else { + break; + } + } + return MatchResult::make_match(max_edits(), min_edits); + } + + /** * Instantly backtrack to the last possible branching point in the DFA where we can * choose some higher outgoing edge character value and still match the DFA. If the node * has a wildcard edge, we can bump the input char by one and generate the smallest diff --git a/vespalib/src/vespa/vespalib/fuzzy/table_dfa.h b/vespalib/src/vespa/vespalib/fuzzy/table_dfa.h index 4ad203c9a46..a15f321f32d 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/table_dfa.h +++ b/vespalib/src/vespa/vespalib/fuzzy/table_dfa.h @@ -46,12 +46,13 @@ public: private: const std::vector<Lookup> _lookup; const bool _is_cased; + const bool _is_prefix; static std::vector<Lookup> make_lookup(const std::vector<uint32_t> &str); public: using MatchResult = LevenshteinDfa::MatchResult; - TableDfa(std::vector<uint32_t> str, bool is_cased); + TableDfa(std::vector<uint32_t> str, bool is_cased, bool is_prefix); ~TableDfa() override; [[nodiscard]] MatchResult match(std::string_view source) const override; [[nodiscard]] MatchResult match(std::string_view source, std::string& successor_out) const override; diff --git a/vespalib/src/vespa/vespalib/fuzzy/table_dfa.hpp b/vespalib/src/vespa/vespalib/fuzzy/table_dfa.hpp index e7c721f644e..721cfe296d2 100644 --- a/vespalib/src/vespa/vespalib/fuzzy/table_dfa.hpp +++ b/vespalib/src/vespa/vespalib/fuzzy/table_dfa.hpp @@ -353,11 +353,13 @@ struct TableMatcher { const TableDfa<N>::Lookup *lookup; const uint32_t end; const bool cased; + const bool prefix; - TableMatcher(const TableDfa<N>::Lookup *lookup_in, uint32_t end_in, bool cased_in) - noexcept : lookup(lookup_in), end(end_in), cased(cased_in) {} + TableMatcher(const TableDfa<N>::Lookup *lookup_in, uint32_t end_in, bool cased_in, bool prefix_in) + noexcept : lookup(lookup_in), end(end_in), cased(cased_in), prefix(prefix_in) {} bool is_cased() const noexcept { return cased; } + bool is_prefix() const noexcept { return prefix; } static constexpr S start() noexcept { return S::start(); } uint8_t match_edit_distance(S s) const noexcept { return s.edits(end); } @@ -473,9 +475,10 @@ TableDfa<N>::make_lookup(const std::vector<uint32_t> &str)->std::vector<Lookup> } template <uint8_t N> -TableDfa<N>::TableDfa(std::vector<uint32_t> str, bool is_cased) +TableDfa<N>::TableDfa(std::vector<uint32_t> str, bool is_cased, bool is_prefix) : _lookup(make_lookup(str)), - _is_cased(is_cased) + _is_cased(is_cased), + _is_prefix(is_prefix) { } @@ -486,7 +489,7 @@ template <uint8_t N> LevenshteinDfa::MatchResult TableDfa<N>::match(std::string_view u8str) const { - TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased); + TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased, _is_prefix); return MatchAlgorithm<N>::match(matcher, u8str); } @@ -494,7 +497,7 @@ template <uint8_t N> LevenshteinDfa::MatchResult TableDfa<N>::match(std::string_view u8str, std::string& successor_out) const { - TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased); + TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased, _is_prefix); return MatchAlgorithm<N>::match(matcher, u8str, successor_out); } @@ -502,7 +505,7 @@ template <uint8_t N> LevenshteinDfa::MatchResult TableDfa<N>::match(std::string_view u8str, std::vector<uint32_t>& successor_out) const { - TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased); + TableMatcher<N> matcher(_lookup.data(), _lookup.size() - 1, _is_cased, _is_prefix); return MatchAlgorithm<N>::match(matcher, u8str, successor_out); } diff --git a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp index 5f242059ccf..5f63925bfef 100644 --- a/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp +++ b/vespalib/src/vespa/vespalib/util/binary_hamming_distance.cpp @@ -6,7 +6,7 @@ namespace vespalib { namespace { constexpr uint8_t WORD_SZ = sizeof (uint64_t); - constexpr uint8_t UNROLL_CNT = 2; + constexpr uint8_t UNROLL_CNT = 4; static_assert(sizeof(uint64_t) == 8); } size_t |