Parqua: Online Reconfigurations in Virtual Ring-Based NoSQL Systems
Short Paper and Poster in Proc. IEEE International Conference on Cloud and Autonomic Computing (ICCAC), 2015
[abstract | pdf | ppt]
The performance of key-value/NoSQL storage systems is highly tied to the choice of (primary) key for the database table. As application requirements change over time, system administrators need to change the primary key of the table to improve performance. The primary key change is a specific example of a broader class of reconfiguration operations that affect a lot of data all at once. In this paper we propose a system called Parqua, which imbues ring-based keyvalue/NoSQL stores with the ability to perform reconfiguration operations in an online and efficient manner. We present the design and implementation of Parqua. Experiments based on our cluster deployments show that during reconfiguration Parqua maintains high availability, and with a small impact on read and write latencies.
Leveraging Metadata in NoSQL Storage Systems
Proc. IEEE International Conference on Cloud Computing (CLOUD), 2015
[abstract | pdf | ppt]
NoSQL systems have grown in popularity for storing big data because these systems offer high availability, i.e., operations with high throughput and low latency. However, metadata in these systems are handled today in ad-hoc ways. We present Wasef, a system that treats metadata in a NoSQL database system, as first-class citizens. Metadata may include information such as: operational history for a database table (e.g., columns), placement information for ranges of keys, and operational logs for data items (key-value pairs). Wasef allows the NoSQL system to store and query this metadata efficiently. We integrate Wasef into Apache Cassandra, one of the most popular key-value stores. We then implement three important uses cases in Cassandra: dropping columns in a flexible manner, verifying data durability during migrational operations such as node decommissioning, and maintaining data provenance. Our experimental evaluation uses AWS EC2 instances and YCSB workloads. Our results show that Wasef: i) scales well with the size of the data and the metadata; ii) minimally affects throughput and operation latencies.
Fast Compaction Algorithms for NoSQL Databases
Proc. IEEE International Conference on Distributed Computing Systems (ICDCS) 2015
[abstract | pdf | ppt]
Compaction plays a crucial role in NoSQL systems to ensure a high overall read throughput. In this work, we formally define compaction as an optimization problem that attempts to minimize disk I/O.We prove this problem to be NPHard. We then propose a set of algorithms and mathematically analyze upper bounds on worst-case cost. We evaluate the proposed algorithms on real-life workloads. Our results show that our algorithms incur low I/O costs compared to optimal and that a compaction approach using a balanced tree is most preferable.
Morphus: Supporting Online Reconfigurations in Sharded NoSQL Systems
Proc. IEEE International Conference on Autonomic Computing (ICAC) 2015
Transactions on Emerging Topics in Computing (TETC), Volume 4, Issue 0, 2016
[abstract | pdf | ppt]
While sharded NoSQL stores offer high availability, reconfiguration operations present a major pain point in deployments today. For instance, in order to change a configuration setting such as the shard (or primary) key of a database table, the prevalent solutions entail shutting down the database, exporting and re-importing the table, and restarting the database. This goes against the philosophy of high availability of data.
Our system Morphus provides support for reconfigurations for NoSQL stores in an online manner, allowing read and write operations to continue concurrently with the data transfer among servers. This paper presents: i) optimal algorithms for online reconfigurations, and ii) a systems architecture for reconfiguration operations incorporated into MongoDB. Our evaluation using realistic workloads shows that our system completes reconfiguration efficiently and incurs minimal overhead for reads and writes during the reconfiguration.
Detecting misbehaviors in VANET with integrated root-cause analysis
Journal of Ad Hoc Networks, Volume 8, Issue 7, 2010
Misbehavior detection schemes (MDSs) form an integral part of misbehaving node eviction in vehicular ad hoc networks (VANETs). A misbehaving node can send messages corresponding to an event that either has not occurred (possibly out of malicious intent), or incorrect information corresponding to an actual event (for example, faulty sensor reading), or both, causing applications to malfunction.
While identifying the presence of misbehavior, it is also imperative to extract the root-cause of the observed misbehavior in order to properly assess the misbehavior.s impact, which in turn determines the action to be taken. This paper uses the Post Crash Notification (PCN) application to illustrate the basic considerations and the key factors affecting the reliability performance of such schemes. The basic cause-tree approach is illustrated and used effectively to jointly achieve misbehavior detection as well as identification of its root-cause.
The considerations regarding parameter tuning and impact of mobility on the performance of the MDS are studied. The performance of the proposed MDS is found to be not very sensitive to slight errors in parameter estimation.
Misbehavior detection scheme with integrated root cause detection in VANET
Proc. ACM International Workshop on VehiculAr InterNETworking, 2009
Securing communication using broadcast authentication schemes (BAS) in V2V does not always guarantee exchange of correct and/or accurate information. Misbehavior Detection Schemes (MDS) are aimed at detecting the exchange of such information. In this paper, we propose a MDS for Post Crash Notification (PCN) application based on root-cause analysis that is capable of detecting different types of misbehaviors possible, for example, a false crash alert raised in the absence of a crash and a crash alert raised with incorrect positional information.
Distributed misbehavior detection in VANETs
Proc. IEEE Wireless Communications and Networking Conference, 2009
In any vehicular adhoc network, there is always a possibility of incorrect messages being transmitted either due to faulty sensors and/or intentional malicious activities. Detecting and evicting sources of such misbehavior is an important problem. We observe that the performance of misbehavior detection schemes will depend on the application under consideration and the mobility dynamics of the detecting vehicle. Further, the underlying tradeoff in any such detection algorithm is the balance between False Positives and False Negatives; one would like to detect as many misbehaviors as possible, while at the same time ensuring that the genuine vehicles are not wrongly accused. In this work we propose and analyze (via simulations) the performance of a Misbehavior Detection Scheme (MDS) for Post Crash Notification (PCN) application. We observe that the performance of this proposed scheme is not very sensitive to the exact dynamics of the vehicle on small scales, so that slight error in estimating the dynamics of the detecting vehicle does not degrade the performance of the MDS.