# Bilayer borophene: The effects of substrate and stacking

Shobair Mohammadi Mozvashi  Mojde Rezaee Kivi  Meysam Bagheri Tagani
<EMAIL_ADDRESS>Department of Physics, University of Guilan, P. O. Box
41335-1914, Rasht, Iran.

###### Abstract

Bilayer borophene has recently attracted much interest due to its outstanding
mechanical and electronic properties. The interlayer interactions of these
bilayers are reported differently in theoretical and experimental studies.
Herein, we design and investigate bilayer $\beta_{12}$ borophene, by first-
principles calculations. Our results show that the interlayer distance of the
relaxed AA-stacked bilayer is about 2.5 Å, suggesting a van der Waals (vdW)
interlayer interaction. However, this is not supported by previous
experiments, therefore by constraining the interlayer distance, we propose a
preferred model which is close to experimental records. This preferred model
has one covalent interlayer bond in every unit cell (single-pillar). Further,
we argue that the preferred model is nothing but the relaxed model under a 2%
compression. Additionally, we designed three substrate-supported bilayers on
the Ag, Al, and Au substrates, which lead to double-pillar structures.
Afterward, we investigate the AB stacking, which forms covalent bonds in the
relaxed form, without the need for compression or substrate. Moreover, phonon
dispersion shows that, unlike the AA stacking, the AB stacking is stable in
freestanding form. Subsequently, we calculate the mechanical properties of the
AA and AB stackings. The ultimate strengths of the AA and the AB stackings are
29.72 N/m at 12% strain and 23.18 N/m at 8% strain, respectively. Moreover,
the calculated Young’s moduli are 419 N/m and 356 N/m for the AA and the AB
stackings, respectively. These results show the superiority of bilayer
borophene over bilayer MoS2 in terms of stiffness and compliance. Our results
can pave the way of future studies on bilayer borophene structures.

##  I Introduction

Borophene has recently attracted a surge of interest for its outstanding
electronic and mechanical properties Ebrahimi (2022); Li  _et al._ (2018);
Mozvashi  _et al._ (2021); Mohebpour  _et al._ (2022); Mogulkoc  _et al._
(2021). It is the lightest 2D material, rendering it a promising candidate for
lightweight nanodevices Li  _et al._ (2015); Saha  _et al._ (2021). Moreover,
the electron deficiency of boron atoms causes complex bonding which in turn
results in diverse allotropes for borophene, including $\alpha$, $\beta$, and
$\gamma$ Zhou  _et al._ (2016); Chand  _et al._ (2021). In addition to
monolayer, bilayer borophenes have also attracted much attention. It was
expected that bilayer borophene would be more stable than monolayer borophene
due to the interlayer bonding Xu  _et al._ (2022).

To date, many theoretical and experimental works have been conducted on the
subject of different bilayer borophene allotropes and their properties Xu  _et
al._ (2022); Gao  _et al._ (2018); Ma  _et al._ (2016); Nakhaee  _et al._
(2018). Moreover, there are still various questions to be answered. For
instance, theoretical studies have suggested the interlayer distance of
bilayer borophene in the range of 2.5 to 3 Å, suggesting a van der Waals (vdW)
interaction between the layers Ahn  _et al._ (2020); Zhong  _et al._ (2018);
Wu  _et al._ (2021). However, the synthesized bilayer borophenes show a much
closer interlayer distance, around 2 Å, implying relatively strong covalent
bonds Liu  _et al._ (2022); Chen  _et al._ (2022). However, some theoretical
studies considered some constraints to design the bilayer borophenes with
similar interlayer distance to the experiment Gao  _et al._ (2018); Li  _et
al._ (2019). Formation energies and phonon dispersions prove that the
constrained models are more stable than the fully relaxed models.

In this paper, by first-principles calculations, we answer why the interlayer
coupling in bilayer borophene should be covalent and under what conditions
this occurs. We first investigate the bilayer $\beta_{12}$ borophene without
constraining the interlayer distance, or _“the relaxed model”_. Afterward, by
applying the constraint of interlayer distance we reach a structure more
similar to the experimental observations, phrased as _“the preferred model”_.
This model, which has one covalent interlayer bond in each unit cell, is more
favorable than the relaxed model. Interestingly, by applying compressive
strain on the relaxed model, it undergoes a transition to the preferred model
and covalent bonds form between the layers. In other words, we suggest that
the preferred model is nothing but the relaxed model under compression.

The experimentally stable bilayer borophenes were synthesized on a metal
substrate with negative mismatches with borophenes, which apply a compressive
strain on the overlayers Liu  _et al._ (2022); Chen  _et al._ (2022); Sutter
and Sutter (2021). Otherwise, the second boron layer does not grow regularly
on the first one; instead small clusters of boron form Chen  _et al._ (2022).
Thus, the fundamental factor for the stability of bilayer borophene and
covalent interlayer bonds could be the compressive strain from the substrate.
To prove this suggestion, we considered substrate-supported borophene bilayers
on Al (111), Ag (111), and Au (111) surfaces and optimized the bilayer
borophene on them. Our results show that the substrate-supported bilayer
borophenes are more stable, with two interlayer covalent bonds in each unit
cell. Our calculations show that these extra covalent bonds are due to the
charge transfer from the substrate to the overlayers. This addresses well the
question of why and how the bilayer borophenes can grow efficiently on the
metal substrates and pave the way for future experiments. In other words, we
suggest that the AA stacking of bilayer $\beta_{12}$ borophene requires a
substrate with negative mismatch to be stable. On the other hand, the AB
stackings of the bilayer $\beta_{12}$ borophene are stable and covalently
bonded in the relaxed form. No compression nor substrate is needed. Therefore,
we strongly suggest that the synthesis of an AB-stacked bilayer $\beta_{12}$
borophene is more probable than the AA-stacked one in freestanding form.

At last, we calculate and compare the mechanical properties of the AA and AB
stackings. Our results show that the ultimate strength of the AA and the AB
stackings are 29.72 N/m at 12% strain and 23.18 N/m at 8% strain,
respectively. Moreover, Young’s moduli of the AA and the AB stackings are 419
N/m and 356 N/m, respectively, which show higher stiffness and compliance of
this bilayer compared to bilayer MoS2. Generally speaking, in this paper, we
tried to exploit the most needed mechanical and structural information about
the AA and AB stackings of the bilayer $\beta_{12}$ borophene, to contribute
in guiding the new explorations about this subject.

##  II Computational details and equations

The Spanish package solution, SIESTA Soler  _et al._ (2002); Garcia  _et al._
(2020), was implemented for all the calculations, which is based on self-
consistent density functional theory (DFT) and standard pseudopotentials. The
exchange-correlation interactions were estimated through generalized gradient
approximation (GGA), with parameterization of Perdew, Burke, and Ernzerhof
(PBE) Zhong  _et al._ (2018). Based on the convergence of the total energy, as
depicted in Supplementary Material Figs S1 and S2, the reciprocal space was
sampled by a mesh of 13×23×1 k points in the Brillouin zone and the density
mesh cut-off was set to 50 Ry. To consider the Van-der Waals interaction, the
DFT-D3 correction of Grimme was implemented Liu  _et al._ (2022). Moreover, a
vacuum space of 20 Å was considered in the $z$-direction to prevent unwanted
interactions.

The interlayer binding energy of the freestanding bilayers was calculated
through:

$E_{b}=(E_{bi}-2E_{mono})/S$ (1)

where $E_{bi}$, $E_{mono}$, and $S$ are the total energy of the bilayer, total
energy of each monolayer, and the area of the unit cell, respectively. The
adhesion energy between the bilayer and the substrate was also calculated
through:

$E_{ad}=(E_{T}-E_{bi}-E_{sub})/S$ (2)

where $E_{T}$ is the total energy of the whole substrate-supported system and
$E_{sub}$ is of the isolated substrate.

Young’s modulus is defined by:

$Y_{i}=\frac{\partial\sigma_{i}}{\partial\epsilon_{i}}$ (3)

where $\sigma_{i}$ and $\epsilon_{i}$ are the stress and the strain in
direction $i$. Also, $Y_{xy}$ is defined as the biaxial Young’s modulus. The
stress tensor is explained in Supplementary Material Eq (S2). The
$\sigma_{11}$ and $\sigma_{22}$ directly give the stress values for strains
along the armchair and zigzag directions, respectively. For the biaxial
strain, the mean square values of biaxial stresses were calculated by:

$\sigma_{xy}=\sqrt{\frac{\sigma_{11}^{2}+\sigma_{22}^{2}}{2}}$ (4)

Moreover, the obtained stress values were multiplied by the vacuum distance
(20 Å) to get the unit of N/m.

##  III Results and Discussion

###  III.1 The basic model

We start our investigations with monolayer $\beta_{12}$ borophene, which is
shown in Fig 1 (a). After full relaxation, a flat structure with lattice
constants and average bond length of $a$ = 5.15, $b$ = 2.97, and $R$ = 1.74 Å
was obtained, which is consistent with previous theoretical and experimental
records Luo  _et al._ (2017); Feng  _et al._ (2016). Subsequently, we designed
and optimized an AA-stacked bilayer, as shown in Fig 1 (b). The lattice
constants and the average bond length are $a$ = 5.14, $b$ = 2.98, and $R$ =
1.74 Å. The binding energy using Eq (1) was calculated -99.5 eV/Å2. The
closest interlayer distance in this bilayer is $d$ = 2.45 Å, which implies a
van der Waals (vdW) interaction between the layers. We call this structure
_“the relaxed model”_ , which is in agreement with several previous works Ahn
_et al._ (2020); Wu  _et al._ (2021); Zhong  _et al._ (2018). However many
stronger theoretical and experimental works suggest a closer interlayer
distance ($\sim$ 2 Å), and a covalent interlayer interaction for bilayer
borophene Liu  _et al._ (2022); Chen  _et al._ (2022); Li  _et al._ (2019).

