Advanced stream processing systems require a high degree of elasticity, namely the ability to rapidly scale to adapt to higher load, often swiftly increasing stream-processing rate by 2x-3x. A challenge for such systems is that the NoSQL data stores that they often depend on, cannot currently adapt as fast in order to sustain the increased level of streaming throughput. Data-store elasticity involves re-distribution of data across nodes and as such it may take a long time and pose a high impact on performance. A related challenge is the need to accurately predict the number of new nodes needed by the data store to accommodate the increased needs of the streaming system. Since the data store serving the needs of the streaming system is on the critical path of stream processing, high throughput, low latency, and rapid failover are also key data store aspects to maintaining high streaming throughput. STREAMSTORE aims to fully support highly elastic scalable stream-processing systems in periods of high variability during which rapid, low-impact elasticity across all system layers becomes a first-class property for maintaining system response. This requires the evolution of the elasticity, predictability, and availability of scalable data store technology beyond the state of the art. STREAMSTORE will deliver a highly elastic (rapidly scalable) NoSQL data store that is optimized for emerging highly-parallel micro-server architectures and fully coordinated with state-of-the-art elastic scalable stream-processing systems. Implementing this targeted scientific breakthrough requires extending state-of-the-art software techniques (such as incremental elasticity, measurement-based performance prediction using non-linear regression, and lightweight checkpointing) and aligning them with novel hardware capabilities of emerging micro-server clusters, to enable highly elastic data stores.