  We consider the allocation of $m$ balls (jobs) into $n$ bins (servers). In
the standard Two-Choice process, at each step $t=1,2,\ldots,m$ we first sample
two bins uniformly at random and place a ball in the least loaded bin. It is
well-known that for any $m \geq n$, this results in a gap (difference between
the maximum and average load) of $\log_2 \log n + \Theta(1)$ (with high
probability). In this work, we consider the Memory process [Mitzenmacher,
Prabhakar and Shah 2002] where instead of two choices, we only sample one bin
per step but we have access to a cache which can store the location of one bin.
Mitzenmacher, Prabhakar and Shah showed that in the lightly loaded case ($m =
n$), the Memory process achieves a gap of $\mathcal{O}(\log \log n)$.
  Extending the setting of Mitzenmacher et al. in two ways, we first allow the
number of balls $m$ to be arbitrary, which includes the challenging heavily
loaded case where $m \geq n$. Secondly, we follow the heterogeneous bins model
of Wieder [Wieder 2007], where the sampling distribution of bins can be biased
up to some arbitrary multiplicative constant. Somewhat surprisingly, we prove
that even in this setting, the Memory process still achieves an
$\mathcal{O}(\log \log n)$ gap bound. This is in stark contrast with the
Two-Choice (or any $d$-Choice with $d=\mathcal{O}(1)$) process, where it is
known that the gap diverges as $m \rightarrow \infty$ [Wieder 2007]. Further,
we show that for any sampling distribution independent of $m$ (but possibly
dependent on $n$) the Memory process has a gap that can be bounded
independently of $m$. Finally, we prove a tight gap bound of $\mathcal{O}(\log
n)$ for Memory in another relaxed setting with heterogeneous (weighted) balls
and a cache which can only be maintained for two steps.