Here, two important questions arise: Why the interlayer interaction should be
covalent? And why some of the theoretical works do not agree with the
experiments? To address these questions, we considered a manipulated model, in
which the interlayer distance was adjustable on demand. The procedure for
designing and optimizing this model is described in Supplementary Material,
Sec. S2. As described in Fig 1 (c), we constrained this structure to have one
interlayer covalent bond in each unit cell, labeled as _‘pillar’_ and adjusted
the interlayer distance to find the most stable state. Fig 1 (d) shows the
variation of binding energy as a function of interlayer distance in this
configuration. Under these circumstances, the most favorable interlayer
distance is around 1.91 Å, with a binding energy of 106.5 eV/Å2. Also, the
lattice constants and the average bond length are $a$ = 5.06, $b$ = 2.97, and
R = 1.74 Å, respectively. Interestingly, this configuration is more stable
than the relaxed structure and it is more similar to the experiments,
therefore, we call this structure _“the preferred model”_.

Figure 1: Structural configuration and electron density map of (a) monolayer
$\beta_{12}$ borophene, (b) relaxed bilayer model, and (c) preferred bilayer
model. The unit cell, interlayer distance, and pillar bonds are also depicted.
(d) Binding energy as a function of interlayer distance in the preferred
model. The paces around the minimum were smaller to obtain more precise
answer.

In aspects of electronic properties, the relaxed and the preferred models
share similar properties. As shown in Fig S7, they both are metals with
dominant p states around the Fermi level. However, as we saw in Fig 1, the
electron density maps show different interlayer interactions for these two
models. There are no electrons in the interlayer space of the relaxed model,
which approves the weak vdW interaction between the layers. However, in the
preferred model, we can see the presence of electron density between the so-
called pillar atoms, which implies covalent-like interlayer bonds. The
electron localization function (ELF) and the electron difference density maps
are also available in Fig S8, approving this conclusion. All of these features
suggest that the preferred model is more compatible with experimental studies
Liu  _et al._ (2022); Chen  _et al._ (2022); Li  _et al._ (2019).

However, as mentioned above, the preferred model is unrealistic; for no one
can hold the pillar atoms at a certain distance in real world. Then what makes
this model so close to the experiment? The answer lies beneath the effects of
the substrate. All the mentioned synthesized bilayer borophenes were grown on
metal substrates, therefore, we should somehow take into account these
effects. As we know, a substrate can influence the overlayers mechanically and
electronically. The mismatch between the substrate and the overlayers can
compress or stretch the latter, which affects other structural parameters
including the interlayer distance. Moreover, a metal substrate, soaked in free
electrons, can dope the overlayers to attract each other more strongly.

Figure 2: Evaluation of (a) stress, (b) total energy, (c) interlayer distance,
and (d) binding energy of the relaxed model with the applied strain. The total
energy was substituted from the pristine total energy ($\Delta$E = E – E0).
The expected harmonic behavior is shown with red dashed lines in (a-b).

We first simulate the mechanical effects of a possible substrate by applying
biaxial strains on the relaxed model and observing the structural evaluation.
We should keep an eye on the variation of stress and total energy with the
applied strain to see if any structural phase transition takes place. In the
harmonic range of a material, the stress is expected to behave linearly and
the total energy to grow parabolic with compression or tension. The structural
variations of the relaxed model with the applied strain are shown in Fig 2.
After a 0.5% compressive strain, the response of the stress and total energy
deviates from the expected harmonic behavior, which implies a structural phase
transition. Moreover, when the relaxed model is compressed around 1.5%, the
binding energy and the interlayer distance drop to -106.3 eV/Å2 and 1.93 Å,
respectively, which is precisely consistent with the preferred model. In other
words, the relaxed model turns into the preferred model under more than 1.5%
compression. This phase transition can be seen graphically in the insets of
Fig 2 (c). This explains well the successful synthesis of bilayer $\beta_{12}$
sheet on Ag (111), Al (111), and Au (111) substrates, all of which have
mismatches between -1% to -3% with borophene Liu  _et al._ (2022); Chen  _et
al._ (2022). As we will further show by phonon dispersion, the AA-stacked
bilayer $\beta_{12}$ is not stable in freestanding form, therefore,
consideration of a proper substrate is inevitable.

###  III.2 Substrate effects

To explore the electronic effects of the substrate, we designed the substrate-
supported bilayer models on the Ag (111), Al (111), and Au (111) surfaces. We
used five-layers of substrate from which the top two layers were allowed to
relax and the bottom three were fixed. Besides, the borophene overlayers were
allowed to fully relax. These substrates, which are among the most frequently
used surfaces for borophene synthesis Zhong  _et al._ (2017); Yu  _et al._
(2021), all apply compressive strains into the borophenes due to their
negative mismatch of the lattice constant. The lattice constants of the
optimized substrate-supported models are $a$ = 5.00, $b$ = 2.88 Å (Ag), $a$ =
4.95, $b$ = 2.86 Å (Al), and $a$ = 4.99, $b$ = 2.88 Å (Au), which apply
compressive strains of 3%, 4%, and 3% to the bilayer, respectively. The
interlayer distance in Ag-, Al-, and Au-supported models drops to 1.90, 1.84,
and 2.2 Å, which causes two covalent interlayer bonds in each unit cell to
form. In other words, the compressive strain and the electrons transferred
from the substrates cause the substrate-supported models to decrease the
interlayer distance and make double-pillar covalently bonded bilayers as shown
Fig S10. The electron doping facilities the interlayer bonding, therefore the
substrate-supported models have one pillar more than our freestanding
preferred model.

Figure 3: Phonon dispersion of bilayer $\beta_{12}$ borophene with AA (left)
and AB (right) stackings. The Brillouin zone is also depicted in the inset.

For a better understanding of this electron transfer, we calculated of
Mulliken population of electrons among the layers. In all the substrate-
supported models, the substrates donate and the overlayers accept electrons.
In the Ag-supported model, the substrate averagely donates 7$\times 10^{17}$
e/m2 to the overlayer, where the lower and the upper layers averagely accept
their shares as 3$\times 10^{17}$ and 4$\times 10^{17}$ e/m2, respectively.
These results support the previous theoretical study of borophene bilayer on
Ag (111) substrate Xu  _et al._ (2022). In the Al-supported model the
substrate donates an average of 3$\times 10^{17}$ e/m2, from which the lower
and the upper layers accept 1$\times 10^{17}$ and 2$\times 10^{17}$ e/m2,
respectively. Moreover, in the Au-supported model the substrate donates around
12 $\times 10^{17}$ e/m2 from which the upper and the lower borophenes accept
5$\times 10^{17}$ and 7$\times 10^{17}$ e/m2, respectively.

The injection of electron from the substrate compensates the electron
deficiency of the borophene, providing a good condition for the two layers to
make covalent bonds. The upper layer only makes bonds with the lower layer
whereas the lower layer pays more electrons to make bonds with both the
substrate and the upper layer, therefore the Mulliken population of the upper
layer is higher. This also suggests for likelihood of production of more than
two-layer structures, opening a way to obtain the bulk layered boron. We also
calculated the adhesion energy between the substrates and the overlayer, which
are 0.18, 0.15, and 0.22 eV/Å2 for Ag-, Al-, and Au-supported models,
respectively. These values show more adhesion in comparison with the
$\nu_{1/12}$ borophene on the Ag (111) substrate (0.11 eV/Å2) Xu  _et al._
(2022). For better comparison of the proposed substrate-supported models
please see Table 1.

Table 1: Structural properties of the substrate-supported bilayer $\beta_{12}$
borophenes: lattice constants ($a$ and $b$), interlayer distance ($d$),
substrate adhesion energy ($E_{ad}$), number of covalent bonds per unit cell
($n_{B}$), and density of electrons donated from the substrate ($\rho_{d}$).
Substrate |  $a$ (Å) |  $b$ (Å) | d (Å) |  $E_{ad}$ (eV/Å2) | $n_{B}$ |  $\rho_{d}$ ($10^{17}$ e/m2)
---|---|---|---|---|---|---
Ag (111) | 5.00 | 2.88 | 1.90 | 0.18 | 2 | 7
Al (111) | 4.95 | 2.86 | 1.84 | 0.15 | 2 | 3
Au (111) | 4.99 | 2.88 | 2.20 | 0.22 | 2 | 12

###  III.3 Stacking effects

