\section{Baseline with Middleware (90 pts)\label{sec:3}}

    This experiment extends on the design of experiment \ref{subsec:2_one-server} by introducing one and two \mw{}s
    into the system. The middleware can be configured to have a variable amount of worker threads where each worker
    thread handles one paired request-reply operation. This parameter is also considered in the evaluation. The
    configurations are listed in table \ref{tab:30_setup}.

    \begin{table}
        \scriptsize{
            \begin{tabular}{|l|c|}
                \hline Number of servers                & 1 \\
                \hline Number of client machines        & 3 \\
                \hline Instances of memtier per machine & 1 (3.1) / 2 (3.2) \\
                \hline Threads per memtier instance     & 2 (3.1) / 1 (3.2) \\
                \hline Virtual clients per thread       & [1, 2, 4, 8, 16, 32, 48] \\
                \hline Workload                         & Write-Only and Read-Only \\
                \hline Multi-Get behavior               & N/A \\
                \hline Multi-Get size                   & N/A \\
                \hline Number of middlewares            & 1 (3.1) / 2 (3.2) \\
                \hline Worker threads per middleware    & [8, 16, 32, 64]  \\
                \hline
            \end{tabular}
        }
            \caption{Experimental parameters for experiments 3.1 and 3.2.\label{tab:30_setup}}
    \end{table}

    \subsection{One Middleware\label{subsec:3_one-middleware}}

        This experiment is similar to experiment \ref{subsec:2_one-server}, but here each \cli{} connects to the single
        instance of \mw{} which itself connects to the single instance of \srv{}.

        \begin{figure*}
            \vspace*{-.5\baselineskip}
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_throughput.png}
                    \caption{Request throughput.\label{fig:single_mw_tp}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_queue-size.png}
                    \caption{Queue sizes.\label{fig:single_mw_qs}}
                \end{subfigure}
            }
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_mc-comm-time.png}
                    \caption{Memcached communication time.\label{fig:single_mw_mct}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_queue-wait-time.png}
                    \caption{Queue waiting time.\label{fig:single_mw_qwt}}
                \end{subfigure}
            }
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_response_time.png}
                    \caption{Response times.\label{fig:single_mw_rt}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_throughput-il.png}
                    \caption{Throughput calculation using the interactive law with an adjusted client
                             count.\label{fig:single_mw_tp-il}}
                \end{subfigure}
            }
            \caption{\mw{} statistics based on SET and GET requests for various amounts of worker threads and active
                     clients.\label{fig:single_mw_all}}
        \end{figure*}

        \subsubsection{Explanation\label{subsubsec:3_one-middleware_summary}}

            Comparing the throughput of GETs with the baseline experiment only a small change in performance for 6
            clients is observed (the performance not reaching the stable phase which happens for 12 and more clients).
            The throughput of SET requests behaves most similarly to the baseline with 64 worker threads yet the
            throughput for 32 worker threads is in general higher for 48 and 96 connected clients. This observation will
            be discussed in the following paragraphs and explained with more data. It can be inferred that the
            throughput of a single client is limited to 11546 requests, a contrast to the measured 16334 without the use
            of a middleware. This limit occurs for 192 virtual clients. The throughput being lower for fewer worker
            threads is reasonable and the non-linear scaling highly likely due to the fact that \mw{}s have only 8
            physical cores.

            The response rates are also similar to the baseline experiment in general with SETs having a smaller
            response time than GETs. Looking at the constituents of response time (with detailed timings for queue
            waiting times and memcached communication and respective packet handling time) it can be observed that for
            few worker threads and many clients queue times grow from a certain point quasi-linear. The memcached
            communication and packet handling time does flatten though. The height of flattened sections can be
            explained due to thread scheduling (the flattened lines are all separated proportional to the number of
            worker threads divided by the core count of the machine). The reasoning for flattening due to the fact that
            the middleware cannot handle more requests in parallel and is therefore saturating for the worker thread and
            client configuration. This can be seen by queues growing for the configuration of active clients and
            threads.

            As such the total response time of the middleware is for a large amount of clients and few worker threads
            determined by the queueing time and for few clients and many worker threads determined mostly by the
            communication time with memcached.

            Coming back to the open question of why 32 worker threads perform better than 64 for 48 and 96 clients
            requires the use of the queue where requests are stored. As long as this queue is not at least the size of
            worker threads, performance impact can be expected due to worker threads being idle and waiting for a new
            request to process. This results in an effectively smaller throughput as only some threads are working but
            the threads waiting for a new element contend on a shared lock on the queue. Only once the queue at 192
            clients approaches 64 elements does the middleware become more saturated and is even more so at 288 clients.
            It is very close to the point of complete saturation when looking at the queue size, yet no real increase in
            throughput was measured. As the standard deviation for 288 clients and 64 worker threads is rather large
            compared to previous results allows the claim that beyond a certain amount of threads and connections the
            cloud environment is not scaling well.

            Overall it can be concluded that for 8\textendash 32 clients the maximal saturation point has been reached
            and for 64 threads the saturation point is within a few percent or has been reached.

            % A note on the large range for the memcached handling time at 12 total clients, 64 worker threads using SET
            % operations: Confirming with dstat logs it shows that performance decreases are observed on all connected
            % machines for the timestamp 03:09:23 (on the second repetition). This is with high probability an artifact of
            % running in a cloud environment where either an elephant flow was started or the machine migrated from one
            % rack to another. This was discovered after the machines have been turned off and a repetition for a single
            % data point deemed too costly. This outlier is less visible in the response time graphs as they scale
            % differently. Other outliers are not noteworthy to discuss.

    \subsection{Two Middlewares\label{subsec:3_two-middlewares}}

        This experiment is virtually identical to the previous experiment with the change of each \srv{} running two
        single-threaded memtier instances where the second connects to the newly added second \mw{}. As such each \mw{}
        is only subject to half the load compared to the previous experiment's single \mw{}.

        \begin{figure*}
            \vspace*{-.5\baselineskip}
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_throughput.png}
                    \caption{Request throughput.\label{fig:double_mw_tp}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_queue-size.png}
                    \caption{Queue sizes.\label{fig:double_mw_qs}}
                \end{subfigure}
            }
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_mc-comm-time.png}
                    \caption{Memcached communication time.\label{fig:double_mw_mct}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_queue-wait-time.png}
                    \caption{Queue waiting time.\label{fig:double_mw_qwt}}
                \end{subfigure}
            }
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_response_time.png}
                    \caption{Response times.\label{fig:double_mw_rt}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_throughput-il.png}
                    \caption{Throughput calculation using the interactive law with an adjusted client
                             count.\label{fig:double_mw_tp-il}}
                \end{subfigure}
            }
            \caption{\mw{} statistics based on SET and GET requests for various amounts of worker threads and active
                     clients.\label{fig:double_mw_all}}
        \end{figure*}

        \subsubsection{Explanation\label{subsubsec:3_two-middlewares_summary}}

            Comparing the throughput of GETs with the baseline experiment and the experiment with a single \mw{} no
            large differences can be observed except a stable phase from the very beginning. The throughput for SET
            requests behaves much ``cleaner'' for increasing amounts of worker-threads, meaning that for not enough
            saturation by connected clients the resulting performance for SETs behaves the same. Also more throughput
            occurs throughout the system. The maximum observed throughput is 15312 requests, very close to the baseline
            experiment of 16334 requests. The middleware shows to be a reasonably small disturbance to the overall
            system for enough worker threads active. The scaling of throughput for worker threads follows the same
            reasoning as in experiment \ref{subsec:3_one-middleware}.

            The response times reflect the increased throughput with overall lower numbers. There is less spread for SET
            requests amongst different amounts of worker threads. A comparison between the response times with a single
            \mw{} and two \mw{}s is conducted in subsection \ref{subsec:3_summary}. The memcached communication and
            packet handling time doubling follows from the fact that with two concurrent \mw{} SET requests sent to the
            same \srv{} a serialization of requests is expected (as the \srv{} is only single-threaded). Thusly larger
            response times on the end of memcached are observed. This would result in an overall higher response time if
            not for the fact that as there are now two \mw{}s, each instance is only subject to half the load generated
            by \cli{}s. As such the queue sizes are also only half of what was measured when compared to a single
            instance of \mw{}.

            The queue sizes grow disregarding the type for different amounts of worker threads similarly. Even though
            fewer load is received by each middleware the system still has growing queues. Applying the previously
            stated argument of the system being fully saturated for queues of size exceeding the current amount of
            worker threads shows that this experiment as well shows saturation points for 8\textendash 32 worker threads
            and being very close to the saturation point of 64 worker threads.

            An artifact of running in a cloud environment can be seen for 6 clients and 32 worker threads where the
            throughput is low and the response time including memcached communication unexpectedly high. Looking at the
            respective logs shows a likely network issue on the second run, as no system is overtaxed yet the
            \srv{} is not sending enough data. Statistics generated by ping indicate unusually high response times for
            communication between \mw{}s and the single \srv{}. This reflects in the memcached communication time and
            response time of the system. The system is for most of the supposedly stable window overall very shaky.

    \subsection{Summary\label{subsec:3_summary}}

    \begin{table}
        \def\sym#1{\ifmmode^{#1}\else\(^{#1}\)\fi}%
        \footnotesize{
            \centering
            \begin{tabular}{l*{10}{c}}
                \toprule
                & & \multicolumn{2}{c}{Throughput}  & \multicolumn{2}{c}{Response Time} &
                \multicolumn{2}{c}{Queueing Time} & \multicolumn{2}{c}{Miss Rate} \\
                \cmidrule(lr){3-4}\cmidrule(lr){5-6}
                \cmidrule(lr){7-8}\cmidrule(lr){9-10}
                Type  & Machine & Exp 3.1  & Exp 3.2  & Exp 3.1 & Exp 3.2 & Exp 3.1 & Exp 3.2 & Exp 3.1 & Exp 3.2 \\
                \midrule
                GET      & \cli & 2936.83  & 2923.78  & 65.32 & 65.92 & N/A   & N/A   & 0.00 & 0.00 \\
                         & \mw  & 2939.61  & 2929.16  & 64.17 & 69.02 & 42.17 & 20.60 & 0.00 & 0.00 \\
                \addlinespace
                SET      & \cli & 11549.70 & 15308.52 & 16.73 & 12.55 & N/A   & N/A   & N/A  & N/A \\
                         & \mw  & 11546.60 & 15312.49 & 8.07  & 11.29 & 3.80  & 3.01  & N/A  & N/A \\
                \bottomrule
            \end{tabular}
            \caption{Evaluation of maximum throughputs for one and two \mw{}s in the system with 192
                     clients and 64 worker threads.\label{tab:3_throughput-summary}}
        }
    \end{table}

        As already mentioned, in the baseline experiments without the use of a middleware the evaluation of GET and SET
        requests follows similar base criteria, namely throughput and response time. In case where these are not
        sufficient, it is possible to use the middleware's instrumentation and deduce the system behaviour from them.

        In the case of GET requests the behaviour between experiments \ref{subsec:2_one-server},
        \ref{subsec:3_one-middleware} and \ref{subsec:3_two-middlewares} is comparable. Oddly for six clients the single
        \mw{} configuration is not immediately saturated for any amount of worker threads. Only at twelve clients this
        saturation occurs. It is quite likely that the overhead of the middleware is just high enough to introduce
        minimal latencies in such a configuration as the system has empty queues and as such it is not a problem of
        queueing. As experiment \ref{sec:2} and \ref{sec:3} were run on two different instances of machines changes in
        benchmarking performances are expected, yet the general behaviour should stay comparable. This is the case for
        GETs in our experiments as well as for SETs.

        In the case for SET requests the trends with more active clients introducing more throughput does not always
        match. As long as worker threads are not oversaturated the performance will not degrade. After oversaturating
        the system the middleware slows down the system as it cannot handle more requests. There is a trend of more
        worker threads introducing more throughput. Also adding another middleware helps and actually shows to scale
        better than adding more worker threads when comparing the throughput graphs for the total amount of comparable
        worker threads between both experiments (for experiment \ref{subsec:3_two-middlewares} half the worker thread
        count must be evaluated as two middlewares are used). This is to be expected as at some point scheduling
        overhead on a single system results in slowdowns. Another viable option is a better allocation in the cloud
        environment.

        For a thorough and clear evaluation of system behaviour it is necessary to include the queue and memcached
        communication time.\newline
        As already observed for a given amount of worker threads the memcached communication begins to flatten for a
        certain amount of active clients. The trend is that more worker threads can handle more clients but the time to
        process grows. This aligns well with the fact that there is contention for the actual cores of the machine by
        each worker thread. A detailed explanation on the respective behaviour has been given in
        subsubsection \ref{subsubsec:3_one-middleware_summary}. The queue sizes also reflect in the queue waiting times
        appropriately for both experiments in this section. Additionally the queue sizes offer a good metric in
        evaluating the saturation of the system and aid in defining the maximum throughput for each configuration of
        worker threads. Once the queue sizes reaches the amount of worker threads there is no more more waiting on the
        next task for each worker thread but adding more elements than there are worker threads slows down the system as
        at that point no bijection exists between worker threads and items to process.

        % Comparing the measured performances for GET requests in \ref{tab:3_throughput-summary} gives for \cli{}s and
        % \mw{}s similar results except for the discrepancy in response time for experiment
        % \ref{subsec:3_two-middlewares}.

        % The response time differences can be explaining by assuming machines to perform
        % similar amongst experiments, thus a standard average is taken. For machines performing differently this can
        % result in being off from the weighted mean, which is the case here. The discrepancy in performance between
        % different machines occurs due to the unavailability of deciding machine allocations in the cloud environment and
        % them being sometimes moved from one rack to another (as has been shown by the previous outliers). The queue time
        % between one and two \mw{}s being different by a factor of two stems from the fact that two \mw{}s subject to
        % half the client load, henceforth a smaller queue is expected for heavy workloads.\newline
        % For SET requests an increase in performance is observed using two \mw{}s with a corresponding decrease of the
        % response time measured at memtier. The difference between response times observed at the middleware and memtier
        % are much larger for the case of a single middleware. A reasonable explanation could be related to the middleware
        % receiving SET requests with a single thread. If multiple requests buffer on the socket then multiple complete
        % requests can be processed much quicker from it than having to receive each TCP alone. Both systems do have the
        % same queue waiting time so the worker threads are performing similarly well. This strengthens the assumption
        % that OS-side buffering of TCP packets occur and not somewhere measurable within the middleware.

        As the middleware doesn't include the full response time the interactive law doesn't hold when assuming the
        whole system is only \mw{} \textendash{} \srv. To fix this the interactive response time law, stated with

        $$ R = \frac{N}{X} - Z $$

        allows the modification of either $N$ (number of active clients) or setting $Z$ (the thinking time) to a
        non-zero value. The latter is usually done by using the RTT between \srv{} and \mw{} (and add some minimal extra to
        allow memtier processing time). To adjust $N$ it is relevant
        to define what the number of actual jobs are in the current system. This is defined by two components, the queue
        of the system modelling inactive jobs still to be processed and the active participants which are inferred from
        the system throughput and memcached communication time. Multiplying the throughput of the system with the time
        it takes for workers to have completely handled communication with memcached gives a good amount of active
        workers. Adding these two together and dividing by the observed response time of the middleware gives a
        prediction of the throughput on the system in relation to active participants.
        $$
        X_{pred} = \frac{X * \text{Time\textsubscript{Memcached}} +
                   \text{Size\textsubscript{Queue}}}{\text{Time\textsubscript{Middleware}}}
        % \begin{cases}
        %     \text{Size\textsubscript{Queue}} + \text{Clients}   & \quad \text{if Worker Threads > Clients} \\
        %     \text{Size\textsubscript{Queue}} + \text{Worker Threads}          & \quad \text{otherwise}
        % \end{cases}
        $$
        In the following the interactive law is applied and the response time derived using the latency from each
        experiment. Figures \ref{fig:single_mw_tp-il} and \ref{fig:double_mw_tp-il} depict the interactive law applied
        with a modified amount of clients and in figure \ref{fig:3_il} the application of the thinking time is compared
        to with measurements from memcached. In general the interactive law holds in both cases but the throughput
        calculation shows cleaner results and is thusly used onwards. Some outliers are expected for high loads as
        graceful failures are not the nature of computers.

        \begin{figure*}
            \vspace*{-.5\baselineskip}
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mw_response-time-il.png}
                    \caption{\mw{} interactive law deriving the response time.\label{fig:mw_rt-il}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-1_mt_response_time.png}
                    \caption{\cli{} measured response time.\label{fig:mt_rt}}
                \end{subfigure}
            }
            \makebox[1\linewidth][c]{%
                \centering
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mw_response-time-il.png}
                    \caption{\mw{} interactive law deriving the response time.\label{fig:mw_rt-il}}
                \end{subfigure}
                \begin{subfigure}[t!]{0.55\textwidth}
                    \centering
                    \includegraphics[width=1\textwidth]{../data_analysis/figures/3-2_mt_response_time.png}
                    \caption{\cli{} measured response times.\label{fig:mt_rt}}
                \end{subfigure}
            }
            \caption{Visualizations of the interactive law plotted for experiments \ref{subsec:3_one-middleware} and
                     \ref{subsec:3_two-middlewares}. High loads result in less correct predictions.\label{fig:3_il}}
        \end{figure*}
