KSKV:Key-Strategy for Key-Value Data Collection with Local Differential Privacy

In recent years,the research field of data collection under local differential privacy(LDP)has expanded its focus fromelementary data types to includemore complex structural data,such as set-value and graph data.However,our comprehensive review of existing literature reveals that there needs to be more studies that engage with key-value data collection.Such studies would simultaneously collect the frequencies of keys and the mean of values associated with each key.Additionally,the allocation of the privacy budget between the frequencies of keys and the means of values for each key does not yield an optimal utility tradeoff.Recognizing the importance of obtaining accurate key frequencies and mean estimations for key-value data collection,this paper presents a novel framework:the Key-Strategy Framework forKey-ValueDataCollection under LDP.Initially,theKey-StrategyUnary Encoding(KS-UE)strategy is proposed within non-interactive frameworks for the purpose of privacy budget allocation to achieve precise key frequencies;subsequently,the Key-Strategy Generalized Randomized Response(KS-GRR)strategy is introduced for interactive frameworks to enhance the efficiency of collecting frequent keys through group-anditeration methods.Both strategies are adapted for scenarios in which users possess either a single or multiple key-value pairs.Theoretically,we demonstrate that the variance of KS-UE is lower than that of existing methods.These claims are substantiated through extensive experimental evaluation on real-world datasets,confirming the effectiveness and efficiency of the KS-UE and KS-GRR strategies.

Key-Value数据库的研究与应用

首先介绍Key-Value数据库的概念,接着比较了Key-Value数据库与关系数据库的区别和优劣点,并分析了各自适用的范围,最后简单介绍了目前Key-Value数据库的企业级应用情况和几款开源的Key-Value数据库,并总结了使用Key-Value数据库之前要考虑的几点技术问题。

基于操作历史图的分布式Key-Value数据库一致性检测算法

分布式数据库系统的副本机制在提高系统可靠性及性能的同时,导致了多副本数据管理的一致性问题;数据一致性的实现需要一致性协议模型来进行预防,也需要一致性检测算法对非一致数据进行检测。首先,对读写操作记录之间的时序关系、安全一致性及并行一致性原则等概念进行定义;其次,根据操作记录集合中读写操作之间的并行与时序关系,提取出操作记录集合向操作记录图转化的规则,并在此基础上设计了操作记录向历史记录图的转化算法;然后,以历史记录图为输入,设计了违反一致性查找算法,查找并返回图中所有违反安全与并行一致性读操作的集合;最后,基于Cassandra进行实验并将读写一致性设置为ONE,通过YCSB产生并行读写压力测试,与同类算法的对比实验验证了所提算法在功能与效率两方面的优越性。

一种基于裸闪存的Key-Value数据库优化方法

近年来,非关系型的key-value数据库得到越来越广泛的应用.然而,目前主流的key-value数据库或者是基于磁盘设计的,或者是传统的基于文件系统和闪存转换层FTL来构建的,难以发挥闪存存储设备的特性,限制了I/O的并发性能,且垃圾回收过程复杂.设计并实现了一种基于裸闪存的keyvalue数据管理架构Flashkv,通过用户态下的管理单元进行空间管理和垃圾回收,充分利用了闪存设备内部的并发特性,并简化了垃圾回收过程,去除了传统文件系统和FTL中的冗余功能,缩短了I/O路径.提出了基于闪存特点的I/O调度技术,优化了闪存的读写延迟,提高了吞吐率;提出了用户态缓存管理技术,降低了数据写入量和频繁系统调用所带来的开销.测试结果表明,Flashkv性能是levelDB的1.9~2.2倍,写入量减少60%~65%.

基于SSD的Key-Value系统优化设计与实现

随着互联网技术的迅猛发展,越来越多的非结构化数据涌入到人们的生活中,为这些数据建立高效的索引面临极大的挑战.键值数据库Key-Value以其结构简单和高扩展性而引起人们的广泛关注,已成为海量数据存储系统中的重要组成部分.由于Key-Value系统对吞吐量要求较高,而基于Flash的固态硬盘(solid state drive,SSD)能够提供很高的随机读性能,在SSD上构建Key-Value系统已成为海量数据存储领域的一大研究热点.鉴于Flash具有非定点更新、寿命有限等特性,基于SSD的KeyValue系统必须针对Flash的特性作专门优化.以一种称为SkimpyStash的基于SSD的Key-Value系统为基础,提出了一种新的Key-Value系统低延迟存储系统(low latency store,LLStore).LLStore使用内存文件映射技术来减少针对SSD的IO请求,除此之外,针对SkimpyStash中低效的压缩策略,提出一种改进方法,可以在少量增加内存开销的情况下极大地减少查询时间.通过与原系统的性能比较实验,LLStore在平均查询时间上可以获得至少12%的加速.

