{'fraction_non_alphanumeric': 0.023430939675488257, 'fraction_numerical': 0.010726765446813122, 'mean_word_length': 5.095014033349843, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
MigCast in Monte Carlo: The Impact of Data Model Evolution in NoSQL Databases

During the development of NoSQL-backed software, the data model evolves naturally alongside the application code. Especially in agile development, new application releases are deployed frequently causing schema changes. Eventually, decisions have to be made regarding the migration of versioned legacy data which is persisted in the cloud-hosted production database. We solve this schema evolution problem and present the results of near-exhaustive calculations by means of which software project stakeholders can manage the operative costs for data model evolution and adapt their software release strategy accordingly in order to comply with service-level agreements regarding the competing metrics of migration costs and latency. We clarify conclusively how data model evolution in NoSQL databases impacts the metrics while taking all relevant characteristics of migration scenarios into account. As calculating all possible combinatorics in the search space of migration scenarios would by far exceed computational means, we used a probabilistic Monte Carlo method of repeated sampling, serving as a well-established means to bring the complexity of data model evolution under control. Our experiments show the qualitative and quantitative impact on the performance of migration strategies with respect to intensity and distribution of data entity accesses, the kinds of schema changes, and the characteristics of the underlying data model.


INTRODUCTION
Developing or maintaining a software-as-a-service application requires the management of steadily increasing amounts of data and their co-evolution with the software code [17,34]. In this context, schema-flexible NoSQL databases have become especially popular backends in agile development. NoSQL databases allow application developers to write code assuming a new data model that is different from the current database schema [13,36]. Furthermore, new software releases can be deployed without migration-related application downtime. In fact, a very recent empirical study on the evolution of NoSQL database schemas has shown that software releases include considerably more schema-relevant changes (>30% compared to 2% with relational databases) [37]. Furthermore, NoSQL database schemas generally grow in complexity over time just like relational database schemas, however, they take longer to stabilize. Arguably, it can be deduced that schemas in NoSQL databases evolve more flexibly alongside the software application code.
Though, eventually, the issue of handling the variational data in the NoSQL database has to be addressed. Imagine as a software project stakeholder, you are planning the next software release and need to take all data into account that is persisted in your cloudhosted production database. A decision has to be made as to when to migrate which legacy data that is structured according to earlier schema versions. If all of the legacy data is curated according to the latest data model in one go at the release of schema changes, i.e., with an eager migration strategy, then maximal charges are produced with the cloud provider. In addition, a lower application performance must be expected during the migration process in case that application downtime needs to be avoided.
Currently, cloud providers such as Google Cloud charge for database reads, writes, and deletes, which we have realized in our cost model. Note that simply adding a field to the data schema requires updating and rewriting of all affected data entities in the database. Curating all variational data by eagerly migrating all legacy entities can significantly drive up the operational costs for the cloud service, especially in case of frequent software releases. For instance, for 10M persisted entities on Google Cloud and 100 monthly schema changes on average throughout a year, charges of approx. USD 13,000 are incurred just for database writes alone 1 -not even counting costs for database reads or for storing the data.
The benefit of this investment is that the application then accesses a structurally homogeneous database instance. Then, reads and writes against the database come at no migration-induced overhead accounting for structural variety and hence, the time that it takes for the requested data entities to be retrieved, the data access latency, is minimal. Short access times are indeed crucial to application performance, especially in cloud-hosted applications [3,7,9,14].
If latency is the sole criterion, then an eager migration strategy is clearly most suitable. If, on the other hand, saving costs is the most important criterion, then a lazy migration strategy should be applied which minimizes migration costs, as data remains unchanged in the event of a release. In this case, if a legacy entity is accessed, it is migrated individually and on-the-fly, then being in congruence with the latest schema version, yet introducing a considerable runtime overhead [22,27,35]. These two metrics, migration costs and data access latency, are in fact competitors in a tradeoff, which is schematically depicted in Figure 1. The metrics cannot be optimized independently from each other and thus, a choice of a migration strategy is also a choice on the tradeoff between these metrics at different opportunity costs for alternative migration strategies.
In fact, the growing importance of not only cost but also energy efficiency is reflected in the dedication of entire workshops to Green Data Centers [24,28]. Similarly, service-level agreements are oftentimes formulated as Green SLAs [5], that is, as SLAs put in place in order to save energy. Although the correlation between migration costs and energy consumption is still being researched, it can surely be assumed that a reduction of data migration (and thus of migration costs) implies a reduction of energy consumption (and thus of the 2 footprint caused by this migration). Thus, the tradeoff between the metrics of migration costs and latency should be decided upon while keeping in mind that any compromise also affects the application system's energy consumption. In any case, a decision by a software project stakeholder on the migration of legacy entities can only then be realized as a certain cost-aware compromise that complies with latency-related SLAs, if the relationship between these metrics is clarified and respective opportunity costs are completely transparent, which we contribute in this paper. In fact, the data management research community has identified data model evolution as one of the hardest problems that is currently being ignored [40]. Especially when a database is considered to be run in a cloud-hosted environment, concerns about high costs are most often cited in surveys, while increased latency being an issue as well [30]. We argue that the lack of cost transparency regarding data migration costs and latency should be a crucial issue to all stakeholders. In this paper, we conclusively investigate and clarify the impact of schema evolution on both metrics for common migration strategies in respect of all relevant migration scenarios.
Yet, solving the schema evolution problem is not trivial, because data migration scenarios are highly complex as they rely on many factors that influence the impact on the metrics. Completely searching the solution space would by far exceed computational means. We use a probabilistic Monte Carlo method of repeated sampling to investigate the scenario characteristics while bringing the complexity of the problem under control [16,31] We parameterize each scenario and calculate the metrics for each migration strategy by means of the tool-based migration advisor MigCast, which we presented in earlier work [22,23]. Our MigCast tool stands on the tradition of advisors in database technology [6] by maintaining a cost model and forecasting migration costs for alternative data migration strategies. By repeatedly sampling all relevant migration scenarios and randomizing some algorithm parameters-the Monte Carlo method-we uncover the correlations of the scenario characteristics and their impact on the metrics. Probabilistic approaches have been applied successfully regarding research questions in database management [1,12,19,25,26,38,41].
Contributions. Our paper makes the following contributions: • By means of near-exhaustive calculations, we investigate in depth and clarify conclusively how schema evolution in NoSQL databases impacts the competing metrics migration costs and latency. We investigated all relevant migration scenario characteristics with an underlying cost model that takes into account (i.) intensity and distribution of data entity accesses, (ii.) different kinds of schema changes, and (iii.) characteristics of the data model. • We present the results and discuss the implications such that software project stakeholders can manage and control the operative costs for schema evolution and adapt the pace of their software release strategy accordingly in order to ascertain the compliance with cost-and latency-related service-level agreements. • We are the first to apply a probabilistic Monte Carlo method of repeated sampling in order to bring the inherent complexity of the schema evolution problem under control. • For all relevant scenario characteristics, we (i.) quantify the average opportunity costs for each migration strategy, (ii.) identify multi-type schema modification operations as the cost driver of schema evolution, (iii.) find a predictive migration strategy utilizing the Pareto principle to be the best compromise between the metrics with regard to SLA compliance, and (iv.) identify high cardinality of the relationships of the underlying data model as the cause for a high variance of the impacts on the metrics.
Structure. This present paper is structured as follows: In the preliminaries, Section 2, we clarify the schema evolution problem, introduce the migration strategies and our terminology, and motivate the Monte Carlo approach. Afterwards, we address related work in Section 3. In Section 4, the system architecture and methodology of the experiment settings are specified. A detailed presentation of the experiment results follows in Section 5. In Section 6, we evaluate the results and discuss their implications, before we conclude this paper in Section 7.
In this section, we clarify the schema evolution problem, introduce the investigated data migration strategies as well as the used terminology, and motivate the Monte Carlo approach. Figure 2 illustrates the data model of an online game that we used in our MigCast in Monte Carlo experiments. The data model of the application has the entity types Player, Mission, and Place (see D.). In the figure, a migration scenario is shown at a certain schema version. The application code queries data entities against the current schema version. During the development of the application, the data model has undergone many changes (see S.) so that variational data, which still abides by older schema versions, has to be curated when legacy entities need to be accessed (see W.). These queries then have to be rewritten and are migrated on-the-fly in order to match the current schema version. In the figure, a legacy entity of the type Mission is currently being updated, whose schema was subject of a modification operation that renamed the property score to points. Thus, the entity is migrated to match the current schema, which causes on-read migration costs. When data entities become legacy entities through a schema change and are instantaneously migrated to match this schema version, then we count these migration costs towards on-release costs.

The Schema Evolution Problem
In order to investigate the impact of schema evolution on the competing metrics of migration costs and latency, we base the calculations of MigCast on a cost model that takes into account (W.) the intensity and distribution of data entity accesses, (S.) the different kinds of schema changes, and (D.) the cardinality of the relationships of the underlying data model. These investigated characteristics are highlighted in Figure 2 in blue and are varied as detailed in Table 1 on page 8.

Investigated Data Migration Strategies
A migration strategy has to be decided for when schema changes are implied through new releases of software application code. Each migration strategy handles the migration of legacy data differently, thereby settling on a different compromise regarding the tradeoff between the competing metrics of migration costs and latency. We define migration costs as the charges occasioned by migrating the legacy data according to the most current data model and (data access) latency as the time that it takes for the data to be retrieved.
Through the eager migration strategy, all legacy entities are migrated according to the latest schema version. Then, latency is optimal as the application code can access a structurally homogeneous database instance, yet migration costs are maximal. With lazy migration, legacy data remains unchanged in the event of a release, incurring minimal migration charges, yet introducing a runtime overhead on reads and writes [22]. The migration strategies are complemented by two more proactive strategies, which act in advance of situations when migrating legacy entities could cause significant latency overhead, the incremental and the predictive migration strategy. With these strategies, a compromise is reached between the competing metrics.
The incremental migration strategy migrates all legacy entities at certain points in time. Lazy periods of time are then interrupted by regular bouts of tidying up the structurally heterogeneous database instance in order to get rid of the runtime overhead intermittently. In order to keep a steady balance on the tradeoff between migration costs and latency, predictive migration is applied when new application code is released that includes schema changes. Predictive migration allows improving latency at moderate costs in case that data entity accesses are Pareto distributed, i.e., concentrate on particular entities. Then, the prediction is based on the assumption that the oftener entities were accessed in the past, the more likely it is that they be accessed again in the future. The predictive migration strategy is implemented by keeping track of past data accesses and ordering the accessed entities accordingly via exponential smoothing. This established technique in time series data weighs the entities by their actuality and access frequency [29]: The more recent the entity accesses, the higher the weight of the entity. Weights decrease exponentially over time simulating an aging process of the entities by accounting for actuality as well as for access frequency.

Motivating a Monte Carlo Approach
In order to enable software project stakeholders to manage the impact of schema evolution, it has to be investigated how relevant factors influence the metrics migration costs and latency. A straightforward approach would be to assume averages for each of the parameters describing a migration scenario, but that would not provide information how the metrics vary and potentially obscure a correlation between scenario characteristics and their impact on the metrics. Furthermore, averages are not reasonably applicable in case of data entity accesses. However, by means of the Monte Carlo approach [16,31,42], that is, an approach utilizing the Monte Carlo method, this correlation can be uncovered. It is a well-established approach used in the data management context [1,12,19,25,26,38,41].
The Monte Carlo method is used to solve problems that are deterministic as such, but more efficiently solved by probabilistic means, that is, when there are too many possibilities to be calculated exceeding the computational means, when relevant input variables of the computations are unknown or their acquisition costly [16,31,42]. Then, a repeated sampling of the input variables of the deterministic algorithm uses random values during the calculation in order to obtain a distribution of results (refer to Subsection 4.1 as to how input parameters are randomized). The sample mean of a metric can then be interpreted as the most probable prediction [16,31,42]. By knowing this sample mean and the possible range of the metrics, stakeholders are enabled to assess and effectively manage the potential risk that usually comes along with a lack of cost transparency and possible variance of the metrics. When applying the Monte Carlo method to our use case of schema evolution, we had to decide how often the sampling needs to be repeated so that the results can be generalized. We now introduce the necessary notions in this context and then return to this question.
In Figure 3, the projected migration costs of 12 releases of schema changes are depicted in a Scatter plot (a.) and a Box-Whisker plot (b.) for the eager migration strategy. The projections are based on 10 runs of a Monte Carlo approach using the migration advisor  MigCast. Release number 11 shows a rather high sample mean. Sample means in the Scatter plot are implemented as arithmetic averages and in the Box-Whisker plot as medians. Outliers are depicted in our Box-Whisker plot as dots and taken into account when calculating the median. If there are no outliers depicted, then all calculated values are within a certain range indicated as boxes, the interquartile range (IQR) or mid-range [42], together with their whiskers. The whiskers determine a range calculated through subtracting the absolute value of the IQR, multiplied by a factor 1.5, from the lower quartile 1 and adding the very same value to the upper quartile 3 , i.e., 1 − 1.5 | IQR| and 3 + 1.5 | IQR |.
As can be noted in Figure 3, of these 10 MigCast runs relatively many values of on-release migration costs have been calculated that are much smaller than the expected correlation. 2 Especially the sample means of releases 3, 10, and 11 would profit from more runs as their sample means deviate considerably from the expected correlation. Then, in accordance with the empirical rule, the deviation of the sample mean to the expected value would be minimized, because the distribution of the errors in the estimates is expected to be normal, that is, Gaussian [16,31,42]. If the random values happen to be rather extreme and thus, a resulting value deviates considerably from the prospective sample mean, the subsequent  resulting value is likely to be a less extreme value. This is called regression to the mean [16,31,42] indicating that the sample mean eventually converges through a sufficient number of samples.
Getting back to the question as to how often the sampling has to be repeated so that the results can be generalized: We compared all metrics after multiple runs of MigCast using an input parameter instantiation that has the highest variance and standard deviation, yet remains a typical scenario. This is the case with high cardinality of the relationships of the underlying data model, where single metrics vary easily by factor 100 and more. Compare the migration costs per release at a 1:25-relationship (for a detailed discussion refer to Subsection 5.4) for the eager strategy after 10, 20, 40, and 80 repeated MigCast runs in Figure 4. Because computation resources are not infinite, we need to put any gain in accuracy in perspective to the invested calculation time. The deviation from the expected correlation in this parameter configuration can be estimated to be less than 18% after 80 runs. With most configurations the resulting values converge much quicker (<2% deviation at 40 runs, not depicted for brevity). Therefore, we decided that 40 runs of calculation time investment into parameter configurations at low cardinality of the relationships and 80 runs for higher cardinality suffice, especially considering that in Section 5, we discuss the cumulation of the migration costs, which naturally varies much less than the migration costs per release (<2% deviation at 80 runs).
Hence, the presented approach utilizing a Monte Carlo method of repeated sampling is justified in order to investigate how data model evolution impacts migration costs and latency while bringing the enormous complexity of data model evolution under control.

RELATED WORK
Data Model and Schema Evolution. Research on data model and schema evolution has a long tradition, with contributions from database research, as well as software engineering research: There are several empirical studies on schema evolution in real-world applications backed by relational databases [11,34,39,43]. Various frameworks for managing schema changes in relational database management systems have been proposed, among the more recent are [2,8,10,20]. Schema evolution has also been investigated in the context of XML [4,18] and object-oriented databases [44].
In the context of application development with schema-flexible NoSQL database systems, new challenges arise. One factor is that such a NoSQL database system does not enforce a global schema, yet the application code will inevitably have to make assumptions about the structure of data stored in the database. As the schema is implicitly declared within the application code, evidence of schema changes can be observed by analyzing the change history of the application code [32,37], rather than an explicitly declared database schema. Moreover, there is evidence that suggests that the application-inherent schema evolves at a higher frequency than what can be observed with schema evolution in relational database management systems [37]. This makes the problem ever more pressing to deal with.
A further aggravation factor is found with zero-downtime web applications, where a new version of the application code is released against a production database that already contains data. On the upside, this allows great flexibility in application development, as the legacy data need not be migrated prior to a new release of the application. In fact, this is often listed as one of the sweet spots when working with NoSQL database systems. On the downside, the mismatches in the structure of legacy data and the data model expected by the application code must be actively managed. Here, strategies for efficiently handling the migration of this legacy data takes on special importance, and is addressed next.
Data Migration. In [15], the costs, duration, and running costs are estimated for migrating entire relational database instances to the cloud, whereas we focus on the impact of legacy data on migration costs and latency caused by schema evolution. The estimates of [15] are based on discrete-event simulation using workload and structure models taken from logs, as well as the schema of the tobe-migrated database, whereas we investigate a range of migration scenario characteristics in a Monte Carlo approach. Since the traditional approach of eager migration can become very expensiveespecially in a cloud environment [15,22]-other approaches to data migration such as lazy [27,35] and proactive [22] approaches have been proposed. To our knowledge, there is no related study on the effects of the various migration strategies, comparable to ours in its systematics. In [22], we have demoed a tool-based advisor for investigating different migration strategies. This work serves as a basis for the Monte Carlo approach presented here.
Monte Carlo Methods in Data Management. In terms of probabilistic methods in the context of database research, surveying uncertain data algorithms and applications, and uncertain data management has been proposed [1]. In particular, Monte Carlo methods for uncertain data have been studied in detail [19,25,26], also regarding the use of Monte Carlo integration methods for data clustering [38].

Architecture of MigCast in Monte Carlo
In Figure 5, an overview is depicted of the system architecture of MigCast in Monte Carlo. MigCast calculates the migration costs and latency in case of data model changes (modules Cost Calculator and Latency Profiler in Figure 5) based on the Darwin middleware and its modules (noted here schematically, refer to [22] for further details). The calculation is based on an internal cost model that counts all I/O-requests. Latency is the time that elapses from the request until the entity is retrieved. The migration scenario characteristics that change the impact on the metrics are considered relevant and investigated conclusively in our experiment. These characteristics are specified in the experiment as input parameters in different MigCast configurations. The investigated configurations concern the intensity and distribution of data entity accesses, the different kinds of schema changes, and the cardinality of the relationships of the underlying data model. Their instantiations and variations are summarized in Table 1 of Section 5. MigCast in Monte Carlo calculates repeated runs of MigCast and the results are aggregated as statistical values and persisted in a dedicated database to ensure reproducibility despite the randomization.
MigCast calculates the migration costs and latency for a given configuration on a case-by-case basis, taking characteristics of the data set instance, database management system, and cloud provider pricing models into account, as well as the workload of served data entity accesses and the schema changes. We refer to the data entity accesses in between two releases of schema changes as workload (module Workload Generator in Figure 5). In terms of the served workload, we distinguish between different data access distributions and between several amounts of served workload of data entity accesses, what we refer to as workload intensity, implemented in  MigCast as executions of a certain parameterizable amount of data entity accesses. The data entity accesses are randomized within the bounds of the parameterized distributions in order to facilitate the reduction in complexity by means of the Monte Carlo method.
Regarding the characteristics of schema evolution, we differentiate between single-type and multi-type operations referring to the number of types that a schema modification operation (SMO) involves. By means of the migration scenario characteristic multi-type SMO complexity, the percentage of those operations that involve more than one entity type can be determined. The concrete SMOs and the affected type(s) are then determined by randomization within the bounds of the parameterized percentages. As regards the characteristics of the data set, the cardinalities of the relationships of the underlying data model is investigated in our experiments. These reflect typical scenarios in database applications, e.g., a 1:1relationship in e-commerce could be a billing address of a customer, and a much higher cardinality of a relationship could be orders per customer per year.
In addition to the varied parameters, the following parameters are fixed as to ensure the comparability of the investigated configurations (compare with Table 1 of Section 5): The data set is determined by its real initial number of entities, which is upscaled to its initial number of entities. We decided for the entities to grow in number by the data growth rate after each release of schema evolution. An exponential growth of entities is by all means imaginable at the beginning of the project life cycle, though it would surely stabilize to a linear growth soon thereafter. The amount of one workload execution is defined by the percentage of accessed data relative to the number of existing entities in the first release, i.e., remains constant throughout the experiment. Lastly, the database management system (DBMS) and price per 1M I/O-requests are also parameterizable, yet we have based most of our discussion on relative values as opposed to absolute values. 3 With each release of new software, the events take place as parameterized in the following order (see Figure 6): The specified amounts of randomized workload of entity accesses are served, which can cause on-read migration costs with migration strategies  that delay migrating legacy entities (** in Figure 6). Then, an SMO is applied, which is randomly chosen according to the specified multi-type SMO complexity. In case of the eager, incremental, and predictive strategies, certain amounts of affected legacy entities are migrated then causing on-release migration costs (* in Figure 6). Lastly in each release, new data entities are generated, supplementing the existing data set according to the specified cardinalities of the relationships of the underlying data model.

Reducing the Search Space Complexity
Although the computational effort is reduced by the randomization of data entity accesses through the Monte Carlo method, one MigCast run for an average configuration and a sampling size of 1,000 entities took approx. 4.5 minutes on our server. Using a typical number of data entities would far exceed the computational resources. Thus, we limited the sampling size of the experiment, yet still ascertaining that the results are representative. We ran the experiments with different sampling sizes and eventually decided for 1,000 entities, since the resulting metrics of the migration strategies and their variance do not significantly change with more entities. We then multiply the results with a factor of 10,000 to scale up the resulting metrics to represent a typical amount of 10M data entities. Furthermore, the decision on the number of parameter variations of the investigated configurations has to be put into perspective in terms of the computational effort of one such cost calculation. The problem search space has exponential complexity and thus, calculating the metrics for all combinations of migration scenario characteristics would by far exceed our life times. We decided to focus on 90 different typical configurations that cover the search space and allow uncovering the correlation between the scenario characteristics and their impacts on the metrics. We discussed in Section 2 how many runs of the cost calculations for each configuration are necessary for the metrics to converge.

Methodical Aspects
In order to methodically approach verifying our hypotheses, we formulated 29 invariants how we expected the migration strategies to perform in terms of migration costs and latency in each of the investigated scenarios. As a welcome side effect, we could check and ascertain model consistency and validate the implementation. All charts of all MigCast runs are routinely evaluated by the invariants. 4 A traffic light system facilitates a relatively quick assessment of whether the results fulfill the invariants, especially quick compared to manually checking 90 configurations times 40/80 runs of logs.
The invariants can be distinguished as either being requirements or hypotheses. The former have to be met in order to prove consistency, shown by a green check mark, or if not met, by a red X mark. In order to pursue our hypotheses how the input parameters correlate with the results, invariants have been formulated as tendencies that, if met, support our hypotheses, then indicated by green check mark as well. In case that a tendency is not met at every single release, a yellow X mark indicates this. The complete, persisted logs can be accessed by means of the configuration number and run index in order to investigate whether the invariant is just temporarily not met, e.g., through outliers, or whether it contradicts a hypothesis. The results presented in Section 5 are all confirmed through the invariants.
The second method that we used to ascertain model consistency addresses the circumstance that a Monte Carlo approach is probabilistic in nature. Despite including randomly instantiated variables, the experiments have to be reproducible in order to meet certain scientific requirements known as data provenance [21]. A MongoDB database, MigCastDB in Figure 5, persists all results and calculated statistical measures in order to ensure their reproducibility, understandability, and comparability. 5 Note that, when repeating an experiment, the latency is the only metric that can vary, although in our setting we minimized external effects on the experiment by removing all potentially interfering routines on the server. In addition, the repeated sampling keeps any effects on latency low. Last but not least, we ran the MigCast tool once after starting the DBMS in order to ensure the comparability of all runs.

PUTTING THE RESULTS INTO CONTEXT
Legacy entities originate in schema changes of the underlying data model. Migration strategies handle legacy entities differently, thus a particular strategy may be more suitable in one migration scenario but less so in another. By means of MigCast in Monte Carlo, we are able to clarify how migration scenario characteristics, represented by instantiations of MigCast's input parameters, impact the competing metrics migration costs and latency. The knowledge of this correlation put stakeholders of a software project in the position to remain in control of the operative costs for data model evolution  and base their decisions during software application development on transparency regarding the impact on the metrics. In Subsection 4.1 we have outlined the architecture of MigCast in Monte Carlo. The concrete instantiations of the input parameters can be divided into fixed and varied parameters, the latter of which we investigated (see Table 1): Two workload distribution patterns (Pareto, uniform), three degrees of workload intensity (low, medium, and high), five multi-type SMO complexity variations (steps of 25 percentage points), and three cardinalities of 1:n-relationships (n being 1, 10, or 25). The served workload of data entity accesses as well as the concrete SMOs are randomized within the bounds of these parameter instantiations. These combinations result in 90 different MigCast configurations amounting to 3,600 runs and approx. 270h of computation time on a server running Ubuntu 16.04.6 and MongoDB (Server: 4.0.2, Driver: 3.9.0) on 24 CPUs and 128 GB RAM. 6 In the following, we present the results of the MigCast in Monte Carlo experiments. We categorize them into four subsections corresponding to the investigated scenario characteristics (Figure 7). Some of them amplify the differences that exist between the different migration strategies in respect of a particular metric, and others level these differences while varying the investigated characteristic. The graphs depicting a metric of the strategies then diverge more or less depending on the variation of an input parameter.
We start in Subsection 5.1 with the analysis how the distribution of the served workload of data entity accesses influences the measured impact on the metrics for each of different migration strategies. In Subsection 5.2 we discuss the impact in respect of varying intensity of workload between releases of schema changes. In Subsection 5.3, the impact is analyzed in respect of how many entity types the data model changes affect, and in Subsection 5.4 the influence of the cardinality of the relationships of the underlying data model is investigated. Note that the diagrams of the cumulated migration costs of each scenario characteristic variation 6 We recorded the application data metrics through the Grafana tool. The charts of CPU load, processes, and used memory can be viewed at https://sites.google.com/ view/evolving-nosql/tools/darwin.

Schema Evolution
Measured Impact on Metrics ( Figures 9, 11 12, and 13), which accompany each subsection, refer to relative costs so that each scenario characteristic can be easily compared with the others (the most influencing charactertistic shows 100% on the y-axis, the others 60% each).

Concentration of Data Entity Accesses
We begin with the investigation on how the distribution of entity accesses of the workload impacts the resulting metrics of migration costs and latency. We ran MigCast in Monte Carlo with the uniform and with the Pareto distribution, the resulting metrics of which are depicted in Figures 8 and 9. The first figure shows the graphs indicating how the metrics develop with the releases of schema changes, of which the second figure is a compact summary after 12 releases. With the uniform distribution the probability of one single entity being accessed is the same for all entities, whereas with the Pareto distribution the probability is greater with hot data entities which are accessed more frequently. We used a Pareto pattern that is common in OLTP database applications [29], where 80% of the workload accesses concentrate on 20% of the data entities, the hot data, and 20% of the workload accesses are distributed among 80% of the data entities, the cold data.
As can be seen in Figure 8, the lazy migration strategy performs better under the Pareto distribution both in terms of the metrics migration costs and latency compared to the uniform distribution. With each distribution pattern any one entity is possibly accessed repeatedly, which is much more probable with the Pareto distribution where the workload concentrates on hot data. Specifically, under the Pareto distribution the migration costs drop by 58% and latency drops by 50% for the lazy migration strategy.
The distribution of entity accesses has an influence on the metrics due to the varying number and age of the legacy entities. The heterogeneity of the data in terms of schema versioning not only depends on the distribution of entity accesses, but also on the chosen migration strategy. For this discussion it has been proven useful to differentiate between on-release and on-read migration costs, which together make up the cumulated migration costs. On-release migration costs depend on how many entities are affected by a schema change and how these legacy entities are being handled. With the eager migration strategy, all legacy entities are migrated to the current schema version, so that no runtime overhead exists.   In this case, only on-release migration costs contribute to the cumulated migration costs. While latency is minimal for eager migration, this approach also causes maximal migration costs compared to other migration strategies. In contrast to on-release migration costs, on-read migration costs are caused when entities are being accessed that exist in older versions than the current schema indicates. With the lazy migration strategy, legacy data remains unchanged in the event of releases of data model changes. Savings in terms of onrelease migration costs are paid for in form of on-read migration costs and a higher latency of the lazy strategy, once a legacy entity needs to be accessed. As can be seen in Figures 8 and 9 for both distributions, the lazy strategy represents an upper bound and the eager strategy a lower bound with respect to the cumulated migration costs, and vice versa with respect to latency.
Regarding the distribution of accesses it can be observed that the lazy migration strategy particularly benefits in terms of both metrics when entity accesses concentrate on hot data. Once a legacy entity is migrated and then up-to-date, future queries benefit from the update in terms of lower on-read migration costs and latency, which pays off in case of repeated accesses on the same entities. In our experiments, 58% of the cumulated migration costs can be saved under the Pareto distribution. Compared to the eager strategy, the lazy strategy causes 39% of the costs under the uniform distribution and only 17% under the Pareto distribution (see Figure 8).
Located in between the lazy and eager approaches is the incremental migration, which migrates all legacy entities at certain preset points in time, here at releases 5 and 10. Characteristic for incremental strategy is that it fluctuates between the eager and lazy strategy both in terms of migration costs and latency. This can be utilized when the workload to be served is known to vary in a certain recurring pattern, to which the increments of migrating legacy entities can be adapted. Lazy periods of time are then interrupted by regular bouts of tidying up the structurally heterogeneous database instance in order to get rid of the runtime overhead caused by updating legacy entities on-the-fly when being accessed. 7 The predictive migration strategy shows its full potential under the Pareto distribution, benefiting from the presence of hot data in similar measure like the lazy strategy: While latency decreases by 41%, 44% of migration costs can be saved (comparing the uniform with the Pareto distribution), latency decreases by 50% and migration costs by 58% with the lazy strategy (refer to Figures 8 and 9). Comparing the predictive with the incremental strategy, it should be noted that the predictive strategy convinces with more stable and thus more predictable metrics, especially important for SLAcompliance when the migration increments cannot be matched to intervals of low workload. Furthermore, the predictive strategy can make use of the Pareto distribution and saves more migration costs.
Interpreting these findings differently, if the hot data of an established Pareto pattern changes to a different set of hot data, then higher migration costs and latency must be expected intermittently, up to the migration costs and latency found for the uniform distribution. The metrics then converge again to previously measured values once this new Pareto pattern is established.
Summing up, if the workload distribution exhibits a pattern in which entity accesses concentrate on hot data compared to randomly distributed entity accesses, then migration strategies that delay migrating legacy entities in the event of schema evolution perform better in terms of a lower latency. At the same time, migration strategies that utilize the Pareto principle can save more migration costs, while the eager strategy remains the same and the incremental strategy saves costs very slightly on average. While latency increases with the releases of schema changes for strategies that utilize the Pareto principle, it is generally more stable with regard to all scenario characteristics than with the incremental strategy. In general, the concentration of data entity accesses amplifies the differences of the migration strategies in terms of migration costs and levels the differences in terms of latency. The opposite is true if the data entity accesses do not concentrate on hot data, i.e., if the probability of being accessed is the same for all data entities, then the differences are amplified in terms of latency and leveled in terms of migration costs. Observation 1. In terms of the distribution of entity accesses, the eager strategy remains invariant and represents an upper bound with respect to cumulated migration costs and a lower bound with respect to latency, and vice versa for the lazy strategy in terms of upper/lower bounds. It also holds that under the Pareto distribution compared to the uniform distribution: • The cumulated migration costs diverge more, thus more costs can be saved with strategies utilizing the Pareto principle, i.e., the lazy and predictive strategies, and (very slightly) with the incremental strategy. • Across all strategies, latency diverges less when accesses concentrate on hot entities. • The opposite of the two previous points holds true under the uniform distribution compared to the Pareto distribution.

Workload Intensity
In order to investigate how workload influences the metrics, we have run MigCast in Monte Carlo with varying intensity of workload between releases of schema changes. The charts in Figure 10 show the migration costs for workload intensity from low to high, where low equals one workload execution and high equals four times as much, simulating varying intensity of served entity accesses in between releases of schema changes. Each workload execution is a certain amount of entity accesses, in our experiments 10%, relative to the initial number of entities in the first release. The amounts of this percentage of accessed data remains the same throughout the releases despite the growth of data, simulating a constant workload over time. Each entity access is random within the bounds of the Pareto distribution, which is the default workload distribution.
As explained earlier, we can see in Figures 10 and 11 that the metrics of the eager strategy remain approximately the same with increasing workload. In contrast to on-release migration costs that are caused by releasing data model changes, on-read migration costs are caused when entities are being accessed that abide by older versions than the current schema indicates. Now, with increasing workload, the percentage of legacy entities declines for the lazy, incremental, and predictive strategies and thus, it can be observed in Figure 10 that, while the cumulated migration costs continuously increase with each release, the advantage over other strategies diminishes, and the graphs diverge less. The proactive strategies, which act in advance of situations when migrating legacy entities could cause latency overhead, are consistently located between the lazy and the eager strategies for both metrics depending on their investment into the structural homogeneity of the database.
It can be observed in Figure 11 regarding the latency that an increase of the workloads corresponds to a decrease of latency for strategies that delay migrating legacy entities. Specifically, it can be noted that with four times the amount of workload (low to high) the migration costs for the lazy strategy increase by 130% (+14 percentage points in respect of the charges for eager) and for the predictive strategy by 149% (+44 percentage points), refer to Figure 10. Latency then drops for lazy from 7.09ms to 6.15ms, that is by 13% (-8 percentage points in respect of the latency for eager), and for predictive from 5.72ms to 5.11ms, that is by 11% (-7 percentage points), refer to Figure 11.   Figure 11: With increasing workload, cumulated migration costs increase and latency decreases on average; Configuration same as in Figure 10.
This shows a particularly efficient investment of migration costs into hot data in case of low workload and for strategies that utilize the Pareto principle. This wears off with increasing workload, then bringing those strategies closer to the incremental strategy. The reason that the predictive strategy gets closer to the incremental strategy with higher workload can be found in the choice of the prediction set size of the predictive strategy: If the workload is lower (1/2/4 times 10% in our experiment) than the prediction set size (30%), then the metrics for the predictive strategy are closer to those for the lazy strategy. In case that the whole extension of a relatively high prediction set size is used, the metrics get closer to the incremental strategy. The efficiency of migration cost investment for the predictive strategy thus depends on the workload and on the prediction set size. Interestingly, with the chosen size of the prediction set and thereby the investment of migration costs, the resulting latency of the predictive strategy proportionally fits in relative to the other strategies. A detailed investigation on the correlation of different prediction set sizes and resulting metrics is part of our future research, following up on [23].
In summary, we can state that the graphs of the different migration strategies are less divergent with higher workload in respect of migration costs, because more entity accesses result in higher migration costs, except for eager migration which stays invariant under the workload. Latency also becomes less divergent as more legacy entities are migrated and up-to-date with strategies that delay migrating legacy entities. Again, eager migration stays invariant under workload for latency as well. The differences between the strategies can be observed as more or less proportional in terms of their investment into the structural homogeneity of the database and the resulting improvement in latency. Thus, we can conclude that high workload levels the differences pertaining to the selected migration strategies as regards both migration costs and latency. Observation 2. In terms of the variance of workload intensity, the eager strategy represents an upper bound with respect to cumulated migration costs and remains invariant as a lower bound with respect to latency, and vice versa for the lazy strategy in terms of upper/lower bounds. It also holds that with higher workload in between releases compared to lower workload: • The cumulated migration costs diverge less with more queries being served, thus less costs can be saved especially in case of the lazy and predictive strategies, and (very) slightly less with the incremental strategy. • Latency also diverges slightly less, i.e., improves for migration strategies that delay migrating legacy entities. • The opposite is true for lower compared to higher workload.

Schema Modification Operations (SMOs)
In the course of schema evolution, different kinds of schema changes occur. They can be distinguished by how many classes, tables, or entity types the data model changes affect [11,36]. Single-type SMOs affect exactly one entity type, specifically, these are add, delete, and rename, all of which are implemented in our middleware Darwin. Multi-type SMOs affect exactly two entity types at once, the most common are copy, move, split, or merge. The first two are investigated in our experiments. For the sake of brevity, we disregard split and merge as they can be mapped onto the implemented SMOs. The higher the percentage of multi-type operations among SMOs becomes compared to single-type operations, the more types and thus, the more entities are affected by the data model changes. We refer to this as higher multi-type SMO complexity.
Our experiments show that the higher the multi-type SMO complexity is, the higher the cumulated migration costs become across all migration strategies. Their increase corresponds with the amount of legacy entities that are being migrated and the number of affected types. Latency also increases for migration strategies that delay migrating entities affected by the schema changes, in our experiments the lazy, incremental, and predictive strategies. This is because queries that refer to types that are affected by a schema change have to be rewritten. A higher multi-type SMO complexity, where entity types are restructured by copying and moving attributes, is oftentimes the case during major schema changes in agile development settings.
In Figure 12, multi-type SMO complexity is increased in steps of 25 percentage points, i.e., 0%, 25%, 50%, 75%, 100%, and the cumulated migration costs for the eager strategy also increase quite proportionally by roughly 40% per 25 percentage points compared to 100% single-type operations. Thus, there is an overhead of 15 percentage points connected with multi-type SMOs, which is part of our further research. It can be noted that the increase of migration costs corresponds almost exactly to the number of affected types (factors of 1.4, 1.79, 2.19, and 2.56, i.e., with slightly declining gradient, which can be attributed to the circumstance that migration becomes slightly more efficient when entities are migrated in bulks). At the same time, the latency of the eager strategy remains approximately equal as all entities are up-to-date. In case of the lazy strategy it can be observed that with higher multi-type SMO complexity, the cumulated migration costs increase (1.88, 2.77, 3.54, 4.54) as well as the latency (1.42, 1.9, 2.45, 3.07, i.e., with slightly increasing gradient). Similarly, this proportionality can be noted for the incremental and predictive strategies as well. The cumulated migration costs of the predictive and the incremental strategies are located regularly in between the lazy strategy and the eager strategy corresponding to the increases in multi-type SMO complexity.   Figure 12: Migration costs and latency increase proportionally with higher multi-type SMO complexity, while latency of the eager strategy remains equal at maximal migration costs; Configuration: Pareto-distributed medium workload, standard cardinality.
The latency consistently reflects the investments of migration costs for both the predictive and the incremental strategies. Summing up, with increasing multi-type SMO complexity, the cumulated migration costs of all migration strategies increase almost proportionally. Although, the absolute difference between lazy and eager more than doubles (+128%), the relative differences decrease from factor 8.1 in case of 0% multi-type SMO complexity (100% single-type SMOs) to factor 4.7 in case of 100% (see Figure 12). In terms of latency, the latency of the eager strategy remains equal whereas for the other strategies it increases proportionally to the number of affected types and invested migration costs. Thus, we can conclude that high multi-type SMO complexity can be considered a cost driver regarding both metrics as it greatly amplifies the absolute differences pertaining to the selected migration strategies in terms of migration costs and latency. Observation 3. In terms of multi-type SMO complexity of schema modification operations, the eager strategy represents an upper bound with respect to cumulated migration costs and remains invariant as a lower bound with respect to latency, and vice versa for the lazy strategy in terms of upper/lower bounds. It also holds with increasing multi-type SMO complexity for all migration strategies that: • The cumulated migration costs increase and diverge more with higher multi-type SMO complexity in absolute values, yet diverge less in relative values. More costs can be saved with migration strategies delaying migrating legacy entities when the multi-type SMO complexity is higher, although in absolute values the costs for these strategies become higher as well. • Latency diverges considerably more with higher multi-type SMO complexity, i.e., worsens considerably with strategies delaying migrating legacy entities proportionally to the number of affected types and invested migration costs. • The opposite holds for decreasing multi-type SMO complexity.

Data Model Cardinality of Relationships
In order to reach clarification how the data model of the persisted entities influences the resulting migration costs and latency, we have run MigCast in Monte Carlo with varying cardinality of the relationships. Figure 13 shows the migration costs for increasing cardinality of 1:1-, 1:10-, and 1:25-relationships, simulating standard, medium, and high cardinality of 1:n-relationships in a data model, in this subsection abbreviated as cardinality. 8 In the data model with 1:1-relationships, we assume the entities to be evenly distributed over the types, whereas at higher cardinality there exist many more entities on the n-sides of the 1:nrelationships. In our experiments, the 1,000 entities are distributed over the types according to the relationships. For instance, with 1:1-relationships there are 33.4% Player entities, 33.3% Mission entities, and 33.3% Place entities, and with 1:25-relationships there are 0.2% Player entities, 4% Mission entities, and 96% Place entities. Not quite intuitively, although the number of affected entities per type changes drastically with higher cardinality, in case of singletype SMOs the overall average number of affected entities does not change as the operations affect the types equally. This holds true regardless of whether each type is filled to the maximum n specified in the relationships or not, as there is always a sampling size of 1,000 entities. Yet, if there are much less Place entities as specified in n as there could possibly be, then the effects that we want to investigate could be mitigated. Thus, we ensured that with a number of 1,000 entities the distribution among the types comes close to the maximum n with all investigated cardinalities.
However, counter-intuitively, in case of multi-type operations higher cardinality of the relationships mean less affected entities on average by a schema change. In our experiments with 1,000 entities, the average number of entities that are affected by a multitype SMO is approx. 667 for a 1:1-, 545 for a 1:10-, and 525 for a 1:25-relationship. In case of 25% multi-type SMO complexity, as is the default parameter instantiation, for a 1:1-relationship approx. 416 entities are affected, for 1:10 386, and for 1:25 381, which corresponds to relative values of 93% for 1:10 and 92% for 1:25 compared to the reference value of a 1:1-relationship. The relative values of affected entities are calculated for 1:10-and 1:25-relationships and for each investigated percentage of multi-type SMO complexity  (values in parentheses in columns 3 and 4 in Table 2). The measured relative migration costs are summarized in Table 2 for the eager strategy. For instance, the 50% row is read as follows: Compared to the costs of 0% multi-type SMO complexity, costs of 50% multi-type SMO complexity are 79% higher for 1:1-relationships, 37% higher for 1:10 (58% higher in theory), and 28% higher for 1:25 (54% higher in theory). We assume that the real measures are lower than the theoretical values due to the efficient implementation of the multi-type SMOs in connection with higher cardinalities of the relationships. Getting back to the investigation how the data model of the persisted entities impacts the resulting metrics: The cumulated migration costs have been measured in our experiments at 86% for medium and for high cardinality (121% with reference to 0% multi-type SMO complexity) for the eager strategy, which is quite close to the theoretic 93% and 92% (130% and 129%). As can be seen in Figure 13, the migration costs for the predictive and the lazy strategy tend to increase slightly for higher cardinality. Although with higher cardinality the workload concentrates on Place entities as these are prevalent in number and thus accesses are more probable, the SMOs affect the types evenly by a third in case of single-type operations and in a 1:2:1-relationship for multi-type operations (Player:Mission:Place). However, the Player entities, of which there are very few with high cardinality, are accessed overproportionally, since we consider this to be more realistic. As a consequence, the migration costs slightly increase with strategies that delay migrating legacy entities.
Due to the high variance of the metrics in case of higher cardinalities, individual results vary considerably (refer back to Figure 3). For instance, with high cardinality, the cumulated migration costs for the eager strategy after 12 releases are 600% as much for the highest measured value compared to the lowest measured value (compare with upper chart of Figure 14, other strategies vary similarly). Thus, a higher safety margin should be assumed to accommodate for the variance of schema evolution in response to the higher cardinality. In case that a 50% confidence interval is viewed as acceptable in order to comply with cost-related SLAs, migrations costs for the eager strategy should be expected being within the boxes. Latency for the eager strategy is then minimal and very predictable due to its low variance.
The averages of the measured latency in Figure 13 corresponds quite consistently with the above discussions that latency responds to the invested migration costs, though in case of the lazy strategy, it stands out that latency increases considerably with higher cardinality at mildly increasing migration costs on average. The predictive and incremental strategies show this effect to lesser extent.
The example of tail latencies shows the difficulty to comply with  Figure 14: With higher cardinality the variance of the cumulated migration costs increases particularly with the eager strategy and latency with the lazy strategy; Configuration same as in Figure 13.
latency-related SLAs, especially frequent with the lazy strategy (see lower chart of Figure 14). Although the median is at 5.8ms and the 75th percentile (for a 50% confidence interval) is at 7.9ms, we have measured tail latencies up to 68ms per one entity and with practically no external influences (note that the average means used in Figure 13 respond more to outliers as explained in 2). In this case, if latency-related SLAs need to be complied with, a compromise between the metrics is potentially risky and should be considered in the decision how and when to migrate legacy entities. Summing up, the cardinality of the relationships of the data model influences the cumulated migration costs. They are lower with higher cardinality for the eager strategy in case that multi-type SMO complexity operations are present. For strategies utilizing the Pareto principle they slightly increase under the above discussed assumption of overproportional accesses of Player entities. Due to a potentially high variance of the metrics, individual results vary considerably and thus, a higher safety margin should be assumed. We can conclude that higher cardinality levels the differences in terms of migration costs and amplifies them in terms of latency.
Observation 4. In terms of higher cardinalities of the relationships of the data model, the eager strategy represents an upper bound with respect to cumulated migration costs and remains invariant as a lower bound with respect to latency, and vice versa for the lazy strategy in terms of upper/lower bounds. It also holds with higher cardinality of the relationships for all migration strategies that: • The cumulated migration costs diverge less with higher cardinality if multi-type SMO complexity operations are present. They show a high variance for all strategies. • Latency diverges more and considerably increases in case of the lazy strategy. The less a strategy migrates legacy entities, the higher becomes the variance of the latency with practically no variance for the eager strategy. • The opposite is true for lower cardinality of the relationships.

DISCUSSION AND SUMMARY
We presented the results of near-exhaustive calculations of MigCast in Monte Carlo by means of which software project stakeholders can remain in control of the consequences of data model evolution.
We can equip them with information so that they can base their decisions during software application development on transparency regarding the impact on the metrics by selecting a migration strategy to suit the production settings. We examined the effects of the variation of migration scenario characteristics in detail, that is, distribution and intensity of workload, kinds of schema modification operations, and the cardinality of the relationships of the data model, on migration costs and latency with respect to the different migration strategies. Fig. 15 summarizes the impacts of the scenario characteristics on the metrics after 12 releases of schema changes, which we discuss in this section. Although the results are specific for typical scenarios, they are representative and constitute a heuristic that allows stakeholders to make reliable predictions in all migration scenarios.
Whether the software development is still ongoing or has shifted to its maintenance, the following development can be influenced with each further release of new software. The characteristics of the migration scenario are beyond a direct control, certainly in case of workload distribution and intensity. In case of multi-type SMO complexity and the cardinalities of the relationships a direct influence is conceivable, yet certainly not recommendable. By means of selecting a migration strategy that most likely suits the given SLAs regarding migration costs and latency, stakeholders can now make a decision that is a cost-aware and well-justified compromise. However, neither the scenario characteristics nor their impact can be predicted and thus, SLA compliance might be in jeopardy. In this case, the impact can still be mitigated by changing how often a new release is rolled out productively, because the release frequency indirectly moderates the impact. In this section, we compare and evaluate the impact of the scenario characteristics on the metrics after 12 releases of schema changes, distill a heuristics, and summarize our findings in a handy table, which supports decision-making on a suitable migration strategy and a release strategy.
If the application has a Pareto distribution typical for database applications, it has been shown that a good compromise can be achieved by the predictive migration. For giving up on a certain amount of latency, the migration costs are reduced by a considerable measure, much more so than under the uniform distribution. Depending on the preferences regarding the tradeoff, maximally saving of costs with the lazy migration seems as too good of a bargain, because if the data model of the application has a high cardinality, then individual costs and latency vary considerably. Depending what the consequences of a non-compliance of SLAs would entail, a confidence interval regarding the metrics can be specified in order to be on the safe side. In comparison to the incremental strategy, the predictive strategy achieves a better compromise between the metrics with regard to SLA compliance, because its latency is generally more stable and predictable under both workload distributions. This is especially true if the migration increments do not match with intervals of low workload.
In Figure 15, the column WL Distribution summarizes the migration costs and latency as factors when the workload changes from the uniform distribution to the Pareto distribution, or vice versa. The factors of each metric can be compared within a row (one strategy) or between rows (more strategies). Column headings highlighted in orange are migration costs and latency in blue.
Comparing two values within a metric, a higher factor means an increase of that metric. The quotient of two values indicates how the characteristic amplifies or levels the differences between the migration strategies, e.g., if the workload distribution changes from uniform to Pareto, then the migration costs for the lazy strategy change from 0.4 to 0.2 (in respect of the eager strategy, i.e., approximately half). The green columns are the default parameter settings, to which all other columns are referenced. In case that factors are especially high (red values), much migration costs must be spent or tail latencies be expected, respectively. E.g., if there is a uniform distribution of data accesses, then care must be taken regarding latency, which reaches 3.3 times the amount after 12 releases of schema changes in case of the lazy strategy compared to the eager strategy while still spending 40% of the migration costs compared to eager migration.
In comparison with the incremental strategy, it can be argued that under both distributions the predictive migration strategy achieves the better compromise between the metrics with regard to SLA compliance, because its latency is generally more stable and predictable (compare Figures 8 and 14). This is especially important if the migration increments executed by the incremental strategy do not match with recurring patterns of low workload.
As regards the distribution of the kinds of SMOs, which we refer to as multi-type SMO complexity, the metrics respond quite proportionally to the number of affected types and in terms of the tradeoff between migration costs and latency (compare with the column Multi-type SMO Complexity of Figure 15). A higher multi-type SMO complexity, where entity types are restructured by copying and moving attributes, is oftentimes the case during major schema changes in agile development settings. During these phases, the stakeholders should be aware that whatever compromise has been decided for in terms of a migration strategy, migration costs and latency usually become considerably higher, with the exception of the latency with the eager strategy which remains approximately the same, yet at much higher migration costs. In case that there are service-level agreements in place that limit the maximum amount of migration costs, then the release strategy could be adapted to plan releases in shorter intervals. This should be considered especially because the migration costs increase with increasing multi-type SMO complexity like with no other scenario characteristic (factors 1.8 for eager through 0.4/0.2≈2 for lazy from 25% to 100% multi-type SMO complexity, compare with Figure 15) and thus, high multi-type

WL Distribution WL Intensity
Multi-type SMO Complexity Cardinality of Relationships C U C P L U L P C L C M C H L L L M L H C 0 C 25 C 50 C 75 C 100 L 0 L 25 L 50 L75 L100 C 1 C10 C25 L 1 L 10 L 25 Eager 1 1 1 1 1 1 1 1 1 1  SMO complexity can be considered the most important cost driver of schema evolution. Notably, the possibility of saving costs with other than the eager strategy should be carefully weighed with regard to tail latency that are very likely when the multi-type SMO complexity changes, especially with the lazy strategy.
If the application has a high cardinality of relationships of the underlying data model, then the cumulated migration costs, somewhat contrary to intuition, are on average lower for eager and incremental and slightly higher for lazy and predictive strategies compared to standard cardinality of 1:1-relationships. Yet, stakeholders should not mistake this information as a rule of thumb. Since individual costs and latency vary considerably with higher cardinalities, it should be clarified what consequences a non-compliance of servicelevel agreements would entail and which confidence interval should be assumed in order to be on the safe side. This is especially true for tail latency in case of the lazy strategy and for migration costs in case of the eager strategy, as they can increase considerably.
By multiplying the factors in the table in order to match the migration scenario, the impact can be predicted and service-level agreements fulfilled even after a migration strategy has been selected. As stated before, adapting the frequency of new software releases can then mitigate the impact of further schema changes. Of course, a longer period in between releases usually includes more schema changes, which usually entails both higher migration costs and latency, so this advice of adapting the release frequency periods has to be weighed carefully in case of longer periods in between releases.

CONCLUSION AND OUTLOOK
We have presented the results of our in-depth investigation how data model evolution impacts migration costs and latency while taking relevant characteristics of migration scenarios into account and identifying cost drivers. We discussed the implications of these results for software project stakeholders enabling them to remain in control of the operative costs for data model evolution and base their decision-making during software application development on transparency regarding the impact on the competing metrics migration costs and latency. We shed light on the possibilities to adapt the pace of software releases according to our findings in order to ascertain the compliance with SLAs. Furthermore, we characterized the performance of the most popular migration strategies with respect to all relevant the migration scenarios. Last but not least, we are the first to apply a probabilistic Monte Carlo method of repeated sampling which brought the complexity of data model evolution under control.
We argued that software project stakeholders can and should base their decision-making during software application development on transparency of the impact on the competing metrics migration costs and latency with regard to the decision alternatives. With this transparency, compromises can be reached in terms of opportunity costs due to the tradeoff between migration costs and latency in accordance with service-level agreements and under consideration of the migration scenario, thus constituting a heuristic approach. Specifically, our near-exhaustive experiments clearly confirm that workload distribution has a high impact on the performance of migration strategies that delay migrating legacy entities. We discussed how workload intensity and multi-type SMO complexity can be mitigated by the release strategy. Furthermore, we have identified multi-type SMO complexity as a cost driver and despite the average impact of the data structure's cardinality being rather negligible, the high variance of potential impacts necessitates precautions with regard to SLA compliance.
These results contribute significantly towards our research goal of defining a migration advisor for all relevant migration scenarios. Further research is focusing now on applying the gained insights in order to develop a self-adaptive migration strategy which realizes the heuristics on the level of a migration strategy. This self-adaptive migration strategy could be parameterized according to the preferences on the tradeoff between migration costs and latency and their opportunity costs, based on a theoretical analysis already published in [23]. This appears especially interesting when selfadaptive strategies would be implemented in cloud solutions, which would compete with on-premise solutions in terms of a better cost efficiency, energy reduction, and sustainability.