  Selling reserved instances (or virtual machines) is a basic service in cloud
computing. In this paper, we consider a more flexible pricing model for
instance reservation, in which a customer can propose the time length and
number of resources of her request, while in today's industry, customers can
only choose from several predefined reservation packages. Under this model, we
design randomized mechanisms for customers coming online to optimize social
welfare and providers' revenue.
  We first consider a simple case, where the requests from the customers do not
vary too much in terms of both length and value density. We design a randomized
mechanism that achieves a competitive ratio $\frac{1}{42}$ for both
\emph{social welfare} and \emph{revenue}, which is a improvement as there is
usually no revenue guarantee in previous works such as
\cite{azar2015ec,wang2015selling}. This ratio can be improved up to
$\frac{1}{11}$ when we impose a realistic constraint on the maximum number of
resources used by each request. On the hardness side, we show an upper bound
$\frac{1}{3}$ on competitive ratio for any randomized mechanism. We then extend
our mechanism to the general case and achieve a competitive ratio
$\frac{1}{42\log k\log T}$ for both social welfare and revenue, where $T$ is
the ratio of the maximum request length to the minimum request length and $k$
is the ratio of the maximum request value density to the minimum request value
density. This result outperforms the previous upper bound $\frac{1}{CkT}$ for
deterministic mechanisms \cite{wang2015selling}. We also prove an upper bound
$\frac{2}{\log 8kT}$ for any randomized mechanism. All the mechanisms we
provide are in a greedy style. They are truthful and easy to be integrated into
practical cloud systems.