Up to this point, we only concentrated on the AA stacking of $\beta_{12}$
bilayer borophene as the basic configuration. To take into account the effects
of layer rotation, we turn our attention to the AB stacking, where the
6-folded B atoms of the upper layer are placed above the hexagon holes of the
lower one, as shown in Fig S11. After full relaxation, this structure has the
lattice constants of $a$ = 5.03 Å, $b$ = 2.97 Å, the average bond length of
$R$ = 1.76 Å, and binding energy of -114.43 eV/Å2. Interestingly, unlike the
AA stacking, the AB stacking has a covalent interlayer interaction in the
relaxed form with $d$ = 2 Å. Thus, the AB stacking does not need the support
of a substrate to have covalent interlayer bonds. The presence of covalent
bonds among the layers is expected to improve the stability of the bilayer. To
see these effects, we calculated phonon dispersions of both relaxed AA and AB
stackings and compared them in 3. The AA stacking has several negative modes
with values of tens of cm-1, which are signatures of dynamical instability.
Interestingly, in the AB stacking phonon bands, no imaginary modes are seen,
which approves its high stability. This suggests that, in a potential
experiment, the bilayer $\beta_{12}$ borophene is very likely to grow with AB
stacking in freestanding form. For a better comparison between the AA and AB
stackings, please pay attention to Table 2.

Despite the differences in the interlayer bonding, the AA and AB stackings
share most of the electronic properties including metallicity and orbital
composition in density of states near the Fermi level (Fig S12). For the
importance of the mechanical properties for applications of 2D materials, in
the following section, we report and compare the mechanical properties of the
bilayer $\beta_{12}$ borophene with the AA and AB stackings.

Figure 4: Mechanical properties of $\beta_{12}$ borophene with AA and AB
stacking. (a, b) Long-range stress-strain curves used to find the critical
strains and ultimate strengths. (c, d) Short-range stress-strain curves in the
harmonic range used to calculate Young’s moduli. Table 2: Comparison between
different models in the freestanding form: lattice constants ($a$ and $b$),
interlayer distance ($d$), binding energy ($E_{b}$) and number of interlayer
bonds in a unit cell ($n_{b}$).
Model |  $a$ (Å) |  $b$ (Å) |  $d$ (Å) |  $E_{b}$ (eV/Å2) | $n_{b}$
---|---|---|---|---|---
AA | Relaxed | 5.14 | 2.98 | 2.45 | 99.53 | 0
Preferred | 5.06 | 2.97 | 1.91 | 106.52 | 1
AB | 5.03 | 2.97 | 2.00 | 114.43 | 1

###  III.4 Mechanical properties

Knowing the mechanical properties of a material is very vital for its
applications in nanodevices. Here, we report critical strains, ultimate
strengths and Young’s moduli for bilayer $\beta_{12}$ borophene with AA and AB
stackings. Here, the relaxed structures were used and no constraints were
applied on the interlayer distances. We first applied tensile strain in the
range of 0 to 30% to evaluate the mechanical strength of the structures. As
shown in Fig 4 (a), with biaxial strain in the range of 0 to 12%, the stress
of AA stacking rises to 29.72 N/m. Afterward, it suddenly drops to lower
values. This gives us the critical strain and the ultimate strength under
biaxial tension. For the zigzag direction, a critical strain of 14% gives the
ultimate strength of 33.63 N/m, mildly higher than the biaxial ones. In the
case of the armchair direction, we have two critical strains of 10% and 18%,
which give closely equal yield and ultimate strengths Walker  _et al._ (2014);
Goli  _et al._ (2021) of around 26 N/m.

A similar investigation was done for the AB stacking, shown in Fig 4 (b). The
critical biaxial strain of 8% gives an ultimate strength of 23.18 N/m.
Moreover, the zigzag direction comes with critical strain and ultimate
strength of 12% and 32.74 N/m, respectively. Again, the armchair direction has
two critical strains of 10% and 22%, with yield and ultimate strengths of
19.41 N/m and 30.89 N/m, respectively. Regardless of the stacking, we can see
that $\beta_{12}$ bilayer has a more complicated mechanical behavior in the
armchair direction. This might be due to the more complex bonding
characteristics in this direction.

Defined by Eq (3), Young’s modulus is the gradient of the stress-strain
relation in the harmonic range. The harmonic range for the AA and AB stacking
is 0% to 4% and -2% to +2%, respectively. The unconventional harmonic range of
the AA stacking is due to the structural phase transition at -0.5%, which was
discussed before. As shown in Fig 4 (c, d), Young’s moduli of the AA stacking
are 420, 322, and 412 N/m for biaxial, armchair, and zigzag strains. In a
similar order, the AB stacking comes with 356, 230, and 436 N/m, respectively.
Thus, the AB stacking is softer along the biaxial and armchair directions, but
mildly stiffer along the zigzag direction. We compared the obtained mechanical
properties with graphene, BN, and MoS2 bilayers in Table 3. Overall, we
suggest that the stiffness and compliance of $\beta_{12}$ bilayer borophene is
higher than MoS2, but lower than graphene and BN.

Table 3: Mechanical properties of AA and AB-stacked bilayer borophene, compared with other 2D bilayers including graphene, BN, and MoS2: Young’s moduli ($Y_{ii}$), critical strain ($\epsilon$*), and ultimate strength ($\sigma$*). | Yx (N/m) | Yy (N/m) | Yxy (N/m) |  $\epsilon$* (%) |  $\sigma$* (N/m)
---|---|---|---|---|---
$\beta_{12}$ bilayer (AA) | 322 | 412 | 420 | 12 | 29.7
$\beta_{12}$ bilayer (AB) | 356 | 230 | 436 | 8 | 23.2
Bilayer graphene Falin  _et al._ (2017) | – | – | 620 | 11 | 72.1
Bilayer BN Falin  _et al._ (2017) | – | – | 560 | 12 | 42.4
Bilayer MoS2 Bertolazzi  _et al._ (2011) | – | – | 260 | 10 | 28.0

##  IV Conclusion

In summary, by first-principles calculations, we investigated the bilayer
$\beta_{12}$ borophenes with different structures. We suggest that the
interlayer bonding plays an important role in the stability of the bilayer.
The AA stacking cannot make covalent interlayer bonds spontaneously, therefore
it cannot grow in freestanding form. It requires a metal substrate such as Ag
(111), Al (111), and Au (111) to be stable. These substrates, by applying
compressive strain and doping electrons, help the two boron layers to attract
each other more closely and make interlayer bonds. However, the AB stacking
has covalent interlayer bonds which makes it stable in freestanding form. This
is approved by phonon dispersion analysis. We also calculated the mechanical
properties of the AA and AB stackings, which show higher stiffness and
compliance of bilayer $\beta_{12}$ borophene than bilayer MoS2. This results
can give a positive contribution for future explorations about bilayer
borophene structures.

## Acknowledgment

We are thankful to the Research Council of the University of Guilan for the
partial support of this research.

## Declaration of Interests

The authors declare that they have no conflict of interest.

