Oh It’s TFRecord files.
So what you want to do then is not try to shuffle all the images together, but shuffle the list of files (Dataset.list_files shuffles the order each epoch). And then do a smaller shuffle of the individual examples. Start with something like this:
# list_files shuffles the order each iteration
ds = tf.data.Dataset.list_files("trian*")
ds = ds.interleave(tf.data.TFRecordDataset, ...)
ds = ds.shuffle(...)

Ref: Dataset.interleave 3