rss rss hh new
rss_rss_hh_new

 -

rss_rss_hh_new

 - e-mail

 

 -

LiveInternet.ru:
: 17.03.2011
:
:
: 51

:

, 01 2017 . 11:07 +
, (heavy hitters). . Qrator Labs janatem .


, , , . , - NGINX , , , .

( ) . . , , , .

, . , .

, . , , .

Decay-based count, (. ), .



:
  • Threshold-$t$. , $t$ .
  • Top-$k$. $k$ .
  • , .

.


, , . (, . .). , .


  • , . , .
  • , . , , , .
  • . , . , $\tau$, .


  • . $(\varepsilon,\delta)$- : $1-\delta$ $\varepsilon$, , $(\varepsilon, \delta)$.
  • , , , , top-$k$, .


, , . . , , . . DRAM , DRAM . , , . L2 . , .


. - . , . , . . , (exponential moving average, EMA) .

EMA. , . . -, . -, .


, ( ), . , . , - . , , , . , :
  • Packet sampling
  • Space saving algorithm
  • HashParallel
  • HashPipe
  • Count-min sketch


, , .

$\{event_k\}_{k\in I}$, $k$ $I\subset\mathbb{Z}$.

: $event_k = t_k$, : $t_{k_1} < t_{k_2}$ $k_1<k_2$. : $t_k\in\mathbb{Z}$, : $t_k\in\mathbb{R}$.

, , . . $\{t_k\}$ :

$t_k = \varphi+pk,\quad k\in\mathbb{Z},$


$p>0$, $\varphi\in[0,p)$ , . . , , $r=1/p$.

$r=r(\{t_k\})$ . , .

, , $c_k$ . , : $event_k = (t_k, c_k)$.

$s$, , $\hat{r}=\hat{r}(s)$, $r\approx\hat{r}$. $event_k$:

$s \leftarrow update(s, event_k),$


$update()$ , . $update()$:
  • : $update_1(s, event_k)=s+1$;
  • : $update_c(s, event_k)=s+c_k$;
  • (EMA) $\beta$. $s=(v,t)$ : EMA .

    $update_{EMA}((v, t), event_k) = (v', t'),$

    $v'=\beta + (1-\beta)^{t_k-t}\cdot v,\quad t'=t_k$.

. , $i=1,\dots N$, . $event_k = (t_k, i_k)$ (, , $event_k = (t_k, i_k, c_k)$), $i_k$ . $k$, $i$ $I_i = \{k\mid i_k = i\}$.


:

$v(t) = v_0 e^{-\lambda t},$


$v_0$ , $v(t)$ $t$, $\lambda$ ( ). , .

:

$\tau = 1/\lambda,\quad\alpha = e^{\lambda}.$


$\lambda$ $\tau$, $\tau$ , .

, $v$, , , .

. 1 , $v$ .



1: $v$

$v$ , . $s$, $t_{now}$ $v$ :

$v=\alpha^{s-t_{now}}.$


.


(). , , , ( , ), .


$s$ . $s$ $s'$, :

