Page 2

Last time out, I was desperately trying to understand why my beautifully crafted page-aware lazy loading S3 list objects function was fetching more pages than it actually needed to fulfil my requirements (doesn't sound very lazy to me!), but to no avail. If you cast your mind back, I had set my page size to 50, and was taking 105 objects:

(comment

  (->> (list-objects logs-client prefix)
       (take 105))
  ;; => ("logs/E1HJS54CQLFQU4.2022-09-15-00.0125de6e.gz"
  ;;     "logs/E1HJS54CQLFQU4.2022-09-15-00.3b36a099.gz"
  ;;     ...
  ;;     "logs/E1HJS54CQLFQU4.2022-09-15-10.ae86e512.gz"
  ;;     "logs/E1HJS54CQLFQU4.2022-09-15-10.b4a720f9.gz")

)

But sadly seeing the following in my REPL buffer:

Fetching page 1
Fetching page 2
Fetching page 3
Fetching page 4

I know that some lazy sequences in Clojure realise in chunks, but those chunks are usually realised 32 at a time in my experience. It is actually absurdly hard to find any documentation that explains exactly how chunking works, but one can gather hints here and there from the dusty corners of the web's ancient past:

Laziness and chunking in Clojure - 2016
Clojure: Not so lazy sequences a.k.a chunking behaviour - 2014
De-chunkifying Sequences in Clojure - 2010

They all mention the number 32 (holiest of all powers of 2, clearly), and the first one even suggests looking at the implementation of clojure.core/map and seeing that map calls the magic chunk-first, which "takes 32 elements for performance reasons". Spelunking deeper into the source for the definition of chunk-first leads one to the following lines:

(defn ^:static  ^clojure.lang.IChunk chunk-first ^clojure.lang.IChunk [^clojure.lang.IChunkedSeq s]
  (.chunkedFirst s))

Which leads to Clojure's Java implementation, which leads to me reading a couple of the classes that implement the IChunk interface, looking for some mention of the chunk size, and running away in tears.

The funny thing about all of this is that I know that one is not supposed to use functions with side effects when processing lazy sequences. In fact, it says exactly that in the docstring for clojure.core/iterate:

(iterate f x)

Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of
side-effects.

But I figured that it would "probably be fine for this use case." 😂

Having received my well-deserved comeuppance—albeit not completely understanding the form said comeuppance is taking—it's time to figure out how to lazily page without chunking. As luck would have it, right after I published my previous post, I opened up Planet Clojure in my RSS reader and saw a post by Abhinav Omprakash on "Clojure's Iteration function ". According to the post, Clojure has a function called iteration, and:

One of the most common use cases for iteration is making paginated api calls.

OK, this looks interesting. Why in the world didn't I know about this? Well, Abhinav's post links to a post on the JUXT blog called "The new Clojure iteration function" (written by the irrepressible Renzo Borgatti!) wherein it is revealed that iteration is new in Clojure 1.11. In the post's introduction, Renzo mentions:

the problem of dealing with batched API calls, those requiring the consumer a "token" from the previous invocation to be able to proceed to the next. This behaviour is very popular in API interfaces such as AWS S3, where the API needs to protect against the case of a client requesting the content of a bucket with millions of objects in it.

He goes on to make a bold claim:

In the past, Clojure developers dealing with paginated APIs have been solving the same problem over and over. The problem is to create some layer that hides away the need of knowing about the presence of pagination and provides the seqable or reducible abstraction we are all familiar with. It is then up to the user of such abstractions to decide if they want to eagerly load many objects or consume them lazily, without any need to know how many requests are necessary or how the pagination mechanism works.

OK, I buy this, having solved this problem in many sub-optimal ways over the years. So iteration really sounds like what I want here. Let's see if I can modify my code based on the iterate function to use iteration instead. Here's what I ended up with last time:

(defn get-s3-page [{:keys [s3-client s3-bucket s3-page-size]}
                   prefix prev]
  (let [{token :NextContinuationToken
         truncated? :IsTruncated
         page-num :page-num} prev
        page-num (if page-num (inc page-num) 1)
        done? (false? truncated?)
        res (when-not done?
              (println "Fetching page" page-num)
              (-> (aws/invoke s3-client
                              {:op :ListObjectsV2
                               :request (mk-s3-req s3-bucket prefix s3-page-size token)})
                  (assoc :page-num page-num)))]
    res))

(defn s3-page-iterator [logs-client prefix]
  (partial get-s3-page logs-client prefix))

(defn list-objects [logs-client prefix]
  (->> (iterate (s3-page-iterator logs-client prefix) nil)
       (drop 1)
       (take-while :Contents)
       (mapcat (comp (partial map :Key) :Contents))))

The JUXT post helpfully walks through an example of listing objects in an S3 bucket, which is exactly what I'm doing, but unhelpfully bases the example on Amazonica (an excellent Clojure wrapper around the AWS Java SDK that I used for years until some cool kids from Nubank told me that all the cool kids were now using Cognitect's aws-api, and I wanted to be cool like them, so I decided to use it for my next thing, which turned out to be a great decision since my next thing was Blambda, which runs on Babashka, which can't use the AWS Java SDK anyway).

Where was I? Oh yeah, the JUXT blog. So it breaks down the arguments to iteration:

(iteration step & {:keys [somef vf kf initk]
                   :or {vf identity
                        kf identity
                        somef some?
                        initk nil}})

step is a function of the next marker token. This function should contain the logic for making a request to the S3 API (or other relevant paginated API) passing the given token.
somef is a function that applied to the return of (step token) returns true or false based on the fact that the response contains results or not, respectively.
vf is a function that applied to the return of (step token) returns the items from the current response page.
kf is a function that applied to the return of (step token) returns the next marker token if one is available.
initk is an initial value for the marker.

Looking at this, my get-s3-page function sounds a lot like step, in that it contains the logic for making a request to S3. However, step is a function taking one argument, and get-s3-page takes three, so clearly it can't be used it as is. But the same was actually true for my previous attempt at paging that used iterate, and in fact I wrote a function to take care of this:

(defn s3-page-iterator [logs-client prefix]
  (partial get-s3-page logs-client prefix))

s3-page-iterator closes over the client and the prefix and returns a function that takes only one argument: prev, which is the previous page of results from S3. So that's step sorted!

In order to figure out what functions I need for somef, vf, and kf (gotta love the terse names of variables in clojure.core!), I need to look at what get-s3-page returns, since all three of those functions operate on the return value of (step token):

(comment

  (->> (get-s3-page logs-client "logs/A1BCD23EFGHIJ4.2022-09-26-" nil)
       keys)
  ;; => (:Prefix
  ;;     :NextContinuationToken
  ;;     :Contents
  ;;     :MaxKeys
  ;;     :IsTruncated
  ;;     :Name
  ;;     :KeyCount
  ;;     :page-num)

)

I'll tackle vf and kf first, since they are pretty straightforward. vf needs to return the items from the current response page. Those items live in the map returned by get-s3-page under the :Contents key, and since keywords are functions that when called with a map, look themselves up in the map, I can use the :Contents keyword as my vf! 🎉

kf returns the next token, which I have in the response as :NextContinuationToken, so it sounds like I should use that for kf. The only problem is that the second invocation of my step function will look like this:

(step (:NextContinuationToken response))

and get-s3-page expects prev to be the response itself, from which it knows how to extract the token all by itself. So I want to just pass the response to my function as-is, and luckily, Clojure has a function for that: identity, which returns its argument unchanged.

Now it's time to look at somef, a function that returns true if the response contains results and false otherwise. In my case, get-s3-page makes a request to the S3 API and returns the response unless the previous response wasn't truncated, in which case it returns nil. So what I want for somef is a function that returns true for any non-nil value, which is exactly what clojure.core/some? does (not to be confused with clojure.core/some).

Now that somef, vf, and kf are sorted, I'll turn my roving eye to initk, which is the initial value for the token passed to my step function. Just like in my previous attempt, I can use nil as the initial argument.

So putting this all together, my new list-objects function would look like this:

(defn list-objects [logs-client prefix]
  (->> (iteration (s3-page-iterator logs-client prefix)
                  :vf :Contents
                  :kf identity
                  :somef some?
                  :initk nil)
       (mapcat (partial map :Key))))

Looks good, lemme test it out!

(comment

  (->> (list-objects logs-client prefix)
       (take 5))
  ;; => ("logs/A1BCD23EFGHIJ4.2022-09-25-00.0187bda9.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.0e46ca54.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.348fa655.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.4345d6ea.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.63005d64.gz")

)

Nice! Except for one thing. My REPL buffer reveals that I actually haven't fixed the problem I set out to fix:

Fetching page 1
Fetching page 2
Fetching page 3
Fetching page 4

Looks like I should have read a little further in the JUXT blog article, because Renzo explains exactly what's happening here:

The results of calling [get-s3-page] are batched items as a collection of collections. In general, we need to collapse the batches into a single sequence and process them one by one [...]
Surprisingly, accessing the [first 5 items from] the first page produces additional network calls for pages well ahead of what we currently need. This is an effect of using [mapcat, which always evaluates the first 4 > arguments]!
The reader should understand that this is not a problem of iteration itself, but more about the need to concatenate the results back for processing maintaining laziness in place.

Renzo being Renzo, of course he has a solution to this:

(defn lazy-concat [colls]
  (lazy-seq
   (when-first [c colls]
     (lazy-cat c (lazy-concat (rest colls))))))

I can fold this into my list-objects function:

(defn list-objects [logs-client prefix]
  (->> (iteration (s3-page-iterator logs-client prefix)
                  :vf :Contents
                  :kf identity
                  :somef some?
                  :initk nil)
       lazy-concat
       (map :Key)))

Since lazy-concat is sewing the lists returned by iteration together, I don't need the chunktacular mapcat anymore; I can just use regular old map. Let's see if this works:

(comment

  (->> (list-objects logs-client prefix)
       (take 5))
  ;; => ("logs/A1BCD23EFGHIJ4.2022-09-25-00.0187bda9.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.0e46ca54.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.348fa655.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.4345d6ea.gz"
  ;;     "logs/A1BCD23EFGHIJ4.2022-09-25-00.63005d64.gz")

)

And the REPL buffer?

Fetching page 1

Amazing!

There's one last thing that's bugging me, though. If I look back at the docs for iteration, I see that it has some default arguments:

(iteration step & {:keys [somef vf kf initk]
                   :or {vf identity
                        kf identity
                        somef some?
                        initk nil}})

So vf and kf default to identity, somef defaults to some?, and initk defaults to nil. Taking a look at how I call iteration, things look quite familiar:

(iteration (s3-page-iterator logs-client prefix)
           :vf :Contents
           :kf identity
           :somef some?
           :initk nil)

My kf, somef, and initk all match the defaults! Looks like the Clojure core team kinda knows what they're doing. 😉

With this knowledge under my belt, I can simplify list-objects even further:

(defn list-objects [logs-client prefix]
  (->> (iteration (s3-page-iterator logs-client prefix)
                  :vf :Contents)
       lazy-concat
       (map :Key)))

The cool thing about all of this is that I could use the exact same get-s3-page function I had before, as well as the same s3-page-iterator function, and only needed to change list-objects and sprinkle in the magic lazy-concat function from Renzo's box o' fun!

Before you try this at home, be sure to read the JUXT blog post carefully enough not to miss this sentence, which probably should have been bold and inside the dearly departed HTML <blink> tag:

You need to remember to avoid using sequence with transducers for processing items even after the initial concatenation, because as soon as you do, chunking will hunt you down.

jmglov's blog

Page 2