Revert moving deleteUnusedDockerImages impl to DockerOperationsImpl

4 files changed, 458 insertions, 8 deletions

diff --git a/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/Docker.java b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/Docker.java
index d31fbd52d96..1729c4843ef 100644
--- a/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/Docker.java
+++ b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/Docker.java
@@ -1,7 +1,6 @@
 // Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 package com.yahoo.vespa.hosted.dockerapi;
 
-import com.github.dockerjava.api.model.Image;
 import com.yahoo.config.provision.DockerImage;
 
 import java.net.InetAddress;
@@ -17,8 +16,6 @@ import java.util.OptionalLong;
  */
 public interface Docker {
 
-    void deleteImage(DockerImage dockerImage);
-
     interface CreateContainerCommand {
         CreateContainerCommand withHostName(String hostname);
         CreateContainerCommand withResources(ContainerResources containerResources);
@@ -87,7 +84,10 @@ public interface Docker {
     /** List all containers, including those not running. */
     List<ContainerLite> listAllContainers();
 
-    List<Image> listAllImages();
+    /**
+     * Deletes the local images that are currently not in use by any container and not recently used.
+     */
+    boolean deleteUnusedDockerImages(List<DockerImage> excludes, Duration minImageAgeToDelete);
 
     /**
      * @param containerName The name of the container
diff --git a/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollector.java b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollector.java
new file mode 100644
index 00000000000..242332ebd54
--- /dev/null
+++ b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollector.java
@@ -0,0 +1,187 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.vespa.hosted.dockerapi;
+
+import com.github.dockerjava.api.model.Container;
+import com.github.dockerjava.api.model.Image;
+import com.google.common.base.Strings;
+import com.yahoo.collections.Pair;
+import com.yahoo.config.provision.DockerImage;
+
+import java.time.Clock;
+import java.time.Duration;
+import java.time.Instant;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.function.Function;
+import java.util.logging.Logger;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+/**
+ * This class keeps track of downloaded docker images and helps delete images that have not been recently used
+ *
+ * <p>Definitions:
+ * <ul>
+ *   <li>Every image has exactly 1 id</li>
+ *   <li>Every image has between 0..n tags, see
+ *       <a href="https://docs.docker.com/engine/reference/commandline/tag/">docker tag</a> for more</li>
+ *   <li>Every image has 0..1 parent ids</li>
+ * </ul>
+ *
+ * <p>Limitations:
+ * <ol>
+ *   <li>Image that has more than 1 tag cannot be deleted by ID</li>
+ *   <li>Deleting a tag of an image with multiple tags will only remove the tag, the image with the
+ *       remaining tags will remain</li>
+ *   <li>Deleting the last tag of an image will delete the entire image.</li>
+ *   <li>Image cannot be deleted if:</li>
+ *   <ol>
+ *     <li>It has 1 or more children</li>
+ *     <li>A container uses it</li>
+ *   </ol>
+ * </ol>
+ *
+ * @author freva
+ */
+class DockerImageGarbageCollector {
+    private static final Logger logger = Logger.getLogger(DockerImageGarbageCollector.class.getName());
+
+    private final Map<String, Instant> lastTimeUsedByImageId = new ConcurrentHashMap<>();
+    private final DockerImpl docker;
+    private final Clock clock;
+
+    DockerImageGarbageCollector(DockerImpl docker) {
+        this(docker, Clock.systemUTC());
+    }
+
+    DockerImageGarbageCollector(DockerImpl docker, Clock clock) {
+        this.docker = docker;
+        this.clock = clock;
+    }
+
+    /**
+     * This method must be called frequently enough to see all containers to know which images are being used
+     *
+     * @param excludes List of images (by tag or id) that should not be deleted regardless of their used status
+     * @param minImageAgeToDelete Minimum duration after which an image can be removed if it has not been used
+     * @return true iff at least 1 image was deleted
+     */
+    boolean deleteUnusedDockerImages(List<DockerImage> excludes, Duration minImageAgeToDelete) {
+        List<Image> images = docker.listAllImages();
+        List<ContainerLite> containers = docker.listAllContainers();
+
+        Map<String, Image> imageByImageId = images.stream().collect(Collectors.toMap(Image::getId, Function.identity()));
+
+        // Find all the ancestors for every local image id, this includes the image id itself
+        Map<String, Set<String>> ancestorsByImageId = images.stream()
+                .map(Image::getId)
+                .collect(Collectors.toMap(
+                        Function.identity(),
+                        imageId -> {
+                            Set<String> ancestors = new HashSet<>();
+                            while (!Strings.isNullOrEmpty(imageId)) {
+                                ancestors.add(imageId);
+                                imageId = Optional.of(imageId).map(imageByImageId::get).map(Image::getParentId).orElse(null);
+                            }
+                            return ancestors;
+                        }
+                ));
+
+        // The set of images that we want to keep is:
+        // 1. The images that were recently used
+        // 2. The images that were explicitly excluded
+        // 3. All of the ancestors of from images in 1 & 2
+        Set<String> imagesToKeep = Stream
+                .concat(
+                        getRecentlyUsedImageIds(images, containers, minImageAgeToDelete).stream(), // 1
+                        dockerImageToImageIds(excludes, images).stream()) // 2
+                .flatMap(imageId -> ancestorsByImageId.getOrDefault(imageId, Collections.emptySet()).stream()) // 3
+                .collect(Collectors.toSet());
+
+        // Now take all the images we have locally
+        return imageByImageId.keySet().stream()
+
+                // filter out images we want to keep
+                .filter(imageId -> !imagesToKeep.contains(imageId))
+
+                // Sort images in an order is safe to delete (children before parents)
+                .sorted((o1, o2) -> {
+                    // If image2 is parent of image1, image1 comes before image2
+                    if (imageIsDescendantOf(imageByImageId, o1, o2)) return -1;
+                    // If image1 is parent of image2, image2 comes before image1
+                    else if (imageIsDescendantOf(imageByImageId, o2, o1)) return 1;
+                    // Otherwise, sort lexicographically by image name (For testing)
+                    else return o1.compareTo(o2);
+                })
+
+                // Map back to image
+                .map(imageByImageId::get)
+
+                // Delete image, if successful also remove last usage time to prevent re-download being instantly deleted
+                .peek(image -> {
+                    // Deleting an image by image ID with multiple tags will fail -> delete by tags instead
+                    Optional.ofNullable(image.getRepoTags())
+                            .map(Stream::of)
+                            .orElse(Stream.of(image.getId()))
+                            .forEach(imageReference -> {
+                                logger.info("Deleting unused docker image " + imageReference);
+                                docker.deleteImage(DockerImage.fromString(imageReference));
+                            });
+
+                    lastTimeUsedByImageId.remove(image.getId());
+                })
+                .count() > 0;
+    }
+
+    private Set<String> getRecentlyUsedImageIds(List<Image> images, List<ContainerLite> containers, Duration minImageAgeToDelete) {
+        final Instant now = clock.instant();
+
+        // Add any already downloaded image to the list once
+        images.forEach(image -> lastTimeUsedByImageId.putIfAbsent(image.getId(), now));
+
+        // Update last used time for all current containers
+        containers.forEach(container -> lastTimeUsedByImageId.put(container.imageId(), now));
+
+        // Return list of images that have been used within minImageAgeToDelete
+        return lastTimeUsedByImageId.entrySet().stream()
+                .filter(entry -> Duration.between(entry.getValue(), now).minus(minImageAgeToDelete).isNegative())
+                .map(Map.Entry::getKey)
+                .collect(Collectors.toSet());
+    }
+
+    /**
+     * Attemps to make dockerImages which may be image tags or image ids to image ids. This only works
+     * if the given tag is actually present locally. This is fine, because if it isn't - we can't delete
+     * it, so no harm done.
+     */
+    private Set<String> dockerImageToImageIds(List<DockerImage> dockerImages, List<Image> images) {
+        Map<String, String> imageIdByImageTag = images.stream()
+                .flatMap(image -> Optional.ofNullable(image.getRepoTags())
+                        .map(Stream::of)
+                        .orElseGet(Stream::empty)
+                        .map(repoTag -> new Pair<>(repoTag, image.getId())))
+                .collect(Collectors.toMap(Pair::getFirst, Pair::getSecond));
+
+        return dockerImages.stream()
+                .map(DockerImage::asString)
+                .map(tag -> imageIdByImageTag.getOrDefault(tag, tag))
+                .collect(Collectors.toSet());
+    }
+
+    /**
+     * @return true if ancestor is a parent or grand-parent or grand-grand-parent, etc. of img
+     */
+    private boolean imageIsDescendantOf(Map<String, Image> imageIdToImage, String img, String ancestor) {
+        while (imageIdToImage.containsKey(img)) {
+            img = imageIdToImage.get(img).getParentId();
+            if (img == null) return false;
+            if (ancestor.equals(img)) return true;
+        }
+        return false;
+    }
+}
diff --git a/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImpl.java b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImpl.java
index 42044d08c5c..683c8a98788 100644
--- a/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImpl.java
+++ b/docker-api/src/main/java/com/yahoo/vespa/hosted/dockerapi/DockerImpl.java
@@ -56,6 +56,7 @@ public class DockerImpl implements Docker {
     private final Set<DockerImage> scheduledPulls = new HashSet<>();
 
     private final DockerClient dockerClient;
+    private final DockerImageGarbageCollector dockerImageGC;
     private final CounterWrapper numberOfDockerDaemonFails;
 
     @Inject
@@ -65,6 +66,7 @@ public class DockerImpl implements Docker {
 
     DockerImpl(DockerClient dockerClient, MetricReceiverWrapper metricReceiver) {
         this.dockerClient = dockerClient;
+        this.dockerImageGC = new DockerImageGarbageCollector(this);
 
         Dimensions dimensions = new Dimensions.Builder().add("role", "docker").build();
         numberOfDockerDaemonFails = metricReceiver.declareCounter(MetricReceiverWrapper.APPLICATION_DOCKER, dimensions, "daemon.api_fails");
@@ -310,8 +312,7 @@ public class DockerImpl implements Docker {
         }
     }
 
-    @Override
-    public List<Image> listAllImages() {
+    List<Image> listAllImages() {
         try {
             return dockerClient.listImagesCmd().withShowAll(true).exec();
         } catch (RuntimeException e) {
@@ -320,8 +321,7 @@ public class DockerImpl implements Docker {
         }
     }
 
-    @Override
-    public void deleteImage(DockerImage dockerImage) {
+    void deleteImage(DockerImage dockerImage) {
         try {
             dockerClient.removeImageCmd(dockerImage.asString()).exec();
         } catch (NotFoundException ignored) {
@@ -332,6 +332,11 @@ public class DockerImpl implements Docker {
         }
     }
 
+    @Override
+    public boolean deleteUnusedDockerImages(List<DockerImage> excludes, Duration minImageAgeToDelete) {
+        return dockerImageGC.deleteUnusedDockerImages(excludes, minImageAgeToDelete);
+    }
+
     private class ImagePullCallback extends PullImageResultCallback {
         private final DockerImage dockerImage;
 
diff --git a/docker-api/src/test/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollectionTest.java b/docker-api/src/test/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollectionTest.java
new file mode 100644
index 00000000000..520f8a74d58
--- /dev/null
+++ b/docker-api/src/test/java/com/yahoo/vespa/hosted/dockerapi/DockerImageGarbageCollectionTest.java
@@ -0,0 +1,258 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.vespa.hosted.dockerapi;
+
+import com.fasterxml.jackson.annotation.JsonProperty;
+import com.fasterxml.jackson.core.JsonProcessingException;
+import com.fasterxml.jackson.databind.ObjectMapper;
+import com.github.dockerjava.api.model.Image;
+import com.yahoo.config.provision.DockerImage;
+import com.yahoo.test.ManualClock;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.time.Duration;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
+
+import static org.mockito.Matchers.any;
+import static org.mockito.Matchers.eq;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.when;
+
+/**
+ * @author freva
+ */
+public class DockerImageGarbageCollectionTest {
+
+    private final ImageGcTester gcTester = new ImageGcTester();
+
+    @Test
+    public void noImagesMeansNoUnusedImages() {
+        gcTester.withExistingImages()
+                .expectDeletedImages();
+    }
+
+    @Test
+    public void singleImageWithoutContainersIsUnused() {
+        gcTester.withExistingImages(new ImageBuilder("image-1"))
+                // Even though nothing is using the image, we will keep it for at least 1h
+                .expectDeletedImagesAfterMinutes(0)
+                .expectDeletedImagesAfterMinutes(30)
+                .expectDeletedImagesAfterMinutes(30, "image-1");
+    }
+
+    @Test
+    public void singleImageWithContainerIsUsed() {
+        gcTester.withExistingImages(ImageBuilder.forId("image-1"))
+                .andExistingContainers(new ContainerLite("container-1", "image-1", "running"))
+                .expectDeletedImages();
+    }
+
+    @Test
+    public void multipleUnusedImagesAreIdentified() {
+        gcTester.withExistingImages(
+                        ImageBuilder.forId("image-1"),
+                        ImageBuilder.forId("image-2"))
+                .expectDeletedImages("image-1", "image-2");
+    }
+
+    @Test
+    public void multipleUnusedLeavesAreIdentified() {
+        gcTester.withExistingImages(
+                        ImageBuilder.forId("parent-image"),
+                        ImageBuilder.forId("image-1").withParentId("parent-image"),
+                        ImageBuilder.forId("image-2").withParentId("parent-image"))
+                .expectDeletedImages("image-1", "image-2", "parent-image");
+    }
+
+    @Test
+    public void unusedLeafWithUsedSiblingIsIdentified() {
+        gcTester.withExistingImages(
+                        ImageBuilder.forId("parent-image"),
+                        ImageBuilder.forId("image-1").withParentId("parent-image").withTags("latest"),
+                        ImageBuilder.forId("image-2").withParentId("parent-image").withTags("1.24"))
+                .andExistingContainers(new ContainerLite("vespa-node-1", "image-1", "running"))
+                .expectDeletedImages("1.24"); // Deleting the only tag will delete the image
+    }
+
+    @Test
+    public void unusedImagesWithMultipleTags() {
+        gcTester.withExistingImages(
+                        ImageBuilder.forId("parent-image"),
+                        ImageBuilder.forId("image-1").withParentId("parent-image")
+                                .withTags("vespa-6", "vespa-6.28", "vespa:latest"))
+                .expectDeletedImages("vespa-6", "vespa-6.28", "vespa:latest", "parent-image");
+    }
+
+    @Test
+    public void taggedImageWithNoContainersIsUnused() {
+        gcTester.withExistingImages(ImageBuilder.forId("image-1").withTags("vespa-6"))
+                .expectDeletedImages("vespa-6");
+    }
+
+    @Test
+    public void unusedImagesWithSimpleImageGc() {
+        gcTester.withExistingImages(ImageBuilder.forId("parent-image"))
+                .expectDeletedImagesAfterMinutes(30)
+                .withExistingImages(
+                        ImageBuilder.forId("parent-image"),
+                        ImageBuilder.forId("image-1").withParentId("parent-image"))
+                .expectDeletedImagesAfterMinutes(0)
+                .expectDeletedImagesAfterMinutes(30)
+                // At this point, parent-image has been unused for 1h, but image-1 depends on parent-image and it has
+                // only been unused for 30m, so we cannot delete parent-image yet. 30 mins later both can be removed
+                .expectDeletedImagesAfterMinutes(30, "image-1", "parent-image");
+    }
+
+    @Test
+    public void reDownloadingImageIsNotImmediatelyDeleted() {
+        gcTester.withExistingImages(ImageBuilder.forId("image"))
+                .expectDeletedImages("image") // After 1h we delete image
+                .expectDeletedImagesAfterMinutes(0) // image is immediately re-downloaded, but is not deleted
+                .expectDeletedImagesAfterMinutes(10)
+                .expectDeletedImages("image"); // 1h after re-download it is deleted again
+    }
+
+    @Test
+    public void reDownloadingImageIsNotImmediatelyDeletedWhenDeletingByTag() {
+        gcTester.withExistingImages(ImageBuilder.forId("image").withTags("image-1", "my-tag"))
+                .expectDeletedImages("image-1", "my-tag") // After 1h we delete image
+                .expectDeletedImagesAfterMinutes(0) // image is immediately re-downloaded, but is not deleted
+                .expectDeletedImagesAfterMinutes(10)
+                .expectDeletedImages("image-1", "my-tag"); // 1h after re-download it is deleted again
+    }
+
+    /** Same scenario as in {@link #multipleUnusedImagesAreIdentified()} */
+    @Test
+    public void doesNotDeleteExcludedByIdImages() {
+        gcTester.withExistingImages(
+                    ImageBuilder.forId("parent-image"),
+                    ImageBuilder.forId("image-1").withParentId("parent-image"),
+                    ImageBuilder.forId("image-2").withParentId("parent-image"))
+                // Normally, image-1 and parent-image should also be deleted, but because we exclude image-1
+                // we cannot delete parent-image, so only image-2 is deleted
+                .expectDeletedImages(Collections.singletonList("image-1"), "image-2");
+    }
+
+    /** Same as in {@link #doesNotDeleteExcludedByIdImages()} but with tags */
+    @Test
+    public void doesNotDeleteExcludedByTagImages() {
+        gcTester.withExistingImages(
+                    ImageBuilder.forId("parent-image").withTags("rhel-6"),
+                    ImageBuilder.forId("image-1").withParentId("parent-image").withTags("vespa:6.288.16"),
+                    ImageBuilder.forId("image-2").withParentId("parent-image").withTags("vespa:6.289.94"))
+                .expectDeletedImages(Collections.singletonList("vespa:6.288.16"), "vespa:6.289.94");
+    }
+
+    @Test
+    public void exludingNotDownloadedImageIsNoop() {
+        gcTester.withExistingImages(
+                    ImageBuilder.forId("parent-image").withTags("rhel-6"),
+                    ImageBuilder.forId("image-1").withParentId("parent-image").withTags("vespa:6.288.16"),
+                    ImageBuilder.forId("image-2").withParentId("parent-image").withTags("vespa:6.289.94"))
+                .expectDeletedImages(Collections.singletonList("vespa:6.300.1"), "vespa:6.288.16", "vespa:6.289.94", "rhel-6");
+    }
+
+    private class ImageGcTester {
+        private final DockerImpl docker = mock(DockerImpl.class);
+        private final ManualClock clock = new ManualClock();
+        private final DockerImageGarbageCollector imageGC = new DockerImageGarbageCollector(docker, clock);
+        private final Map<DockerImage, Integer> numDeletes = new HashMap<>();
+        private boolean initialized = false;
+
+        private ImageGcTester withExistingImages(ImageBuilder... images) {
+            when(docker.listAllImages()).thenReturn(Arrays.stream(images)
+                    .map(ImageBuilder::toImage)
+                    .collect(Collectors.toList()));
+            return this;
+        }
+
+        private ImageGcTester andExistingContainers(ContainerLite... containers) {
+            when(docker.listAllContainers()).thenReturn(List.of(containers));
+            return this;
+        }
+
+        private ImageGcTester expectDeletedImages(String... imageIds) {
+            return expectDeletedImagesAfterMinutes(60, imageIds);
+        }
+
+        private ImageGcTester expectDeletedImages(List<String> except, String... imageIds) {
+            return expectDeletedImagesAfterMinutes(60, except, imageIds);
+        }
+        private ImageGcTester expectDeletedImagesAfterMinutes(int minutesAfter, String... imageIds) {
+            return expectDeletedImagesAfterMinutes(minutesAfter, Collections.emptyList(), imageIds);
+        }
+
+        private ImageGcTester expectDeletedImagesAfterMinutes(int minutesAfter, List<String> except, String... imageIds) {
+            if (!initialized) {
+                // Run once with a very long expiry to initialize internal state of existing images
+                imageGC.deleteUnusedDockerImages(Collections.emptyList(), Duration.ofDays(999));
+                initialized = true;
+            }
+
+            clock.advance(Duration.ofMinutes(minutesAfter));
+
+            imageGC.deleteUnusedDockerImages(
+                    except.stream().map(DockerImage::fromString).collect(Collectors.toList()),
+                    Duration.ofHours(1).minusSeconds(1));
+
+            Arrays.stream(imageIds)
+                    .map(DockerImage::fromString)
+                    .forEach(image -> {
+                        int newValue = numDeletes.getOrDefault(image, 0) + 1;
+                        numDeletes.put(image, newValue);
+                        verify(docker, times(newValue)).deleteImage(eq(image));
+                    });
+
+            verify(docker, times(numDeletes.values().stream().mapToInt(i -> i).sum())).deleteImage(any());
+            return this;
+        }
+    }
+
+    /**
+     * Serializes object to a JSON string using Jackson, then deserializes it to an instance of toClass
+     * (again using Jackson). This can be used to create Jackson classes with no public constructors.
+     * @throws IllegalArgumentException if Jackson fails to serialize or deserialize.
+     */
+    private static <T> T createFrom(Class<T> toClass, Object object) throws IllegalArgumentException {
+        final String serialized;
+        try {
+            serialized = new ObjectMapper().writeValueAsString(object);
+        } catch (JsonProcessingException e) {
+            throw new IllegalArgumentException("Failed to serialize object " + object + " to "
+                    + toClass + " with Jackson: " + e, e);
+        }
+        try {
+            return new ObjectMapper().readValue(serialized, toClass);
+        } catch (IOException e) {
+            throw new IllegalArgumentException("Failed to convert " + serialized + " to "
+                    + toClass + " with Jackson: " + e, e);
+        }
+    }
+
+    // Workaround for Image class that can't be instantiated directly in Java (instantiate via Jackson instead).
+    private static class ImageBuilder {
+        // Json property names must match exactly the property names in the Image class.
+        @JsonProperty("Id")
+        private final String id;
+
+        @JsonProperty("ParentId")
+        private String parentId = ""; // docker-java returns empty string and not null if the parent is not present
+
+        @JsonProperty("RepoTags")
+        private String[] repoTags = null;
+
+        private ImageBuilder(String id) { this.id = id; }
+
+        private static ImageBuilder forId(String id) { return new ImageBuilder(id); }
+        private ImageBuilder withParentId(String parentId) { this.parentId = parentId; return this; }
+        private ImageBuilder withTags(String... tags) { this.repoTags = tags; return this; }
+        private Image toImage() { return createFrom(Image.class, this); }
+    }
+}