$\alpha^{s'-t_{now}} = \alpha^{s-t_{now}} + 1.$


$v$ , $v$ , ( ). .

$update()$ :

$update_1(s, event_k) = t_k + \log_\alpha(1 + \alpha^{s-t_k}).$


$t_{now}$ $t_k$ .


$r$, $p=1/r$. .

, $t_{now}=t_n$ $n$, $s$ :

$\alpha^{s-t_{now}} = \sum_{k=-\infty}^n\alpha^{t_k-t_{now}}=\sum_{k=0}^\infty \alpha^{-kp},$



$\alpha^{-\Delta s} + \alpha^{-p} = 1,$


$\Delta s = s-t_{now}$ .

:
$t_{now}=t_n+\psi$, $\psi\in[0,p)$. $\psi$:

$\alpha^{-(\Delta s+\psi)} + \alpha^{-p} = 1.$


, . , , , $\psi=0$ $\psi=p$:

$r^-\le r < r^+,$



$\begin{align}r^+&=r^+(\Delta s)=\frac1{\log_\alpha(1+\alpha^{-\Delta s})}\\r^-&=r^-(\Delta s)= \left\{\begin{array}{ll}\frac1{-\log_\alpha(1-\alpha^{-\Delta s})}&\mbox{ }\Delta s>0\\ 0&\mbox{}\end{array}\right.\end{align}$


$r^+$ $r^-$ $s$ (. . 2), , , .



2: $r^-$ $r^+$ $\tau=15$

( ) $r^+$ $r^-$. , , .


, .

-, , . $r_{max}=1$. $\Delta s = s-t_{now}$ $\sigma_{max}$, :

$r^-(\sigma_{max}) = r_{max}.$


$\sigma_{max}$ :

$\sigma_{max}=\tau\ln\tau+\omega(\tau),$


$0\le\omega(\tau)\le1/2$.

-, () : $\Delta s$ $r^+$ $r^-$ , $\Delta s$ .

, . $t_{now}$ , $\sigma_{max}$, . 64- , 100 . .



EMA , ( ) . : $s$ , $v=\alpha^{s-t_{now}}$ , . $T_{vanish}$, , $\tau$ . $T_{vanish}=T_{min}+\sigma_{max}$, $T_{min}$ , . $T_{min}$, : $T_{vanish} = O(\tau\ln\tau)$ .

, $T_{vanish}\cdot r_{max}$ . , $\tau$, L3 L2. , .

-, . , $s$ $s-t_{now} \le T_{min}$.

Decay-based count



:

$\rho_\tau(x) = \tau\ln(1+e^{x/\tau}) = \log_{\alpha}(1+\alpha^x).$


:

$s' = t_{now} + \rho_\tau(s-t_{now}).$


, $\rho_\tau$. , , , ${R:\mathbb{Z}\to\mathbb{Z}}$, , :

$R_\tau(T) \approx \rho_\tau(T)\quad\mbox{ }T\in\mathbb{Z}.$


, , . , - 0.5 .
, , , . , 10 , , $R_\tau$ : $\left|R_\tau(T) - \rho_\tau(T)\right| \le 10.$

$R_\tau$ .

$R_\tau$: FPU


$\rho_\tau$ . 100 , .

$R_\tau$:


, .

-,

$\rho_\tau(-x) = -x + \rho_\tau(x),$


$R_\tau(T)$ $T\le0$.

-,

$\rho_\tau(x)\to 0 \mbox{ } x\to-\infty,$


$T_{min}>0$, $R_\tau(T)=0$ $T\le-T_{min}$. $T_{min}$ :

$T_{min}=\lceil t_{min}\rceil,\quad \rho_\tau(t_{min})=1/2,$


$T_{min}=\lceil-\log_\alpha(\alpha^{1/2}-1)\rceil=\lceil-\tau\ln(e^{1/{2\tau}}-1)\rceil.$

, $R_\tau(T)$ ${T_{min}<T\le0}$.

$\rho_\tau(x)$ . 3. , $\tau$ .



3: $\rho_\tau(x)$

$R_\tau$ $T_{min}$ , . 0 $\rho_\tau(0)=\tau\ln2$, $T_{min}\log_2(\tau\ln2)$ .

:

$\begin{align} t_{now}& \leftarrow getTime()\\ \delta & \leftarrow \min\{|s-t_{now}|, T_{min}\}\\ \delta' &\leftarrow R(-\delta)\\ s' &\leftarrow \delta' + \max\{s, t_{now}\} \end{align}$



1/2, .


:
1. EMA;
2. FPU ( exp() log() );
3. .

: pastebin.com/wiiEe6MP.

update() $\tau=100000$ ( $R_\tau$ L1) 1, 2 3 125, 100, 11 , .

. , . , -, , -, , . : .


Qrator. , .
Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/334354/

:  

— — : [1] []
 

:
: 

: ( )

:

  URL