云计算系统中Key-Value数据管理研究

Key-Value数据库是应用于云环境下的典型云存储系统,基于key-value数据模型的研究对大数据管理或称云数据管理系统提出了新的需求与挑战,成为人们关注的热点。本文对key-value数据模型与数据读写方式作了简单介绍,引入了key-value索引机制,重点讨论了key-value查询操作,给出了关于多维点查询的通用算法。

基于Linux内核的Key-Value存储系统——KStore

Key-Value存储系统在各种互联网服务中被广泛使用,但现有的Key-Value存储系统通常在用户态空间设计和实现,因为频繁的模式切换和上下文切换,导致访问接口、事务处理效率不高,在高并发、低延迟的数据存储需求中尤为突出。针对该问题,给出了一个内核态Key-Value存储系统的实现——KStore:提供内核空间的索引和内存分配机制,并在此基础上,通过基于内核Socket的远程接口以及基于文件系统的本地接口,保证了KStore的低延迟;同时,通过基于内核多线程的并发处理机制,保证了KStore的并发性。实验结果表明,与Memcached相比,KStore在实时性和并发性方面都取得显著优势。

一种基于key-value数据库的快速地名地址输入提示方法

现有地址输入提示方法涉及标准地址和POI的研究较少,地址字符串的索引大多采用Trie(字典)树索引,但Trie树建立时内存消耗巨大,在面临海量数据时,问题更加突出。针对以上问题,提出一种基于key-value数据库的快速地名地址输入提示方法。该方法基于Trie树结构进行改进,降低了地址索引的复杂度;基于keyvalue数据库构建Trie树,避免了内存消耗巨大的问题。实验结果表明,基于key-value数据库构建的Trie树索引较基于内存构建的Trie树索引在事务响应性能和内存消耗方面具有明显的优势和效率。

基于Key-Value的云数据管理应用接口标准化研究

分析了基于Key-Value的云数据管理应用接口的标准化问题和面临的挑战,对现有基于Key-Value的云数据管理服务进行了调研,总结出包括数据模型和REST API等方面的异同,并提出未来的标准化工作建议。

分布式key-value系统错误污染检测

随着key-value存储系统的广泛使用,越来越多的研究开始关注分布式系统中的可信问题,其中一个重要的问题是,如何在系统被入侵或者管理员配置错误并运行一段时间后,检测出受污染的数据,从而可以在恢复错误数据的同时保留系统的合法更新.文中提出了一种基于key-value存储系统的错误污染检测方法,该方法允许在客户端不可信的前提下,检测客户端之间的污染扩散.文中设计了一种基于各服务器逻辑时钟的向量时钟,该时钟以用户关联操作为更新规则,记录了跨服务器的读写请求逻辑关系,用以进行错误污染跟踪;同时为了减少大规模系统中污染检测的开销,基于该向量时钟,文中进一步提出了一种在分布式系统中由操作序列构成有向无环图的污染分析方法.基于广泛使用的Voldmort key-value系统,文中实现了一个错误污染检测系统,Tracker Store.在集群测试环境下,文中对引入新的检测系统后产生的额外延迟开销进行了测试.

Key-Value Store Coupled with an Operating System for Storing Large-Scale Values

The key-value store can provide flexibility of data types because it does not need to specify the data types to be stored in advance and can store any types of data as the value of the key-value pair.Various types of studies have been conducted to improve the performance of the key-value store while maintaining its flexibility.However,the research efforts storing the large-scale values such as multimedia data files(e.g.,images or videos)in the key-value store were limited.In this study,we propose a new key-value store,WR-Store++aiming to store the large-scale values stably.Specifically,it provides a new design of separating data and index by working with the built-in data structure of the Windows operating system and the file system.The utilization of the built-in data structure of the Windows operating system achieves the efficiency of the key-value store and that of the file system extends the limited space of the storage significantly.We also present chunk-based memory management and parallel processing of WR-Store++to further improve its performance in the GET operation.Through the experiments,we show that WR-Store++can store at least 32.74 times larger datasets than the existing baseline key-value store,WR-Store,which has the limitation in storing large-scale data sets.Furthermore,in terms of processing efficiency,we show that WR-Store++outperforms not only WR-Store but also the other state-ofthe-art key-value stores,LevelDB,RocksDB,and BerkeleyDB,for individual key-value operations and mixed workloads.