## References

  * Ebrahimi (2022) M. Ebrahimi, Nat. Chem. 14, 3 (2022).
  * Li  _et al._ (2018) W. Li, L. Kong, C. Chen, J. Gou, S. Sheng, W. Zhang, H. Li, L. Chen, P. Cheng, and K. Wu, Sci. Bull. 63, 282 (2018).
  * Mozvashi  _et al._ (2021) S. M. Mozvashi, M. A. Mohebpour, S. I. Vishkayi, and M. B. Tagani, Sci. Rep. 11, 1 (2021).
  * Mohebpour  _et al._ (2022) M. A. Mohebpour, S. M. Mozvashi, S. I. Vishkayi, and M. B. Tagani, Phys. Rev. Mater. 6, 014012 (2022).
  * Mogulkoc  _et al._ (2021) Y. Mogulkoc, A. Mogulkoc, H. Guler, and E. Durgun, Phys. Rev. Mater. 5, 124002 (2021).
  * Li  _et al._ (2015) X.-B. Li, S.-Y. Xie, H. Zheng, W. Q. Tian, and H.-B. Sun, Nanoscale 7, 18863 (2015).
  * Saha  _et al._ (2021) S. Saha, W. von der Linden, and L. Boeri, Phys. Rev. Mater. 5, L080601 (2021).
  * Zhou  _et al._ (2016) X.-F. Zhou, A. R. Oganov, Z. Wang, I. A. Popov, A. I. Boldyrev, and H.-T. Wang, Phys. Rev. B 93, 085406 (2016).
  * Chand  _et al._ (2021) H. Chand, A. Kumar, and V. Krishnan, Adv. Mater. Interfaces 8, 2100045 (2021).
  * Xu  _et al._ (2022) Y. Xu, X. Xuan, T. Yang, Z. Zhang, S.-D. Li, and W. Guo, Nano Lett. 22, 3488 (2022).
  * Gao  _et al._ (2018) N. Gao, X. Wu, X. Jiang, Y. Bai, and J. Zhao, FlatChem 7, 48 (2018).
  * Ma  _et al._ (2016) F. Ma, Y. Jiao, G. Gao, Y. Gu, A. Bilic, Z. Chen, and A. Du, Nano Lett. 16, 3022 (2016).
  * Nakhaee  _et al._ (2018) M. Nakhaee, S. A. Ketabi, and F. M. Peeters, Phys. Rev. B 98, 115413 (2018).
  * Ahn  _et al._ (2020) J. Ahn, I. Hong, G. Lee, H. Shin, A. Benali, and Y. Kwon, J. Phys. Chem. C 124, 24420 (2020).
  * Zhong  _et al._ (2018) H. Zhong, K. Huang, G. Yu, and S. Yuan, Phys. Rev. B 98, 054104 (2018).
  * Wu  _et al._ (2021) R. Wu, Y. Gao, and X. Wang,  _IOP Conference Series: Earth and Environmental Science_ , Vol. 702 (2021) p. 012026.
  * Liu  _et al._ (2022) X. Liu, Q. Li, Q. Ruan, M. S. Rahn, B. I. Yakobson, and M. C. Hersam, Nat. Mater. 21, 35 (2022).
  * Chen  _et al._ (2022) C. Chen, H. Lv, P. Zhang, Z. Zhuo, Y. Wang, C. Ma, W. Li, X. Wang, B. Feng, and P. Cheng, Nat. Chem. 14, 25 (2022).
  * Li  _et al._ (2019) D. Li, Q. Tang, J. He, B. Li, G. Ding, C. Feng, H. Zhou, and G. Zhang, ACS Omega 4, 8015 (2019).
  * Sutter and Sutter (2021) P. Sutter and E. Sutter, Chem. Mater. 33, 8838 (2021).
  * Soler  _et al._ (2002) J. M. Soler, E. Artacho, J. D. Gale, A. García, J. Junquera, P. Ordejón, and D. Sánchez-Portal, J. Phys. Condens. Matter 14, 2745 (2002).
  * Garcia  _et al._ (2020) A. Garcia, N. Papior, A. Akhtar, E. Artacho, V. Blum, E. Bosoni, P. Brandimarte, M. Brandbyge, J. I. Cerdá, F. Corsetti, _et al._ , J. Chem. Phys. 152, 204108 (2020).
  * Luo  _et al._ (2017) Z. Luo, X. Fan, and Y. An, Nanoscale Res. Lett. 12, 1 (2017).
  * Feng  _et al._ (2016) B. Feng, J. Zhang, Q. Zhong, W. Li, S. Li, H. Li, P. Cheng, S. Meng, L. Chen, and K. Wu, Nat. Chem. 8, 563 (2016).
  * Zhong  _et al._ (2017) Q. Zhong, L. Kong, J. Gou, W. Li, S. Sheng, S. Yang, P. Cheng, H. Li, K. Wu, and L. Chen, Phys. Rev. Mater. 1, 021001 (2017).
  * Yu  _et al._ (2021) Z. Yu, S. Meng, and M. Liu, Phys. Rev. Mater. 5, 104003 (2021).
  * Walker  _et al._ (2014) J. Walker, R. Resnick, and D. Halliday,  _Halliday and resnick fundamentals of physics_ (Wiley, 2014).
  * Goli  _et al._ (2021) M. Goli, S. Mozvashi, P. Aghdasi, S. Yousefi, and R. Ansari, Superlattices Microstruct. 152, 106854 (2021).
  * Falin  _et al._ (2017) A. Falin, Q. Cai, E. J. Santos, D. Scullion, D. Qian, R. Zhang, Z. Yang, S. Huang, K. Watanabe, T. Taniguchi, _et al._ , Nat. Commun. 8, 1 (2017).
  * Bertolazzi  _et al._ (2011) S. Bertolazzi, J. Brivio, and A. Kis, ACS Nano 5, 9703 (2011).


