a key is in a range.It also reduces the amount of work required for partitions.As both partitions are locked during the migration of e uaicn herey rventin anyation csdrcohcecoiguion artition with after y to update the WAREHOUSE Squall the deadlock detection topr the tracki Ouce the the blocking cd by disrupi ve for ac 4.3 Identifying Data Locatior 4.5 Asynchronous Migration the DBMS.the on 3.1).it then dure tha ons to tha 29.32 s this p Thi ples and th chronous pull re e【o execut task did to e hepam each nk to the dest nalionpartition are uncertain,then it for the requ st to the table.This process repeats uled at a all tra g rtition to 10 the ed tuple mproves perf as only ma ing data at the source ine a tuple the ti is para 4.4 Reactive Migration chu d by Squ Squall schedule transaction at its Tspondinedcstina We explore the opti of th when it executes Like 5.OPTIMIZATIONS pe This 5.1 Range Splitting ng) As described in Section 4.1.Squall computes the initial transfe ranges of tuples for a n isqueued just like a transaction sacquires exa key is in a range. It also reduces the amount of work required for range splitting and simplifies the tracking of keys with non-discrete domains (e.g., strings or floating-point values). When a transaction reads or updates tuples, Squall ensures that all required data is present. Using our TPC-C example from above, assume that no data has yet been migrated (i.e., all of the entries in the tracking table are set to NOT STARTED). A transaction then arrives at partition 4 that executes a query to update the WAREHOUSE tuple with W_ID = 7. After failing to find a matching key entry in the tracking table and checking that the corresponding range is not marked as COMPLETE, partition 4 issues a request for (WAREHOUSE, W_ID = 7). Once the warehouse is migrated, both partitions set the corresponding WAREHOUSE range in the status table to PARTIAL and add a key-based entry for (WAREHOUSE, W_ID = 7) in the tracking table with the status of COMPLETE. 4.3 Identifying Data Location Under normal operation, when a new transaction request arrives at the DBMS, the system evaluates the routing parameters for the stored procedure that the transaction wants to execute with the cur￾rent plan to determine the base partition for that request [29, 32]. But during a reconfiguration, Squall intercepts this process and uses its internal tracking metadata to determine the base partition. This is because the partition plan is in transition as tuples move and thus the location of a migrating tuple is uncertain. The mechanisms in Section 4.2 ensure safe execution of transactions on migrating data, whereas the following techniques for determining where to execute transactions are for improving the DBMS’s performance. If the data that a transaction needs is moving and either the source or destination partition is local to the node receiving the transac￾tion, then Squall will check with the local partition to determine whether the required tuple(s) are present (i.e., the source partition has the range marked NOT STARTED or the destination partition has the range marked COMPLETE). If Squall deems that the tuples’ loca￾tions are uncertain, then it forwards the request to the destination partition. Since a transaction could have been (correctly) sched￾uled at a source partition before tuples were migrated, Squall traps transaction execution before it starts to verify that those required tuples were not migrated out while the transaction was queued. In this scenario, the transaction is restarted at the destination partition. Scheduling the transaction at the partition that always has the re￾quired tuples improves performance by avoiding a migration when a transaction has already arrived at the same local site. But in all other cases, it is better to send the transaction to the destination partition and then use Squall’s reactive migration mechanism to pull data as it is needed. This alleviates overloaded partitions more quickly by migrating hot tuples first and minimizes the communi￾cation overhead of partitions trying to determine a tuple’s location. 4.4 Reactive Migration Squall schedules each transaction at its corresponding destina￾tion partition, even if the system has not completed the migration of the data that the transaction will access when it executes. Like￾wise, when a transaction invokes a query, Squall examines the re￾quest to determine whether the data that it accesses has migrated to its destination partition. In this scenario, the destination partition blocks the query while the data is reactively pulled from the source partition. This blocks all transactions that access these partitions during this time, thereby avoiding consistency problems (e.g., two transactions modify the same the tuple while it is moving). To perform the reactive migration, Squall issues a pull request to the source partition. This request is queued just like a transaction and thus acquires exclusive locks on both source and destination partitions. As both partitions are locked during the migration of data items, no other transaction can concurrently issue a read or update query at these partitions, thereby preventing any transaction anomalies due to the reconfiguration. The pull request is scheduled at the source partition with the highest priority so that it executes immediately after the current transaction completes and any other pending reactive pull requests. Squall relies on the DBMS’s standard deadlock detection to pre￾vent cyclical reactive migrations from stalling the system, since all transactions are blocked while the source partition is extracting the requested data. Additionally, transaction execution is also blocked at the destination partition when it loads the requested data. Since the blocking caused by reactive migrations can be disruptive for ac￾tive transactions, Squall also employs an additional asynchronous migration mechanism to minimize the number of reactive pulls. 4.5 Asynchronous Migration After Squall initializes the list of incoming data ranges for each partition (cf. Section 3.1), it then generates a series of asynchronous migration requests that pull data from the source partitions to their new destination. During the reconfiguration, Squall periodically schedules these requests one-at-a-time per partition with a lower priority than the reactive pull requests. When the source partition receives an asynchronous pull request, it first marks the target range as PARTIAL in its tracking table. It then sub-divides the request into tasks that each retrieve a fixed-size chunk to prevent transactions from blocking for too long if Squall migrates a large range of tuples. If the last task did not extract all of the tuples associated with the range, then another task for the asynchronous pull request is rescheduled at the source partition. As Squall sends each chunk to the destination partition, it includes a flag that informs the destination whether it will send more data for the current range. For the first chunk that arrives at the destination for the range, the destination lazily loads this data and marks the range as PARTIAL in its tracking table. This process repeats until the last chunk is sent for the current range. Squall will not initiate two concurrent asynchronous migration requests from a destination partition to the same source. Addition￾ally, before issuing an asynchronous pull request, Squall checks if the entire range has been pulled by a prior reactive migration (i.e., marked as COMPLETE). If so, the request is discarded; otherwise the full request is issued as only matching data at the source will be returned. Additionally, if a transaction attempts to access partially migrated data, then this forces a reactive pull to migrate the remain￾ing data or flush pending responses (if any). Since limiting the amount data per extraction and interleaving regular transaction execution is paramount to minimizing perfor￾mance impact, the time between asynchronous data requests and the asynchronous chunk size limit are both controlled by Squall. These settings allow Squall to balance the trade-off between time to completion and impact of reconfiguration. We explore the opti￾mal setting for these parameters in Section 7.6. 5. OPTIMIZATIONS We next present several optimizations for improving the runtime performance of the DBMS during a reconfiguration with Squall. 5.1 Range Splitting As described in Section 4.1, Squall computes the initial transfer ranges of tuples for a new reconfiguration by analyzing the differ￾ence between the previous and new partition plans. If the new parti￾tion plan causes a large number of tuples to move to a new location, Squall may schedule transactions on the destination partition when