The disclosed embodiments disclose techniques for accessing a scale-out block interface in a cloud-based distributed computing environment (CBDCE). During operation, an instance of a block device service (BDS) receives a data request from a client. The BDS instance translates the data request into a set of data block accesses, and then sends the translated data request to a data processing layer service (DPL). The DPL instance services the data request using a set of data operations that leverage one or more of a distributed cache, a distributed database, and a cloud storage system. The BDS service leverages the DPL instance to provide to the client an abstraction of a highly-available block storage device with unlimited storage space via the scale-out block interface.