\bgroup\appto\lst@DeInit{\egroup

#  Kafka Consumer Group Autoscaler

Diogo Landau  Department of Electrical Engineering
University of Porto - FEUP
<EMAIL_ADDRESS>Xavier Andrade  Department of Industrial
Engineering
University of Porto - FEUP
<EMAIL_ADDRESS>Jorge G. Barbosa  Department of Informatics
Engineering
University of Porto - FEUP, LIACC
<EMAIL_ADDRESS>
###### Abstract

Message brokers enable asynchronous communication between data producers and
consumers in distributed environments by assigning messages to ordered queues.
Message broker systems often provide with mechanisms to parallelize tasks
between consumers to increase the rate at which data is consumed. The
consumption rate must exceed the production rate or queues would grow
indefinitely. Still, consumers are costly and their number should be
minimized. We model the problem of determining the required number of
consumers, and the partition-consumer assignments, as a variable item size bin
packing variant. Data cannot be read when a queue is being migrated to another
consumer. Hence, we propose the R-score metric to account for these
rebalancing costs. Then, we introduce an assortment of R-score based
algorithms, and compare their performance to established heuristics for the
Bin Packing Problem for this application. We instantiate our method within an
existing system, demonstrating its effectiveness. Our approach guarantees
adequate consumption rates – something the previous system was unable to – at
lower operational costs.

###### Index Terms:

variable item size, bin packing, consumer group autoscaling, message broker

##  I Introduction

Message Brokers are a common tool employed to fixture communication in a
distributed environment [1]. This system provides with asynchronous
communication between producers and consumers, and handles some of the
challenges that are common within distributed and concurrent data processing.

We consider a queue or partition to be a structure within a message broker
environment where messages are appended in the same order as they were
produced. It is also important that this structure is capable of delivering
the messages in the same order as they were produced. This consumption model
is often a requirement to guarantee state consistency between two distinct
distributed systems for a specific business related entity. Common
applications that employ replaying a set of messages in the same order as they
were produced include event-carried state transfer, and system state
simulation. The former consists of having two systems reading the same set of
messages in the same order to replicate an entities state within their data
store [2, 3], whereas the latter is used to simulate a system’s state at a
given point in time by reproducing the messages up until that point [4, 5].

Figure 1:  On request, our algorithm determines the number of consumers and
partition-consumer assignment based on the message broker’s current load.

Two common message broker implementations, Kafka and RabbitMQ, have different
ways of guaranteeing message order on consumption. Within Kafka, all the
messages produced to a partition are appended and delivered in the same order
as they were published. Messages can be consistently produced to the same
partition if the same key is used111Kafka Message Ordering:
https://kafka.apache.org/documentation/#intro_concepts_and_terms. As for
RabbitMQ, it guarantees messages toward a queue are enqueued in the same order
as they were produced. Therefore, to guarantee same order message delivery,
only a single consumer can be reading messages from the queue222RabbitMQ
Message Ordering: https://www.rabbitmq.com/queues.html#message-ordering.

Within a distributed message broker environment, provided we are given a set
of independent queues, our goal is to manage a group of consumers, so as to
guarantee the rate of consumption is at least as high as the production rate.

Since message ordering is important, only one consumer can be assigned a
queue, but multiple queues can be assigned the same consumer. This also
implies that the maximum number of consumers is limited to the number of
queues.

As each consumer represents an active computing resource, while attempting to
determine the amount of parallelism required, we are also aiming to minimize
the operational cost, by reducing the number of consumers.

Considering consumers as bins, and queues as items that have to be assigned a
bin, this problem was modeled as a variation of the Bin Packing (BP) Problem,
with the particularity that items vary in size over time. This occurs because
a queue’s size correlates to its current write speed, which fluctuates based
on the current system’s load and inevitably implies that a BP solution for a
given time instant may not hold true in future instants. Figure 1 provides
with a high level representation of the interacting entities.

On account of this BP variation, a new solution has to be computed at
different time instants, each having different information as to the size of
each item (each queue’s ”current” write speed for that time instant). This
might lead to a queue (item) being migrated to a different consumer (bin) when
compared to the consumer group’s previous configuration.

Since two consumers cannot read from the same queue concurrently, there is
another cost to take into account associated to rebalancing a partition. This
cost is related to the amount of data that is not being read while the queue
is being rebalanced.

Provided this is the first time the variable item size bin packing variant is
applied in this context, existing algorithms do not take this rebalance cost
into account. Hence, in Section IV-A we propose a metric to account for a
given iteration’s rebalance cost (Rscore). Additionally, using the Rscore, in
Section IV-B we propose four new BP heuristic algorithms that account for the
rebalance costs, three of which are shown in Section VI-C to be a competitive
alternative to the multi-objective optimisation problem at hand.

Furthermore, it is our belief that this model is applicable in other contexts,
e.g., the Kubernetes node autoscaling problem. In Kubernetes, nodes are
machines that have resources, to which pods are assigned. Each pod is
independent and the node resources it consumes varies with time. Therefore,
modeling nodes as bins and pods as items whose size varies over time, this
problem also fits our variation of the BP problem, with the added complexity
of bins being allowed to have different sizes, which is not considered in our
scenario. This problem presents similar characteristics to the work elaborated
in [6] and [7].

In Section II, we present applications of the Bin Packing Problem, and a
comparison of existing approximation algorithms to solve the Bin Packing
problem. Section III, formally defines the problem, followed by the proposed
approach in Section IV. We also present in Section V an application within a
message broker environment, more specifically Kafka, of autoscaling a group of
consumers based on the broker’s current load. We use Section VI to present and
discuss the tests performed on the proposed algorithms, and the autoscaling
model when applied to Kafka. Lastly, we conclude this paper through Section
VII.

##  II Related Work

###  II-A Bin Packing Applications

There are several applications where BP is used to provide with an optimal or
sub-optimal solution [8, 9, 10, 11]. The Virtual Machine Placement (VMP)
problem, which has gained more attention due to increasing use of cloud
providers to support companies’ technological infrastructure. The problem can
be generalized to a set of Virtual Machines (VM), each having to be assigned
one of the cloud provider’s Physical Machines (PM) while attempting to
minimize the operational cost. A variation of BP arrises in this scenario
where the items are considered ephemeral and add another temporal dimension
since they have associated a start time and a duration.

Cauwer et al. [12] study BP with a temporal variant, where the tasks have an
equal start time. Their aim is to minimize the unused capacity of a physical
machine over time, and therefore the optimal solution for the BP problem does
not necessarily provide the optimal solution in their Temporal variant of the
BP problem. In addition to the time model presented by [12], Aydın et al. [13]
study the case where items may have differing start times. Their objective
function is more in line with the traditional BP, as it aims to minimize the
number of physical machines (bins) used. Moreover, due to the increased energy
costs related to machine fire-ups (switching a machine off when it is not in
use and back on again when required), the authors also attempt to minimize the
number of fire-ups, making their problem multi-objective.

Furini et al. in [14], study a stateful BP variant, where the time dimension
is discretized into several time instants, each with tasks that have to be
executing at that time, and therefore have to be assigned a PM. Their problem
has an additional constraint, related to the tasks having to run
uninterrupted, and therefore cannot be assigned two different bins for their
execution period. Consequently, solving each discrete problem independently
does not provide with an optimal arrangement, as that would require the items
to be reassigned.

The variable item size variant of the bin packing problem, has also been
studied by Wolke et al. [6] and Song et al. [7], due to the varying load
patterns presented by VMs. Both periodically execute a reallocating controller
that determines new PM assignments for each VM, while aiming to minimize the
cost of having multiple PMs running, and the migration cost. The migration
cost in their problem is related to a VMs memory footprint.

Xia et al. [15] considers the online bin packing problem within the context of
Fog computing, to determine whether a cloudlet has the resources to offload a
user’s request.

Bin packing has also been applied to real-time data streaming, which is a new
paradigm of data processing, where compute nodes process the data in real-
time, as opposed to batch processing the data periodically. Further
elaborating, when processing data in real-time, a query is executed
”continuously” to provide with real-time insights as soon as a new tuple is
provided. As Gulisano et al. [16] point out, a continuous query can be
construcuted as a direct acyclic graph, where the different operators can be
distributed to different nodes, having upstream nodes communicating with their
downstream conterparts to communicate the result of its operator. This also
enables for a distributed execution of a query, and an elastic infrastructure
capable of scaling based on the current system’s load. The authors use
utilization thresholds to determine how to scale its cluster of nodes.

Heinze et al. [17], use bin packing to dynamically scale in or out a set of
nodes based on the current system’s query load, while maintaining process
latency constraints. The authors observed underutilization, due to query
operators no longer occupying computing resources in host machines after task
completion, and therefore, devised a re-balance policy. They acknowledge re-
executing the bin packing heuristic would provide with better utilization
rates, but in their scenario this was not feasible due to excessive re-balance
cost, and therefore devise a re-balancing algorithm that re-places only the
operators that present minimal load in their system, until a specific
condition is met. As a complement to the previous findings, [18] extends the
algorithm to use reinforcement learning to improve the decision to scale out
or in, based on the utilization rates and latency measurements.

###  II-B Approximation Algorithms

The Bin Packing (BP) problem is a well established research problem, and has
been extensively reviewed in the literature. Due to the time constraints
imposed by our applicatoin, this paper gives emphasis to the Approximation
Algorithms that heuristically solve the problem in low-order polynomial time,
as opposed to the higher time complexity Linear Programming approach.

A method is presented to classify the BP problem in [19], which will be used
throughout this section. During an algorithm’s execution, a bin can find
itself either open or closed. In the former, the bin can still be used to add
additional items, whereas in the latter, it is no longer available and has
already been used.

The list of bins is indexed from left to right, and the number of bins used by
an algorithm can be computed using the index of the first empty bin in the
list of bins. When creating a bin, this process can be visualized as opening
the lowest index of the empty bins (left-most empty bin).

Using $A(L)$ to denote the amount of bins a certain algorithm makes use of for
a configuration of items $L$, $OPT(L)$ to represent the amount of bins
required to achieve the optimal solution, and defining $\Omega$ as the set of
all possible lists, each with a different arrangement of their items,

$R_{A}(k)=\sup_{L\in\Omega}\left\\{\frac{A(L)}{k}:k=OPT(L)\right\\},$ (1)

encodes a performance metric relative to the optimal number of bins used by an
algorithm. The Asymptotic Performance Ratio (APR) of an algorithm $A$
($R_{A}^{\infty}$) is defined as

$R_{A}^{\infty}=\limsup_{k\to\infty}R_{A}(k).$ (2)

This is the metric that will be used throughout this section to compare the
algorithms’ performance.

Despite the mulititude of classes presented in [19], the only class of
problems that is of interest for this paper, is the offline bin packing
variant.

Offline BP algorithms are aware of the list of items that are to be assigned
bins prior to its execution. As long as the set of items remains the same,
items can be grouped, sorted or anything that might be convenient to the
algorithm that is going to iterate over the list of items.

The Any Fit subclass of algorithms must fit the constraint: if bin $j$ is
empty, an item will not be assigned to it if the item fits into any bin to the
left of $j$. These algorithms perform best if the list of items is sorted in a
non-increasing order prior to assigning bins to the items. The offline
approximation algorithms that are going to be described, follow this sorting
strategy, and all but the Next Fit Decreasing (NFD) belong to this subclass of
algorithms. Provided a list of sorted items, the NFD only has a single open
bin at a time, which is also the last created bin. This algorithm attempts to
place the item in the right-most non-empty bin. If it does not fit, then the
bin to the right is used. As shown in [20], this algorithm has as APR,

$R_{NFD}^{\infty}\approx 1.6910.$ (3)

With regards to the Worst Fit Decreasing (WFD), for each item, it attempts to
assign the bin with most slack. If the size constraint is not satisfied, a new
bin is assigned.

The Best Fit Decreasing (BFD) is similar to the WFD differing only on its
packing strategy, wherein this algorithm attempts to place the item in the bin
where it fits the tightest. In case there is no open bin to fit the current
item, a new bin is created where the item is inserted.

Lastly, the First Fit Decreasing (FFD) places each item in the left-most bin
as long as the bin’s capacity is not exceeded. As shown in [21],

$R_{BFD}^{\infty}=R_{FFD}^{\infty}=\frac{11}{9}.$ (4)

In combination with their online variants, these algorithms will be used as a
reference to evaluate the performance of our Modified Any Fit algorithms in
Sec. VI.

###  II-C Conclusion

Although the temporal aspect of the Bin Packing Problem has already been
reviewed, there is a gap when it comes to the possibility of rebalancing the
items between the different bin instances. Existing solutions lack a
deterministic metric to account for the rebalancing cost, and present
conservative heuristic algorithms to migrate the items to different bins
(items with higher cost are not migrated).

Also, in view of the fact that the existing approximation algorithms were
developed to solve a single iteration of the BP problem, these have to be
adapted to the problem at hand, which requires solving a new iteration given
an already existing assignment of items to bins. Despite the fact that the
adaptation presented in Section IV-C improves these algorithms’ performance
with respect to the rebalance cost, there is still room for improvement.

Therefore, since modeling the message broker consumption domain as a variable
item size bin packing variant, is, to the best of our knowledge, a novel
approach, in Section IV-A we provide with a metric (Rscore) that encodes the
rebalance cost for a given iteration. Based on this metric, we contribute with
four new heuristic algorithms that simultaneously aim to minimize the
operational and migration costs (Section IV-B).

##  III Problem Formulation

A group of consumers is interested in consuming data from several
partitions/queues with varying load within the message broker. The set of
partitions is distributed between the different consumers of the group to
simultaneously parallelize and load-balance. Each partition can only be
assigned a single consumer, whereas a consumer can be assigned several
partitions. This problem is contained within the Data Consumption Domain of
Figure 2.

Figure 2:  Representation of data production and consumption domains within a
message broker environment.

The aim of our work is to achieve a deterministic approach to determine the
number of consumers required working in parallel, so as to guarantee that the
rate of production into a partition is not higher than its rate of consumption
by the consumer group. In contrast, if this were not the case, messages would
accumulate leading to the lag between the last message inserted and the last
message read by the consumer group to increase with time.

We assume that the maximum consumption rate of a single consumer is constant,
and if there is enough data to be consumed, this is the speed the consumer
functions at when working ”full throttle”. This is elaborated in Section VI
based on several tests performed to determine this capacity value for a
consumer.

Based on the previous information, the model for this pipeline fits the
constraints of the Single Bin Size Bin Packing (SBSBP) variant, where the bins
are consumers that have as capacity their maximum consumption rate, and the
weights are the partitions and their respective write speeds. The problem then
is to find the minimum amount of consumers where to fit all the partitions so
as to make sure that the sum of the write speeds of the partitions assigned to
a single consumer does not exceed its maximum capacity.

For a single iteration, the optimal solution finds the arrangement between the
partitions and the consumers that minimizes the amount of instances, but this
solution is not static, as the write speeds of the partitions changes with
time. As such, there is a second factor to take into consideration which is
the partition reassignment.

When a partition is reassigned, because two consumers from the same group
cannot be consuming from the same partition at a time, when assigning a
partition to another consumer, the one it is currently assigned to has to stop
consuming in order to allow the new consumer to start. Due to this process,
there is some downtime where data is not being consumed from a partition.

For this reason, making use of an optimal algorithm that also minimizes
partition redistribution, is not feasible as it would not run within the
necessary time requirements due to the NP-hard nature of the problem [22]. To
determine the arrangement of partitions and consumers, this work is based on
approximation algorithms. As is clear, there is no approximation algorithm
which considers item redistribution.

Consequently, the BP problem is remodeled to take the time instant $t$ at
which the algorithm is to be executed into account.

$\displaystyle\min$ $\displaystyle\sum_{i\in B}y_{i}$ (5) subject to
$\displaystyle\sum_{j\in L}\hat{w}_{j}(t)\cdot x_{ij}\leq y_{i}\quad$
$\displaystyle\forall\;i\in B$ (6) $\displaystyle\sum_{i\in B}x_{ij}=1,\quad$
$\displaystyle\forall\;j\in L$ (7) $\displaystyle y_{i}\in\\{0,1\\}$
$\displaystyle\forall\;i\in B$ (8) $\displaystyle x_{ij}\in\\{0,1\\}$
$\displaystyle\forall\;i\in B,j\in L,$ (9)

where set $B$ corresponds to the available bins, and $L$ as the list of items
to be arranged into different bins. Decision variable $x_{ij}$ and $y_{i}$,
indicate whether an item $j$ is packed in the bin $i$, and whether bin $i$ is
used respectively. As for Constraints 6 and 7, the former assures that the sum
of the items in a bin does not exceed it’s capacity, and the latter makes sure
that every item is assigned a bin.

Time instant $t$ represents an instant at which a measurement was performed of
the items’ sizes, leading to a new computation of the bin packing assignment,
and new values for $x_{ij}$ and $y_{i}$.

Since an assignment represents a consumer reading data from a partition, an
item can also be reassigned to another consumer (bin), if at time instant $t$
there is already a consumer from the group reading data from it.

##  IV Algorithm

###  IV-A Rscore

Within this problem’s context, rebalancing inevitably implies having the
consumer group stop consuming from a partition while it is being reassigned
from one consumer to another. There cannot be a concurrent read from the same
partition by members of the same group.

This paper introduces the Rscore metric to compute the total rebalance cost of
a group’s reconfiguration. The metric reflects the impact of stopping the data
consumption from the partitions that are being rebalanced. As such, the Rscore
computes the rate at which data accumulates, in consumer iterations per
second.

In essence, the combination of the time it took to rebalance a set of
partitions and the Rscore, encodes information as to the maximum number of
consumer iterations required to fully recover the data that accumulated, while
the set of partitions was being rebalanced.

TABLE I: Data required to compute the Rscore. Notation |  Description
---|---
$P_{i}$ |  Set of partitions rebalanced in iteration $i$
$s(p)$ |  Write speed of partition $p$
$C$ |  Maximum consumer capacity in bytes/s

Provided the data presented in Table I, the following Equation 10 presents
$R_{i}$, the Rscore for iteration $i$.

$R_{i}=\frac{1}{C}\sum_{p\in P_{i}}s(p)$ (10)

###  IV-B Modified Any Fit

Any Fit algorithms focus on reducing the amount of bins used to pack a set of
items, disregarding the cost associated with reassigning items. These need to
be modified to include the rebalancing costs that affect the solution
performance significantly. Algorithm 1 illustrates the implementation of the
modified any fit that will be further described for the remainder of this
section.

Given the current consumer group’s state (the partitions assigned to each
consumer), and a set of unassigned partitions, the modified algorithms differ
from the decreasing versions of the Any fit algorithms described in Section
II-B, wherein the former class of algorithms does not sort the set of items
but, in turn the consumers of a consumer group based on their assignment.

There are two sorting strategies when sorting the group of consumers:

  * •

Sorting consumers based on the cumulative speed of all partitions assigned to
it (cumulative sort);

  * •

Sorting consumers based on the partition assigned to it that has the biggest
measured write speed (max partition sort).

After sorting the current consumer group using one of the above strategies,
for each consumer in the sorted group, the partitions assigned are sorted
based on their write speed. From smallest to biggest, each partition is
inserted into one of the bins that have already been created for the next
iteration’s assignment (future assignment). The insertion is made based on one
of the any fit strategies, which can either be the Best or Worst Fit strategy.
If the insert is successful, the partition is removed from the sorted list of
partitions. Otherwise, if there is no existing bin that can hold the
partition, then the current consumer assigned to it is created.

The remaining partitions in the sorted list are inserted into the created bin
(which is also the consumer they are currently assigned to), from biggest to
smallest. If the partition is inserted successfully, it is removed from the
list of partitions. If a partition does not fit into the newly created
consumer, then the remaining partitions are added to the set of unassigned
partitions.

After repeating this procedure for all consumers, there is now a set of
partitions which have not been assigned to any of the consumers in the future
assignment. The final stage involves first sorting the unassigned partitions
in decreasing order (based on their measured write speed), and assigning each
partition to consumer from the new consumer group according to a fit strategy.

TABLE II: Modified implementations of the any fit algorithms. Algorithm |  Consumer Sorting Strategy
---|---
Modified Worst Fit (MWF) |  Cumulative write speed
Modified Best Fit (MBF) |  Cumulative write speed
Modified Worst Fit Partition (MWFP) |  Max partition write speed
Modified Best Fit Partition (MBFP) |  Max partition write speed
Algorithm 1 Modified Any Fit Algorithm

0: current consumer group configuration $C$ & currently unassigned partitions
$U$

0: new consumer group configuration $N$

1: $N\leftarrow$ new ConsumerList with assign strategy

2: $S\leftarrow$ sort $C$ on cumulative or max partition

3: for $c\in S$ do

4: $pset\leftarrow$ partitions assigned to $c$

5: $pset\leftarrow$ sort $pset$ in decreasing order

6: for $i\leftarrow pset.size()-1$ to $0$ do

7: $p\leftarrow pset[i]$

8: $result\leftarrow N.assignOpenBin(p)$

9: if $result=false$ then

10: $break$

11: end if

12: $pset.remove(p)$

13: end for

14: if $pset.size()=0$ then

15: $continue$

16: end if

17: $N.createConsumer(c)$

18: for $p\in pset$ do

19: $result\leftarrow N.assign(c,p)$

20: if $result=false$ then

21: $break$

22: end if

23: $pset.remove(p)$

24: end for

25: $U.extend(pset)$

26: end for

27: $U\leftarrow$ sort $U$ decreasing order

28: for $p\in U$ do

29: $N.assignBin(p)$

30: end for

31: return $N$

###  IV-C Approximation Algorithms Adaptation

Adding to the procedures described in Sec. II, another step was included in
the approximation algorithms when creating a new bin that does not have an
affect on the total number of bins used by these algorithms. If the consumer
that is currently assigned to the partition has not yet been created in the
future assignment, this is the bin that is created, otherwise, the lowest
index bin that does not yet exist is the one created. This is not presented as
a modification to the existing algorithms, it simply adapts these to the added
rebalance concern.

##  V Kafka Consumer Group Autoscaler

Figure 3: System architecture.

There are three components that interact with one another to provide a fully
dynamic pipeline capable of autoscaling based on the current load of data
being produced to the partitions of interest, as presented in Fig. 3.

  1. 1.

The monitor process is responsible for measuring the write speed of each
partition the group is interested in consuming data from, which is equivalent
to specifying the size of the items of the bin packing problem.

  2. 2.

This information is then delivered to the controller, which is responsible for
managing a consumer group (creating and deleting consumer instances), and
mapping each partition to a consumer.

  3. 3.

The consumers are then informed of their tasks and read the data from the
partitions that were assigned to them by the controller.

This system was applied in a real world context, with the goal of extracting
data published to Kafka topics to be inserted into a Datalake, being a part of
the Extraction domain of the ETL process.

###  V-A Monitor

To solve the BP problem, initially, the controller requires as input the write
speed of each partition the consumer group is interested in consuming data
from. The monitor process is responsible for providing this information.

Kafka provides an Admin client, which can be used to administer the cluster
and query information about it. This client/class exposes a method
$describeLogDirs()$ which queries the cluster for the amount of bytes each
TopicPartition has. A TopicPartition is a string-integer pair, which
identifies any partition (integer) within a topic (string).

Each time the admin client queries the partition size, a timestamp is appended
to the measurement, and it is inserted into the back of a queue. Any query
older than $30$ seconds, which is guaranteed to be in the front of the queue,
is removed. We use the average write speed over the last 30 seconds to
estimate a single partition’s write speed. We compute the difference between
the first and last queue elements (i.e., the earliest and latest measurement
of the partition size) regarding the last $30$ seconds. We divide the result
by that time amount to obtain our write speed estimate in $bytes/s$.

After computing the write speed for all the partitions of interest, the
information has to be communicated to the controller/orchestrator. To benefit
from an asynchronous approach, this monitor process communicates with the
controller/orchestrator process via a Kafka topic illustrated in Fig. 3 as
monitor.writeSpeed.

###  V-B Consumer

The Consumer goes through four important phases within its process to
approximate its consumption rate to a constant value when being challenged to
work at its peak performance. These phases repeat cyclically until the
consumer is terminated by an external signal. Fig. 4 illustrates the
consumer’s process.

Figure 4: Consumer Insert Cycle.

The consumer is configured with two important parameters, $BATCH\\_BYTES$ and
$WAIT\\_TIME\\_SECS$, which indicate respectively, the amount of bytes the
consumer waits to gather in a single iteration, and the amount of time it is
allowed to wait to gather the information.

The first phase has the consumer attempt to fetch $BATCH\\_BYTES$ from the
partitions it is consuming data from. After this condition is satisfied or
$WAIT\\_TIME\\_SECS$ is exceeded, the consumer moves on to the second phase.
Here the consumer processes each individual record, and batches records that
originated from the same topic together. There are different data lake tables
for each topic, and therefore not all records are inserted into the same
destination table.

The third phase is where the consumer sends the records into the data lake,
performing an asynchronous request for each topic it fetched data from in the
same iteration.

Having forwarded all the records into their respective data lake tables, the
consumer then verifies its metadata queue to verify if there are any change in
state messages to be consumed. This queue is how the Controller process (Sec.
V-C) informs each consumer of their assignments. If there are new messages,
the consumer reads all messages in the queue, and updates its state. Only
after having successfully updated its state and persisted its metadata, does
the consumer send an acknowledgment back to the Controller to indicate the
successful change in state. This cycle repeats until the Controller removes
the consumer from its group of active consumers.

###  V-C Controller

The controller is the system component responsible for orchestrating and
managing the consumer group. The write rate of each partition computed by the
monitor process is an input to the approximation algorithm that determines new
consumer group configurations. Based on these configurations, the controller
creates the consumers that do not yet exist, communicates changes in
assignment to each consumer in the group, and deletes consumers that are not
required in new computed group’s states.

As shown in Fig. 3, there are two topics that function as communication
intermediaries between the three system components. The topic illustrated by
monitor.writeSpeed is where the controller reads the partitions’ write speeds,
whereas the topic illustrated by consumer.metadata is where the controller
sends messages to each consumer to inform the change in their state. Regarding
the latter Kafka topic, partition 0 is reserved for communication directed
toward the controller, whereas the remaining partitions within
consumer.metadata represent a one-to-one mapping to each consumer. Therefore,
if the controller wants to communicate with consumer $N$, it sends a record
into metadata partition $N$.

This communication architecture was devised to achieve an efficient
communication model, defined as the amount of information that is relevant
relative to the amount of data read. With this pattern, all the data read is
relevant to the reading entity.

The controller can be summarized by a state machine, intended to continuously
manage a group of consumers and their assignments, illustrated by Fig. 5.

Figure 5: Controller State Machine.

The Sentinel state has the controller read the information published by the
monitor component to update its current consumer group’s state, and determine
whether it has to recompute the group’s assignments. If it evaluates one of
the exit conditions as true, the controller transitions into the Reassign
Algorithm state. Then, it employs one of the approximation algorithms
mentioned in Sections II-B and IV-B to solve the Bin Packing Problem
heuristically.

The approximation algorithm outputs the desired state in which the controller
wants its group of consumers. Hence, the first step within the Group
Management state is to compute the difference between the current state of the
group and the desired state. This difference encodes information regarding:
the consumers to be created; the partitions each consumer has to stop
consuming from; the partition each consumer has to start consuming from; and
lastly, the consumers that have no assignment, and therefore can be
decommissioned.

The state difference allows the controller to operationalize the transition
into the new state. Firstly, the controller creates the new consumer
instances, which involves the controller communicating with a Kubernetes
cluster to create the deployments related to each consumer. We chose to have
different deployments for each consumer, so that the information related to
which $consumer.metadata$ partition the consumer had to read from, could be
transmitted through the deployment’s manifest $metadata.name$ attribute.
Secondly, the controller informs each consumer of their change in state by
transmitting the start and stop consuming messages to each consumer via their
respective $consumer.metadata$ partition. It is important to note that
communicating the state change is a synchronous process. This assures that
while rebalancing partitions there at most one consumer from the group reading
data from a partition. This means that for each partition being rebalanced,
the controller first sends out the stop consuming message. Only after the
consumer informs the controller of having acted upon the message, can the
controller send out the start consuming record to the new consumer. After the
consumers have reached their intended state, the controller shuts down the
inactive consumers.

The Synchronize state is used to synchronize the consumer group’s real state
with the controller’s perceived state. This is to guarantee the controller is
capable of recovering from an unexpected termination, which can lead to an
inconsistent perception of the consumer group’s state.

##  VI Experimentation

###  VI-A Test Data Generation

Throughout this section, we use the term measurement to represent a map of
values that indicate the speed for each partition of interest. The term stream
refers to a sequence of measurements in the form of a list. Each measurement
of a stream simulates the items’ sizes for an instance of the BP problem,
which is an input for the approximation algorithms.

TABLE III: Data to generate a stream. Symbol | Description
---|---
$P$ | Set of partitions of interest for the consumer group.
$s_{i}(p)$ | Speed for a partition $p\in P$ at an iteration $i$
$\phi(\delta)$ | Uniform random function that selects a value between $[-\delta,\delta]$
$C$ | Bin Capacity for the Bin Packing Problem.

To generate a stream of measurements, given $N$ (the number of measurements
desired) and $\delta$ (maximum relative speed variation between two sequential
iterations), at first the initial speed $s_{0}(p),\;\forall p\in P$ has to be
defined. Four different approaches were tested for the partition’s initial
value: choosing a random value between $[0,100]\%\cdot C$; setting the initial
speed of all partitions to $0$; setting the initial speed of all partitions to
$50\%\cdot C$; setting the initial speed of all partitions to $C$. Given that
there was no significant difference on the outcome with these variations, the
results presented were obtained using the streams of data generated having an
initial speed for all partitions that was randomly selected between
$[0,100]\%\cdot C$.

Therefore, given $s_{0}(p)\ \forall p\in P$, the remaining measurements were
obtained using:

$\begin{split}s_{i}(p)=&\max\\{0,s_{i-1}(p)+\frac{\phi(\delta)}{100}\cdot
C\\},\\\ &\forall\ p\in P\ \wedge\ i\in\\{1,2,...,N-1\\}\end{split}$ (11)

Using the aforementioned procedure, 6 different streams of data were generated
by setting $N=500$ and setting $\delta$ to a value belonging to the set
$\\{0,5,10,15,20,25\\}$ for each stream of data ($\delta$ does not change
within a stream).

###  VI-B Metrics

The metrics used to compare the performance between the algorithms are the
Cardinal Bin Score ($CBS_{\delta}(a)$) and the Average Rscore
($E_{\delta}^{a}(R)$) over all iterations of each stream.

TABLE IV:  Data to compute the cardinal bin score and the expected Rscore for a stream of measurements.  Symbol |  Description
---|---
$A$ |  Set containing the existing and proposed approximation algorithms.
$z_{i}^{\delta}(a)$ |  number of bins used in iteration $i\in\\{0,1,...,N-1\\}$ of a stream defined by $\delta$, by algorithm $a\in A$.
$R_{i}^{a}$ |  Rscore for an iteration $i\in\\{0,1,...,N-1\\}$ for the outcome provided by algorithm $a\in A$.

The cardinal bin score is calculated using the following expression:

$\begin{split}CBS_{\delta}(a)=&\frac{1}{N}\sum_{i=0}^{N-1}\frac{z_{i}^{\delta}(a)-min_{b\in
A}\\{z_{i}^{\delta}(b)\\}}{min_{b\in A}\\{z_{i}^{\delta}(b)\\}},\\\ &\forall\
a\in A\ \wedge\ \delta\in\\{0,5,10,15,20,25\\}.\end{split}$ (12)

This metric expresses how many more bins, on average, an algorithm $a\in A$
has compared to the algorithm that made use of the least bins, which encodes
the operational cost. The lower this value, the better the algorithm performed
for a given stream.

The expected value of the Rscore, is used to compare the rebalance cost for a
single stream, and is computed as follows:

$\begin{split}E_{\delta}^{a}(R)=&\frac{1}{N}\sum_{i=0}^{N-1}R_{i}^{a},\quad\\\
&\forall\ a\in A\ \wedge\ \delta\in\\{0,5,10,15,20,25\\}.\end{split}$ (13)

The aim is also to minimize an algorithm’s Average Rscore.

###  VI-C Modified Any Fit Evaluation

Each algorithm was evaluated over a stream of measurements, persisting the
Rscore and the number of bins used for each iteration. The algorithms are
compared with respect to the same stream.

Figure 6:  Cardinal Bin Score (CBS) for all implemented algorithms.

When evaluating the Cardinal Bin Score, the worst performing algorithm, as
shown in Fig. 6, is the next fit followed by its decreasing version. The
remaining any fit decreasing algorithms, are the ones that perform the best,
with the best fit decreasing consistently presenting the best results.

Figure 7:  Cardinal Bin Score (CBS) filtered to present the modified and the
BFD algorithms.

As for the modified versions of these algorithms, due to its sorting strategy,
MBFP shows the best results. It is also worth noting that for smaller
variabilities, the modified algorithms behave similarly to the online versions
of their any fit strategy with respect to the CBS, since the partitions aren’t
necessarily assigned from biggest to smallest. On the other hand, the higher
the delta, the bigger the variability, which also leads to more rebalancing,
having the modified algorithms behave more like the decreasing versions of
their fit strategy.

Figure 8:  Impact on Rscore for different Deltas (random initial partition
speed).

With regards to the Rscore, a common trend can be verified for all algorithms,
where an algorithm’s Average Rscore increases with the value of $\delta$, as
can be seen in Fig. 8. This should be expected as the bigger the $\delta$, the
more variability there is between the items’ sizes in two consecutive
measurements of a stream.

With respect to the average Rscore, the algorithms that perform the best are
the Modified Any Fit algorithms and the NFD. The reason why the NFD appears
within the five best algorithms, is due to the increased amount of bins
required to pack the items into its bins. This is related to the modification
made to the existing approximation algorithms, presented in Sec. IV-C. This
modification leads to less rebalancing, as the partition might not have to be
assigned a different bin than it is currently assigned, if new bin is created
for it.

For a similar reason, the modified algorithms that perform the best with
regards to the Rscore, are also the ones that perform worst (compared to the
remaining modified algorithms) when evaluating the CBS. As such, on account of
the added rebalance concern within the modified algorithms, these present an
improvement when it comes to the rebalance cost compared to the existing
approximation algorithms.

We find the pareto front, so as to determine the set of solutions that are
most efficient, provided there are trade-offs within a multi-objective
optimization problem. Excluding MWFP, the modified algorithms are consistently
a part of the pareto front, as shown in Fig. 9, which implies these are a
competitive alternative when solving this variation of the BP problem.

(a)  Pareto front for $\delta=5$.

(b)  Pareto front for $\delta=25$.

Figure 9:  Pareto front for different deltas comparing the Cardinal Bin Score
and the Average Rscore.

###  VI-D Kafka Consumer Group Autoscaler Evaluation

The consumer group autoscaler, was developed as a proof of concept as to how
this variation of the Bin Packing problem could be applied in a message broker
environment. As such, we now present the results when running this system in
Maersk’s (HUUB) production message broker environment, with the compute
resources summarized by Table V.

TABLE V: Infrastructure used for experimentation Component |  Cloud Platform |  Resource Classification
---|---|---
Kafka Cluster (3 Nodes) |  AWS |  r5.xlarge
Kubernetes |  GCP |  GKE autopilot
Monitor |  GCP |  Kubernetes Deployment (GKE)
Controller |  GCP |  Kubernetes Deployment (GKE)
Consumer Group |  GCP |  As many Deployments as consumers in the group (GKE)

One of the first assumptions, was that this problem was a variation of the
SBSBP problem, and therefore, the consumer should present a constant maximum
capacity when challenged to work at peak performance. To obtain this value,
the consumer was tested in three very disparate conditions, specified in Table
VI, all requiring the consumer to be reading the data at its maximum
consumption rate. Between each test, we varied: the average amount of bytes
present in each partition; the number of destination tables in the data lake;
and the number of partitions assigned to the consumer instance. Fig. 10
presents the results of having the consumer run in these conditions, and
clearly shows a common mode for the maximum consumption rate, around
$2.3Mbytes/s$.

TABLE VI:  Testing conditions to obtain consumer maximum throughput measure.  Test ID | Total Bytes | Average Bytes | Number of Partitions | Number of Tables
---|---|---|---|---
Test 1 | $648\ Mbytes$ | $20\ Mbytes$ | $32$ | $1$
Test 2 | $100\ Mbytes$ | $0.86\ Mbytes$ | $116$ | $5$
Test 3 | $678\ Mbytes$ | $4\ Mbytes$ | $144$ | $5$
Figure 10:  Density Plot for the consumer’s measured throughput in the three
testing conditions.

##  VII Conclusions

The work introduces a deterministic approach to minimize the number of
consumers required working in parallel, where message brokers are concerned.
This minimizes operational costs. The approach assigns partitions to consumes
guaranteeing that the rate of production into a set of partitions is not
higher than the rate of consumption.

This study solves the consumer group autoscaling problem deterministically by
analogizing the issue to a Bin Packing problem. The analogy corresponds item
sizes to write speeds and bins to consumers. This paper also considers that
write speeds can change over time, and assignments need to adapt to these
changes. Reassignments pose a cost since they limit the consumers’ capacity to
read data. Terefore, we propose the Rscore to account for rebalancing costs.

To the best of our knowledge, there is no algorithm that accounts for the
dynamic aspect of our BP problem. Hence, we propose four new BP-based
heuristics that consider the re-scheduling costs (Rscore). Three of them are
proven to be competitive solutions when solving the multi-objective
optimization problem. Thus, the assignments they lead to have some robustness
to future write speed changes.

Lastly, this paper challenges some of Kafka’s core functionalities and
provides tested alternatives which can be used as a foundation so as to
improve the way in which a consumer’s load is modeled, and the manner in which
the load (partitions) is distributed between the elements of a consumer group.
Ultimately, our approach solves a real-world problem regarding the sensor
reads of a logistics company at lower operational costs than their previous
non-functioning solution.

## References

  * [1] L. Magnoni, “Modern messaging for distributed sytems,” in _Journal of Physics: Conference Series_ , vol. 608, no. 1. IOP Publishing, 2015.
  * [2] S. Burckhardt, D. Leijen, M. Fähndrich, and M. Sagiv, “Eventually consistent transactions,” in _European Symposium on Programming_. Springer, 2012, pp. 67–86.
  * [3] Y.-Y. Su and J. Flinn, “Slingshot: Deploying stateful services in wireless hotspots,” in _Proceedings of the 3rd international conference on Mobile systems, applications, and services_ , 2005, pp. 79–92.
  * [4] P. Carbone, S. Ewen, G. Fóra, S. Haridi, S. Richter, and K. Tzoumas, “State management in apache flink®: consistent stateful distributed stream processing,” _Proceedings of the VLDB Endowment_ , vol. 10, no. 12, pp. 1718–1729, 2017.
  * [5] A. D. Kshemkalyani, M. Raynal, and M. Singhal, “An introduction to snapshot algorithms in distributed computing,” _Distributed systems engineering_ , vol. 2, no. 4, p. 224, 1995.
  * [6] A. Wolke, B. Tsend-Ayush, C. Pfeiffer, and M. Bichler, “More than bin packing: Dynamic resource allocation strategies in cloud data centers,” _Information Systems_ , vol. 52, pp. 83–95, 2015.
  * [7] W. Song, Z. Xiao, Q. Chen, and H. Luo, “Adaptive resource provisioning for the cloud using online bin packing,” _IEEE Transactions on Computers_ , vol. 63, no. 11, pp. 2647–2660, 2013.
  * [8] M. Nardelli, V. Cardellini, V. Grassi, and F. L. Presti, “Efficient operator placement for distributed data stream processing applications,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 8, pp. 1753–1767, 2019.
  * [9] F. Furini, E. Malaguti, R. Medina Durán, A. Persiani, and P. Toth, “A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size,” _European Journal of Operational Research_ , vol. 218, no. 1, pp. 251–260, 2012.
  * [10] M. Dell’Amico, F. Furini, and M. Iori, “A branch-and-price algorithm for the temporal bin packing problem,” _Computers & Operations Research_, vol. 114, p. 104825, 2020.
  * [11] M. Delorme, M. Iori, and S. Martello, “Logic based benders’ decomposition for orthogonal stock cutting problems,” _Computers & Operations Research_, vol. 78, pp. 290–298, 2017.
  * [12] M. De Cauwer, D. Mehta, and B. O’Sullivan, “The temporal bin packing problem: an application to workload management in data centres,” in _2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)_. IEEE, 2016, pp. 157–164.
  * [13] N. Aydın, İ. Muter, and Ş. İ. Birbil, “Multi-objective temporal bin packing problem: An application in cloud computing,” _Computers & Operations Research_, vol. 121, p. 104959, 2020.
  * [14] F. Furini and X. Shen, “Matheuristics for the temporal bin packing problem,” in _Recent Developments in Metaheuristics_. Springer, 2018, pp. 333–345.
  * [15] Q. Xia, W. Liang, and W. Xu, “Throughput maximization for online request admissions in mobile cloudlets,” in _38th Annual IEEE Conference on Local Computer Networks_. IEEE, 2013, pp. 589–596.
  * [16] V. Gulisano, R. J. Peris, M. P.Martinez, C. Soriente, and P. Valduriez, “Streamcloud: An elastic and scalable data streaming system,” _IEEE Trans. on Parallel and Dist. Systems_ , vol. 23(12), pp. 2351–2365, 2012.
  * [17] T. Heinze, Y. Ji, Y. Pan, F. J. Grueneberger, Z. Jerzak, and C. Fetzer, “Elastic complex event processing under varying query load.” _BD3@ VLDB_ , vol. 1018, pp. 25–30, 2013.
  * [18] T. Heinze, V. Pappalardo, Z. Jerzak, and C. Fetzer, “Auto-scaling techniques for elastic data stream processing,” in _2014 IEEE 30th Int. Conf. on Data Engineering Workshops_. IEEE, 2014, pp. 296–302.
  * [19] E. G. Coffman, J. Csirik, G. Galambos, S. Martello, and D. Vigo, “Bin packing approximation algorithms: survey and classification,” in _Handbook of combinatorial optimization_ , 2013, pp. 455–531.
  * [20] B. S. Baker and E. G. Coffman, Jr, “A tight asymptotic bound for next-fit-decreasing bin-packing,” _SIAM Journal on Algebraic Discrete Methods_ , vol. 2, no. 2, pp. 147–152, 1981.
  * [21] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, “Worst-case performance bounds for simple one-dimensional packing algorithms,” _SIAM Journal on computing_ , vol. 3, no. 4, pp. 299–325, 1974\.
  * [22] M. R. Garey and D. S. Johnson, ““strong”np-completeness results: Motivation, examples, and implications,” _Journal of the ACM (JACM)_ , vol. 25, no. 3, pp. 499–508, 1978.