Formal methods are increasingly adopted in systems where reliability and correctness are critical, enabled by improvements in tool usability, speed, and automation. This industrial experience report presents three projects at Huawei Cloud showcasing different trade-offs in investment and assurance levels. We applied probabilistic concurrency testing, model checking, and deductive verification to two foundational services in the database and networking domains: the K2 transactional key-value store and the Global Server Load Balancer (GSLB).

TrueTime clocks (TTCs) that offer accurate and reliable time within limited uncertainty bounds have been increasingly implemented in many clouds. Multi-region data stores that seek decentralized synchronization for high performance represent an ideal application of TTC. However, the co-designs between the two often failed to realize their full potential. This paper proposes K2, a multi-region data store that explores the opportunity of using TTC for distributed transactions. Compared to its pioneer, Google Spanner, K2 augments TTC's semantics in three core design pillars. First, K2 carries a new timestamp-generating scheme that is capable of providing a small time uncertainty bound at scale. Second, K2 revitalizes existing multi-version timestamp-ordered concurrency control to realize multi-version properties for read-write transactions. Third, K2 introduces a new TTC-based visibility control protocol that provides efficient reads at replicas. Our evaluation shows that, K2 achieves an order of magnitude higher transaction throughput relative to other geo-distributed transaction protocols while ensuring a lower visibility delay at asynchronous replicas.

The page size of NAND flash continuously grows as the manufacturing process advances. While larger pages can reduce the cost per bit and improve the throughput of NAND flash, it may waste the storage space and data transfer time, causing more frequent garbage collections when serving small write requests. The main methods solving the mismatch problem between the request size and the write unit are write buffer cache and flash page reprogramming. However, multi-level cell (MLC) chips impose additional constraints on page programming so reprogramming MLC pages is prohibited. We proposed a multiple subpage writing flash translation layer (MSPW-FTL) for MLC by exploiting single-level cell (SLC)/MLC dual mode and flash page reprogramming feature. By converting MLC mode blocks to SLC mode blocks, we store small data in subpages of the SLC mode block. Moreover, we proposed three management methods to improve system efficiency: 1) two-level mapping to serve requests of different sizes; 2) an allocation strategy determines how the subpages of different logical pages are mapped to physical pages; and 3) a data management module to deal with the data fragmentation caused by the subpage granularity allocation. We compared MSPW-FTL with some related state-of-the-art FTLs under different types of workloads. Experimental results show that in average, MSPW-FTL reduces the I/O response time by 57.2%, the write amplification by 52.1%, and the number of erasures by 34.1%.

3D MLC NAND Flash is more appreciated for its massive capacity and significant performance. It's common to configure a portion of flash blocks to SLC-mode to further shorten the requests latency at a small cost of capacity. However, the limited SLC-mode blocks provoke GC (Garbage Collection) procedures more frequently and the GC penalty is heavier for 3D Flash than that for 2D Flash. As the block of 3D Flash consists of much more pages, the increment in the block size prolongs the erase operation latency and increases the number of migrated pages during GC. Existing works focus on reducing the number of migrated pages with sub-block GC strategies, which deeply depends on the distribution of valid pages across the sub-blocks in the victim block. In this paper, we propose a set of schemes called DCD which consists of Dual-mode Handler, Compensated GC and Dynamic Data Distribution. The key idea is to exploit the shorter operation delays of SLC-mode to accelerate the valid pages' migrations during GC, which doesn't rely on the distribution of valid pages inside the victim block. Experimental results show that compared with state-of-the-art designs, DCD shortens the average read response time by 19.8% and 37.3% for block-level and page-level FTL, respectively.

The page size of NAND flash continuously grows as the manufacturing process advances. While larger page can reduce the cost per bit and improve the throughput of NAND flash, it may waste the storage space and data transfer time. Meanwhile, it causes more frequent garbage collections when serving small write requests. To address the issues, we proposed a Mapping Granularity Adaptive FTL (MGA-FTL) based on flash page re-programming feature. MGA-FTL enables a finer granularity NAND flash space management and exploits multiple subpage writes on a single flash page without erase. 2-Level Mapping is introduced to serve requests of different sizes in order to control the overhead of DRAM requirement. Meanwhile, the allocation strategy determines whether different logical pages can be mapped to a single physical page to balance the space utilization and performance. Subpage merging limits the number of associated physical pages to a logical page, which could reduce data fragmentation and improves the performance of read operations. We compared MGA-FTL with some typical FTLs, including page-level mapping FTL and sector-log mapping FTL. Experimental results show that MGA-FTL reduces the I/O response time, write amplification and the number of erasures by 53%, 30% and 40% respectively. Despite the overhead of finegrained management, MGA-FTL increases no more than 16.5% DRAM requirement compared with a page-level mapping FTL. Unlike the subpage-level mapping, MGA-FTL only needs one third of DRAM space for storing mapping tables.

3D architectures are considered the most promising approach to continuously increasing memory density and reducing cost/bit for NAND flash memory by stacking more layers. However, 3D MLC flash memory brings two serious problems, referred to as cell-to-cell program disturbance and big block problem. To solve the disturbance problem for better reliability, we proposed a Disturbance Compensation Programming Scheme (DCPS). Based on quantitatively analyzing the disturbance from each direction in 3D flash memory, the scheme accordingly set the verify voltage (VVFY) a little lower than the original value when Incremental Step Pulse Programming (ISPP) is performed. After disturbance compensation, the threshold voltage of flash cells can shift towards the ideal distribution. Moreover, Read reference Voltage Shifting (RVS) and Artificial Compensation (AC) strategies on margin pages are introduced to adapt to the three-dimensional structures to further enhance reliability. To solve big block problem, Multiple-Level-Queue page allocation (MLQ) is proposed. We use multiple queues to filter the logical addresses of different update counts and choose different data blocks to respond. The stored data are gradually well organized and generate less data migration when performing garbage collection. Experimental results show that our design reduces the disturbed BER by at least 82% with respect to a FTL with traditional allocation and garbage collection scheme. Besides, we demonstrate MLQ can achieve more effective results than the state of the art scheme in the big block environment. The write amplification, I/O response time and the number of erasures are reduced by 31.2%, 22.2% and 14.6% on average, respectively.