skip to main content


Title: BullFrog: Online Schema Evolution via Lazy Evaluation
BullFrog is a relational DBMS that supports single-step schema migrations --- even those that are backwards incompatible --- without downtime, and without need for advanced warning. When a schema migration is submitted, BullFrog initiates a logical switch to the new schema, but physically migrates affected data lazily, as it is accessed by incoming transactions. BullFrog's internal concurrency control algorithms and data structures enable concurrent processing of schema migration operations with post-migration transactions, while ensuring exactly-once migration of all old data into the physical layout required by the new schema. BullFrog is implemented as an open source extension to PostgreSQL. Experiments using this prototype over a TPC-C based workload (supplemented to include schema migrations) show that BullFrog can achieve zero-downtime migration to non-trivial new schemas with near-invisible impact on transaction throughput and latency.  more » « less
Award ID(s):
1718581 1910613
PAR ID:
10283168
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Proceedings of the 2021 International Conference on Management of Data
Page Range / eLocation ID:
194 to 206
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Web applications often handle large amounts of sensitive user data. Modern secure web frameworks protect this data by (1) using declarative languages to specify security policies alongside database schemas and (2) automatically enforcing these policies at runtime. Unfortunately, these frameworks do not handle the very common situation in which the schemas or the policies need to evolve over time—and updates to schemas and policies need to be performed in a carefully coordinated way. Mistakes during schema or policy migrations can unintentionally leak sensitive data or introduce privilege escalation bugs. In this work, we present a domain-specific language (Scooter) for expressing schema and policy migrations, and an associated SMT-based verifier (Sidecar) which ensures that migrations are secure as the application evolves. We describe the design of Scooter and Sidecar and show that our framework can be used to express realistic schemas, policies, and migrations, without giving up on runtime or verification performance. 
    more » « less
  2. There have been numerous studies on heterogeneous memory systems comprised of faster DRAM (e.g., 3D stacked HBM or HMC) and slower non-volatile memories (e.g., PCM, STT-RAM). However, most of these studies focused on static policies for managing data placement and migration among the different memory devices. These policies are based on the average behavior across a range of applications. Results show that these techniques do not always result in higher performance when compared to systems that do not migrate data across the devices: some applications show performance gains, but other applications show performance losses. It is possible to utilize offline analyses to identify which applications benefit from page migration (migration friendly) and use page migration only with those applications. However, we observed that several applications exhibit both migration friendly and migration unfriendly behaviors during different phases of execution supporting a need for adaptive page migration techniques. We introduce and evaluate techniques that dynamically adapt to the behavior of applications and either reduce or increase migrations, or even halt migrations. Our adaptive techniques show performance gains for both migration friendly (on average of 81% over no migrations) and unfriendly workloads (by an average of 3%): it should be remembered that previous migration techniques resulted in performance losses for unfriendly workloads. 
    more » « less
  3. Abstract

    Migration theorizing has coalesced around sets encompassing several frameworks. Despite many contributions of these collections, contemporary migration theorizing exhibits three important shortcomings, which this paper aims to address. First, sets of theories have traditionally not explicitly and jointly addressed fundamental questions in migration, namely (i) key motivations beyond those related to “labor” (turmoil; environmental strain; family, or self‐realization factors); (ii) how important axes of social difference produce distinct motivations and mechanisms (e.g., by gender and sexuality); (iii) the (in)direct roles of the state; (iv) important spatial considerations, that is, immobility, internal versus international movement, step/onward/secondary migrations; and (v) key issues of temporality, that is, return migration, its timing, and intentionality. Engaging with classical and contemporary scholarship, I provide an updated, revised, and broadened set of frameworks and analytical lenses that better incorporate these issues. Second, the most common typology used to categorize frameworks into “initiation” and “continuation” suffers from ambiguity and imprecision. I offer a new classification, typifying mechanisms as more/less endogenous to prior migrations. Third, scholarship has advanced little in systematically examining whether/how theories relate to each other. I provide a basic taxonomy of mechanism “competition,” “coexistence,” co‐occurrence, and interrelation. I conclude by proposing a new and expanded set of frameworks and analytical lenses, reflecting on the implications of these modifications.

     
    more » « less
  4. Unlike dense linear algebra applications, graph applications typically suffer from poor performance because of 1) inefficient utilization of memory systems through random memory accesses to graph data, and 2) overhead of executing atomic operations. Hence, there is a rapid growth in improving both software and hardware platforms to address the above challenges. One such improvement in the hardware platform is a realization of the Emu system, a thread migratory and near-memory processor. In the Emu system, a thread responsible for computation on a datum is automatically migrated over to a node where the data resides without any intervention from the programmer. The idea of thread migrations is very well suited to graph applications as memory accesses of the applications are irregular. However, thread migrations can hurt the performance of graph applications if overhead from the migrations dominates benefits achieved through the migrations. In this preliminary study, we explore two high-level compiler optimizations, i.e., loop fusion and edge flipping, and one low-level compiler transformation leveraging hardware support for remote atomic updates to address overheads arising from thread migration, creation, synchronization, and atomic operations. We performed a preliminary evaluation of these compiler transformations by manually applying them on three graph applications over a set of RMAT graphs from Graph500.---Conductance, Bellman-Ford's algorithm for the single-source shortest path problem, and Triangle Counting. Our evaluation targeted a single node of the Emu hardware prototype, and has shown an overall geometric mean reduction of 22.08% in thread migrations. 
    more » « less
  5. Abstract Background Migrations in temperate systems typically have two migratory phases, spring and autumn, and many migratory ungulates track the pulse of spring vegetation growth during a synchronized spring migration. In contrast, autumn migrations are generally less synchronous and the cues driving them remain understudied. Our goal was to identify the cues that migrants use in deciding when to initiate migration and how this is updated while en route . Methods We analyzed autumn migrations of Arctic barren-ground caribou ( Rangifer tarandus ) as a series of persistent and directional movements and assessed the influence of a suite of environmental factors. We fitted a dynamic-parameter movement model at the individual-level and estimated annual population-level parameters for weather covariates on 389 individual-seasons across 9 years. Results Our results revealed strong, consistent effects of decreasing temperature and increasing snow depth on migratory movements, indicating that caribou continuously update their migratory decision based on dynamic environmental conditions. This suggests that individuals pace migration along gradients of these environmental variables. Whereas temperature and snow appeared to be the most consistent cues for migration, we also found interannual variability in the effect of wind, NDVI, and barometric pressure. The dispersed distribution of individuals in autumn resulted in diverse environmental conditions experienced by individual caribou and thus pronounced variability in migratory patterns. Conclusions By analyzing autumn migration as a continuous process across the entire migration period, we found that caribou migration was largely related to temperature and snow conditions experienced throughout the journey. This mechanism of pacing autumn migration based on indicators of the approaching winter is analogous to the more widely researched mechanism of spring migration, when many migrants pace migration with a resource wave. Such a similarity in mechanisms highlights the different environmental stimuli to which migrants have adapted their movements throughout their annual cycle. These insights have implications for how long-distance migratory patterns may change as the Arctic climate continues to warm. 
    more » « less