Utility-Improved Key-Value Data Collection with Local Differential Privacy for Mobile Devices

The structure of key-value data is a typical data structure generated by mobile devices.The collection and analysis of the data from mobile devices are critical for service providers to improve service quality.Nevertheless,collecting raw data,which may contain various per⁃sonal information,would lead to serious personal privacy leaks.Local differential privacy(LDP)has been proposed to protect privacy on the device side so that the server cannot obtain the raw data.However,existing mechanisms assume that all keys are equally sensitive,which can⁃not produce high-precision statistical results.A utility-improved data collection framework with LDP for key-value formed mobile data is pro⁃posed to solve this issue.More specifically,we divide the key-value data into sensitive and non-sensitive parts and only provide an LDPequivalent privacy guarantee for sensitive keys and all values.We instantiate our framework by using a utility-improved key value-unary en⁃coding(UKV-UE)mechanism based on unary encoding,with which our framework can work effectively for a large key domain.We then vali⁃date our mechanism which provides better utility and is suitable for mobile devices by evaluating it in two real datasets.Finally,some pos⁃sible future research directions are envisioned.

A Surfing Concurrence Transaction Model for Key-Value NoSQL Databases

As more and more application systems related to big data were developed, NoSQL (Not Only SQL) database systems are becoming more and more popular. In order to add transaction features for some NoSQL database systems, many scholars have tried different techniques. Unfortunately, there is a lack of research on Redis’s transaction in the existing literatures. This paper proposes a transaction model for key-value NoSQL databases including Redis to make possible allowing users to access data in the ACID (Atomicity, Consistency, Isolation and Durability) way, and this model is vividly called the surfing concurrence transaction model. The architecture, important features and implementation principle are described in detail. The key algorithms also were given in the form of pseudo program code, and the performance also was evaluated. With the proposed model, the transactions of Key-Value NoSQL databases can be performed in a lock free and MVCC (Multi-Version Concurrency Control) free manner. This is the result of further research on the related topic, which fills the gap ignored by relevant scholars in this field to make a little contribution to the further development of NoSQL technology.

PRS:Predication-Based Replica Selection Algorithm for Key-Value Stores

The tail latency of end-user requests,which directly impacts the user experience and the revenue,is highly related to its corresponding numerous accesses in key-value stores.The replica selection algorithm is crucial to cut the tail latency of these key-value accesses.Recently,the C3 algorithm,which creatively piggybacks the queue-size of waiting keys from replica servers for the replica selection at clients,is proposed in NSDI 2015.Although C3 improves the tail latency a lot,it suffers from the timeliness issue on the feedback information,which directly influences the replica selection.In this paper,we analysis the evaluation of queuesize of waiting keys of C3,and some findings of queue-size variation were made.It motivate us to propose the Prediction-Based Replica Selection(PRS)algorithm,which predicts the queue-size at replica servers under the poor timeliness condition,instead of utilizing the exponentially weighted moving average of the state piggybacked queue-size as in C3.Consequently,PRS can obtain more accurate queue-size at clients than C3,and thus outperforms C3 in terms of cutting the tail latency.Simulation results confirm the advantage of PRS over C3.

Key-Value系统LSM模型实现技术的研究

随着时代的进步,社交网络的普及,Web2.0时代的到来,互联网的数据量呈现出爆炸式的增长。传统的数据库模型在高并发性、可扩展性等方面表现不佳,对于一些大数据的应用,传统的数据库模型无法胜任。为了解决这方面的需求,近些年来NoSQL技术快速的发展。其中Key-Value存储系统是最常见和简单的NoSQL系统,本文就将对Key-Value类型的系统实现技术进行研究和讨论。

MyWAL:performance optimization by removing redundant input/output stack in key-value store

Based on a log-structured merge(LSM)tree,the key-value(KV)storage system can provide high reading performance and optimize random writing performance.It is widely used in modern data storage systems like e-commerce,online analytics,and real-time communication.An LSM tree stores new KV data in the memory and flushes to disk in batches.To prevent data loss in memory if there is an unexpected crash,RocksDB appends updating data in the write-ahead log(WAL)before updating the memory.However,synchronous WAL significantly reduces writing performance.In this paper,we present a new WAL mechanism named MyWAL.It directly manages raw devices(or partitions)instead of saving data on a traditional file system.These can avoid useless metadata updating and write data sequentially on disks.Experimental results show that MyWAL can significantly improve the data writing performance of RocksDB compared to the traditional WAL for small KV data on solid-state disks(SSDs),as much as five to eight times faster.On non-volatile memory express soild-state drives(NVMe SSDs)and non-volatile memory(NVM),MyWAL can improve data writing performance by 10%–30%.Furthermore,the results of YCSB(Yahoo!Cloud Serving Benchmark)show that the latency decreased by 50%compared with SpanDB.

Design and Implementation of Key-Value Database for Ship Virtual Test Platform Based on Distributed System

The virtual test platform is a vital tool for ship simulation and testing.However,the numerical pool ship virtual test platform is a complex system that comprises multiple heterogeneous data types,such as relational data,files,text,images,and animations.The analysis,evaluation,and decision-making processes heavily depend on data,which continue to increase in size and complexity.As a result,there is an increasing need for a distributed database system to manage these data.In this paper,we propose a Key-Value database based on a distributed system that can operate on any type of data,regardless of its size or type.This database architecture supports class column storage and load balancing and optimizes the efficiency of I/O bandwidth and CPU resource utilization.Moreover,it is specif-ically designed to handle the storage and access of largefiles.Additionally,we propose a multimodal data fusion mechanism that can connect various descrip-tions of the same substance,enabling the fusion and retrieval of heterogeneous multimodal data to facilitate data analysis.Our approach focuses on indexing and storage,and we compare our solution with Redis,MongoDB,and MySQL through experiments.We demonstrate the performance,scalability,and reliability of our proposed database system while also analysing its architecture’s defects and providing optimization solutions and future research directions.In conclu-sion,our database system provides an efficient and reliable solution for the data management of the virtual test platform of numerical pool ships.

Key-Value键值对数据在新生儿听力筛查登记系统中的应用

本文围绕新生儿听力筛查登记系统的技术实现,着重从新生儿不同报告单资料数据的保存及展示方面来阐述技术核心实现过程,针对不同的基层医院需要存储的新生儿数据格式不一致问题,在关系数据库中采用Key-Value形式来进行存储,而数据的查询展示则利用数据库编程技术或JAVA函数式编程技术实现。

MemSC： A Scan-Resistant and Compact Cache Replacement Framework for Memory-Based Key-Value Cache Systems

Memory-based key-value cache systems, such as Memcached and Redis, have become indispensable components of data center infrastructures and have been used to cache performance-critical data to avoid expensive back-end database accesses. As the memory is usually not large enough to hold all the items, cache replacement must be performed to evict some cached items to make room for the newly coming items when there is no free space. Many real-world workloads target small items and have frequent bursts of scans （a scan is a sequence of one-time access requests）. The commonly used LRU policy does not work well under such workloads since LRU needs a large amount of metadata and tends to discard hot items with scans. Small decreases in hit ratio can result in large end-to-end losses in these systems. This paper presents MemSC, which is a scan-resistant and compact cache replacement framework for Memcached. MemSC assigns a multi-granularity reference flag for each item, which requires only a few bits （two bits are enough for general use） per item to support scanresistant cache replacement policies. To evaluate MemSC, we implement three representative cache replacement policies （MemSC-HM, MemSC-LH, and MemSC-LF） on MemSC and test them using various workloads. The experimental results show that MemSC outperforms prior techniques. Compared with the optimized LRU policy in Memcached, MemSC-LH reduces the cache miss ratio and the memory usage of the resulting system by up to 23% and 14% respectively.

R-Memcached: A Reliable In-Memory Cache for Big Key-Value Stores

Large-scale key-value stores are widely used in many Web-based systems to store huge amount of data as(key, value) pairs. In order to reduce the latency of accessing such(key, value) pairs, an in-memory cache system is usually deployed between the front-end Web system and the back-end database system. In practice, a cache system may consist of a number of server nodes, and fault tolerance is a critical feature to maintain the latency Service-Level Agreements(SLAs). In this paper, we present the design, implementation, analysis, and evaluation of R-Memcached, a reliable in-memory key-value cache system that is built on top of the popular Memcached software. R-Memcached exploits coding techniques to achieve reliability, and can tolerate up to two node failures.Our experimental results show that R-Memcached can maintain very good latency and throughput performance even during the period of node failures.